Every game is secretly Nim

Chapter 5 gave every position a letter: W if the player whose turn it is can force a win, L if they cannot. Chapter 6 gave every Nim position a number: write the piles in binary, add the columns without carrying, and if that nim-sum is 0 you are standing on an L. Two different tools, and it looked as if the second one only worked for Nim.

Here is a puzzle that breaks the first tool. Put two games on the table at once. Game A is a pile of 6 stones where a move takes 1, 2, or 3. Game B is a pile of 4 stones where a move takes 1, 3, or 4. On your turn you move in one of the games, whichever you like, and if you cannot move anywhere, you lose. Each game on its own is a W for the player to move (6 mod 4 is not 0, and 4 is not an L position from Chapter 5's challenge). Put them together and the player to move loses. Change Game B to 5 stones, still a W on its own, and the player to move wins. W plus W is sometimes L and sometimes W, and the letters cannot tell you which.

You need something finer than a letter: a number. Finding it takes one new idea with a funny name.

Take any set of whole numbers and look for the smallest whole number that is not in it. For {0, 1, 2} the answer is 3. For {1, 2, 3} the answer is 0, because 0 is missing. For {0, 1, 3, 4} it is 2. This is the mex of the set (say: mex, rhymes with checks), short for minimum excluded value. Repeats do not matter and neither does the order: the mex of {3, 0, 0, 1} is 2. The mex of the empty set, the set with nothing in it, is 0: 0 is the first number you look for, and it is not there.

Try the calculator, then do the five problems without it.

Now give every position a number, called its Grundy value (say: GRUN-dee) and written G. The rule looks like the W and L rule from Chapter 5, with mex doing the work:

Try it on the 21 Game, takes of 1, 2, or 3. From 0 there are no moves, so G(0) = 0. From 1 the only move is to 0, so G(1) = mex{0} = 1. From 2 you can reach 1 and 0, whose values are 1 and 0: mex{1, 0} = 2. From 3: mex{2, 1, 0} = 3. From 4 you can reach 3, 2, and 1, whose values are 3, 2, and 1. The set is {1, 2, 3}, 0 is missing, so G(4) = 0. Keep going and the values run 0, 1, 2, 3, 0, 1, 2, 3, and so on forever. You have seen that pattern before: G(n) = n mod 4.

Look at where the zeros landed: 0, 4, 8, 12. Those are exactly the L positions from Chapter 5. That is not luck. G = 0 means L, and G > 0 means W, in every game, and two sentences say why. If G = 0, then 0 is missing from the set of values you can reach, so every move hands the other player a nonzero position. If G > 0, then 0 is not the mex, so 0 must be in the set: some move reaches a position worth 0, and you hand that one over. That is the W and L rule with 0 playing the part of L. A position with no moves is both L and 0, so the two labelings agree from the end of the game all the way back to the start.

So the Grundy values know everything the letters knew, and more: they tell a 1 from a 2 from a 3, and the next section is where that pays off. First, label a game yourself. Type each value or use the small buttons. "Check" marks the wrong cells without giving answers, and "Show me" walks through the mex reasoning one position at a time.

Back to the puzzle at the top. Playing two games side by side is called a sum of games, and the rules of a sum are exactly what you would guess. On your turn you make one legal move in exactly one of the games. You lose when it is your turn and neither game has a move left. Nim itself is a sum: each pile is a tiny game of its own, and a Nim pile of n stones has Grundy value n, because from n you can reach every smaller pile, and the mex of {0, 1, ..., n − 1} is n.

Here is the theorem this chapter is named for.

Games that fit that description are called impartial games (say: im-PAR-shul). The important word is impartial: both players have the same moves from every position. Every subtraction game is impartial, and so is Nim. Chess is not, because you may only move your own pieces.

Read the theorem again slowly, because it says something surprising. A position with Grundy value 2 combines with other games exactly the way a Nim pile of 2 stones would. That is the sense in which every game is secretly Nim. To play a sum of games, replace each game by a Nim pile of size G, then use Chapter 6's rule: move so that the nim-sum becomes 0.

Now the puzzle at the top makes sense. Game A, 6 stones with takes of 1, 2, 3, has G = 6 mod 4 = 2. Game B, 4 stones with takes of 1, 3, 4, has G = 2 as well (the Math corner works it out). Two piles of 2: 2 XOR 2 = 0, a loss for the player to move. Change B to 5 stones and its value becomes 3. Now 2 XOR 3 = 1, a win, and the winning move is to bring B's value down from 3 to 2 by taking 1 stone. The two games have different rules and you cannot copy a move from one into the other, but the numbers see straight through that.

Play it. Robo does this arithmetic silently unless you tick "Show the secret". The hint tells you which game to fix, what value to aim for, and which stones get you there.