Kvant Math Problem 949

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m00s
Source on kvant.digital

Problem

Given 1985 weights with masses 1 g, 2 g, 3 g, $\ldots$, 1984 g, 1985 g. Is it possible to divide them into five groups so that both the number of weights and their total mass are the same in all five groups?

E. P. Eroshenkov

All-Russian Mathematical Olympiad for School Students (XI)

Exploration

Consider small cases first. For $n=5$ weights $1,2,3,4,5$, the total sum is $15$ and dividing into five groups requires each group to have sum $3$. The individual weights are too large to split evenly, indicating small sequences often fail. Extending to larger numbers, the total number of weights is $1985$, and the total sum is

$$1+2+\cdots+1985 = \frac{1985 \cdot 1986}{2} = 1970355.$$

Dividing into five groups requires each group to have $397$ weights since $1985/5=397$ and sum $1970355/5=394071$. This means each group must have $397$ weights summing to $394071$. The sum of consecutive numbers grows quadratically, suggesting that achieving identical sums for equal-sized subsets is highly constrained. Attempting to pair large and small weights symmetrically indicates some potential, but the arithmetic suggests that the total sum modulo 5 is relevant. Computing $1970355 \mod 5$ shows $1970355 \equiv 0 \pmod 5$, so the sum is divisible by 5. Thus, divisibility is not an immediate obstruction. The main difficulty is achieving equal sums with equal numbers of terms.

Exploring the parity of weights and sums suggests that distributing odd and even numbers uniformly may fail because the number of odd numbers is $\lceil 1985/2\rceil = 993$ and even numbers $992$. Dividing these into five equal groups of $397$ yields that some groups would have to contain unequal numbers of odd and even numbers, making their sums differ in parity. Therefore, parity may prevent equal sums. This indicates the problem likely has a negative answer.

Problem Understanding

The problem asks whether the set of weights $1,2,3,\ldots,1985$ can be partitioned into five groups with the same number of weights and identical sums. This is a Type A problem because it asks for all possible divisions, effectively determining whether such a division exists. The core difficulty lies in reconciling the requirement of equal cardinality of groups with equal total mass, given the asymmetric distribution of even and odd numbers. Preliminary investigation suggests that such a partition is impossible due to parity constraints: an odd number of odd weights cannot be evenly distributed among five groups.

Proof Architecture

The proof will proceed as follows. First, compute the total number of weights and the sum of all weights. Second, determine the number of weights and sum required per group. Third, examine the distribution of odd and even weights among five groups of equal size. Fourth, show that dividing $993$ odd weights into five groups of $397$ elements each is impossible because $993$ is not divisible by $5$. Fifth, conclude that equal sums cannot be achieved since each group would require a non-integer number of odd weights. The most delicate step is ensuring that the parity argument fully accounts for the impossibility, without ignoring potential redistributions of weights.

Solution

The total number of weights is $1985$, and the total mass is

$$1+2+\cdots+1985 = \frac{1985 \cdot 1986}{2} = 1970355.$$

If the weights are to be divided into five groups with equal numbers of weights and equal sums, each group must contain

$$\frac{1985}{5} = 397 \text{ weights}$$

and have total mass

$$\frac{1970355}{5} = 394071.$$

The set of weights consists of $993$ odd weights and $992$ even weights. If each group contains $397$ weights, denote by $o_i$ the number of odd weights in the $i$-th group and $e_i$ the number of even weights, so that $o_i + e_i = 397$ for each $i$. Then

$$\sum_{i=1}^{5} o_i = 993, \quad \sum_{i=1}^{5} e_i = 992.$$

However, if all $o_i$ were equal, then $o_i = 993/5 = 198.6$, which is not an integer. Therefore, it is impossible for all groups to contain the same number of odd weights. Since the sum of weights in each group depends on the distribution of odd and even numbers, any imbalance in the number of odd weights between groups implies that the total mass of the groups cannot all be equal. More precisely, because odd weights are odd integers and even weights are even integers, changing the number of odd weights in a group changes the total mass by at least $1$, making it impossible to achieve the required sum of $394071$ in all five groups. Consequently, no partition of the weights into five groups of equal size can also have equal total mass.

This completes the proof.

∎

Verification of Key Steps

The most delicate step is the parity argument. The number of odd weights is $993$. Dividing $993$ by $5$ gives $198.6$, a non-integer, confirming that the odd weights cannot be evenly distributed. If one attempts an alternative distribution, some groups would have $198$ odd weights and others $199$, leading to differences in the total mass of at least $1$, contradicting the requirement of equal sums. The calculation of the total sum $1970355$ and the per-group sum $394071$ is verified by direct multiplication and division. The argument does not rely on unproven assumptions about distribution; the impossibility follows strictly from integer constraints.

Alternative Approaches

An alternative approach would use modular arithmetic to analyze the sums modulo $5$. The sum of the weights modulo $5$ is $1970355 \equiv 0 \pmod 5$. Each group must therefore have sum congruent to $0 \pmod 5$. Examining the possible residues of individual weights modulo $5$ shows that the odd and even numbers cannot combine to produce five groups of equal sum, leading to the same impossibility conclusion. The parity method is preferable because it directly demonstrates the obstruction using integer counts, avoiding the need for residue bookkeeping and yielding a simpler, more transparent argument.