Maths Olympiad Prep

Library / /5 of 5

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Greece

Each student of a class has finite number of cards. Each card has a number on it from the interval [0,1][0,1]. Find the smallest possible constant c>0c > 0, 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 cc.

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 10+x110+x210+x10010 + x_1 \ge 10 + x_2 \ge \dots \ge 10 + x_{100}, respectively. Since the total sum is less or equal to 1000, we get
10+x1+10+x2++10+x1001000x1++x1000. 10 + x_1 + 10 + x_2 + \dots + 10 + x_{100} \le 1000 \Leftrightarrow x_1 + \dots + x_{100} \le 0.

Since x100x_{100} is the smallest, we have x1+99x100x1+x2++x1000x_1 + 99x_{100} \le x_1 + x_2 + \dots + x_{100} \le 0. Suppose, for sake of contradiction, that x1>9091x_1 > \frac{90}{91}.
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 [0,1][0,1], therefore, there will be a card with value at most 10+x11110 + \frac{x_1}{11}.

---

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 10+x110 + x_1, otherwise, we would have a configuration with smaller maximal sum. However, after that movement, the 100-th would have total sum at most
10+x100+10+x11110x199+10+x111=10+x1+9091x199<10+x1, 10 + x_{100} + \frac{10 + x_1}{11} \le 10 - \frac{x_1}{99} + \frac{10 + x_1}{11} = 10 + x_1 + \frac{90 - 91x_1}{99} < 10 + x_1,
contradiction.
We will prove that c=1111ac = 11 - 11a, with 1>a>110011 > a > \frac{1}{1001} doesn't work. Indeed, take r[11001,a)r \in [\frac{1}{1001}, a) and let n=10001rn = \lfloor \frac{1000}{1-r} \rfloor. Since r11001r \ge \frac{1}{1001}, we have that n1001n \ge 1001. Now take nn cards each of value 1r1-r. Their sum is n(1r)10001r(1r)=1000n(1-r) \le \frac{1000}{1-r}(1-r) = 1000. Now, no matter how we place them in 100 boxes, as n1001n \ge 1001, there exist 11 cards in the same box. But 11(1r)>1111a11(1-r) > 11 - 11a, so the constant c=1111ac = 11 - 11a, doesn't work.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.