Maths Olympiad Prep

Library / /287 of 299

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Iran

Ali has 100100 cards with numbers 1,2,,1001, 2, \ldots, 100. Ali and Amin play a game together. In each step, Ali firstly chooses a card from the remaining cards and Amin decides to pick that card for himself or throw it away. In the case that he picks the card, he can't pick the next card chosen by Amin, and he has to throw it away. This procedure continues until when there is no remaining card for Ali. Amin wants to pick cards in a way that the sum of the numbers of his cards is maximized and Ali wants to choose cards in a way that the sum of the number of Amin's cards is minimized. Find the largest value of kk such that Amin can play in a way that guarantees the sum of the number of his cards will at least be equal to kk.

Solution

First, note that Ali can adopt the following strategy: He shows the cards in order until Amin picks a card. In the next step, Ali shows the largest card that has not been shown yet, and in the next step, he again starts with the smallest card that has not been shown yet and continues this process. If Amin chooses kk cards using this strategy, then the sum of numbers on these cards will be at most:
f(k):=(100k+1)+(100k+2)++(1002k+2) f(k) := (100 - k + 1) + (100 - k + 2) + \dots + (100 - 2k + 2)
We claim that for each kk we have f(k)f(34)f(k) \le f(34). Note that f(k)=(2003k+3)k2f(k) = \frac{(200-3k+3)k}{2} and since the minimum of this function of degree 22 occurs at k=f(33)3k = \frac{f(33)}{3}, it suffices to compare f(33),f(34)f(33), f(34), and f(33)f(33) is greater. Therefore, Ali can ensure that the sum of Amin's cards is at most f(33)f(33). On the other hand, Amin can ensure that the sum of his cards reaches f(33)f(33). Having done this, Amin never picks a card with a number less than or equal to 3535, and whenever possible, he picks cards with larger numbers. In this case, Amin can take 3333 cards such that their sum is at least f(33)f(33).

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.