5
Part II · Games with turns

Thinking backwards

Twenty-one stones. Take one, two, or three. Whoever takes the last stone wins. Robo never makes a mistake, and there is still a way to beat it. The trick is to solve the game from the end.

Here are the rules. There is a pile of stones. You and Robo take turns. On your turn you take 1, 2, or 3 stones. Whoever takes the last stone wins. That is the whole game.

Play it a few times. Robo plays perfectly, so if you lose, that is expected. Pay attention to the number of stones you keep losing from. There is a pattern, and once you see it, Robo cannot beat you when you go first.

The 21 Game

Take 1, 2, or 3 on your turn. Last stone wins.
21 stones left
Stones Allowed takes Change the rules and watch the losing positions move.

Start at the end

Do not start by thinking about 21 stones. Start with the smallest pile you can imagine, and work upward.

  • 0 stones on your turn. The other player just took the last stone. You lost. Call 0 a losing position, and write L.
  • 1, 2, or 3 stones. Take them all and win. These are winning positions: W.
  • 4 stones. Whatever you take, you leave 3, 2, or 1, and those are all W for the other player. Every move hands them a win. So 4 is L.
  • 5, 6, or 7. Take 1, 2, or 3 to leave exactly 4. You hand the other player an L. So these are W.
  • 8. Every move leaves 5, 6, or 7, all W for them. So 8 is L.

You just discovered the rule that solves every game with turns:

The rule

A position is W if at least one move leads to an L.
A position is L if every move leads to a W.

Solve the end of the game first, then the positions one step before the end, then the ones before those. This is called backward induction (say: in-DUCK-shun).

Do it yourself. Click a number to mark it W or L (click again to change your mind). Mark all of them, then check. If you get stuck, "Show me" walks through the reasoning one number at a time.

Label the positions

W = the player whose turn it is can force a win. L = they cannot.
Allowed takes Up to
Click a number to label it.
Math corner

Remainders. The losing positions are 0, 4, 8, 12, 16, 20: the multiples of 4. To find your move from any number, divide by 4 and look at the remainder. 21 ÷ 4 = 5 remainder 1, so take 1. Mathematicians write the remainder like this:

21 mod 4 = 1

and say "21 mod 4". So the winning move is: take (n mod 4) stones. If n mod 4 = 0, there is no winning move. You are standing on an L, and all you can do is take something and hope.

Why 4? Because with takes of 1, 2, or 3, whatever the other player takes, you can take the amount that makes the two of you take exactly 4 together. Every round of the game removes 4 stones, and you control the last stone. If you are allowed to take up to k, the magic number becomes k + 1. Try "Allowed takes: 1, 2, 3, 4" above and see 5, 10, 15, 20 light up.

Flip the rule

Now play the version where whoever takes the last stone loses. Mathematicians call it the misère version (say: mee-ZAIR, French for "misery").

Before you play, predict: which numbers are L now? Work it out from the end again. Facing 0 stones now means the other player took the last stone and lost, so 0 is W for you. Facing 1 stone, you must take it, and lose: 1 is L. Keep going. Then switch the game board to "Last stone loses" and test your theory against Robo.

Check your prediction

The losing positions move by one: 1, 5, 9, 13, 17, 21. The winning move is to leave the other player on a number that is 1 more than a multiple of 4. In mod language: leave n with n mod 4 = 1.

Notice something uncomfortable: 21 is now a losing position for the player who moves first. In the misère game, you want to go second.

Try it on paper

1. Normal rules, takes of 1 to 3, and you face 30 stones. What do you take?

Answer

30 mod 4 = 2. Take 2, leaving 28, a multiple of 4.

2. Takes of 1 to 5, and there are 40 stones. Which positions are L? What do you take from 40?

Answer

The magic number is 5 + 1 = 6, so L positions are the multiples of 6: 0, 6, 12, 18, 24, 30, 36. 40 mod 6 = 4, so take 4 and leave 36.

3. Misère rules, takes of 1 to 3, 21 stones, and you go first. Can you force a win?

Answer

No. 21 mod 4 = 1, which is a losing position in the misère game. Whatever you take, Robo can return you to 17, 13, 9, 5, and finally 1. Offer to go second.

Challenge

Change the allowed takes to 1, 3, 4 (no 2). Use the labeling tool up to 30. The losing positions are not multiples of anything, but there is still a repeating pattern. What is the length of the repeat, and can you say the rule using mod?

Answer

The L positions are 0, 2, 7, 9, 14, 16, 21, 23, 28, 30. They repeat every 7. The rule: n is L exactly when n mod 7 is 0 or 2. Games like this are called subtraction games, and the losing positions of every subtraction game eventually repeat. Proving that is a good project for a rainy afternoon.

True story

In 1913 the mathematician Ernst Zermelo proved that every game like this one, with two players, turns, no dice, no secrets, and a definite end, has a definite answer: either the first player can force a win, or the second player can, or both can force a draw. Chess is one of those games. So there is a correct answer to "who wins at chess?" We just cannot compute it. The chess game tree has more positions than there are atoms in the universe. Tic-tac-toe (Chapter 7) is small enough that we know its answer: a draw.

Stars in this chapter

Earn them by doing the clever thing, not by clicking around.