Maths Olympiad Prep

Library / /5 of 5

Combinatorics Difficulty 9.2 IMO level Prove it Netherlands

Each pupil in the Netherlands is given a finite number of cards. On each card, there is a real number in the interval [0,1][0, 1]. (The numbers on different cards do not have to be different.) Find the smallest real number c>0c > 0 for which the following holds, independent of the numbers on the cards each person has been given.
Any pupil for who the sum of the numbers on their cards is at most 10001000, can distribute their cards over 100100 boxes such that the sum of the cards in each box is at most cc.

Solution

Suppose one of the pupils has been given 10011001 cards, each containing the number 10001001\frac{1000}{1001}. Since the sum of the cards is 10001000, this pupil should be able to distribute the cards among the 100100 boxes. Because of the pigeonhole principle, there is at least one box with 1111 cards. The sum of these 1111 cards is 1110001001=11(111001)=11111001=1119111 \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=11191c = 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 d1d2d100d_1 \le d_2 \le \dots \le d_{100} be the sums corresponding to the 100100 boxes in this distribution, ordered from low to high (with the last kk of them equal to the maximum). Since the sum of all cards is at most 10001000, we have that
99d1+d100d1+d2++d1001000. 99d_1 + d_{100} \le d_1 + d_2 + \dots + d_{100} \le 1000.
On the other hand, moving a positive card from the box (with sum) d100d_{100} to the box (with sum) d1d_1 cannot create a better distribution per assumption: i.e. the new distribution does not have a smaller maximum, or less than kk boxes equal to this maximum value. This means that the new value of d1d_1 is at least equal to d100d_{100}. If d10010d_{100} \le 10 we are immediately done, because 10<1119110 < 11 - \frac{1}{91}. So we may assume that d100>10d_{100} > 10. Since each card is at most 11, this implies that box d100d_{100} contains at least 1111 positive cards. This in turn implies that there is a card in this box with positive value at most d10011\frac{d_{100}}{11}. Therefore, if we move this card to box d1d_1, then it must hold that
d1+d10011“new value of box d1d100. d_1 + \frac{d_{100}}{11} \ge \text{``new value of box } d_1\text{''} \ge d_{100}.
We can rewrite this as 11d110d10011d_1 \ge 10d_{100}. Combining this with the first equation, we find
91d100=90d100+d10099d1+d1001000. 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 d100100091=100191191=11191d_{100} \le \frac{1000}{91} = \frac{1001}{91} - \frac{1}{91} = 11 - \frac{1}{91}. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.