# 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.

## External links and references