Heaps, binary sums, and the founding move of combinatorial game theory.
Play It
Characterization
Nim is one of the simplest games that can be stated and one of the most consequential that has been solved. Players alternate removing any number of objects from any single heap; the player who takes the last object wins (or, in misère play, loses). The game is Chinese in origin, closely related to jiǎn shízi ("picking stones"), but it received its modern name and its definitive analysis from the Harvard mathematician Charles L. Bouton, who published "Nim, a Game with a Complete Mathematical Theory" in the Annals of Mathematics in 1902. Bouton proved that the game has a complete winning strategy expressible as a "nim-sum" — the bitwise exclusive-or (XOR) on the binary representations of the heap sizes. This was a founding move in what would become combinatorial game theory; the Sprague–Grundy theorem of 1939 demonstrates that every impartial game is mathematically equivalent to a Nim heap. Nim entered the cultural imagination through Alain Resnais's 1961 film L'Année dernière à Marienbad, in which the enigmatic "M" repeatedly wins at misère Nim with the 1-3-5-7 arrangement, transforming the mathematical game into a haunting metaphor for memory, manipulation, and unfreedom. The Academy hosts Nim in the Mind School because it is the hidden binary skeleton beneath ordinary acts of choice: a game so transparent in its structure that to learn it is to see parity itself — the deep, impartial fairness (or unfairness) that binary arithmetic lends to every position.
Lineage
Chinese origin as jiǎn shízi; modern analysis by Charles L. Bouton, "Nim, a Game with a Complete Mathematical Theory" (Annals of Mathematics, 3:14, 1901–1902, pp. 35–39). The Sprague–Grundy theorem independently proved by R. P. Sprague (1935) and P. M. Grundy (1939) generalises the nim-value to all impartial games. Filmed by Alain Resnais in L'Année dernière à Marienbad (1961). The 1962 computer game "Marienbad" by Witold Podgórski for the Odra 1003 is considered possibly the first Polish computer or video game. Comprehensive treatment in Elwyn Berlekamp, John Conway, and Richard Guy, Winning Ways for Your Mathematical Plays (1982).
From the Library
Quests
The Magus
Design or select a variant of Nim — Wythoff's game, Fibonacci Nim, Moore's Nim, or a variant of your own devising — and derive its winning strategy, or prove that no simple closed-form strategy exists. Compare the result to Bouton's nim-sum.
The Adventurer
Play Nim in its classical form — at least three games with an opponent, using heaps of your choice. In at least one game, use the nim-sum strategy consciously and observe the moment when your opponent's position becomes losing. Record the heap configuration at which the binary structure became visible to you.
The Sage
Explain the lineage of Nim's mathematical theory: Bouton's 1902 complete analysis, the Sprague–Grundy theorem of 1939, and the place of Nim in the broader structure of combinatorial game theory. Cite Bouton's paper, at least one treatment of Sprague–Grundy, and one cultural reception (Resnais's Marienbad or another).