Maths Olympiad Prep

Library / /57 of 61

Combinatorics Difficulty 6.9 National Olympiad Prove it Ibero-American Mathematical Olympiad

Problem:

Given a pile of 2000 stones, two players take turns in taking stones from the pile. Each player must remove 1,2,3,41, 2, 3, 4, or 55 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

Solution:

The first player has a winning strategy. He takes 44 on his first move leaving 7 mod 137 \bmod 13 (2000=153×13+7+42000 = 153 \times 13 + 7 + 4). Now we claim that the first player can always leave: (1) 0 mod 130 \bmod 13, (2) 3 mod 133 \bmod 13 by taking away 33, (3) 5 mod 135 \bmod 13 by taking away 55, or (4) 7 mod 137 \bmod 13, and that the second player can never leave 0 mod 130 \bmod 13.

Let us look at each of these in turn. If the first player leaves 0 mod 130 \bmod 13, then the second player can take 33 and leave 1010. In that case the first player takes 55 (a type (3) move). If the second player takes 1,2,41, 2, 4 or 55, leaving 12,11,912, 11, 9 or 8 mod 138 \bmod 13, then the first player takes 5,4,2,15, 4, 2, 1 (respectively) and leaves 7 mod 137 \bmod 13 (a type (4) move).

If the first player leaves 3 mod 133 \bmod 13 by taking away 33, then the second player cannot leave 0 mod 130 \bmod 13, because he cannot take 33 stones. If he takes 1,21, 2 leaving 2,1 mod 132, 1 \bmod 13 respectively, then the first player takes 2,12, 1 leaving 0 mod 130 \bmod 13 (a type (1) move). If the second player takes 4,54, 5 leaving 12,11 mod 1312, 11 \bmod 13, then the first player takes 5,45, 4 leaving 7 mod 137 \bmod 13 (a type (4) move).

If the first player leaves 5 mod 135 \bmod 13 by taking 55, then the second player cannot leave 0 mod 130 \bmod 13, because he cannot take 55 stones. If he takes 1,2,3,41, 2, 3, 4 stones, leaving 4,3,2,1 mod 134, 3, 2, 1 \bmod 13, then the first player takes 4,3,2,14, 3, 2, 1 stones leaving 0 mod 130 \bmod 13 (a type (1) move).

Finally, if the first player leaves 7 mod 137 \bmod 13, and the second player takes 11 stone, then the first player takes 33 stones leaving 3 mod 133 \bmod 13 (a type (2) move). If the second player takes 2,3,42, 3, 4, or 55 stones leaving 5,4,3,2 mod 135, 4, 3, 2 \bmod 13, then the first player takes 5,4,3,25, 4, 3, 2 stones leaving 0 mod 130 \bmod 13 (a type (1) move).

So the second player can never leave 0 mod 130 \bmod 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 20002000 moves there will be no stones left).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.