Nim is a combinatorial game for two players based on removing objects (usually matchsticks) from several heaps. In every turn the player may remove several objects from one heap (but always at least one, maximum number of removed objects differs according to rules of the given Nim variant). In a standard game the player, who takes the last object, wins. In an often played misère game loses the player, who takes the last object.
History of the game
Origins of Nim have not been completely clarified, but it is supposed that the game originated in China. First European references to this game are from 16. century. A winning strategy for Nim was proved and published by Charles L. Bouton in 1901 in the article Nim, a game with a complete mathematical theory.
Winning strategy
At first, we have to convert a number of objects (matchsticks) to the binary numeral system. Let's suppose that we have 3 heaps with 3, 4 and 5 objects. The player may remove at most 3 objects from exactly one heap.
Now we sum the binary sum sizes together, while neglecting carries from one digit to another (we perform XOR operation). The result is called nim-sum.
To get into the winning position, we must always make sure that the nim-sum is equal to zero. In this case, we have to perform such operation, which will set the middle digit to zero – we have to remove two objects from the first heap.
It can be proved, that the opponent cannot turn the game – he cannot make the nim-sum equal to zero and if he takes any step, we will be able to reset nim-sum again.
Misère Nim modification
The winning strategy for misère game is almost the same. The only difference is in endgame, when there remain only heaps of size 1 – in this situation we remove objects in a way that there remains always an odd number of heaps (in standard game, there will always remain even number of heaps).
Sources
- BOUTON, L. Charles. The Annals of Mathematics, 2nd Ser., Vol. 3, No. 1/4. (1901 - 1902), pp. 35-39.
- Nim. In Wikipedia : the free encyclopedia [online]. St. Petersburg (Florida) : Wikipedia Foundation, 25 February 2002, last modified on 22 November 2010 [2010-11-27]. Available at WWW: <http://en.wikipedia.org/wiki/Nim>.