Ali has $100$ cards with numbers $1,2,\ldots,100$. Ali and Amin play a game together. In each step, first Ali 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 action repeats until when there is no remaining card for Ali. Amin wants to pick cards in a way that the sum of the number 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 most value of $k$ such that Amin can play in a way that is sure the sum of the number of his cards will be at least equal to $k$.
Problem
Source: Iran MO Third Round 2022 Mid-Terms P5
Tags: combinatorics, cards, Game Theory
Behanorm_rifghcky
18.08.2022 15:15
The largest value of $k$ is $1717$. On the one hand,Amin has a strategy to let the sum of numbers of his cards be at least $1717$: (1)If the number of the card Ali chose is less or equal than $33$,then Amin throws it away. (2)If the number of the card Ali chose is larger or equal than $34$,then Amin picks it if possible. By using this strategy,Amin can always pick $\left \lceil \frac{100-33}{2}\right \rceil=34$ cards among the cards numbered $34,35,36,...,100$,which sums to at least$~34+35+...+67=\frac{101\times 34}{2}=1717$. On the other hand,Ali has a strategy to let the sum of numbers of Amin's cards be at most $1717$: (1)First Ali chooses the card numbered $1$. (2)If Amin threw Ali's card away in the last round,then Ali chooses the smallest numbered card among the remaining. (3)If Amin picked Ali's card in the last round,then Ali chooses the largest numbered card among the remaining. Assume that Amin get $x$ cards at last.Then by using this strategy,Ali can always let the largest $x-1$ card with numbers $100,99,...,(102-x)$ be thrown away by Amin.Thus the sum fo Amin's cards is at most $(101-x)+(100-x)+...+(102-2x)=\frac{x(203-3x)}{2}$,which achieve its maximum when $x=34$ and the maximum value is exactly $1717$. So $\boxed{k_{\max}=1717}.$Done!