Maths Olympiad Prep

Library / /20 of 22

Combinatorics Difficulty 6.9 National Olympiad Prove it Italy

Problem:

Camilla has a box containing 2015 paperclips. She takes a positive number nn of them and puts them on Federica's desk, challenging her to the following game. Federica has two types of moves available: she can remove 3 paperclips from the pile on her desk (if the pile contains at least 3 paperclips), or she can remove half of the paperclips present (if the pile contains an even number of them). Federica wins if, by means of a sequence of moves of the types described above, she manages to remove all the paperclips from her desk.

a) For how many of the 2015 possible values of nn can Federica win?

b) The girls change the rules of the game and decide to award the win to Federica if she manages to leave a single paperclip on the desk. For how many of the 2015 values of nn can Federica win under the new rules?

Solution

Solution:

a. Federica wins if and only if nn is a multiple of 33.
If nn is a multiple of 33 Federica can win: it suffices for her to carry out the move by which she removes three paperclips from the desk exactly n/3n / 3 times.
On the other hand, if at some point the number of paperclips on Federica's desk is not a multiple of 33, all the moves available to Federica leave on the desk a number of paperclips that is again not a multiple of 33: if kk is even but not a multiple of 33, then k/2k / 2 cannot be a multiple of 33 either; on the other hand, in the same way, if kk is not a multiple of 33, then k3k-3 is not either. Consequently, if Federica begins the game with a number of paperclips that is not a multiple of 33, any sequence of moves will lead to a number of paperclips that is also not a multiple of 33; Federica therefore has no way to remove all the paperclips, since 00 is a multiple of 33.
In conclusion, Federica manages to win if nn is a multiple of 33 between 11 and 20152015: there are 671671 possible values for nn.

b. This time Federica manages to win if and only if nn is not a multiple of 33.
If nn is not a multiple of 33 we can write it as 3k+r3k + r, where rr is the remainder of the division by 33, and hence is 11 or 22. By applying the first move kk times, Federica obtains 11 (in which case she has won) or 22 (in which case she uses the second move and wins).
It remains to show that if nn is a multiple of 33, then Federica will never reach 11. It suffices to show that if Federica applies a move to a number that is a multiple of 33 she obtains a number that is a multiple of 33 (and hence in particular she cannot reach 11). This is true, because if a=3ka = 3k is a multiple of 33, then so are a3=3(k1)a-3 = 3(k-1) and a2=3k2\frac{a}{2} = 3 \frac{k}{2}.
So Federica manages to win for 2015671=13442015 - 671 = 1344 values of nn.

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 translated into English from it; metadata (topic, difficulty) added by this project.