Nim
For information on NIMH, see National Institute of Mental Health
NIM is also short for the National Independents Movement. ---
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 +1Heap A 4 =4Heap B 5 =4+1Heap 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), you can only make random moves hoping to confuse your opponent.
For a misère game, the strategy has to be slightly altered. To win, play the game like normal until all but one of the non-empty heaps contain a single object. Then take from the heap with multiple objects to leave an odd number of single object heaps.
In a typical game (with 3 heaps of 3, 4 and 5), the strategy would be applied like this:
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 2 from C
1 4 3 110 I take 2 from B
1 2 3 000 You take 1 from C
1 2 2 001 I take 1 from A
0 2 2 000 You take 1 from C
This is where the alternate strategy kicks in.
0 2 1 010 I take the entire A heap, to leave an odd number (1) of single object heaps.
0 0 1 000 You take 1 from C, and lose.