Who Wins the Race to 20?

Smaller races

A race to 20 is long to think about. Shrink it.

Race to 3. The first player says 1 or 2. Either way, the second player adds what is needed and says 3. So the second player wins.

Race to 4. Now the first player says 1. The second must say 2 or 3, and from either, the first player can say 4. The first player wins.

Here is the table so far, with a few more.

Race to	3	4	5	6	7	8	9	10	11	12
Who wins	second	first	first	second	first	first	second	first	first	second
First says		1	2		1	2		1	2

Work backwards from 20

Here is the idea that cracks the whole game. Don’t start at 0: start at the end.

If you say 20, you have won. So 20 is a number you want to say. What about 19? If you say 19, the other player adds 1 and says 20. Bad for you. If you say 18, the other player adds 2 and says 20. Also bad. Now 17. If you say 17, the other player must say 18 or 19, and either way you can then say 20. So 17 is a number you want to say, as good as 20 itself.

Call a number a winning number if the player who says it can go on to win, whatever the other player does, and a losing number if not. Then there are two rules, and they are all you need:

• A number is winning if every number the other player can say next is losing.
• A number is losing if the other player can say a winning number next.

Each number’s fate depends only on the numbers just above it. So you can start at 20 and work down, one number at a time, all the way to 0.

Look at the finished grid. The numbers are in rows of 3, and the winning numbers, 2, 5, 8, 11, 14, 17 and 20, all fall in one column.

And 0? It is the total before anyone has moved, as if the second player had “said” it. It is a losing number: from 0, the first player can say 2, a winning number. That is why the first player wins.

Whatever you add, I add the rest of 3

Why are the winning numbers exactly 3 apart? Suppose you have just said 11. The other player adds 1 or 2: the total is now 12 or 13. Whatever they added, you add the rest of 3: if they added 1, you add 2; if they added 2, you add 1. The total is now 14, exactly 3 more than your last number.

They add	You add	Together
1	2	3
2	1	3

So once you have said a winning number, you can always say the number 3 above it, and the other player can never land on one: from a winning number, a step of 1 or 2 always lands in between. Counting back from 20 in threes gives 17, 14, 11, 8, 5, 2: the numbers that are 20 minus a multiple of 3. In Grade 6 words: a number is winning when 20 minus it is a multiple of 3.

This is also why the second player wins a race to 3, 6, 9 or 12. For a race to 12, the winning numbers are 12, 9, 6, 3 and 0, and 0 is where the game starts. The first player is already standing on the second player’s winning number, and anything the first player says, the second player answers by adding the rest of 3.

Positions, and working backwards

The totals in the race are its positions, and a winning number is what game theory calls a P-position: P for the previous player, the one who has just moved into it, who wins with best play. A losing number is an N-position: the next player to move can win from it. Working out every position from the end of the game back to its start is called backward induction, or working backwards.

It works for the race because of three things:

1. The game always ends. The total goes up every turn, so the race to 20 lasts at most 20 turns.
2. Nothing is left to chance, and both players can see everything.
3. Every position is either winning or losing. There are no draws.

Wherever those hold, the two rules settle every position, starting from the last ones.

Any race

What if you may add 1, 2 or 3? Then “the rest of 4” works: they add 1, you add 3; they add 2, you add 2; they add 3, you add 1. The winning numbers are 4 apart. With adds of 1 up to k, the winning numbers are (k + 1) apart, counting back from the target. So:

• if the target is a multiple of k + 1, the second player wins;
• otherwise the first player wins, by first saying what the target leaves over when divided by k + 1.

Whoever says 20 loses

Turn the race around: now whoever is forced to say 20 loses. (You still may not pass 20, so a player on 19 has to add 1.)

Add 1, 3 or 4

So far, the winning numbers have always been one even step apart. Here is a race where they aren’t. On your turn you may add 1, 3 or 4, but not 2, and you may not pass the target. Whoever says 30 wins.

The trick of “the rest of 5” doesn’t work here: if they add 3, the rest of 5 is 2, and you may not add 2. So is there any pattern at all? Work it out backwards and see.

Why must a pattern appear at all? Each number’s fate depends only on the 4 numbers above it, because nobody can add more than 4. So if 4 numbers in a row come out the same as 4 numbers in a row 7 places higher, then the next number down copies the one 7 places higher too, and the next, and so on for ever. Working backwards found the first repeat; after that, the pattern can’t change.

A game where you know who wins, but not how

Here is a stranger twist. A bar of chocolate has its top-left square poisoned. Two players take turns to eat: choose any square that is left, and eat it with every square below it and to its right. Whoever has to eat the poison loses. The game is called Chomp.

Chomp ends (the bar gets smaller every turn), has no luck and no draws. So working backwards settles it, and with 4 rows and 6 columns a computer can do that in a blink: there are only 210 shapes the bar can be eaten into, counting the whole bar and the empty one. But for a big bar there are far too many shapes to work through. And yet, for every rectangle bigger than one square, mathematicians know who wins: the first player. Here is the proof, and it is a famous one.

Suppose the first player starts by eating only the bottom-right square. Either that is a winning move, or it isn’t.

• If it is, the first player wins.
• If it isn’t, then the second player has a winning reply: some bite after which the first player can’t win, whatever they do. But every bite takes the bottom-right square too, if it is still there, so that reply would leave exactly the same shape if the first player had made it as the first move. Then the first player could have made it first, and won.

Either way, the first player has a winning first move. This is called a strategy-stealing argument: if the second player had a winning plan, the first player could steal it. But look at what it doesn’t say: it doesn’t tell you which move wins. For a few shapes the winning move is known. On a bar with 2 rows, eat the bottom-right square; on a square bar, eat the square diagonally below-right of the poison, leaving an L with two equal arms. For most rectangles, nobody knows a rule. On the 4 × 6 bar above there is exactly one winning first bite, and the computer found it by searching.

The race, Chomp and noughts and crosses are games in which the players take turns, both see everything, nothing is left to chance, and the game must end. In 1913 the German mathematician Ernst Zermelo published a paper about chess, and the idea now called Zermelo’s theorem is named after it: in such a game, if it cannot end in a draw, one of the two players has a way to win whatever the other does. With draws allowed, either one player can force a win, or both can force at least a draw. Finding out which is called solving the game.

Noughts and crosses is a draw if neither player slips. In 2007 Jonathan Schaeffer’s team at the University of Alberta in Canada showed with computers that checkers (draughts) is a draw too. And in 2009, Lim Yew Jin and Jürg Nievergelt published their proof that Nepal’s own Bagh-Chal is a draw when both sides play perfectly. Chess has not been solved: its positions are far too many to work through.

• How Do You Always Win at Nim? (Computing, Going Further 6–8) Many piles instead of one total, winning positions found with binary, and a program that plays them.
• Can Eight Rules Play Tic-Tac-Toe Without Ever Losing? (Computing, Going Further 6–8) Noughts and crosses, solved with a short list of rules.
• Who Wins Bagh-Chal When Nobody Makes a Mistake? (Computing, Going Further, Grades 9–12) Nepal’s own game, and the search that proved it a draw.
• Is This Game Fair? Games with dice, where luck is the point and the question is who wins in the long run.
• How Do You Cut a Cake Fairly for Three? Playing fair when the players want different things.
• Should You Cooperate or Cheat? (Grades 9–12) Games where both players move at once and neither knows the other’s choice.