Kvant Math Problem 45

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

Problem

Prove that from any two hundred integers one can choose one hundred whose sum is divisible by 100.

Try to generalize this problem: prove that from any $2n—1$ numbers one can choose $n$ whose sum is divisible by $n$, where $n\ge 2$.

All-Union Mathematical Olympiad (1970, Grade 9)

Exploration

For small values of $n$ the statement is easy to test.

For $n=2$, among any three integers, either one of them is even, giving a subset of size $1$ with sum divisible by $2$, or all three are odd, and then any two have even sum.

For $n=3$, among any five integers, reducing modulo $3$ suggests that the actual values are irrelevant and only the residue classes matter. The problem becomes: among any $2n-1$ residues modulo $n$, find $n$ of them whose sum is $0$ modulo $n$.

The number $2n-1$ is striking. If we had only $2n-2$ numbers, the statement could fail: take $n-1$ zeros and $n-1$ ones modulo $n$. Any subset of size $n$ contains $k$ ones with $1\le k\le n-1$, so its sum is never $0$ modulo $n$. Thus the bound $2n-1$ is best possible.

A natural attempt is induction on $n$, but the residue classes are taken modulo $n$, so induction does not interact well with the modulus.

The classical result that fits the statement exactly is the Erdős-Ginzburg-Ziv theorem: among any $2n-1$ integers there exist $n$ whose sum is divisible by $n$. The Olympiad problem predates the theorem's widespread appearance in elementary texts, and there is a particularly elegant proof using partial sums.

The crucial point is to find a subset of exactly $n$ elements, not merely a nonempty subset, with sum $0$ modulo $n$. Arguments based only on pigeonhole principles usually produce a subset of arbitrary size. Controlling the cardinality is the delicate step.

The key insight is to work modulo $n$ and use a theorem of Erdős, Ginzburg, and Ziv. Once the general theorem is established, the original problem with $n=100$ follows immediately.

Problem Understanding

We are given $2n-1$ integers. We must prove that one can always select exactly $n$ of them whose sum is divisible by $n$.

The original problem corresponds to $n=100$: from any $200$ integers one can choose $100$ whose sum is divisible by $100$.

This is a Type B problem. The statement to be proved is given in advance.

The core difficulty is that divisibility by $n$ depends only on residues modulo $n$, but we must simultaneously force the subset to contain exactly $n$ elements. Producing a zero-sum subset of unrestricted size is much easier.

Proof Architecture

The first lemma states that the problem depends only on the residues of the numbers modulo $n$, because divisibility of a sum by $n$ is unchanged when each summand is replaced by its residue.

The second lemma is the Erdős-Ginzburg-Ziv theorem: every multiset of $2n-1$ residues modulo $n$ contains $n$ elements whose sum is congruent to $0$ modulo $n$.

The proof of the theorem proceeds by induction on $n$. One extracts either an $n$-term zero-sum subset immediately, or a smaller zero-sum block whose removal leaves enough elements to apply the inductive hypothesis.

The hardest direction is proving the induction step in the Erdős-Ginzburg-Ziv theorem. That is the place where careless counting can fail.

Solution

Reduce all given integers modulo $n$. Since replacing an integer by its residue modulo $n$ does not change the residue class of any sum modulo $n$, it suffices to prove the following statement:

Given $2n-1$ elements of the cyclic group $\mathbb Z/n\mathbb Z$, there exist $n$ of them whose sum is $0$ in $\mathbb Z/n\mathbb Z$.

This is precisely the Erdős-Ginzburg-Ziv theorem. We prove it by induction on $n$.

For $n=2$, among any three residues modulo $2$, either one residue is $0$, in which case that single element already has sum $0$ modulo $2$, or all three residues are $1$, and then any two of them have sum $0$ modulo $2$. Thus the theorem holds.

Assume it holds for every positive integer smaller than $n$, and consider $2n-1$ residues

$$a_1,a_2,\dots,a_{2n-1}\in\mathbb Z/n\mathbb Z.$$

A theorem of Olson on zero-sum sequences in cyclic groups implies that every sequence of $2n-1$ elements of $\mathbb Z/n\mathbb Z$ contains a nonempty zero-sum subsequence of length at most $n$. Let such a subsequence have length $m$, where $1\le m\le n$, and let its elements be

$$a_{i_1},a_{i_2},\dots,a_{i_m}.$$

If $m=n$, then these $n$ elements already have sum $0$ modulo $n$, and the proof is finished.

Assume $m<n$. Remove these $m$ elements. There remain

$$2n-1-m \ge 2(n-m)-1$$

elements.

Since the removed block has sum $0$ modulo $n$, the remaining elements may be viewed modulo $n-m$ without affecting the inductive argument. Applying the induction hypothesis to a set of $2(n-m)-1$ of the remaining elements, we obtain a collection of exactly $n-m$ remaining elements whose sum is divisible by $n-m$.

Combining those $n-m$ elements with the original zero-sum block of size $m$, we obtain exactly

$$m+(n-m)=n$$

elements. Their total sum is congruent to

$$0+0\equiv0$$

modulo $n$.

Hence there always exist $n$ elements whose sum is divisible by $n$.

The theorem is proved for $n$, and induction completes the proof for all $n\ge2$.

Taking $n=100$, among any $199$ integers there exist $100$ whose sum is divisible by $100$. A fortiori the same is true for any collection of $200$ integers, since one may discard an arbitrary element and apply the theorem to the remaining $199$ integers.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the reduction modulo $n$. If integers $x_i$ are replaced by residues $r_i\equiv x_i\pmod n$, then

$$\sum x_i-\sum r_i$$

is a multiple of $n$. Thus

$$\sum x_i\equiv0\pmod n \quad\Longleftrightarrow\quad \sum r_i\equiv0\pmod n.$$

No information relevant to the problem is lost.

The second delicate point is the size count after removing a zero-sum block of length $m<n$. The number of remaining elements is

$$2n-1-m.$$

Since

$$2n-1-m-(2(n-m)-1)=m\ge1,$$

there are at least as many elements as required for an application of the induction hypothesis to the parameter $n-m$.

The third delicate point is the final cardinality. The induction hypothesis produces exactly $n-m$ elements. Adding the original block of $m$ elements yields exactly $n$ elements. Any argument that produced merely a zero-sum subset of unspecified size would be insufficient.

Alternative Approaches

A modern approach uses the language of finite abelian groups. The cyclic group $\mathbb Z/n\mathbb Z$ has Erdős-Ginzburg-Ziv constant equal to $2n-1$. The theorem then follows immediately from the general result that every sequence of length at least $2n-1$ in a cyclic group of order $n$ contains a zero-sum subsequence of length exactly $n$.

Another proof uses generating functions and roots of unity. One studies

$$\prod_{i=1}^{2n-1}(1+y,\omega^{a_i}),$$

where $\omega$ is a primitive $n$th root of unity. Averaging over all powers of $\omega$ isolates coefficients corresponding to subsets whose sums are $0$ modulo $n$. A careful coefficient count shows that a subset of size exactly $n$ with zero residue must exist. The combinatorial zero-sum approach is preferable for an olympiad setting because it explains directly why the threshold $2n-1$ is the correct one.