The theorem that needed none of the theory

Charles Bouton published a complete solution of Nim in 1901. It names the winner of every position, gives the winning move, and proves both.

It does this without the concept of a game value, without the disjunctive sum, without Grundy values, and without anything that would today be called combinatorial game theory — because none of that existed, and would not for another thirty-four years.

The argument is two sentences long.

The two properties #

Write each heap size in binary and stack them. Bouton’s claim is about the columns.

(a) From a position where every column is even, every legal move makes some column odd.

(b) From a position where some column is odd, some legal move makes every column even.

That is all of it. Together with the observation that the empty position has all columns even and is a loss for whoever must move, the two properties settle the game: a player handed an odd position moves to an even one, the opponent is forced back off it, the heaps strictly decrease, so play ends — and it ends on the opponent.

Property (a) is the easy half. A move changes exactly one heap, so it changes exactly one row of the binary array, and it must change it: a move that took nothing would not be a move. Changing one row changes at least one column’s parity. Done, and note that nothing about which moves are legal entered the argument.

Property (b) is where the work is. Take the highest column with an odd number of marks; some heap has a mark in it; that heap can be reduced to exactly the size that fixes every column at once, and the required size is smaller than what is there, so the move is legal.

The last clause is the one to check rather than nod at. Reducing a heap is only a move if the new size is smaller, and the new size is obtained by flipping some of that heap’s bits — which could in principle make it larger. It cannot, and the reason is that the highest odd column was chosen: the heap chosen has a 1 in that column and the repair turns it into a 0, so the change at the highest affected bit is downward and everything below it is noise.

The condition has a second statement as arithmetic rather than as parity, and the two are the same statement. Adding the heap sizes without carrying — bitwise exclusive-or, which the nim-sum essay is about — gives zero exactly when every column holds an even number of ones, because a column’s contribution to the sum is its parity and nothing else. So every column even and the nim-sum is nought are one condition written twice, and the rest of this essay uses whichever is shorter at the moment.

Checked, rather than asserted #

The two properties are quantified over every position, and this site’s habit is to check a claim of that shape over every position of a stated size rather than to nod at it.

The hero figure above is drawn from a run over all 512 positions with three heaps of at most seven. Property (a) was tested on every move out of every position with all columns even — 672 moves in that range — and none of them landed back on an even position. Property (b) was tested on all 448 positions with an odd column, and every one of them had a repairing move.

That is not a proof and is not offered as one; the proof is in the paragraph above. It is a test of the code, and the distinction matters. A proof about mathematics does not protect a figure from an error in its own arithmetic, and every value on this site is drawn by a program.

Now run it on a different game #

Here is the thing about Bouton’s argument that its fame obscures. It is not a method. It is one invariant, for one game, and the way to see that is to assert the identical two properties of a different game and watch.

Take the subtraction game where a move removes one, two or three counters from a single heap. Everything else is the same: several heaps, whoever cannot move loses.

Property (a) survives, and it survives for a reason worth sitting with: it says that no move may do something, and taking moves away cannot create a move. The proof of (a) never mentioned which moves were legal, so restricting them changes nothing.

Property (b) fails. It needs a move to a particular heap size, and a subtraction game may simply not offer it. From two heaps of 0 and 5, the criterion says this is a win and the repairing move is to take all five — which the rules forbid, because a move takes at most three.

So Bouton’s criterion is not merely unproved for other games. It is wrong for them: over the 100 positions in that figure’s range it disagrees with the truth on 16.

Test it #

The criterion is a hundred and twenty-four years old and it does not miss.

The reason to include a playable figure in an essay about a 1901 paper is that the paper’s claim is unusually strong and unusually testable. Most results in this subject are about classes of position and are demonstrated on examples. This one names the winning move from every position of a specific game, and a reader can spend as long as they like looking for the position where it does not.

What is worth noticing while playing: the machine never appears to think. It has no evaluation, no depth, no lookahead. It reads the columns and repairs them. A program that plays perfectly and consists of one exclusive-or is a strange object, and it is strange for exactly the reason the rest of this essay is about — the answer was found before there was any theory to make it look inevitable.

The sixteen errors all run the same way #

“Wrong on 16 of 100” is the crude form of the result, and the sixteen are not scattered between the two kinds of mistake. Every one of them is Bouton calling a loss a win. Not one is the reverse.

The same holds when the range is widened, and widening it is the first thing to try, because sixteen errors out of a hundred is a small enough sample for the one-sidedness to be an accident of the range.

Sixty-four out of five hundred and twelve, in one direction, is no longer a small sample. So the transplanted criterion is not unreliable. It is sound and incomplete — when it says a position is lost it is right, and it fails to notice some of the positions that are.

Which is the two properties, showing through #

That one-sidedness is exactly the split the essay has already made, seen from the other end.

