# Tagged Questions

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.

884 views

### Reference for combinatorial game theory.

What is a good reference material for elementary combinatorial game theory? By combinatorial game theory I mean chiefly the study of zero-sum, deterministic two-player games (perhaps even more ...
118 views

### Game: two pots with coins

Rules of the game with two players. First player puts any number of coins in the first pot. Then second player, knowing that number, puts any amount of coins in the second pot. Then they in turns (...
6k views

### The Ring Game on $K[x,y,z]$

I recently read about the Ring Game on MathOverflow, and have been trying to determine winning strategies for each player on various rings. The game has two players and begins with a commutative ...
74k views

### Maximum board position in 2048 game

A game called 2048 is making rounds on social media. I am trying to determine the maximum score attainable for this game. Let's assume WLOG that only 2s are returned (if 4s are possible the max score ...
565 views

### Does a finite game that cannot be drawn imply a winning strategy exists?

The author of this page, about a simple game (Chomp) http://plus.maths.org/content/mathematical-mysteries-chomp makes the following statement: "One of the players is sure to have a winning strategy. ...
1k views

### Converting a Gomoku winning strategy from a small board to a winning strategy on a larger board

Gomoku is the game where Black and White take turns placing stones of their own color, and the winner is the player who first gets five of their own stones in a row. Black moves first. In Gomoku on ...
545 views

### Game involving tiling a 1 by n board with 1 x 2 tiles?

Consider a $1$ by $n$ tiled rectangle. You want to play a game with one opponent in which you place $1$ by $2$ "dominoes" on this rectangle. The player who places the last domino wins. Which player ...
4k views

### game combinations of tic-tac-toe

How many combinations are possible in the game tic-tac-toe (Noughts and crosses)? So for example a game which looked like: (...
115 views

### Name for a certain “product game”

Let $G,H$ be two (combinatorial impartial) games. Consider the following new game $P$: The positions are the pairs of positions of $G$ and $H$. A move in $P$ is a move in $G$, or a move in $H$, or a ...
6k views

### Winning strategy for a matchstick game

There are $N$ matchsticks at the table. Two players play the game. Rules: (i) A player in his or her turn can pick $a$ or $b$ match sticks. (ii) The player who picks the last matchstick loses the game....
88 views

### Are there combinatorial games of finite order different from $1$ or $2$?

Are there any combinatorial games whose order (in the usual addition of combinatorial games) is finite but neither $1$ nor $2$? Finding examples of games of order $2$ is easy (for example any ...
75 views

### Can we construct from $[0,\omega_1)$ a space which is strictly-Frechet with no winning strategy in $G_{np}(q,E)$?

I have asked in here a question which tured out to make no sense. I think I have found the confusion and would like to try and rephrase my question: Let $E$ be a topological space, $q \in E$. ...
108 views

### In the card game “Projective Set”: Compute the probability that $n$ cards contain a set

In the game of Projective Set, it turns out that any seven cards contain a projective set. For fewer than 7 cards, how can we determine the probability that one or more sets exist (in terms of the ...
344 views

### A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
654 views

### Prime Numbers and a Two-Player Game

In this question, $\mathbb{N}_0$ is the set of all nonnegative integers. The notation $\mathbb{N}$ is reserved for the set of all positive integers. Alex and Beth are playing the following game. ...
301 views

### Optimal strategy for this Nim generalisation?

Consider the following game: There are a number of piles of stones. On each turn a player can remove as many stones he likes (at least 1) from up to $N$ piles (at least 1). It is allowed to remove a ...
155 views

### In the card came “Projective Set”, show that 7 cards do always contain a set. [duplicate]

In the game of Projective Set, it turns out that any seven cards contain a projective set. How can one prove this? And for fewer than 7 cards, how can we determine the probability that one or more ...
577 views

### Traversing the infinite square grid

Suppose we start at $(0.5,0.5)$ in an infinite unit square grid, and our goal is to traverse every square on the board. At move $n$ one must take $a_n$ steps in one of the directions, north,south, ...
350 views

### A question about something in Conway's “On Numbers and Games”

In the book mentioned in the title, which deals with (among other things), Conway's "surreal numbers", there is a small section (pp. 37-38) where the "gaps" in the surreal number line are discussed. ...
218 views

### Tutorials for Sprague-Grundy Theorem/Nimbers?

Help needed in understanding S-Grundy Number , any good tutorial. I am trying to solve Mathalon Problem 146 S-Grundy Game (dead link).
61 views

### The application of Nimbers to Nim strategy

I've been reading about combinatorial game theory, and some works start with the game of Nim. After that, they introduce Nimbers, which are numbers that represent Nim games. So far so good. I get ...
803 views

### board game: 10 by 10 light bulbs, minimum switches to get all off?

Hy all! My problem is as follows: There's a board of 10 by 10 light bulbs. (So it's a square with 10 columns and 10 rows.) Every single bulb has got its own switch. However, something went wrong and ...
3k views

### How many turns can a chess game take at maximum?

The shortest number of moves that a game of chess can have is 2, as far as I know: White moves pawn from f2 to f3, black moves ...
170 views

### In what way is combinatorial game theory connected to the rest of mathematics?

Since my University library lists Conway's "Winning ways for your mathematical plays in the section "recreational mathematics" alongside books on origami and puzzles, I wondered to what extent game ...
1k views

### How many different chess-board situations can occur?

If you play a standard chess game on a normal $8 \cdot 8$ chess board with the usual rules: How many different "board representations" can exist? Upper bound: Well, you have 16+16 = 32 chess pieces ...
792 views

### Trying to find the name of this Nim variant

Consider this basic example of subtraction-based Nim before I get to my full question: Let $V$ represent all valid states of a Nim pile (the number of stones remaining): $V = 0,1,2,3,4,5,6,7,8,9,10$ ...
1k views

### TicTacToe State Space Choose Calculation

I understand there are numerous questions around the internet about the state space of tic-tac-toe but I have a feeling they've usually got it wrong. Alternatively, perhaps it is I who have it wrong. ...
213 views

### It seems like a nim variant

Now this is a more of a computer science problem than a math problem but it is concerning game theory and it does seem a lot like nim (it's from an online judge), so i'm kinda stuck on this one i'd ...
81 views

### Exceptional values in a combinatorial game

Consider the following combinatorial game: We have two heaps of sizes $n_1 \leq n_2$ (with $n_1,n_2 \in \mathbb{N}$). A move leaves the sizes $m_1,m_2$, where $0 \leq m_1 \leq n_1 \leq m_2 \leq n_2$, ...
115 views

### Counting all possible legal board states in Quoridor

Ignoring pawns there are 1,375,968,129,062,134,174,771 possible ways to place 0 to 20 walls on the Quoridor board, as answered here. Ignoring walls there are 81 * 81 = 6410 ways to place the two ...
719 views

### two elementary games in number theory

I solved these two problems from a programming challenge website: numgame and numgame2. These two problems are very similar. In the first one, the position is a number $n$ and each player can ...
116 views

### A variation of Nim game

There are two players X and Y . They write N integers on paper ( A_1 , A_2 , A_3 , .... A_N ). They have also p integers (b_1 , b_2 , b_3 , .... b_p ) . Now , Player X always takes turn first . He ...
855 views

### Splitting Stacks Nim

A game is played with two players and an initial stack of $n$ pennies ($n\geq 3$). The players take turns choosing one of the stacks of pennies on the table and splitting it into two stacks. When a ...
677 views

### Why does the strategy-stealing argument for tic-tac-toe work?

On the Wikipedia page for strategy-stealing arguments, there is an example of such an argument applied to tic-tac-toe: A strategy-stealing argument for tic-tac-toe goes like this: suppose that the ...
162 views

### Are there non-zero combinatorial games of odd order?

Are there any combinatorial games with odd order (under the usual addition of combinatorial games), apart from $0$? In Are there combinatorial games of finite order different from $1$ or $2$? I asked ...
Let $$\mathcal{N}=\{\{k_1,\ldots,k_s\}:\ s>0,\ \mbox{and the}\ k_i\ \mbox{are non-negative and pairwise different integers}\}\cup\{\emptyset\}.$$ Note that there is a bijection with the naturals, $$... 2answers 112 views ### Game: Group and Multi-Dimensional Chessboard Let G be a group and S\subseteq G. Consider a d-dimensional chessboard of size n_1\times n_2\times \ldots \times n_d, where n_1,n_2,\ldots,n_d\in\mathbb{N}. Each unit hypercube of the ... 2answers 261 views ### Gomoku on an infinite big board I always used to play Gomoku in school on paper, and if we reached the edge of the field, we just put another one at that side. And now I just saw that black can always win on 1 15x15 board. But what ... 1answer 656 views ### Nim Variant (reducing by divisors) Alice and Bob play the following game. They choose a number N to play with. The rules are as follows: Alice plays first, and the two players alternate. In his/her turn, a player can subtract from ... 1answer 212 views ### Counting all possible board positions in Quoridor I'm trying to figure out how many possible board positions there are for the game Quoridor. I think sorting out the legal positions from the illegal positions will be difficult, so to start I'm trying ... 1answer 68 views ### Placing stones on vertices of polygon We have an n-gon with n\geq 3. Players A and B place a stone alternately on one of the unused vertices that is not adjacent to a vertex with a stone. The player who cannot move loses. Who has ... 1answer 51 views ### CGT: value of sum game is sum of values of games I am involved in a little study about combinatorial game theory. The study makes heavy use of the fact that, at least in a simple combinatorial game called domineering, the value of the sum game is ... 1answer 217 views ### Algorithm to multiply nimbers Let a,b be nimbers. Is there an efficient algorithm to calculate a*b, the nim-product of a and b? The following rule seems like it could be helpful:$$ 2^{2^m} * 2^{2^n} = \begin{cases} 2^{2^...
Alice and Bob play the following game : There are $N$ piles of stones with $S_i$ stones in the $i$th pile. Piles are numbered from 1 to $N$. Alice and Bob play alternately, with Alice starting. In a ...