Grundy's game on:
[Wikipedia]
[Google]
[Amazon]
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.
Grundy's game on MathWorld
Mathematical games Combinatorial game theory Recreational mathematics
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.
Illustration
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 losesMathematical theory
The game can be analysed using theSprague–Grundy theorem
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as ...
. 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
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
as {{OEIS2C, id=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
Elwyn Ralph Berlekamp (September 6, 1940 – April 9, 2019) was a professor of mathematics and computer science at the University of California, Berkeley.Contributors, ''IEEE Transactions on Information Theory'' 42, #3 (May 1996), p. 1048. DO10.1 ...
, John Horton Conway
John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...
and Richard Guy have conjecturedE. Berlekamp, J. H. Conway, R. Guy. ''Winning Ways for your Mathematical Plays.'' Academic Press, 1982. that the sequence does become periodic eventually, but despite the calculation of the first 235 values by Achim Flammenkamp, the question has not been resolved.
See also
* Nim *Sprague–Grundy theorem
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as ...
* Wythoff's game
Wythoff's game is a two-player mathematical subtraction game, played with two piles of counters. Players take turns removing counters from one or both piles; when removing counters from both piles, the numbers of counters removed from each pile m ...
* Subtract a square
Subtract-a-square (also referred to as take-a-square) is a two-player mathematical subtraction game. It is played by two people with a pile of coins (or other tokens) between them. The players take turns removing coins from the pile, always removin ...
References
External links
Grundy's game on MathWorld
Mathematical games Combinatorial game theory Recreational mathematics