Property (b) is the half that failed, and (b) is the half that would have established the wins: from a position with an odd column, some move repairs it. Without it there is nothing to say that a Bouton-odd position is a win — and a Bouton-odd position that is not a win is precisely an error of the observed kind.

Property (a) is the half that survived, and (a) is what keeps the other direction clean: no move goes from an even position to an even one, so nothing lets a Bouton-even position be a win.

Two halves, two directions, and the measurement finds errors in exactly the direction the failed half was responsible for. That is a much better account than a count, because a count of sixteen says nothing about what the criterion may still be used for and the direction says everything.

Why the errors run that way, arithmetically #

There is a second reading of the same fact, and it says what Bouton’s criterion is doing wrong in one sentence.

The subtraction game $\{1,2,3\}$ has Grundy value $n \bmod 4$ — the heap size’s low two bits, and nothing else. The correct criterion is that those low two bits exclusive-or to nothing across the heaps.

Bouton’s criterion asks that all the bits exclusive-or to nothing. And exclusive-or is bitwise, so a zero over all the bits is in particular a zero over the low two. Bouton’s condition implies the true one and not conversely, which is the one-sidedness written as arithmetic.

So the criterion is not reading the wrong quantity in a scattered way. It is reading too much of the number: the game uses two bits of a heap’s size and Bouton’s test consults all of them, and consulting extra bits can only refuse positions the true test would have accepted.

That is the sharpest statement of what the intervening thirty-four years supplied. Not a repair to the parity argument — the parity argument is exactly right, on exactly the right quantity — but the discovery that the quantity is the heap’s value rather than its size, and that for Nim alone the two are the same number. Every column Bouton counted was a column of a Grundy value in disguise, and the disguise is why the theorem could be found in 1901 and the reason for it could not.

And the one-sidedness is itself special, which is worth knowing before anybody carries it away as a rule. It holds here because $4$ is a power of two: a Grundy value that is the size’s low $k$ bits is a truncation, and truncating cannot turn a zero exclusive-or into a non-zero one.

Take a subtraction game whose period is not a power of two and the protection should be gone. $\{1,2\}$ has Grundy value $n \bmod 3$, which is not a truncation of anything, so there is nothing to stop the errors running both ways. The two-heap range is the wrong place to look for them.

That is the reason the two-heap range says nothing about the direction of the errors, and it says nothing for a reason that has no connection to Bouton or to truncation. Three heaps is the smallest range in which a Bouton-even position can fail to be a genuine loss, so it is the smallest range in which the question is asked at all.

$\{2,3\}$ gives 30 of those as well, over the same range, and a third game with a third period gives fewer without giving none.

So the clean sixteen are clean because that game’s values happen to sit inside the bits Bouton is reading. In general his criterion is not sound either, and the two properties come apart in both directions at once — which is the strongest available statement that a criterion is a fact about one game rather than a method.

What was missing, stated exactly #

The repair is not a patch to the argument. It is a different criterion, and the shape of the difference is the whole of what the next thirty-four years produced.

Bouton’s condition is the nim-sum of the heap sizes. The correct condition is the nim-sum of the heaps’ Grundy values — and for Nim itself those coincide, because a Nim heap of $n$ has Grundy value $n$. Bouton’s theorem is the general theorem specialised to the one game where the specialisation is invisible.

The Grundy values of the subtraction game $\{1,2,3\}$ run 0, 1, 2, 3, 0, 1, 2, 3 and repeat for ever. A heap of four counters behaves exactly like a Nim heap of nought — it is worth nothing at all — which is the fact Bouton’s criterion has no way of expressing, because his criterion reads the heap size directly. Each figure above prints that sequence under its own game, so the correct criterion is on the page beside the one being tested.

This is why the two heaps of 0 and 5 came out wrong. Under the correct reading the heap of 5 is worth 1, the heap of 0 is worth 0, the nim-sum is 1, and the position is a win — which is right — but the winning move is to take one counter and leave 4, a heap worth zero. Bouton’s criterion would have looked for a heap of size 0 and found the move illegal, because it is reading sizes where it should be reading values.

Two heaps, and the reason the argument feels like a trick #

There is a version of Nim that everybody solves by themselves, and comparing it with Bouton’s is the fastest way to see what he actually added.

With two heaps the answer is obvious after a few games: keep them equal. If the heaps are unequal, make them equal; if they are equal, whatever the opponent does can be answered by restoring equality; the heaps shrink; the last counter falls to the player doing the restoring. No binary anywhere.

That strategy is a mirroring argument, and mirroring arguments are ancient and everywhere — they are why every game has a negative and why $G + (-G) = 0$. A reader who has met one recognises it instantly.

With three heaps the mirroring argument evaporates. There is nothing to mirror, the obvious generalisations are false, and hand analysis produces a list of special cases rather than a rule. What Bouton supplies is a criterion that reduces to keep them equal on two heaps — two equal heaps have every column even — and keeps working on any number.

