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:
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.
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 (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.
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
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