Nim

Nim is a game in which players take turns removing objects from heaps, but may only take from one heap at a time. In the normal version, the player to take the last object wins; in the misere version of the game, the player to take the last object loses. The name (probably from German nimmt == "he takes") and the complete theory of the game were invented by C. L. Bouton[?] of Harvard University about 100 years ago.

Nim is now used as a simple illustration of the Sprague-Grundy theory of games.

A version of this game is played in Alain Resnais' movie L'année dernière à Marienbad.

A typical normal game starts with heaps of 3, 4 and 5:

 A B C           (Heaps A, B, and C)
 3 4 5           I take 2 from A
 1 4 5           You take 3 from C
 1 4 2           I take 1 from B
 1 3 2           You take 1 from B
 1 2 2           I take entire C heap
 2 2 0           You take 1 from A
 1 2 0           I take 1 from B (In the misere game I would take the entire 2 heap)
 1 1 0           You take 1 from B
 1 0 0           I take the last 1 and win.

Nim has been mathematically solved; that is, there is a defined and guaranteed way to win. In a typical misere game that starts with heaps of 3, 4, and 5, player 1 should always win.

 011           Heap A in binary
 100           Heap B in binary
 101           Heap C in binary
 ---
 010           The digital sum[?] of heaps A, B, and C

To win, you must end every turn with a digital sum[?] of 0, unless you are playing the misere game. In the misere game play normally until only heaps of size 1 will remain and move to ensure an odd number of heaps. Let's play a misere game:

 A B C   Sum   (Heaps A, B, and C)
 3 4 5   010   I take 2 from A, leaving a sum of 000, so I will win.
 1 4 5   000   You take 3 from C
 1 4 2   111   I take 1 from B
 1 3 2   000   You take 1 from C
 1 3 1   011   I take 2 from B leaving 3 heaps of size 1
 1 1 1           You take 1 from C
 1 1 0           I take 1 from B leaving 1 heap of size 1
 1 0 0           You take the last 1 and lose.

External links and references

• an interactive column about Nim (http://www.cut-the-knot.com/ctk/May2001).
• Play Nim online (http://www.gametheory.net/html/games)
• Nim Programs and Websites (http://sjhs.freeshell.org/nim/)