Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorial-game-theory]

Combinatorial game theory (abbreviated CGT) is the subfield of combinatorics (not traditional game theory) which deals with games of perfect information such as Nim and Go. It includes topics such as the Sprague-Grundy theorem and is tangentially related to the Surreal Numbers.

0
votes
1answer
50 views

Show that the first child can not win

Three children have 10 pieces numbered from 0 to 9 on both sides. They play the following game: -The first child chooses a piece, so a number, preserves it and passes the number on a sheet -The ...
2
votes
1answer
63 views

Proof that “$\uparrow$ is the unique solution of $tiny(G) = G$”

Tiny & miny games can be defined as: $$tiny(G) = \{0||0|-G\}$$ $$miny(G) = -tiny(G) = \{G|0||0\}$$ From the Wikipedia page for tiny and miny: Similarly curious, mathematician John Horton ...
1
vote
1answer
37 views

Proof one aspect of Nim game

Prove that if the Nim sum is not zero, then one of the piles is bigger than the Nim sum of the all the other piles. I've already proven that if the Nim sum of the piles is zero, then any one move ...
2
votes
3answers
111 views

A number game for two

Alice and Bob play the following number game. A target N is fixed, N being a positive integer. Alice then writes the number 1 on the blackboard. Bob responds with the number 2. Thereafter, at each of ...
3
votes
1answer
50 views

Distinction between “fuzzy” and “confused with.”

In the terminology of game theory, "fuzzy" and "confused with" signify different things. How are their associated concepts alike and distinct? EDIT: My initial encounter with the terms was here: ...
1
vote
0answers
46 views

Is there a solution to the stone game using the greedy method?

It’s a two player game. Both the players play optimally. Given n number of stones, a player can choose either 1 stone or p stones or q stones where 1 < p < q. Suppose player 'A' starts the game ...
2
votes
0answers
49 views

Queens on a torus chessboard.

