Nim

Nim is a mathematical strategy game for two players. The game starts with several piles (heaps) of objects — traditionally stones, coins, or matchsticks. Players take turns removing any number of objects from a single pile (at least one, up to the entire pile). In the standard version (normal play), the player who takes the last object wins. In the misère variant, the player who is forced to take the last object loses. Nim is one of the most fundamental games in combinatorial game theory.

Rules (Normal Play)

1. The game begins with a number of piles, each containing one or more objects. A common starting configuration is piles of 3, 5, and 7.
2. Two players alternate turns.
3. On each turn, a player must remove at least one object from exactly one pile. They may take as many objects as they wish from that pile, up to and including the entire pile.
4. The player who takes the last object from the last remaining pile wins.

Rules (Misère Variant)

Same as above, except the player who is forced to take the last object loses.

Strategies

• Nim-Sum (XOR Strategy): The key to winning Nim is the binary digital sum (XOR) of all pile sizes. If the XOR of all piles is 0, the position is losing for the player whose turn it is (with perfect play by the opponent). If the XOR is non-zero, the current player can always make a move that leaves the opponent in a zero-XOR position.
• How to Calculate Nim-Sum: Convert each pile size to binary and XOR them together. For example: piles of 3 (011), 5 (101), 7 (111) → XOR = 001 (non-zero, current player can win).
• Winning Move: To win from a non-zero XOR position, find a pile where removing some objects makes the total XOR equal to zero. There is always at least one such pile.
• Misère Strategy: Play the same XOR strategy as normal Nim, but with one exception: when all remaining piles have size 1, take to leave an odd number of piles (forcing your opponent to take the last one).
• Single Pile Endgame: If only one pile remains, take the entire pile (normal play) or all but one (misère).
• Two Equal Piles: If there are exactly two piles of the same size, this is a losing position in normal play (XOR = 0). Mirror your opponent's moves until the endgame.

Nim has ancient origins, though the exact history is difficult to trace. Games involving the removal of objects from piles have been played for centuries across many cultures. The name "Nim" was coined by Charles L. Bouton, a professor of mathematics at Harvard University, who published the complete mathematical analysis of the game in 1901 in a paper titled "Nim, A Game with a Complete Mathematical Theory." The origin of the name is uncertain — it may come from the German word "nimm" (take) or the archaic English "nim" (to steal).

Bouton's key insight was the XOR-based winning strategy, which he proved rigorously. This was one of the first games to be completely solved mathematically, and it laid the groundwork for the field of combinatorial game theory. His analysis showed that the entire game could be reduced to a simple binary calculation, making Nim one of the most elegant intersections of mathematics and games.

In 1939, Edward U. Condon, Willard A. Derr, and Gerald L. Tawney at Westinghouse built the "Nimatron," an electromechanical machine that played Nim. It was exhibited at the 1940 New York World's Fair, where it won about 90% of the 100,000 games played against it, making it one of the earliest game-playing machines. In 1951, the Nimrod computer was built specifically to play Nim and was displayed at the Festival of Britain, becoming one of the earliest examples of digital game-playing computers.

Nim's mathematical theory, particularly the Sprague-Grundy theorem (developed by Roland Sprague in 1935 and Patrick Grundy in 1939), became the foundation of combinatorial game theory. The theorem shows that every impartial game (one where both players have the same moves available) is equivalent to a Nim position. This means that the strategy for Nim can, in theory, be applied to any impartial game. Nim remains a standard topic in mathematics and computer science education and is frequently used to introduce students to game theory and binary arithmetic.