Subtraction Game

 

Start with a number; letís say 17. Two players take turns to do subtractions. Each turn a player can subtract 1, 2 or 3 from the number; the result is then handed to the other player for the next turn; and so on. The player who reaches zero wins. (That is, the player who has no move loses.)

 

Observe that these numbers are important: 0, 4, 8, 12, 16... If we start with a larger number, the sequence will continue correspondingly. We call these the key positions of the game.

 

0 is important because whoever reaches 0 wins.

 

4 is important because if you reach 4, no matter how your opponent moves, you can reach 0 in your next move. This means whoever reaches 4 will win (eventually).

 

8 is important for similar reason. If you reach 8, no matter how your opponent moves, you can reach 4 in your next move. So whoever reaches 8 will also win eventually.

 

These numbers are multiples of 4 (3+1). n is a key position if and only if

††††††††††††††† n mod 4 = 0

 

Now, suppose we start with two numbers; letís say 9 and 14. Each turn a player can subtract 1, 2 or 3 from one of the numbers. The one who makes the last move wins.

 

What is the winning strategy ?

 

 

Home