Consider a Torus chessboard $\mathbb T$ of dimension $8\times8 $. How much queens it is possible to put on in such a way that no one attacks another? (I assume we use the same rules of standard ...
0
votes
0answers
22 views

Proof of Tartan's Theorem?

I have read only one proof online that shows that the Sprague-Grundy value of a position in an impartial game, denoted by say $g(x,y)$, is equal to $g_1(x) \otimes g_2(y)$, where $\otimes$ denotes Nim-...
1
vote
1answer
126 views

How to prove that for $n$ even and positive, the first player can guarantee a win?

Two players take turns placing dominoes on an $n \times 1$ board of squares, where each domino covers two squares and dominoes cannot overlap. The last player to play wins. (a) Where would ...
0
votes
1answer
27 views

What is the payoff function for games with more than two players?

For two player games, with payoff matrices $(A,B)$, let $x \in \Delta_x$ denote the mixed strategy of player $1$, and $y \in \Delta_y$ denote the mixed strategy of player $2$. Then the payoff ...
2
votes
1answer
44 views

Can the following Nim-like game be broken down into two parallel Nim sub-games (disjuctive sum)?

Say that there are two players, and two piles of chips. The first pile of chips has $m$ chips in it, where $m \geq 0$, but the second pile has exactly $1$ chip in it. The players alternate in taking ...
0
votes
0answers
49 views

How can I find the Sprague-Grundy function of this game?

The game involves N coins and a player can flip any consecutive $K$ sequence of coins, where $K$ is a perfect square. I have developed a function to list the values, but I am looking for a ...
0
votes
1answer
34 views

Impartial games: why is a game the disjunctive sum of its components?

Why is that for a game like Turning Turtles, the Sprague-Grundy value of a whole configuration $g$ is the disjunctive sum of its components with only one head? For example, $g(TTHTH) = g(TTH) + g(...
-2
votes
2answers
44 views

Unbiased coin game [closed]

Suppose Alice and Bob want to play a game sharing an unbiased coin. In her turn, Alice flips the coin only once. If she gets heads she sums one point, none otherwise. Then she hands the coin to Bob. ...
7
votes
2answers
52 views

Two-player game in $19$ rounds

Aashna and Radhika see the integers $1$ to $211$ written on a blackboard. They alternate turns and in every step each of them wipes out any $11$ numbers until only $2$ numbers are left on the ...
2
votes
2answers
81 views

A polytree game.

Starting from a directed star graph with $n$ nodes and all edges pointing away from the center, let two players alternate making one of the following moves: Tail move: $b \leftarrow a \rightarrow c \...
9
votes
1answer
73 views

Is multiplication of games that are equivalent to numbers well-defined?

It's well-known that if you take the definition of surreal multiplication and attempts to generalize it to all games, the result is not well-defined, in that it does not respect equivalence of games. ...
6
votes
0answers
53 views

Nim-Like Game: Subtracting powers of 2 from 1000. [duplicate]

A professor of one of my courses introduced us to a game to play during down-time, we start with 1000, then we take turns subtracting the powers of 2 (1 to 512), from 1000, we can use the same power ...
0
votes
0answers
65 views

What is the maximal value that we can have after 99 operations?

we begin with the numbers $1,\frac{1}2 ,\frac{1}3,\ldots \frac{1}{100}$ written in a board. We do the following operation : we delete $2$ numbers $a$ and $b$ from the board , and we remplace them with ...
0
votes
1answer
36 views

Optimal strategy for the biggest interval conquest?( Game similar to Nim )

There is an interval and say 3 players. Each player wants to capture the biggest subinterval, and each successive player can influence the subinterval gained by previous players. We want to find the ...
1
vote
0answers
51 views

A rabbit on an integer [duplicate]

Let $a$ and $b$ be two positve integers. An invisible rabbit is standing on the number line at the number $a$. Every step we tell an integer to a magician and he tells us if the rabbit is there. After ...
2
votes
1answer
41 views

Draws in Quarto

I was recently introduced to Quarto, a game invented by Swiss mathematician Blaise Muller (which even has its own Wikipedia page). The conjecture of interest is that there are no draws possible in ...
13
votes
0answers
309 views

Strategy for board game 2

In this question the following was asked: Alice and Bob are playing the following game: They have a $4 \times 4$ empty grid and take turns coloring one square each, starting with Alice, both using ...
3
votes
0answers
52 views

Solving the Matrix Game

Let $\{v_j\}_j$ be a collection of $n$ column vectors $v_j \in \mathbb{F}_2^{r}$ s.t. the matrix built from those has no zero rows. Now we play a game: You have 3 options: You may drop any column ...
4
votes
0answers
92 views

Improper integrals over the reals and surreal numbers

Is it possible to assign improper integrals over the reals a surreal value in a consistent way? Are there any papers available on this? Note that I am not inquiring about formalizing integration over ...
2
votes
1answer
24 views

Expected time until the range halves

Let look at the next model: We start with with $n$ points in the interval $[-1,1]$, with each point being set uniformly and independently in the range. At discrete times two points are picked ...
17
votes
2answers
577 views

Make triangle of rods (game strategy)

There are set of rods of length $1,2,3,4 \dots N$. Two players take turns to chose 3 rods and compose triangle with non-zero area. After that this particular 3 rods are removed. If it is not possible ...
5
votes
1answer
78 views

Existence of finite strategy in a “synergy”-hopping game

I have in mind the next Game: Given $n$ points on $\mathbb{R}$, two random points are picked and moved to the location of their average. E.g., pick points at location $x_1, x_2$ and they both ...
1
vote
0answers
194 views

Cyclic Partisan Nim Variant

This game is played with a sequence of heaps and a position marker, where each heap is owned by exactly one player. The game ends when a player has removed all objects from their own heaps, and this ...
13
votes
3answers
2k views

An invisible ghost jumping on a regular hexagon

Given a regular hexagon and an invisible ghost at one of the vertices of the hexagon (we don’t know which). We have a special gun, that can kill ghosts. In a step we are able to shoot the gun twice (i....
2
votes
1answer
60 views

Find a great strategy to a pentomino type game

I have a game. Given an $8\times 8$ square and a set, which contains the pentominoes and four $1\times 1$ squares. Players alternately pick one item from the set. Then players (starting with the ...
2
votes
1answer
113 views

A question about IMO 1986 P3

IMO 1986 P3: To each vertex of a pentagon, we assign an integer $x_i$ with sum $s=\sum x_i>0$. If $x,y,z$ are numbers assigned to three successive vertices and if $y<0$, then we replace $(x,y,z)$...
25
votes
3answers
711 views

Hat 'trick': Can one of them guess right?

There are $n$ boys and $n$ girls. Each of them is given a hat of only 4 possible (known) colors and doesn't know its color. Now each can only see all the colors of hats of those of the other gender ...
6
votes
2answers
168 views

Alice and Bob picking game

Alice and Bob play the following game. There is one pile of $N$ stones. Alice and Bob take turns to pick stones from the pile. Alice always begins by picking at least one, but less than $N$ stones. ...
1
vote
1answer
42 views

How to design a nim game?

I am required to give an example of nim game such that: the initial position is an N-position, there are exactly three optimal moves from the initial position, every pile has at least 20 chips, every ...
4
votes
0answers
79 views

Betting on intervals

Assume we have $n$ white points on a line, and that at a certain time a random subset of those points turns black. We have two teams A and B consisting of a finite number of players each of which is ...
0
votes
2answers
84 views

Winning strategies in n-circular TicTacToe

The game of N-Circular TicTacToe is defined as follows: Informally, there is a circular board with $N$ empty slots where Alice and Bob place $X$'s and $O$'s. Whoever gets to place three consecutive ...
3
votes
2answers
134 views

Combinatorics: Tic-Tac-Toe

I have found information on how many various unique games of tic-tac-toe (naughts and crosses) can be played. However, I am working to build an AI on the TI-84+ which uses a learning system which was ...
2
votes
1answer
53 views

confusion in the combinatorial analysis in the game of baccarat

Update (14th Jun 18) My argument here is that if we assume all hands are 6-card hands, we have created a lot of extra invalid combinations to the "total". For example in this game, an extra of ...
0
votes
1answer
73 views

What are the two possible solutions to this round of Mastermind?

I have just started self-studying with Alan Tucker's Applied Combinatorics. The intro to the book is a series of problems based on the game Mastermind, which I have had a good amount of success with. ...
3
votes
1answer
72 views

Proof that $x+(-x)=0$ for surreal numbers

This is from Conway's on numbers and games: $x+(-x)=0$. We have to show $x+(-x)\geq 0$ and $x+(-x )\leq 0$. If say $(x+(-x))\ngeq 0$, we should have some $(x+(-x))^R\leq 0$, that is $x^R+(-x)\leq 0$ ...
4
votes
1answer
43 views

How many possible rankings in a game?

This is an interesting problem that I have no easy solution for, but an inkling that there may be one! Consider an $n$ player game. If we disallow draws, we know that the number of permutations of $...
6
votes
2answers
186 views

Proof of solutions to “24” operations game

Consider a deck of cards with values $1$ through $13$, each with multiplicity $4$, so that $$S = \left( \bigcup_{i=1}^{13} \{ i \} \right) \times \{1,2,3,4\}$$ Supposedly, there exists a game in ...
1
vote
0answers
277 views

Sum of Zero Nim-sum Triplets

I'd like to ask the sum of triplets satisfying that its nim-sum is zero, i.e., $$\operatorname{sum}_3(n)=\sum_{0 \leq i,j,k \leq n, i \text{ xor } j \text{ xor } k=0} (i+j+k).$$ If just counting the ...
6
votes
0answers
167 views

British Maths Olympiad (BMO) 2004 Round 1 Question 4 alternative solutions?

The question states: Alice and Barbara play a game with a pack of $2n$ cards. On each of which is written a positive integer. The pack is laid out in a row, with the numbers facing upwards. Alice ...
1
vote
0answers
21 views

Fair sharing sequence for n players

When $2$ players are given an infinite stream of items to divide between them. There is no way to quantify the value of the items, but their value is strictly decreasing. Which person should take the $...
2
votes
0answers
87 views

Math problem from logical game

We have a set of arrows and can start from any point. Every next point must be chosen in direction of previous and can be used only one time. We need to visit all points. Direction of last point doesn'...
2
votes
1answer
39 views

Descending Game Condition and Transfinite induction

I am having a bit of trouble understanding the proof of Conway induction. Definition: Descending Game condition: There does not exist an infinite sequence of games $G^i=(L^i,R^i)$ with $G^{i+1}\...
2
votes
0answers
128 views

Clearing all levels with minimum coins [closed]

Thor is playing a game where there are N levels and M types of available weapons. The levels are numbered from 0 to N-1 and the weapons are numbered from 0 to M-1 . He can clear these levels in any ...
3
votes
2answers
75 views

What is the minimum number of questions to find the ring

There are 11 rings around a circle numbered from 1 to 11. We know that exactly 9 of them are fake and exactly 2 of them are real rings. In each step, we can choose 5 consecutive rings and ask the ...