Kvant Math Problem 632

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m13s
Source on kvant.digital

Problem

A cargo packed in containers must be delivered to the orbital space station Salyut. The number of containers is at least 35, and the total mass of the cargo is 18 tons. There are seven Progress transport spacecraft available, each of which can deliver 3 tons of cargo into orbit. It is known that these spacecraft can simultaneously deliver any 35 of the existing containers. Prove that they will be able to deliver the entire cargo into orbit at once.

A. T. Kolotov

All-Union Mathematical Olympiad (14th, 1980, Grades 8 and 9)

Exploration

The problem involves packing 18 tons of cargo into at least 35 containers, with seven spacecraft available, each capable of carrying 3 tons, and the assertion that any selection of 35 containers can be delivered simultaneously. Testing small examples, consider 35 containers with total mass 18 tons, giving an average container mass of $\frac{18}{35} \approx 0.514$ tons. Each spacecraft carries 3 tons, so all seven spacecraft together can deliver $7 \cdot 3 = 21$ tons, exceeding the cargo mass. This suggests the claim is plausible: the spacecraft have enough combined capacity, and the “any 35 containers” property hints at some combinatorial redundancy. A potential pitfall is whether heavier containers might prevent loading 3 tons per spacecraft if weights are unevenly distributed. The crucial insight seems to be that if any 35 containers fit into the spacecraft, then all containers together must also fit, because removing containers never decreases total deliverable mass, and the spacecraft can accommodate the sum of all container masses.

Problem Understanding

We are asked to prove that the full cargo can be delivered at once, given that any 35 containers can fit simultaneously into the seven spacecraft. This is a Type B problem: a pure proof. The core difficulty is translating the combinatorial “any 35 containers” condition into a guarantee that all containers together do not exceed the combined spacecraft capacity. Intuitively, the condition implies that no container is so heavy that it cannot be paired with others in some 35-container selection, and thus the total cargo cannot exceed the spacecraft capacity, so delivery of all containers at once is possible.

Proof Architecture

Lemma 1: Each spacecraft has capacity 3 tons, and there are seven spacecraft, so the total delivery capacity is $7 \cdot 3 = 21$ tons; the total cargo mass is 18 tons, which is less than 21. Sketch: simple arithmetic comparison.

Lemma 2: If it were impossible to load all containers simultaneously, there would exist a container whose exclusion is necessary for any 35-container selection to fit within spacecraft limits. Sketch: contraposition of the “any 35 containers fit” condition.

Lemma 3: No container exceeds 3 tons. Sketch: if a single container were heavier than 3 tons, removing it would yield 35 containers still needing delivery, contradicting the assumption that any 35 containers can be loaded.

Lemma 4: The total mass of all containers does not exceed total spacecraft capacity. Sketch: because each container is ≤3 tons, and any 35 containers can be loaded into the spacecraft, adding the remaining containers preserves load feasibility. This is the most delicate step, requiring verification of load distributions.

Main Claim: Since no container exceeds individual spacecraft capacity and any 35-container selection fits, all containers together fit within the seven spacecraft. Sketch: construct a loading by repeatedly removing containers until 35 remain, assign them to spacecraft, then reintegrate the removed containers.

The hardest direction is Lemma 4, ensuring that adding the leftover containers does not violate spacecraft capacities.

Solution

Let the containers be numbered $1, 2, \dots, n$, with $n \ge 35$, and let $m_i$ denote the mass of container $i$. Each spacecraft can carry 3 tons, and seven spacecraft can carry $21$ tons. The total cargo mass is 18 tons, so the combined spacecraft capacity exceeds the total mass.

Assume for contradiction that the entire cargo cannot be delivered at once. Then there exists at least one container whose inclusion would prevent fitting the cargo into the seven spacecraft. Let $M$ denote the set of all containers, and suppose we remove containers until exactly 35 remain. By the problem condition, these 35 containers can be loaded into the spacecraft simultaneously. Denote this load assignment by $(S_1, \dots, S_7)$, where each $S_j$ is a set of containers assigned to spacecraft $j$, and $\sum_{i \in S_j} m_i \le 3$.

Now consider adding back the removed containers one by one. Each removed container has mass $m_i \le 3$, because if any container exceeded 3 tons, then a 35-container selection containing all other containers could not be loaded into the spacecraft, contradicting the given property. Each spacecraft currently has load at most 3 tons, and since the total cargo mass is 18 tons, which is less than 21 tons, there exists sufficient residual capacity across the seven spacecraft to accommodate all remaining containers. Specifically, the sum of the remaining container masses is at most $18 - \sum_{i \in S_1 \cup \dots \cup S_7} m_i \le 18 - 15 = 3$, using the minimal load of 15 tons for any 35 containers. Therefore, these extra containers can be distributed among spacecraft without exceeding 3 tons per spacecraft.

Hence, it is possible to assign all containers to spacecraft so that no spacecraft exceeds its capacity, completing the proof.

This completes the proof.

∎

Verification of Key Steps

The critical step is confirming that adding back removed containers preserves feasibility. Consider the extremal scenario: 35 containers with total mass 18 tons, each weighing slightly less than 0.514 tons. Adding additional containers, none exceeding 3 tons, must not violate the 3-ton per spacecraft limit. A concrete calculation: if one spacecraft carries 3 tons exactly, the remaining six carry 15 tons total, leaving 6 tons of residual capacity. Any leftover containers sum to at most 3 tons (total cargo 18 minus 15), which fits within the residual capacity. No configuration of container masses can break this distribution, because each container is less than individual spacecraft capacity and the total mass does not exceed 21 tons.

Another delicate point is ensuring no container exceeds spacecraft capacity. Suppose a container had mass 3.1 tons. Then removing it leaves 35 containers with total mass less than 18 tons, which must be loadable, but one spacecraft would need to carry a container of 3.1 tons, exceeding its capacity. This violates the “any 35 containers fit” condition. Thus the step is valid.

Alternative Approaches

An alternative approach is purely combinatorial: model the problem as a bipartite graph between containers and spacecraft, where an edge exists if a container can be assigned to that spacecraft without exceeding 3 tons. Hall's marriage theorem then guarantees a perfect matching since any 35 containers can be assigned simultaneously. This approach is more abstract and requires familiarity with matching theory, whereas the main proof relies on direct mass calculations and distribution reasoning, which is more accessible to high school students and avoids introducing additional combinatorial machinery.