fbpx
Wikipedia

Grundy's game

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.

Stacks of coins. Any of these stacks can be split into two stacks of different sizes: once the leftmost stack of three has been split, it can be split no further.

Illustration edit

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 

Mathematical theory edit

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 OEISA002188:

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 235 values by Achim Flammenkamp, the question has not been resolved.

See also edit

References edit

  1. ^ E. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays. Academic Press, 1982.

External links edit

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

grundy, game, player, mathematical, game, strategy, starting, configuration, single, heap, objects, players, take, turn, splitting, single, heap, into, heaps, different, sizes, game, ends, when, only, heaps, size, smaller, remain, none, which, split, unequally. 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 Stacks of coins Any of these stacks can be split into two stacks of different sizes once the leftmost stack of three has been split it can be split no further Contents 1 Illustration 2 Mathematical theory 3 See also 4 References 5 External linksIllustration editA 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 editThe 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 235 values by Achim Flammenkamp the question has not been resolved See also editNim Sprague Grundy theorem Wythoff s game Subtract a squareReferences edit E Berlekamp J H Conway R Guy Winning Ways for your Mathematical Plays Academic Press 1982 External links editGrundy s game on MathWorld Sprague Grundy values for Grundy s Game by A Flammenkamp Retrieved from https en wikipedia org w index php title Grundy 27s game amp oldid 1181393002, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.