Grundy's Game
Grundy's Game is played with one or more heaps of items. The nature of the items is not important, but in the applet below they may perhaps remind of chocolate squares . The only legal move in the game is to split a single heap into smaller two of different sizes.
To perform a move click between any two (with the above provision) adjacent squares.
This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.
Explanation
Copyright © 1996-2008 Alexander Bogomolny
Grundy's Game
Clearly the game ends when all the heaps have either one or two items. The Grundy number of heaps of size 0, 1, 2 is 0. By the Mex rule , that of the heap of size 3 is 1. For other sizes the Grundy numbers are found successively: 0, 0, 0, 1, 0, 2, 1, ... Here is a list of values for heap sizes up to 60 [WW , p. 96]:
0-9 0 0 0 1 0 2 1 0 2 1
10-19 0 2 1 3 2 1 3 2 4 3
20-29 0 4 3 0 4 3 0 4 1 2
30-39 3 1 2 4 1 2 4 1 2 4
40-49 1 5 4 1 5 4 1 5 4 1
50-59 0 2 1 0 2 1 5 2 1 3
As usual, the P -positions are those whose Grundy number is 0. You are bound to win the game if, on every move, you leave a P -Position.
References
E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays , Volume 1, A K Peters, 2001
J. H. Conway, On Numbers And Games , A K Peters, 2001
R. Guy, fair game , Comap's Explorations in Mathematics, 1989
Copyright © 1996-2008 Alexander Bogomolny
28765975
Amazon.com Widgets
Amazon.com Widgets