Grundy's game
From Wikipedia, the free encyclopedia
Grundy's game is a two-player mathematical game of strategy. The starting configuration is a single heap of objects, and the two players take turn splitting a single heap into two heaps of different sizes. The game ends when only heaps of size two and smaller remain, none of which can be split unequally. The game is usually played as a normal play game, which means that the last person who can make an allowed move wins.
Contents |
[edit] Illustration
A normal play game starting with a single heap of 8 is a win for the first player provided she does 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 she hands back to her 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
[edit] Mathematical theory
The game can be analysed using the Sprague–Grundy theory. 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 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.
