Nim
For information on NIMH, see National Institute of Mental Health
Nim is a two-player game in which players take turns removing objects from heaps, one or more objects at a time but only from a single heap. The players are forced to take at least one object, and are allowed to take the whole heap. In the normal version, the player to take the last object wins; in the misère version of the game, the player to take the last object loses. It is this version that is most commonly played in practice.
The name was invented by C. L. Bouton of Harvard University, who also developed the complete theory of the game about 100 years ago, but the origins of the name were never explained. The name is probably derived from German nimm! meaning "take!". Some people have noted that turning the word NIM results in WIN, but this is probably just a coincidence.
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 objects:
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
1 2 0 You take 1 from A
0 2 0 I take entire B heap and win.
(In the misère game I would only take 1)
Nim has been mathematically solved for any number of initial heaps and objects; that is, there is a defined and guaranteed way to win for one of the players, be it the normal or misère game. In a typical misère game that starts with heaps of 3, 4, and 5, player 1 will win with optimal play.
The key to the theory of the game is the binary digital sum of the heap sizes, that is, the sum (in binary) neglecting all carry overs.
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
An equivalent procedure, which can be performed mentally, is to express the heap sizes as a sum of powers of 2, cancel pairs of equal powers, and then add what's left:
3 = 2 + 1 Heap A
4 = 4 Heap B
5 = 4 + 1 Heap C
---
2 = 2 What's left after cancelling
In the normal game, the strategy is finishing every move with a digital sum of 0, which is always possible if it is different from 0 (in the example above, it suffices taking 2 objects from heap A). If the digital sum is 0 and you must make a move, there is no way you can win the game (assuming the other player is a perfect player). The strategy in the misère game is just like playing normally, except you subtract one from a heap of your choice in the analysis.
So if we have stacks of 3,4,5 like before, we lie to ourselves and pretend that it's 3,3,5, taking one away from B.
A B C Sum (Heaps A, B, and C)
3 3 5 110 I take 5 from C, leaving a sum of 000, so I will win.
3 3 0 000 You take 1 from A
2 3 0 001 I take 1 from B
2 2 0 000 You take 1 from C
Now here, C was the one we artificially subtracted from, so we have to pick another one. You can think of it as that we pretend you took one from another stack, say A.
1 2 0 011 I take one from B
1 1 0 000 You take one from B
1 0 0 001 I take one from A, and I win.
But you see, since A was our artificial stack, it still looks like 1,0,0, and they have to make the last move.
External links and references
