info prev up next book cdrom email home

Nim-Value

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 $(x, x)$ where $x\in [1, 7]$. 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.




© 1996-9 Eric W. Weisstein
1999-05-25