|
|
|
Every position of every Impartial Game has a nim-value, making it equivalent to a Nim-Heap. To find the
nim-value (also called the Sprague-Grundy Number), take the Mex of the nim-values of the possible moves. The
nim-value can also be found by writing the number of counters in each heap in binary, adding without carrying, and replacing
the digits with their values mod 2. If the nim-value is 0, the position is Safe; otherwise, it is Unsafe. With
two heaps, safe positions are 
where ![$x\in [1, 7]$](n_595.gif){kind=small}
. With three heaps, (1, 2, 3), (1, 4, 5), (1, 6, 7), (2, 4, 6), (2,
5, 7), and (3, 4, 7).
See also Grundy's Game, Impartial Game, Mex, Nim, Safe, Unsafe
References
Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 36-38, 1987.
Grundy, P. M. ``Mathematics and Games.'' Eureka 2, 6-8, 1939.
Sprague, R. ``Über mathematische Kampfspiele.'' Tôhoku J. Math. 41, 438-444, 1936.