Browse · MathNet
Print55th IMO Team Selection Test
Bulgaria counting and probability
Problem
Find the least positive real number 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 tons then the pumpkins can be distributed in 50 boxes (some of the boxes may remain empty) such that there are no more than tons of pumpkins in every box.
Solution
We prove that the desired value of is .
Assume that some satisfies the condition of the problem. Choose nonnegative integer such that . Consider pumpkins each having weight 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 , a contradiction.
We show that satisfies the condition of the problem. Let the number of pumpkins be . Take empty boxes and put a pumpkin in every one of them. If the two lightest boxes contain in common not more than 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 and they contain tons of pumpkins. Thus and hence . Therefore implying . We have that all the pumpkins are distributed in no more than 50 boxes and there are no more than tons of pumpkins in each box. This completes the proof.
Assume that some satisfies the condition of the problem. Choose nonnegative integer such that . Consider pumpkins each having weight 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 , a contradiction.
We show that satisfies the condition of the problem. Let the number of pumpkins be . Take empty boxes and put a pumpkin in every one of them. If the two lightest boxes contain in common not more than 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 and they contain tons of pumpkins. Thus and hence . Therefore implying . We have that all the pumpkins are distributed in no more than 50 boxes and there are no more than tons of pumpkins in each box. This completes the proof.
Final answer
2/51
Techniques
Pigeonhole principleGames / greedy algorithmsColoring schemes, extremal arguments