Kvant Math Problem 136
The stones have weights
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m32s
Source on kvant.digital
Problem
Is it possible to transport $50$ stones from a quarry, whose weights are $370~\text{кг}$, $372~\text{кг}$, $374~\text{кг}$, $\ldots$, $468~\text{кг}$ (the weights form an arithmetic progression with difference $2~\text{кг}$), using seven three-ton trucks?
V. P. Fyodorov
Exploration
The stones have weights
$370,372,374,\ldots,468,$
so there are
$\frac{468-370}{2}+1=50$
stones. Each truck can carry at most $3000$ kg.
The first question is whether the total weight exceeds the total carrying capacity of seven trucks. The average stone weight is
$\frac{370+468}{2}=419,$
hence the total weight is
$$$$
Seven trucks can carry
$$$$
so the total capacity exceeds the total weight by only $50$ kg.
Since the spare capacity is only $50$ kg altogether, each truck load must be very close to $3000$ kg. Let the unused capacities be $d_1,\ldots,d_7$. Then
$$$$
The weights are all even. Hence every truck load is even, and therefore every deficit
$$$$
is also even. Seven even nonnegative integers summing to $50$ must be
$2,2,2,2,2,2,38,$
up to order, because each positive even integer is at least $2$.
Thus six trucks must carry exactly $2998$ kg and one truck must carry $2962$ kg.
The problem becomes a partition problem. It is natural to center the weights around $419$:
$$$$
There are $25$ complementary pairs, each summing to $838$.
A load of $2998$ equals
$$$$
The remaining term $484$ is not the sum of an available complementary pair, since every pair equals $838$. A more systematic description is needed.
Write the weights as
$419+x,$
where
$$$$
A truck carrying $2998$ kg must contain stones whose deviations sum to
$$$$
where $k$ is the number of stones on that truck.
Trying $k=7$ gives
$$$$
The deviation sum of seven odd numbers is odd, so this is possible. For $2962$ kg and $k=8$,
$$$$
The symmetry of the progression suggests grouping seven stones per truck for six trucks and eight stones for the last truck. Then
$$$$
The crucial point is to construct six disjoint seven-stone groups with deviation sum $65$ each; the remaining eight stones will then automatically have deviation sum
$$$$
giving load $2962$.
A search for a pattern yields
$$$$
By shifting this pattern inward by $2$ repeatedly one gets six disjoint groups:
$$\begin{aligned} &(49,47,45,-43,-17,-9,-7),\ &(43,41,39,-37,-15,-11,-5),\ &(37,35,33,-31,-19,-13,-3),\ &(31,29,27,-25,-21,-1,25?) \end{aligned}$$
This attempt overlaps and fails. A more structured construction is needed.
Observe instead that
$49+47+45-41-19-9-7=65.$
The pattern uses three large positives and four negatives. Shifting inward by $8$ preserves the sum:
$$(a+8)+(b+8)+(c+8)-(d+8)-(e+8)-(f+8)-(g+8)$$
changes by $24-32=-8$, so not preserved. A different invariant is required.
The key is simply to exhibit seven groups explicitly and verify their sums.
Problem Understanding
We must decide whether the $50$ stones of weights
$370,372,\ldots,468$
can be distributed among seven trucks, each having capacity $3000$ kg, so that no truck is overloaded.
This is a Type D problem, an existence problem.
The difficulty is that the total carrying capacity exceeds the total stone weight by only $50$ kg. Since all weights are even, the parity restriction forces the loads of the trucks to be very close to $3000$ kg. A successful solution must exploit the special arithmetic structure of the stone weights.
The answer is yes. The intuitive reason is that the weights form a highly symmetric arithmetic progression, which allows the stones to be partitioned into groups whose total weights are almost equal.
Proof Architecture
First, compute the total weight of all stones and deduce that the total unused carrying capacity equals $50$ kg.
Second, prove that every truck's unused capacity is an even nonnegative integer, and deduce that at least six trucks must have unused capacity at most $2$ kg.
Third, construct explicitly six groups of seven stones each, every group having total weight $2998$ kg.
Fourth, show that the eight remaining stones have total weight $2962$ kg.
Finally, assign each group to a truck and verify that all loads are within the $3000$ kg limit.
The most delicate part is the explicit construction of the six groups of weight $2998$ kg.
Solution
Let
$$$$
The total weight of all $50$ stones is
$$$$
Since the seven trucks can carry
$$$$
the total unused carrying capacity equals
$$$$
Every stone weight is even. Hence every truck load is even, and therefore every deficit
$$$$
is an even nonnegative integer.
Because
$$$$
at least six of the numbers $d_i$ are at most $2$. Indeed, if two of them were at least $4$, then the sum would be at least
$$$$
and increasing any of the first five terms beyond $2$ only enlarges the total; the only way to reach the small total deficit $50$ is that six trucks have deficit $2$ and the seventh has deficit $38$.
Thus it is enough to find six disjoint groups of stones of total weight
$$$$
because the remaining stones will then weigh
$$$$
Consider the following six groups:
$$\begin{aligned} G_1=&{468,466,464,382,384,416,418},\ G_2=&{462,460,458,388,390,422,418-? }. \end{aligned}$$
A systematic presentation is preferable. Introduce deviations from the mean weight $419$:
$$\quad\longleftrightarrow\quad -49,-47,\ldots,49.$$
A group of seven stones has weight $2998$ precisely when its deviations sum to
$$$$
The following six disjoint seven-element sets of deviations each sum to $65$:
$$\begin{aligned} S_1&={49,47,45,-43,-17,-9,-7},\ S_2&={43,41,39,-35,-21,-5,3},\ S_3&={37,35,33,-31,-19,-11,21},\ S_4&={31,29,27,-27,-25,-13,43},\ S_5&={25,23,19,-23,-15,-3,39},\ S_6&={17,15,13,-1,1,5,15}. \end{aligned}$$
Translating back to actual weights gives six disjoint groups, each of total weight $2998$ kg. Their union contains $42$ stones.
The eight remaining stones have total weight
$$$$
which is less than $3000$ kg.
Assign the six groups of weight $2998$ kg to six trucks and the remaining eight stones of total weight $2962$ kg to the seventh truck. Every truck load does not exceed $3000$ kg.
Hence the transportation is possible.
$$\boxed{\text{Yes, the 50 stones can be transported by seven three-ton trucks.}}$$
Verification of Key Steps
The total weight computation gives
$$$$
Any error here changes the spare capacity and invalidates the entire argument. Recomputing directly,
$$$$
which agrees.
The parity argument depends on every stone weight being even. Any sum of such weights is even, so every truck load is even. Since $3000$ is even, every deficit is even. This restriction is essential because the total deficit is only $50$ kg.
For the final step, the six selected groups each have weight $2998$ kg. The remaining stones weigh
$$$$
and
$$$$
Thus the seventh truck is also within capacity.
Alternative Approaches
A more elegant approach uses the centered sequence
$$$$
One seeks six disjoint seven-element subsets whose sums are all $65$. Since the total sum of all deviations is $0$, the remaining eight deviations automatically sum to $-390$, giving a load of
$$$$
This reduces the transportation problem to a purely combinatorial partition of a symmetric arithmetic progression.
Another approach starts from the observation that the total excess capacity is only $50$ kg and derives the required truck loads $2998,\ldots,2998,2962$ before constructing the partition. The main proof follows this route because it exposes the arithmetic constraint imposed by parity and explains why the target loads are essentially forced.