A Workbook for Weighing Heaps
Being a short course in the one arithmetic that tells you, before a single stone is moved, whether the player about to move has already lost. After Bouton (1901), Sprague (1935), and Grundy (1939).
You will need: several small heaps of stones, a patient opponent, and the willingness to unlearn how you were taught to add. That last is the whole of the difficulty. The sums in this book come out strange, and they are correct, and the strangeness is the lesson.
We play the simplest fair game there is. Stones lie in heaps on the table. On your turn you take any number of stones you like from any one heap — but from one heap only. Players alternate. Whoever takes the last stone wins. No dice, no hidden cards, no one side stronger than the other: everything either player can do, the other could have done from the same position. Games of this kind are called impartial, and this particular one is called Nim. Master its arithmetic and you have, it turns out, mastered the arithmetic of every impartial game — but we are getting ahead of the exercises.
Lesson 1. The weight of a single heap.
Take one heap, all by itself. We are going to assign it a number — call it the heap’s weight — that measures exactly how much trouble it is worth to the player who must move.
Start at the bottom. An empty heap has weight 0: the player who faces nothing at all has no move, and (last stone wins) has lost. Weight 0 will mean, always and everywhere in this book, the player to move is losing. Hold onto that; it is the only thing the whole edifice is built to compute.
Now the rule that generates every other weight, and it has an ugly name — the mex, for minimum excludant. To weigh a position, list the weights of all the positions you could move to, and take the smallest non-negative whole number that is missing from that list. That missing number is the weight.
Work it for a single Nim heap and watch what falls out.
- A heap of 1 can move only to the empty heap (weight 0). The list is {0}. The smallest number missing is 1. Weight of a 1-heap: 1.
- A heap of 2 can move to a 1-heap (weight 1) or the empty heap (weight 0). The list is {0, 1}. Smallest missing: 2.
- A heap of 3 reaches weights {0, 1, 2}. Smallest missing: 3.
You see the pattern and you may as well prove it to yourself: a single Nim heap of n stones has weight n. The weight of a lone heap is just its size. This is the least surprising fact in the book, and I make you do it by hand only so that when the machine below hands you the same rule for a wildly different game, you will believe it.
Lesson 2. Two heaps, and the arithmetic that isn’t yours.
Here is where the schoolroom fails you. Put two heaps on the table — a heap weighing 4 and a heap weighing 6 — and ask: what is the weight of both together?
Your instinct says ten. Your instinct is wrong, and not by a little. The weight of the pair is not the sum. It is the sum with every carry thrown away. Write the two weights in binary, one over the other, and add each column on its own, refusing — always refusing — to carry anything left into the next column:
4 = 1 0 0
6 = 1 1 0
─────────────
carry ↑ (both 1: cancels)
answer = 0 1 0 = 2
Four and six make two. The leftmost column had a one in both rows; ordinary addition would carry that pair leftward as an eight. Here it simply cancels — one and one make zero and nothing moves on — and the eight never appears. This column-by-column, carry-nothing addition has a name, nim-addition, and a symbol, ⊕, and it is the true arithmetic of the table. The pair of heaps, one weighing 4 and one weighing 6, is worth exactly 2: it will behave, in every way that decides the game, like a single Nim heap of two stones. Not approximately. Exactly.
Exercise. Convince yourself the eight is really gone by playing. From heaps of 4 and 6, whatever your opponent does to make the total nim-weight non-zero, you can answer to drag it back to zero — and 4⊕6=2 tells you a zero is reachable, so you, moving second here, hold the whip. Ten would have told you nothing. Two tells you who wins.
Lesson 3. Why the carries have to vanish.
A student always asks: yes, but why throw the carries away? It looks like vandalism.
It is not vandalism; it is the opponent. Think about what a carry is — a debt one column owes to the column on its left, a little collaboration between the digits, a “we two together amount to something bigger over there.” Now remember who is sitting across the table. Anything you gain by making two heaps cooperate, your opponent can undo by answering in the other heap; they are a mirror, and a mirror strips back every coupling you attempt. What survives their mirroring is only the part that had no partner to cancel it — the lonely, un-carried bit. So the arithmetic of a game with a perfect adversary in it cannot keep carries. It keeps exactly the remainder that no answer can erase. Ordinary addition is what columns do when they help each other; nim-addition is what is left when every act of help can be undone. XOR is arithmetic under an enemy.
Lesson 4. The turn the whole book was built for.
You have weighed a lone heap (Lesson 1) and learned to combine two (Lesson 2). Now the theorem — Sprague’s, and Grundy’s four years after him, each without knowing of the other, which is its own small proof that the fact was there to be found:
Every impartial game, however baroque, is worth a single whole number, computed by the mex; and a sum of such games is worth the nim-sum (⊕) of their numbers; and the player to move has already lost exactly when that nim-sum is zero.
Every game. Not just heaps you take stones from. To feel the reach, trade Nim for a game that looks nothing like it — Kayles, a row of bowling pins. A move knocks down one pin, or two adjacent pins, and if you knock a gap in the middle of a row you have split it into two independent rows that now sit on the table as their own heaps. The weights here are not the sizes; they jump around — 0, 1, 2, 3, 1, 4, 3, 2, 1, 4, 2, 6 for rows of 0 through 11 pins — and then, gorgeously, they repeat with a period of twelve forever after. You would never guess them. You compute them, each by the very same mex, each row’s move-list built (because of the splitting) out of the ⊕ of its two pieces — so Kayles is already nim-addition, hiding inside a game about pins.
And then you never think about the tangle again. Three rows of pins, or thirty, make a knot whose full game-tree is beyond drawing — the positions multiply, every row’s every future crossing every other’s. Weigh each row alone. Nim-add the weights. Read the answer. If it is zero, the player about to move is doomed, and no cleverness in the knot will save them; if it is anything else, they can win, and the arithmetic even tells them the move. A game the size of the sky, decided by a sum you can do on your fingers — provided you have learned, at last, to add the way the table adds, and to let the carries go.
The examples above are not illustrations; they are the output of a machine that reproduces the published Kayles weights exactly, and that has checked the theorem on 16,105 compound positions of pins by grinding out the full game-tree the long way and finding it agree, every time, with the nim-sum done the short way. Eight heaps or two, the book holds. — I.
