Maths Olympiad Prep

Library / /13 of 15

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Argentina

Given several coins arranged in a row, a legal move is to take either the first or the last coin. In the initial arrangement there are nn coins of arbitrary denominations. Ana and Maria make moves in succession. Ana starts by making 2 moves, then Maria makes 1 move, and the same repeats until all coins are taken away: 2 moves of Ana are followed by 1 move of Maria. (Only the last Ana's move can be taking 1 coin if there is a single coin left.) Ana's objective is to ensure at least 23\frac{2}{3} of the total sum of the coins for herself. Determine if she can do this with certainty if a) n=2013n=2013; b) n=2014n=2014.

Solution

The answer is yes for n=2013n=2013 and no for n=2014n=2014. More generally Ana can complete her task if n=0(mod3)n=0 \pmod{3} (n3n \ge 3), and Maria can prevent her from doing so if n1(mod3)n \equiv 1 \pmod{3} (n4n \ge 4).
Let nn be a multiple of 3. Color the coins in 3 colors periodically: 1, 2, 3, 1, 2, 3, ..., 1, 2, 3. The coins of some color cc have total value at most 1/31/3 of the total sum. We claim that Ana can force Maria to take a coin colored cc on every move, which will imply that Ana can ensure at least 2/32/3 of the total amount for herself.
Indeed, let c=1c=1; then Ana takes the last coin 3 first, then the last coin 2 in the new sequence. Thus Maria must move at a sequence 1, 2, 3, ..., 2, 3, 1, so she has to take a coin 1. Moreover each of her two possible moves yields a sequence either starting or ending with 2, 3. Ana can take these consecutive coins 2, 3 on her next move, thus obtaining a sequence of the kind 1, 2, 3, ..., 2, 3, 1, again. By following the same strategy Ana can ensure that Maria takes away all coin 1, as needed. If c=2c=2 Ana takes the first coin 1 and the last coin 3, obtaining 2, 3, 1, ..., 3, 1, 2. Now any move of Maria is 2 and leaves a sequence either starting or ending with 3, 1. Ana removes such two consecutive coins and obtains 2, 3, 1, ..., 3, 1, 2 again. So the pattern repeats: Ana makes sure that takes away all coins 1 and 3.
The case c=3c=3 is completely analogous. Here Ana takes the first two coins 1, 2, in succession, yielding a sequence 3, 1, 2, ..., 1, 2, 3. Maria is forced to take a coin 3, after which Ana can restore the pattern 3, 1, 2, ..., 1, 2, 3 by taking two consecutive 1, 2 from an extreme.
Let n=1(mod3)n=1 \pmod{3}. Color the coins periodically
1,2,3,1,2,3,,1,2,3,1.(1) 1, 2, 3, 1, 2, 3, \dots, 1, 2, 3, 1. \qquad (1)
Suppose that all coins 1 are 5 cents and all remaining ones are 1 peso. Then Maria can force Ana to take all coins 1, so that Ana will have less than 2/32/3 of the total amount (this is easy to check). If Ana takes two consecutive coins from one extreme of (1), Maria takes the third coin from the same extreme; it is a 2 or a 3. The same pattern (1) occurs. If Ana takes the two extremal 1's in (1), Maria takes the first coin 2 in the resulting sequence. This gives
3,1,2,3,,1,2,3.(2) 3, 1, 2, 3, \dots, 1, 2, 3. \qquad (2)
There are three cases depending on Ana's next move. (a) If Ana takes two coins from the left extreme of (2), Maria takes the coin 2 following them and (2) occurs again. (b) If Ana takes two coins 2, 3 from the right extreme of (2), Maria takes the first coin 3 and (1) occurs again. (c) If Ana takes one coin of each extreme of (2). The resulting sequence ends in a 2. Maria takes this 2 and obtains (1).
Thus Maria ensures that one of the patterns (1) or (2) occurs after each combined move of the two. Eventually the sequence will become 1, 2, 3, 1 or 3, 1, 2, 3. In both cases Maria can make sure that Ana gets the remaining coin(s) 1.

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.