Problem

Source: Iran MO Third Round 2022 Mid-Terms P5

Tags: combinatorics, cards, Game Theory



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$.