Ali has cards with numbers . 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 such that Amin can play in a way that guarantees the sum of the number of his cards will at least be equal to .
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 cards using this strategy, then the sum of numbers on these cards will be at most:
We claim that for each we have . Note that and since the minimum of this function of degree occurs at , it suffices to compare , and is greater. Therefore, Ali can ensure that the sum of Amin's cards is at most . On the other hand, Amin can ensure that the sum of his cards reaches . Having done this, Amin never picks a card with a number less than or equal to , and whenever possible, he picks cards with larger numbers. In this case, Amin can take cards such that their sum is at least .