Nim-sum — where it appears
Named by 40 essays across 5 fields — each of them below, with the objects they name alongside it.
Nim, and the nim-sum
Three heaps of counters, take as many as you like from one of them, and the player who takes the last counter wins. The winning condition is not a search, not a table, and not a heuristic — it is the bitwise exclusive-or of the heap sizes, and it was found in 1901.
The theorem that needed none of the theory
Bouton solved Nim completely in 1901, with an argument that mentions no value, no sum of games and no Grundy number, because none of the three existed. The argument is two closure properties and it is airtight — and run on any other game it fails at the step that does the work.
The game with the shortest rule is the hard one
Deciding a generalised board game is PSPACE-complete, which is a statement about families and encodings rather than about size. Nim in the same subject is settled by one pass over the input at any size, and green Hackenbush by one pass over the edges — while Domineering, whose rules take a single line, has no shortcut anybody has found.
Two people, four years apart, one theorem
Roland Sprague proved it in 1935 and Patrick Michael Grundy proved it in 1939, neither knowing of the other. That looks like coincidence until the alternatives are examined — and the rule they both reached turns out to be the only one that can work at all.
The move that gives counters back
Poker Nim adds one rule to Nim — a player may put counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. The winner is decided by exactly the same nim-sum, and the reason is the single most useful idea in the whole reduction apparatus.
A row of coins is already a sum
Everywhere else on this site a sum is several positions side by side. In a coin-turning game it is one row — each coin showing heads is a game in its own right, and the row is worth the exclusive or of them. The decomposition is inside a single picture.
Nim is easy, in binary
Three heaps of a thousand counters take thirty bits to write down and three thousand counters to lay out. The nim-sum does three exclusive-ors either way. Whether that counts as fast depends entirely on which of the two numbers the work is compared against.
Take one, three or four
A heap and a list of legal takes. It is the smallest interesting impartial game there is, and the only family in the subject where eventual periodicity is not observed, not conjectured, but guaranteed — with a bound on when it must appear.
"Left wins" has no short proof
A complete solution of Nim on heaps of 7, 11 and 13 is 480 table entries. A winning strategy for the same position — one move of the winner's at each of their turns, and an answer to every reply — has 56,167,022 nodes in it. The answer is smaller than the proof by a factor of a hundred thousand.
The nimbers multiply
Nim-addition is exclusive-or and everybody meets it first. There is also a multiplication, defined by the same take-the-least-value-not-forced manoeuvre as the mex — and it makes the nimbers below sixteen a field, with every axiom checked here and an inverse for every non-zero value.
The tartan theorem
The nimbers are a field, with a multiplication defined by a mex-style rule that looks like an algebraist's amusement. Lay two coin-turning games on a grid and the Grundy value of each square is the nimber product of its two coordinates — which is the point at which the multiplication stops being a curiosity and starts computing answers.
A move that must be answered
Every argument on this site about sums assumes the parts are independent: a move in one leaves the others alone, and the reply may go anywhere. Top Entails denies it — take the top coin of a heap and the opponent must answer in that heap. The nim-sum then misreads 9 of 36 two-heap positions, and two heaps of two coins are a first-player win, which no impartial game the theory covers can be.
The losing positions are a code
Turn over one, two or three coins, and the rows a player has already lost turn out to be closed under adding two of them together. That makes them a linear code — and on eight coins it is the extended Hamming code exactly, sixteen words with a weight enumerator of 1 + 14x⁴ + x⁸, produced by a move rule that knows nothing about codes.
Three different claims are all called solved
Hex is solved in the sense that the first player provably wins, by an argument that names no move whatever. Nim is solved in the sense that a formula gives the right move from any position at any size. Between them sit strategies for one opening, and databases of a few billion positions. The word covers all four.
Taking from several heaps at once
Moore's Nim lets a move take from as many as k heaps at a time, and the losing positions are still read off the binary columns — divisible by k + 1 rather than by two. The rule agrees with exhaustive search over 54,264 positions and never disagrees, and it decides every outcome while supplying no value at all: reading the same columns as a base-3 number gets the Grundy value right on 42 of 330 positions.
What a tame heap may be replaced by
Calling a heap tame is only worth anything because a tame heap can be swapped for a Nim position with the same genus in any misère sum. The swap is not always a single heap: Kayles' heap of eight is worth ∗ under normal play and carries the genus of 2 + 3, and substituting ∗ instead gets three of the twenty-eight Kayles pairs wrong.
Three players and no answer
Every theorem here is about two players, and the reason is not convenience. With two players the game is zero-sum, so 'play well' needs no further explanation. Add a third and the winner of a Nim position becomes a fact about the convention: two reasonable ones disagree on 56 of the 71 positions swept. The one question no convention touches — can a player force a win against the other two together — is answered 'nobody' in 65 of the 71.
A pass is not a move
Put a single pass token on a Nim board and one clause decides everything. If it may be taken at any time — including as the move that ends the game — the value of the whole is the nim-sum with a one added, in all 120 positions swept: the pass is a heap of one. Forbid it as the final move and the value stops being a function of the nim-sum at all, and 3 and 1 + 2 come apart.
The code names the move
If the lost rows of a coin-turning game are a linear code, then a won row is a codeword with errors in it and the winning move is whatever turns the errors off. Over all 256 rows of Mock Turtles on eight coins: 16 codewords, 240 won rows, none more than two coins from a lost one — and 64 of them whose cheapest winning move has to turn three coins anyway.
No two heaps alike
Welter's game is Nim with one extra clause — no two heaps may be the same size — and the clause is fatal to the nim-sum, which gives the right answer in none of the 120 three-coin positions. What replaces it is a function of pairs: ⟨a | b⟩ = (a ⊕ b) − 1, exact on all 55 two-coin positions, and nim-added over every pair it is exact on the whole board provided the number of coins is even.
Splitting is a move
Add to Nim a move that removes nothing — break a heap in two — and the Grundy sequence gets simpler, not harder. Lasker's Nim has a closed form with one clause per residue modulo four, exact on all 2,001 heaps checked: the identity with every fourth pair transposed. Kayles is the same kind of game with the taking bounded instead of the splitting, and it has no closed form at all, settling into a period of twelve only from heap 71 with fourteen values outside it for ever.
A period with a constant added
An octal code says what a player may do when removing k counters, in three bits; a hexadecimal code adds a fourth — leave three heaps — and the digits run to fifteen. Over twenty-two codes swept to six hundred heaps, five hexadecimal ones repeat with a fixed amount added each time round and no octal one does. Their values climb for ever and never repeat, so a search that looks only for repetition reports them unsettled.
What a component has to carry
Three impartial games on this site break the sum, and they break it for the same reason: a component cannot say what its own legal moves are. Measured with one instrument — one number per part, exclusive-ored — the failure rate runs from a quarter to nearly half, against a control where the same recipe is a theorem and is never wrong.
A code that climbs by three
Five hexadecimal codes were known to repeat with a constant added, and every one of the five constants was a power of two — either a fact about exclusive-or or a coincidence over five cases. Sweeping all 255 two-digit codes settles it: seventy-one climb, seventy of them by 1, 2, 4 or 16, and one by three. The exception is ·3f, whose values are 3⌊n/6⌋ + (n mod 3) on every heap to twelve hundred.
The rule a smaller move breaks
Moore's Nim lets a player take from at most k heaps, and its winning condition is the binary columns summed modulo k + 1. Cap the amount as well and the obvious repair — reduce each heap modulo the cap plus one, then read the columns — is exact at every cap when k is one and wrong at every cap when k is two or three. The reason is stronger than a broken rule: at k ≥ 2 the residues do not determine the outcome at all, so nothing of that shape can work.
The wider move is the easier game
An earlier essay ruled out every rule that reduces the heaps and reads the residues, and asked for a two-part statistic: the residues plus one more count. Four second parts are tested here and none of them decides. What turns up instead contradicts the premise the request was made under — a move that may reach three heaps is more predictable than one that may reach two, on every cap, every candidate rule, and after the change in the base rate is taken out.
The parities, in size order
The rung below settled four of six parity classes in bounded Moore's Nim and asked whether the sizes pick out the losing positions in the two it could not. They do — but only through the order they put the parities in. Sort the heaps largest first, read off their parities, and that five-bit word settles the whole game at every width of move, with the losing words forming a subspace.
The dual was the value table
A coin-turning game's losing rows form a linear code, and a code has a dual that nothing in the game appeared to read. It reads it constantly: the dual is spanned by the bit-planes of the Grundy values — the parity checks are the value table stood on end — and on Mock Turtles over eight coins the losing rows are exactly the span of the table that decides them.
The pairing the formula hides
Welter's closed form sums a function over every pair of coins and needs an extra term when the count is odd, which the rung below called a surprise. Read as a matching it is not: an odd number of coins cannot be paired, the left-over coin contributes its own square, and some matching gives the value on every position measured.
The parts are worth nothing and the sum is not
Every chain and every loop in Nimstring, taken alone, has Grundy value nought. So the Sprague–Grundy theorem predicts that every position built from them is worth nought — and ninety-six of the two hundred and seven positions checked here are not. The theorem is not being misapplied; it does not apply, because a capture keeps the turn. What replaces it is smaller and sharper: count the short chains, and one long component of any kind reverses the parity.
Four hundred and seventy steps
The tartan theorem replaces a search with a multiplication. Measured on every grid a brute-force solve can reach, the two agree on all of them — and the ratio doubles with every square added. On the 8 × 8 grid the theorem is normally drawn at, the search would have to value eighteen quintillion arrangements; the theorem needs twenty-six different nimber products, and computing all of them by the rule that defines them looks at four hundred and seventy pairs.
Three complete solutions in nine years
Bouton in 1901, Wythoff in 1907, Moore in 1910 — three airtight solutions of three games, all published before there was any theory of games at all. Asked about each other's games they all fail, and two of them fail by being wrong while one fails by having no form for the question. Only the last kind of failure decides anything.
A set with a short description
Bouton's argument is a closure argument about a set, and every impartial game has such a set — its own losing positions. So the method is complete and proves nothing. What made 1901 a theorem is that his set had a description shorter than the game, and swept over fifty-six subtraction games, exactly seven have one of his kind.
The sentence that solved the other convention
Bouton's paper solves misère Nim too, in one line, and it is the only misère result in the subject that fits on one. Transplanted the way the normal criterion is, it fails differently — the normal one calls losses wins and never the reverse, and this one errs in both directions on every game tried, because the clause it adds is about counters rather than about moves.
Where the needle has a sentence
Strategy stealing proves the first player wins every Chomp bar and names no square to take. On two families the square can be said in a sentence — a square bar and a bar two rows deep — and in both the sentence is a pairing that names every later move too. Three rows deep the needle wanders, and the observation that every bar has exactly one needle survives ninety-four rectangles and fails on the ninety-fifth.
The step nobody took for thirty-four years
Bouton's criterion is that the heap sizes exclusive-or to nothing. The 1935 theorem is that the heap Grundy values do. The exclusive-or is the same operation in both and it is his, so the whole of the intervening thirty-four years is one substitution — and run over eight games and 672 positions, the substituted criterion is exact on every one while the original is exact on Nim and nowhere else.
The proof is sixteen cells
Lasker's Nim has a four-clause formula that was checked on two thousand heaps and never proved. The proof fits in a four-by-four table: the last two bits of a split's value are fixed by the last two bits of its parts, so no split can land in its own heap's class — except at 3 mod 4, where it lands exactly on the one value the takes leave missing and pushes the answer up by one.
One split is enough
A heap of n in Lasker's Nim offers ⌊n/2⌋ ways to split, and the values use at most one of them. Allow only the split that takes a single counter off and every heap to six hundred keeps its value; of all sixty-three sets of split sizes up to six, a set keeps the formula exactly when it contains 1 or 2. Equal halves alone give back plain Nim, because a split into equal parts is a move to nought.
Three heaps and a pass
Nim with a single pass that may not end the game is easy on one heap and on two: a heap swaps each odd size with the even one above it, and two heaps lose exactly at (2k − 1, 2k). On three heaps the losses are known only as a list. Fix the smallest heap and each slice of the list settles into a pattern after an irregular start — period 4, 8, 10, then 160 at a smallest heap of ten, and nothing visible from eleven.
A misère sum is searched, not added
Under normal play the outcome of a sum of heaps is a nim-sum of numbers already known: twenty stored values decide every sum of Dawson's chess with heaps up to nine, however many heaps it has. Under misère play each sum is a new position to search. One outcome costs six positions for a single heap, two hundred for four heaps and over five thousand for eight, and a table of every eight-heap outcome costs a hundred thousand. The misère quotient is the only thing that brings the price back down.
Named alongside it
The objects these essays reach for when they reach for this one.
Grundy valueExhaustive searchImpartialNimMexXORSprague–GrundyDisjunctive sumNormal playOctal gameClosed formCounterexample