Maths Olympiad Prep

Library / /14 of 20

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

Fifty counters are on a table. Two players alternate taking away 1, 2, 3, 4, or 5 of them. Whoever picks up the last counter is the loser. Who has a winning strategy, the first player or the second?

Solution

Solution:

Note that if you make a turn and there is 1 counter left, you have won since the other player must pick up that counter.

If you make a turn and there are 7 counters left, you can win: if your opponent picks up 1, 2, 3, 4, or 5 of them, you can respectively take 5,4,3,25, 4, 3, 2, or 11 of them to leave 11.

Likewise, if you play and there are 1313 counters left, you can in the same way play to leave 77 on your next turn.

Continuing in this way, we see that the first player can win by removing 11 counter, leaving 4949, and then playing on the succeeding turns to leave 43,37,31,25,19,13,743, 37, 31, 25, 19, 13, 7, and 11.

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.