Olympiad Maths Prep

Library / /4 of 6

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 k0k \ge 0 such that 151×2kα<151×2k1\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×2k1>α\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 x1x2xnx_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+(n2)×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.

Looking for a route rather than 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.