Maths Olympiad Prep

Library / /12 of 16

Combinatorics Difficulty 6.4 National Olympiad Find the answer Italy

Problem:

Agnese, Beatrice, Claudio and Dario play with 53 piles of coins. Given any two piles, these have a different number of coins. On each turn, a player chooses a pile and removes one coin from it. The player loses who, by removing a coin from a pile, makes this pile have a height equal to another one present on the table.

A pile may have 0 coins and two piles with 0 coins are considered equal. Agnese starts, then Beatrice, Claudio and Dario play in order, after which it is again Agnese's turn, and play always proceeds in this order.

If at the start of the game there are 2020 coins in total and if everyone plays optimally, who loses?

Pick one

Solution

Solution:

The answer is (C). Let us call a1,a2,,a53a_{1}, a_{2}, \ldots, a_{53} the piles ordered in increasing order of height.

We observe that the game ends. On each move the total number of coins decreases by 1, and if there are 51 coins in total then the game has already ended because there are at least two piles with 0 coins.

Certainly, if the game has not already been lost, aia_{i} will have fewer coins than aja_{j} if i<ji<j: if this were not so, since on each move the number of coins decreases by 1, there would be a moment in which the two piles have the same number of coins, but this implies that the game has ended, which is absurd.

Moreover, the only configuration in which every move leads the player to lose (let us call it the decisive configuration) is the one in which the heights of the piles are 0,1,2,,520,1,2, \ldots, 52, in some order. Indeed, if the difference in height between ai+1a_{i+1} and aia_{i} were at least 2 for some ii, then we could remove a coin from ai+1a_{i+1}; if a1a_{1} had more than 0 coins then we could remove a coin from it.

Therefore the pile aia_{i} at the end of the game will have i1i-1 coins for every i{1,2,,53}i \in\{1,2, \ldots, 53\}. The number NN of coins that will be removed to reach the decisive configuration is equal to the difference between the number of coins present initially and the number of coins in the final configuration, that is
N=2020(0+1++52)=202052532=642 N=2020-(0+1+\cdots+52)=2020-\frac{52 \cdot 53}{2}=642
Since we can write N=4160+2N=4 \cdot 160+2 and since there are 4 players, when the decisive configuration is reached it will be Claudio's turn, so Claudio loses.

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.