Maths Olympiad Prep

Library / IMO Team Selection Test /6 of 20

IMO Team Selection Test

Combinatorics Difficulty 8.3 Shortlist Prove it Bulgaria

Find the least positive real number α\alpha with the following property: if the weight of a finite number of pumpkins is 1 ton and the weight of every pumpkin is not more than α\alpha tons then the pumpkins can be distributed in 50 boxes (some of the boxes may remain empty) such that there are no more than α\alpha tons of pumpkins in every box.

Solution

We prove that the desired value of α\alpha is α=251\alpha = \frac{2}{51}.

Assume that some α<251\alpha < \frac{2}{51} satisfies the condition of the problem. Choose nonnegative integer k≥0k \ge 0 such that 151×2k≤α<151×2k−1\frac{1}{51 \times 2^k} \le \alpha < \frac{1}{51 \times 2^{k-1}}. Consider 51×2k51 \times 2^k pumpkins each having weight 151×2k\frac{1}{51 \times 2^k} tons. For any distribution of pumpkins in 50 boxes there exists a box with at least two pumpkins and therefore the weight of this box equals at least 151×2k−1>α\frac{1}{51 \times 2^{k-1}} > \alpha, a contradiction.

We show that α=251\alpha = \frac{2}{51} satisfies the condition of the problem. Let the number of pumpkins be mm. Take mm empty boxes and put a pumpkin in every one of them. If the two lightest boxes contain in common not more than 251\frac{2}{51} tons of pumpkins then gather all pumpkins of these two boxes into one of them and remove the empty box. When this operation terminates let the number of boxes be nn and they contain x1≤x2≤⋯≤xnx_1 \le x_2 \le \dots \le x_n tons of pumpkins. Thus x1+x2>251x_1 + x_2 > \frac{2}{51} and hence x2>151x_2 > \frac{1}{51}. Therefore
1=x1+x2+⋯+xn>251+(n−2)×151, 1 = x_1 + x_2 + \dots + x_n > \frac{2}{51} + (n-2) \times \frac{1}{51},
implying n<51n < 51. We have that all the pumpkins are distributed in no more than 50 boxes and there are no more than 251\frac{2}{51} tons of pumpkins in each box. This completes the proof.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.