Kvant Math Problem 59
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m49s
Source on kvant.digital
Problem
There are several weights with masses 1 g, 2 g, 3 g, ..., $n$ g. They must be divided into three groups of equal total weight. For which $n$ can this be done?
E. B. Dynkin, S. A. Molchanov, A. L. Rosenthal, A. K. Tolpygo
Mathematical Problems. 3rd ed. — Moscow: Nauka, 1971.
Exploration
Let
$$S=1+2+\cdots+n=\frac{n(n+1)}2.$$
If the weights can be split into three groups of equal total mass, then each group must have mass
$$\frac S3=\frac{n(n+1)}6.$$
Hence a necessary condition is
$$3\mid S,$$
that is,
$$3\mid \frac{n(n+1)}2.$$
Since $3$ is relatively prime to $2$, this means
$$3\mid n(n+1),$$
so
$$n\equiv 0 \text{ or }2 \pmod 3.$$
Because $S$ must also be an integer, no further divisibility condition is needed.
Testing small values:
$$n=2:\quad S=3,$$
each group would have mass $1$, impossible because the weights are $1,2$.
$$n=3:\quad S=6,$$
$3\nmid S$.
$$n=5:\quad S=15,$$
each group has mass $5$, and
$$5,\qquad 4+1,\qquad 3+2$$
works.
$$n=6:\quad S=21,$$
each group has mass $7$, and
$$6+1,\qquad 5+2,\qquad 4+3$$
works.
The congruence condition suggests that every $n\equiv0,2\pmod3$ except perhaps a few small cases should work. Checking further:
$$n=8:\quad S=36,$$
each group has mass $12$, and
$$8+4,\qquad 7+5,\qquad 6+3+2+1$$
works.
A recursive construction seems likely. If $n\equiv2\pmod3$, then removing the five largest weights
$$n,n-1,n-2,n-3,n-4$$
allows the decomposition
$$n+(n-4),\qquad (n-1)+(n-3),\qquad n-2,$$
all having sum $2n-4$. The remaining weights are $1,\dots,n-5$, and $n-5\equiv0\pmod3$.
If $n\equiv0\pmod3$, removing the six largest weights gives
$$n+(n-5),\qquad (n-1)+(n-4),\qquad (n-2)+(n-3),$$
all having sum $2n-5$. The remaining weights are $1,\dots,n-6$, and $n-6\equiv0\pmod3$.
The single step most likely to hide an error is verifying that after adding these top weights to an equal partition of the smaller set, the three group sums remain equal. That computation must be checked carefully.
Problem Understanding
We have weights of masses
$$1,2,3,\dots,n.$$
The task is to determine for which integers $n$ these weights can be partitioned into three groups whose total masses are equal.
This is a Type A problem, a classification problem.
The necessary condition comes from divisibility of
$$1+2+\cdots+n=\frac{n(n+1)}2.$$
It suggests that
$$n\equiv0 \text{ or }2\pmod3.$$
Small cases show that $n=2$ fails although it satisfies the congruence condition. The expected answer is that all values
$$n\equiv0 \text{ or }2\pmod3,$$
except $n=2$, work. The intuitive reason is that for large $n$ one can peel off the largest five or six weights in balanced triples and reduce the problem to a smaller value of the same type.
Proof Architecture
Lemma 1. If a partition into three equal-weight groups exists, then $3$ divides $\frac{n(n+1)}2$, hence $n\equiv0$ or $2\pmod3$.
Sketch. The total weight must be three times the weight of one group.
Lemma 2. The values $n=5$ and $n=6$ admit such partitions.
Sketch. Write explicit decompositions.
Lemma 3. If $n\equiv2\pmod3$ and $n\ge8$, then existence for $n-5$ implies existence for $n$.
Sketch. Distribute the weights $n,n-1,n-2,n-3,n-4$ among the three groups as balanced additions of equal weight.
Lemma 4. If $n\equiv0\pmod3$ and $n\ge9$, then existence for $n-6$ implies existence for $n$.
Sketch. Distribute the six largest weights in three pairs of equal sum.
The hardest direction is sufficiency. The lemma most likely to fail under scrutiny is Lemma 3 or Lemma 4, because one must verify that the added weights contribute exactly the same amount to each group.
Solution
Let
$$S_n=1+2+\cdots+n=\frac{n(n+1)}2.$$
Suppose the weights can be divided into three groups of equal total mass. If each group has mass $T$, then
$$3T=S_n.$$
Hence $3$ divides $S_n$. Since $3$ is relatively prime to $2$,
$$3\mid \frac{n(n+1)}2 \quad\Longleftrightarrow\quad 3\mid n(n+1).$$
Therefore
$$n\equiv0 \text{ or }2\pmod3.$$
This condition is necessary.
We now prove that it is sufficient, except for $n=2$.
For $n=2$, the total mass equals $3$, so each group would have mass $1$. Since there are only two weights, three groups of mass $1$ cannot be formed. Thus $n=2$ is impossible.
For $n=5$,
$$5=(5),\qquad 5=(4+1),\qquad 5=(3+2),$$
so a required partition exists.
For $n=6$,
$$7=(6+1),\qquad 7=(5+2),\qquad 7=(4+3),$$
so a required partition exists.
We now prove by induction that every integer $n\ge5$ satisfying
$$n\equiv0 \text{ or }2\pmod3$$
admits a partition.
Assume first that
$$n\equiv2\pmod3,\qquad n\ge8.$$
Then
$$n-5\equiv0\pmod3.$$
By the induction hypothesis, the weights
$$1,2,\dots,n-5$$
can be divided into three groups $A,B,C$ of equal mass $M$.
Add the remaining weights as follows:
$$n,\ n-4 \text{ to } A,$$
$$n-1,\ n-3 \text{ to } B,$$
$$n-2 \text{ to } C.$$
The added masses are
$$n+(n-4)=2n-4,$$
$$(n-1)+(n-3)=2n-4,$$
$$n-2.$$
Since the total of the five removed weights is
$$n+(n-1)+(n-2)+(n-3)+(n-4)=5n-10,$$
and
$$5n-10=3(2n-4)+(n-2),$$
the third group must also receive an additional mass $2n-4$. Indeed,
$$(n-2)+(1+2+\cdots+0)=n-2$$
is not enough by itself, so we reinterpret the construction correctly: place $n-2$ together with the entire third old group $C$, whose mass is $M$, while the first two groups receive additions $2n-4$. Equality of the final sums requires
$$M+2n-4=M+2n-4=M+(2n-4).$$
Thus the third added portion must also have mass $2n-4$, and this is achieved by assigning the five largest weights as
$$A:\ n+(n-4),$$
$$B:\ (n-1)+(n-3),$$
$$C:\ (n-2)+(n-5),$$
which uses six consecutive largest weights. This observation shows that the reduction by $5$ is inconvenient.
We therefore use the cleaner reduction by $6$ for all admissible $n$.
Assume
$$n\ge8,\qquad n\equiv0 \text{ or }2\pmod3.$$
Then
$$n-6\equiv0 \text{ or }2\pmod3.$$
By the induction hypothesis, the weights
$$1,2,\dots,n-6$$
can be divided into three groups $A,B,C$ of equal mass $M$.
Add the six largest weights according to
$$n,\ n-5 \text{ to } A,$$
$$n-1,\ n-4 \text{ to } B,$$
$$n-2,\ n-3 \text{ to } C.$$
Each added pair has mass
$$n+(n-5) =(n-1)+(n-4) =(n-2)+(n-3) =2n-5.$$
Consequently the new group masses are
$$M+(2n-5), \qquad M+(2n-5), \qquad M+(2n-5),$$
and are equal.
Thus existence for $n-6$ implies existence for $n$.
The base cases $n=5$ and $n=6$ have already been established. Repeated application of the reduction by $6$ yields existence for every
$$n\ge5$$
with
$$n\equiv0 \text{ or }2\pmod3.$$
Combining this with the necessary condition and the exceptional impossibility of $n=2$, we obtain the complete classification:
$$\boxed{\text{The partition is possible exactly for }n\equiv0\text{ or }2\pmod3,\ n\ne2.}$$
Verification of Key Steps
The first delicate step is the necessity condition. Since
$$S_n=\frac{n(n+1)}2,$$
a partition into three equal sums requires $3\mid S_n$. Because $3$ does not divide $2$,
$$3\mid \frac{n(n+1)}2 \Longleftrightarrow 3\mid n(n+1).$$
Among two consecutive integers, exactly one is divisible by $3$ when the residue class is $0$ or $2$ modulo $3$. The residue class $1$ modulo $3$ is excluded.
The second delicate step is the inductive extension. The six added weights are
$$n-5,n-4,n-3,n-2,n-1,n.$$
Pairing the smallest with the largest among them gives
$$(n-5)+n=2n-5,$$
$$(n-4)+(n-1)=2n-5,$$
$$(n-3)+(n-2)=2n-5.$$
Every group receives exactly one such pair, so every group gains the same amount.
A careless argument would try to remove only five weights. Then the added masses cannot be made equal by the simple pairing method, and the induction would not close correctly. The reduction by six avoids this difficulty completely.
Alternative Approaches
A different proof proceeds by constructing the partition directly. When $n\equiv0$ or $2\pmod3$, one repeatedly forms triples whose sums are equal. For example, the numbers can be arranged symmetrically so that consecutive blocks of six numbers contribute three equal pairs
$$(n,n-5),\quad (n-1,n-4),\quad (n-2,n-3).$$
Accumulating these pairs into three running groups yields equal totals.
The inductive approach is preferable because the necessary condition and the construction fit together naturally. After the base cases are established, every admissible value of $n$ is obtained by adding one balanced block of six new weights, and the equality of the group sums is verified by a single computation.