Grundy's game

A normal play game starting with a single heap of 8 is a win for the first player provided they start by splitting the heap into heaps of 7 and 1:

player 1: 8 → 7+1

Player 2 now has three choices: splitting the 7-heap into 6 + 1, 5 + 2, or 4 + 3. In each of these cases, player 1 can ensure that on the next move he hands back to his opponent a heap of size 4 plus heaps of size 2 and smaller:

player 2: 7+1   → 6+1+1        player 2: 7+1   → 5+2+1        player 2: 7+1   → 4+3+1
player 1: 6+1+1 → 4+2+1+1      player 1: 5+2+1 → 4+1+2+1      player 1: 4+3+1 → 4+2+1+1

Now player 2 has to split the 4-heap into 3 + 1, and player 1 subsequently splits the 3-heap into 2 + 1:

player 2: 4+2+1+1   → 3+1+2+1+1
player 1: 3+1+2+1+1 → 2+1+1+2+1+1
player 2 has no moves left and loses

The game can be analysed using the Sprague–Grundy theorem. This requires the heap sizes in the game to be mapped onto equivalent nim heap sizes. This mapping is captured in the On-Line Encyclopedia of Integer Sequences as OEIS: A002188:

Heap size           : 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 ...
Equivalent Nim heap : 0  0  0  1  0  2  1  0  2  1  0  2  1  3  2  1  3  2  4  3  0 ...

Using this mapping, the strategy for playing the game Nim can also be used for Grundy's game. Whether the sequence of nim-values of Grundy's game ever becomes periodic is an unsolved problem. Elwyn Berlekamp, John Horton Conway and Richard Guy have conjectured[1] that the sequence does become periodic eventually, but despite the calculation of the first 2³⁵ values by Achim Flammenkamp, the question has not been resolved.

• Nim
• Sprague–Grundy theorem
• Wythoff's game
• Subtract a square

• Grundy's game on MathWorld
• Sprague-Grundy values for Grundy's Game by A. Flammenkamp