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 meaning "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 theorem.

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.

Nim

External links and references