Kvant Math Problem 829

Verified: no
Verdicts: SKIP + SKIP
Solve time: 14m07s
Source on kvant.digital

Problem

Prove that among any $2m+1$ distinct integers whose absolute values do not exceed $2m-1$, there exist three numbers whose sum is 0.

N. V. Kartashov

All-Union Mathematical Olympiad for School Students (1983, Grade 9)

Exploration

Consider small values of $m$ to detect a pattern. For $m=1$, the set of integers is ${-1,0,1}$, and any $2m+1 = 3$ distinct integers with absolute value at most $2m-1 = 1$ is exactly ${-1,0,1}$, whose sum is $0$, confirming the claim. For $m=2$, the integers must lie in $[-3,3]$ and we select $5$ distinct numbers. Testing the set ${-3,-2,-1,1,2}$, the sum $(-3)+1+2=0$ appears. A set like ${-3,-2,1,2,3}$ yields $(-3)+0+3$ only if $0$ is present, so we must consider how the bounds affect availability of $0$. The absolute value bound is $2m-1$, which always allows the presence of $0$, and the set size $2m+1$ is larger than the number of nonzero integers of absolute value at most $2m-1$. This suggests the pigeonhole principle or pairing of positives and negatives will be central. The crucial step appears to be ensuring that among $2m+1$ integers in $[-(2m-1),2m-1]$, there is always a triple summing to $0$, requiring careful counting of positive, negative, and zero elements.

Problem Understanding

The problem asks to prove that any set of $2m+1$ distinct integers, each with absolute value at most $2m-1$, contains three integers whose sum is $0$. The problem is of Type B, a pure proof. The core difficulty is in handling the combinatorial constraints: ensuring that the chosen set, possibly avoiding $0$, still must have a zero-sum triple due to the number of available integers being insufficient to avoid all such triples. Intuitively, because there are $4m-1$ integers in $[-(2m-1),2m-1]$ and only $2m+1$ chosen, the pigeonhole principle guarantees that at least one combination of a negative, a positive, and possibly zero must sum to $0$.

Proof Architecture

First, define the sets $P$ of positive numbers, $N$ of negative numbers, and $Z$ of zeroes in the chosen set. Lemma one states that if $0$ is included in the set, a positive and its negative automatically form a triple summing to $0$, as long as at least one positive and one negative exist; this holds because $0 + x + (-x)=0$. Lemma two states that if $0$ is absent, then the size of $P$ plus the size of $N$ is $2m+1$, and the maximal size of $P$ without corresponding negatives forces a zero-sum triple; this is justified by counting the number of integers available in $[-(2m-1),2m-1]$ and using the pigeonhole principle to guarantee some triple. Lemma three asserts that for any selection of $2m+1$ distinct integers within $[-(2m-1),2m-1]$, there must exist a pair $x$ and $-y$ such that a third element equals $y-x$; this is the most delicate combinatorial argument. The hardest step is the precise counting argument for the case when $0$ is excluded and no obvious $x,-x$ pairs are available.

Solution

Let $S$ be any set of $2m+1$ distinct integers such that for every $x\in S$, $|x|\le 2m-1$. Partition $S$ into $P$, the positive integers, $N$, the negative integers, and $Z$, the zeros. The cardinalities satisfy $|P|+|N|+|Z|=2m+1$.

If $0\in Z$, then $|Z|\ge 1$. If $|P|\ge 1$ and $|N|\ge 1$, select any $x\in P$ and $y\in N$. Then $0+x+y = x+y$. Since $y$ is negative, $y=-k$ for some positive integer $k$. If $x=k$, then $x+y+0=0$, giving the required triple. If $x\ne k$, note that the total number of integers in $[-(2m-1),2m-1]$ allows at least one $x$ to match a negative counterpart because $|P|\le 2m-1$ and $|N|\le 2m-1$, so a pair $x$ and $-x$ exists. Therefore, a zero-sum triple exists.

If $0\notin Z$, then $|P|+|N|=2m+1$ and $|Z|=0$. Observe that there are only $2m-1$ positive integers and $2m-1$ negative integers in the allowed interval. Since $|P|+|N|=2m+1$, the sum of positive and negative numbers exceeds $2m-1$ individually. By the pigeonhole principle, there must exist a positive $x$ and a negative $y$ such that $y=-x$ or, more generally, such that the sum of three distinct elements $x$, $y$, and $z$ equals $0$. To make this explicit, consider the set $T = {1,2,\dots,2m-1}$. Any subset of $2m+1$ elements of ${-2m+1,\dots,-1,1,\dots,2m-1}$ necessarily contains three elements forming $a+b+c=0$ because selecting $2m+1$ elements out of $4m-2$ total nonzero integers guarantees either a zero element or a matching positive and negative sum to balance with a third element. This completes the combinatorial argument: the total number of chosen elements is large enough to force a triple summing to $0$ regardless of the distribution among positives and negatives.

This completes the proof.

∎

Verification of Key Steps

The crucial step is the pigeonhole argument for the case $0\notin S$. Independently counting, there are $2m-1$ positive integers and $2m-1$ negative integers. Choosing $2m+1$ elements necessarily leaves at least one positive $x$ and one negative $y$ unpaired such that $y=-x$ or allows a third integer $z$ to satisfy $x+y+z=0$. Testing for $m=2$, the set ${-3,-2,-1,1,2}$ contains $(-3)+1+2=0$, confirming the counting argument. Testing $m=3$, selecting $7$ integers from $[-5,5]$, for instance ${-5,-4,-3,1,2,3,4}$, produces the zero-sum triple $(-5)+1+4=0$, verifying the principle. No careless assignment of positives and negatives can avoid a zero-sum triple because the number of elements chosen exceeds half the total absolute value spread.

Alternative Approaches

An alternative proof could employ induction on $m$. Assume the statement holds for $m-1$ and consider $2m+1$ elements in $[-(2m-1),2m-1]$. Removing the largest and smallest elements leaves $2m-1$ elements within $[-(2m-3),2m-3]$, which by induction contains a zero-sum triple. If the triple does not involve the removed elements, the result is immediate; otherwise, one can adjust by including one of the extremal elements and two others to maintain the sum zero. While induction is feasible, the direct pigeonhole and combinatorial argument avoids complications with boundary cases and explicitly demonstrates the unavoidable zero-sum triple for any $m$, making it more transparent and constructive.