IMO Team Selection Test 3

Suppose one of the pupils has been given $1001$ cards, each containing the number $\frac{1000}{1001}$. Since the sum of the cards is $1000$, this pupil should be able to distribute the cards among the $100$ boxes. Because of the pigeonhole principle, there is at least one box with $11$ cards. The sum of these $11$ cards is $11\cdot \frac{1000}{1001}=11(1-\frac{1}{1001})=11-\frac{11}{1001}=11-\frac{1}{91}$. We are now going to show that this is the smallest possible value, i.e. $c=11-\frac{1}{91}$.

For a random pupil, we first consider those distributions for which the maximum of the sums of the cards per box is as small as possible. From these distributions we then pick a distribution for which the number of boxes having their sum equal to this maximum, is as small as possible. Let $d_1\le d_2\le \cdots \le d_{100}$ be the sums corresponding to the $100$ boxes in this distribution, ordered from low to high (with the last $k$ of them equal to the maximum). Since the sum of all cards is at most $1000$, we have that $$99d_1+d_{100}\le d_1+d_2+\cdots +d_{100}\le 1000.$$ On the other hand, moving a positive card from the box (with sum) $d_{100}$ to the box (with sum) $d_1$ cannot create a better distribution per assumption: i.e. the new distribution does not have a smaller maximum, or less than $k$ boxes equal to this maximum value. This means that the new value of $d_1$ is at least equal to $d_{100}$. If $d_{100}\le 10$ we are immediately done, because $10<11-\frac{1}{91}$. So we may assume that $d_{100}>10$. Since each card is at most $1$, this implies that box $d_{100}$ contains at least $11$ positive cards. This in turn implies that there is a card in this box with positive value at most $\frac{d_{100}}{11}$. Therefore, if we move this card to box $d_1$, then it must hold that $$d_1+\frac{d_{100}}{11}\ge \text{“new value of box }{d}_1\text{”}\ge d_{100}.$$ We can rewrite this as $11d_1\ge 10d_{100}$. Combining this with the first equation, we find $$91d_{100}=90d_{100}+d_{100}\le 99d_1+d_{100}\le 1000.$$ So, for each pupil, the smallest maximum of the sums of the cards per box is $d_{100}\le \frac{1000}{91}=\frac{1001}{91}-\frac{1}{91}=11-\frac{1}{91}$. $\square$