Given a pile of 2000 stones, two players take turns in taking stones from the pile. Each player must remove 1, 2, 3, 4, or 5 stones from the pile at each turn, but may not take the same number as his opponent took on his last move. The player who takes the last stone wins. Does the first or second player have a winning strategy?
Solution
The first player has a winning strategy. He takes 4 on his first move leaving 7 mod 13 (2000 = 153.13 + 7 + 4). Now we claim that the first player can always leave: (1) 0 mod 13, (2) 3 mod 13 by taking away 3, (3) 5 mod 13 by taking away 5, or (4) 7 mod 13, and that the second player can never leave 0 mod 13.
Let us look at each of these in turn. If the first player leaves 0 mod 13, then the second player can take 3 and leave 10. In that case the first player takes 5 (a type (3) move). If the second player takes 1, 2, 4 or 5, leaving 12, 11, 9 or 8 mod 13, then the first player takes 5, 4, 2, 1 (respectively) and leaves 7 mod 13 (a type (4) move).
If the first player leaves 3 mod 13 by taking away 3, then the second player cannot leave 0 mod 13, because he cannot take 3 stones. If he takes 1, 2 leaving 2, 1 mod 13 respectively, then the first player takes 2, 1 leaving 0 mod 13 (a type (1) move). If the second player takes 4, 5 leaving 12, 11 mod 13, then the first player takes 5, 4 leaving 7 mod 13 (a type (4) move).
If the first player leaves 5 mod 13 by taking 5, then the second player cannot leave 0 mod 13, because he cannot take 5 stones. If he takes 1, 2, 3, 4 stones, leaving 4, 3, 2, 1 mod 13, then the first player takes 4, 3, 2, 1 stones leaving 0 mod 13 (a type (1) move).
Finally, if the first player leaves 7 mod 13, and the second player takes 1 stone, then the first player takes 3 stones leaving 3 mod 13 (a type (2) move). If the second player takes 2, 3, 4, or 5 stones leaving 5, 4, 3, 2 mod 13, then the first player takes 5, 4, 3, 2 stones leaving 0 mod 13 (a type (1) move).
So the second player can never leave 0 mod 13 and hence, in particular, can never take the last stone. But we have shown that the first player can always make a move of one of the four types, so can always move and hence must win (since after less than 2000 moves there will be no stones left).
© John Scholes
jscholes@kalva.demon.co.uk
9 Sep 2002