Three heaps of 3, 5 and 7 is where the intuition stops. The mirroring strategy has nothing to attach to, and the parity criterion that replaces it reads the binary columns instead: 011, 101, 111, the ones column holding three marks and failing to cancel, so the nim-sum is 1 and the mover wins by taking one counter from the heap of three. The position is worth ∗1 — and Bouton’s criterion reached the same verdict without any notion of a position being worth anything.

So the argument feels like a trick because it is a generalisation of something that felt like common sense, arrived at from the other end. It is not derived from the two-heap case; it happens to contain it.

The surprise: a solved game held the subject up #

The natural story is that Nim was solved and the theory grew out of it. The record is closer to the opposite: Nim was solved so cleanly that it suggested nothing.

Bouton’s proof is self-contained, elementary, and complete. It has no loose end to pull, no case it handles awkwardly, no quantity it introduces that might be interesting elsewhere. The nim-sum appears in it as a condition to check, not as a value a position has — the difference between “these heaps satisfy a parity property” and “this heap is worth 5” — and the second reading is the one that generalises.

Thirty-four years passed. What broke the silence was not a harder version of Nim; it was somebody looking at a game that is not Nim and noticing that it behaves like a Nim heap anyway.

And the rule that had to be found is a rule about values rather than about columns: the value of a position is the least value not among its options’. Five plausible alternatives to it are run and killed on the rung above, each on a computed heap — which is why two people reaching the same rule four years apart says something about the rule rather than about the two of them.

What the picture cannot show #

The binary array is the clearest statement of the criterion and it hides one thing completely: it gives no sense of how large the winning move can be.

A player looking at the columns sees a local repair — flip these bits — and the corresponding move may take almost the whole of a heap or a single counter, with no visual difference. From heaps 3, 5, 7 the winning move takes one counter from the heap of three; from heaps 3, 5, 5 it takes all three of them. The two binary arrays differ in one digit and the two moves do not resemble each other at all.

That is a real limitation of the representation and not a defect of the figure, and it is the reason Nim’s easiness is a claim about its encoding: the criterion is linear in the digits and the game is exponential in the counters.

The convention, named #

Everything above is normal play: the player who cannot move loses.

Bouton’s paper also treats the other convention, and this is genuinely to his credit, because it is a harder result and he got it. Under misère play — last player to move loses — the winning condition for Nim is almost the same, with one exception: when every heap has size one, the criterion inverts.

The rule is: play by the ordinary criterion until the move to hand would leave every remaining heap of size one, and at that moment leave an odd number of them rather than an even number.

The exception has one position in it worth stating outright. Under normal play three heaps of one is a first-player win by the parity criterion — one column, three marks, odd. Under misère play it is a loss, and the criterion has inverted on exactly that shape of position. Everywhere else in Nim the two conventions agree on which positions are wins, which is why the exception can be stated as a single sentence rather than as a second theory.

That exception looks like a footnote and is a warning. Misère Nim is the one misère game with a clean answer, and the reason is that Nim’s heaps are so simple that the endgame has only one special case. For nearly every other game the misère theory does not have a clean answer, does not compose, and was for decades considered hopeless.

The general shape of that failure is worth stating here because Bouton’s success hides it. Under normal play the value of a sum is computed from the values of the parts, and one number per position is enough. Under misère play it is not: two positions can agree everywhere in isolation and differ inside a sum, so the objects that behave like values are much larger, and how much larger depends on which other games are in the room. Nim escapes because its parts are so simple that the whole apparatus collapses to a single special case.

The step everybody skips #

Both properties are about single moves, and the theorem is about whole games. The bridge between them is one sentence that is easy to read past.

The heaps strictly decrease, so play ends.

Without it the argument proves nothing. Properties (a) and (b) together say a player can always hand back an even position and the opponent can never hand back one — but “always able to move to an even position” is not a win unless the game stops. A position from which one can shuffle for ever is a draw, not a victory, however good the parity looks.

Nim earns the sentence trivially: every move removes at least one counter from a finite pile. That is why the termination clause is invisible in Bouton and load-bearing everywhere else, and it is exactly the hypothesis Zermelo’s theorem is built around. A game with the same two closure properties and no decreasing quantity would have a strategy that never wins.

Where the ladder goes next #

Bouton is rung one of an anchor with a specific job: what a complete solution looks like when it arrives before the theory that would explain it.

The next rung is the theory arriving — Sprague and Grundy, independently, four years apart — and the rung after that is what the theory bought, which is not a better answer to Nim but the ability to ask the question of anything.

That is the pattern this whole field is here to record, and Bouton is its clearest instance. A complete, correct, elementary solution can be a dead end rather than a foundation, and whether it is one has nothing to do with how good the solution is. What decides it is whether the solution introduces an object that turns out to have a life outside the problem. Bouton’s nim-sum is such an object and his paper does not treat it as one: it appears as a test to apply, and it took thirty-four years for somebody to write down that a heap of five is five rather than merely satisfying a condition involving five.