Nim (mathematical impartial game)

Rules and common variants

Standard (unbounded) Nim: start with several heaps, each containing a positive number of counters. A move consists of choosing one heap and removing any positive number of counters from it. Bounded Nim: a variant limits removals to at most k counters on a turn (for example, "up to 3" is often used in teaching examples). Misère Nim: same moves as standard Nim, but the player who takes the last counter loses instead of wins. Small-rule changes can alter strategies, so it is useful to distinguish these cases when analyzing positions.

Winning strategy

Charles L. Bouton gave the complete solution for ordinary Nim in 1901. The central tool is the nim-sum: compute the binary xor of the heap sizes. If the nim-sum equals zero, the position is a P-position (previous-player win with perfect play); if it is nonzero, the position is an N-position (next-player win). A winning move converts a nonzero nim-sum to zero by reducing a single heap to an appropriate size. For a worked example, heaps (3, 4, 5) produce 3 xor 4 xor 5 = 2, so the next player can win by decreasing one heap so that the xor becomes zero. For more on the calculations see the mathematical strategy.

Theory and generalizations

Nim is the prototype for the Sprague–Grundy theory: every impartial game under normal play has a Grundy value (or nimber) and is equivalent to a nim-heap of that size. This reduces analysis of many impartial games to nim arithmetic. For subtraction games where the allowed removals are 1..k, each heap behaves like its size modulo (k+1), which simplifies strategy for bounded Nim. Misère Nim is nearly as tractable: the normal nim-sum rule applies in most cases, but positions consisting entirely of heaps of size one require a different parity-based rule.

History and significance

Nim's solution by Bouton helped launch systematic study of impartial games and inspired later work on impartial and partizan game theory. Nim and its generalizations appear in algorithmic game analysis, teaching of binary operations, and in the classification of combinatorial games via nimbers and octal games. Its clear rules and exact solution make Nim a standard example in textbooks and lecture courses.

Notable points

• Nim demonstrates an exact, constructive winning method based on binary xor.
• Bouton's result is one of the earliest solved games in modern combinatorial game theory.
• Variants (bounded moves, misère play) change the analysis but often remain amenable to nimber methods.