Each student of a class has finite number of cards. Each card has a number on it from the interval . Find the smallest possible constant , such that the following holds, independently from the distribution of the cards to the students:
Each student that has a total sum of numbers less than 1000, shares the cards into 100 boxes, such that the sum of the cards in each box is at most .
Solution
Amongst all possible arrangements into boxes, pick one, where the maximum value inside a box is as small as possible. If there are several arrangements, achieving this smallest maximum value, pick one where the number of boxes achieving this value is as small as possible.
Say that the boxes have total values equal to , respectively. Since the total sum is less or equal to 1000, we get
Since is the smallest, we have . Suppose, for sake of contradiction, that .
Since the total sum in the first box is bigger than 10, the first box contains at least 11 cards, and each card has a number from , therefore, there will be a card with value at most .
---
Remove that card from the first box and put it in the 100-th box. Then, the 100-th box should have sum bigger or equal to , otherwise, we would have a configuration with smaller maximal sum. However, after that movement, the 100-th would have total sum at most
contradiction.
We will prove that , with doesn't work. Indeed, take and let . Since , we have that . Now take cards each of value . Their sum is . Now, no matter how we place them in 100 boxes, as , there exist 11 cards in the same box. But , so the constant , doesn't work.