Maths Olympiad Prep

Library / /24 of 31

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Italy

Problem:

Alberto, to celebrate Barbara's birthday, proposes to play the following game: given the set of numbers 0,1,,10240, 1, \ldots, 1024, Barbara removes 292^{9} numbers from this set. At the next turn, Alberto removes from the remaining 282^{8} numbers. It is again Barbara's turn, who removes 272^{7} from the remaining ones, and so on, until only 2 numbers aa and bb remain. At this point Alberto must pay Barbara ab|a-b| euros.

Determine the maximum amount of euros that Barbara is sure to be able to collect, regardless of the strategy adopted by Alberto.

Solution

Solution:

The maximum sum that Barbara is sure to collect is 32 euros.

At each move, Barbara can at least double the minimum distance between the remaining numbers. Indeed, on the first move she can remove all the odd numbers, and on the subsequent ones, regardless of Alberto's moves, she can remove the 22^{\circ}, the 44^{\circ}, the 66^{\circ}, ... of the remaining numbers according to increasing order. After her 5 moves, the minimum distance between the remaining numbers will be at least 25=322^{5} = 32.

On the other hand, Alberto can at each move at least halve the maximum distance between the remaining numbers. Indeed, after Barbara's first move there will remain 210+129=29+12^{10} + 1 - 2^{9} = 2^{9} + 1 numbers; among these, necessarily either among those less than 292^{9} or among those greater than 292^{9} there will not be more than 282^{8}. Alberto can therefore remove those remaining, arranging things so that only numbers remain in the interval [0,29][0, 2^{9}] or only numbers in the interval [29,210][2^{9}, 2^{10}].

Before Alberto's next move, 29+28+272^{9} + 2^{8} + 2^{7} numbers will already have been removed, and so there will remain 27+12^{7} + 1 numbers, contained in an interval of length 292^{9}. Consequently, either in the first half or in the second half of the remaining interval (excluding the central number), there will not remain more than 262^{6}, and so Alberto will be able to remove them all, leaving only numbers in an interval of length 282^{8}.

Continuing with this strategy up to his fifth and last move, Alberto will be able to arrange things so as to leave only two numbers in an interval of length 25=322^{5} = 32, and hence with distance not exceeding 32.

In conclusion, Barbara is sure to earn at least 32 euros, Alberto is sure not to have to pay out more than 32 euros, and therefore 32 euros is the maximum sum that Barbara is sure to be able to collect.

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.