Encyclopedia > Nim

Article Content

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

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 North Haven, New York ... to 44, 28.7% from 45 to 64, and 28.1% who are 65 years of age or older. The median age is 50 years. For every 100 females there are 86.7 males. For every 100 females ...