Maths Olympiad Prep

Library / /87 of 196

Combinatorics Difficulty 5.0 AIME Prove it Soviet Union

Problem:

35 containers of total weight 18 must be taken to a space station. One flight can take any collection of containers weighing 3 or less. It is possible to take any subset of 34 containers in 7 flights. Show that it must be possible to take all 35 containers in 7 flights.

Solution

Solution:

Let the lightest container be SS weighing ss. The other containers can be taken in 7 flights. The smallest load on these flights must be (18s)/7\leq (18 - s) / 7, and so that flight has spare capacity of at least 3(18s)/7=(3+s)/73 - (18 - s) / 7 = (3 + s) / 7. Thus it can accommodate SS provided that (3+s)/7s(3 + s) / 7 \geq s, or s1/2s \leq 1 / 2.

At least one of the 7 flights takes 4\leq 4 containers. These weigh at most the weight of the 4 heaviest. Since the 31 lightest weigh at least 31s31s, the 4 heaviest weigh at most 1831s18 - 31s. Thus this flight has spare capacity of at least 3(1831s)=31s153 - (18 - 31s) = 31s - 15 and can accommodate SS provided that 31s15s31s - 15 \geq s, or s1/2s \geq 1 / 2.

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.