Kvant Math Problem 768

Consider small values of $n$ first.

kvantmathematicsolympiad

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

Problem

The sum of $n$ numbers, each of which does not exceed 1 in absolute value, is equal to $s$. Prove that it is possible to select several of these numbers so that the sum of the selected numbers differs from $\dfrac s3$ by at most $\dfrac13$.

V. P. Grinberg

Exploration

Consider small values of $n$ first. For $n=1$, the number itself is $s$, and since $|s|\le 1$, the single number differs from $s/3$ by at most $|s - s/3| = 2|s|/3 \le 2/3 < 1/3$ only if $|s|\le 1/2$, which is always smaller than the allowed $1/3$ bound. For $n=2$, with numbers $x_1$ and $x_2$, their sum $s = x_1 + x_2$, each $|x_i|\le 1$. Selecting either number individually or their sum, one can test all possible sums: $x_1$, $x_2$, $x_1 + x_2$, and zero. Numerical experiments suggest that choosing an appropriate subset allows getting within $1/3$ of $s/3$. For larger $n$, the subset sums form a dense set in $[-n,n]$, since each number is bounded by 1 in absolute value. The crucial difficulty seems to be guaranteeing a subset sum within $1/3$ of $s/3$ regardless of $n$ and regardless of the specific arrangement of numbers with varying signs. The step most likely to hide an error is a careless claim that one can “always” pick numbers near $s/3$ without precisely tracking how negative numbers or clusters near $-1$ might interfere. A method involving partitioning the numbers or using a greedy accumulation of numbers seems promising, with careful attention to partial sums.

Problem Understanding

We are asked to prove that for $n$ real numbers $x_1,\dots,x_n$ with $|x_i|\le 1$ and sum $s$, there exists a subset of them whose sum differs from $s/3$ by at most $1/3$. This is a Type B problem, as the claim is universal and we are to prove it holds for all such sequences. The core difficulty is constructing a subset whose sum is guaranteed to fall in the interval $[s/3 - 1/3, s/3 + 1/3]$ despite potential cancellation from negative numbers. The intuitive idea is that because each number is bounded in absolute value, one can gradually accumulate numbers until reaching a partial sum close to $s/3$, and that the final step requires careful handling to ensure the error does not exceed $1/3$.

Proof Architecture

Lemma 1: For any finite set of numbers bounded in absolute value by 1, the set of subset sums is dense in the interval $[-n,n]$ in the sense that each interval of length 1 contains some subset sum. Sketch: iteratively add numbers greedily, moving the partial sum by at most 1 at each step, guaranteeing coverage.

Lemma 2: Given numbers $x_1,\dots,x_n$ with sum $s$, there exists a subset whose sum lies within $1$ of $s/3$. Sketch: consider subsets of the sequence built by adding elements one by one, the sequence of partial sums modulo 1 produces a difference of at most 1.

Lemma 3: Refining Lemma 2, one can select a subset whose sum is within $1/3$ of $s/3$. Sketch: partition numbers into three groups whose total sums are near $s/3$, then choose the group closest to $s/3$; the error is bounded by 1/3 due to the bounded size of each number.

The hardest direction is Lemma 3, since careless accounting may allow the error to exceed $1/3$ if the sums are not carefully grouped. The step most likely to fail is assuming that partial sums can be adjusted arbitrarily without exceeding the error bound.

Solution

Consider the sequence $x_1,\dots,x_n$ with $|x_i|\le 1$ and total sum $s$. Arrange the numbers arbitrarily in a sequence. Construct the partial sums $S_0 = 0$, $S_1 = x_1$, $S_2 = x_1+x_2$, $\dots$, $S_n = s$. Consider the intervals $I_k = [S_k - 1/3, S_k + 1/3]$ for $k = 0,1,\dots,n$. Each interval has length $2/3$. Since the final partial sum $S_n = s$, the interval $[s/3 - 1/3, s/3 + 1/3]$ lies within the overall range $[0,s]$ if $s\ge 0$ (or $[s,0]$ if $s<0$).

Observe that the difference between consecutive partial sums is $|S_{k} - S_{k-1}| = |x_k| \le 1$, which is strictly larger than the interval radius $1/3$. Therefore, by the discrete intermediate value principle, the intervals $I_k$ cover the entire path from 0 to $s$ in overlapping steps of size at most 1. Since the interval around $s/3$ has radius $1/3 < 1$, there exists $k$ such that $S_k$ lies in $[s/3 - 1/3, s/3 + 1/3]$. The subset consisting of the first $k$ numbers then satisfies the required property.

Explicitly, if $s \ge 0$, start with $S_0=0$ and add numbers one by one. If at some step $k$ the partial sum $S_k$ satisfies $S_k \le s/3 + 1/3$ and $S_k + x_{k+1} > s/3 + 1/3$, then either $S_k$ itself lies in $[s/3 - 1/3, s/3 + 1/3]$, or $S_{k+1}$ does, because $x_{k+1} \le 1$, and the distance from $s/3$ is less than $1/3$. If $s<0$, apply the same argument to $-x_1,\dots,-x_n$ to obtain a subset sum within $1/3$ of $-s/3$, and then negate back. This completes the proof.

∎

Verification of Key Steps

The delicate step is asserting that one of the partial sums lies within $1/3$ of $s/3$. Verify by considering consecutive partial sums $S_k$ and $S_{k+1}$: their difference is $|x_{k+1}|\le 1$, which is strictly greater than $1/3$. The interval $[s/3 - 1/3, s/3 + 1/3]$ has length $2/3$, so at least one of $S_k$ or $S_{k+1}$ lies in it, as the jump cannot skip over it entirely. Testing examples such as $x_1 = 1$, $x_2 = -1$, $x_3 = 1/2$ confirms that the argument holds even when numbers alternate in sign and partial sums oscillate.

The other delicate step is handling negative $s$. Replacing $x_i$ by $-x_i$ ensures the same argument applies, because absolute values are preserved and the sum becomes $-s$, allowing the same interval argument to work. Checking with $x_1 = -1$, $x_2 = -1/2$, $x_3 = 1$ yields a valid subset sum near $s/3$.

Alternative Approaches

An alternative approach uses a greedy partitioning into three groups with approximately equal sums, invoking the pigeonhole principle. By partitioning numbers such that no group sum exceeds $s/3 + 1/3$, at least one group must be within $1/3$ of $s/3$. This method emphasizes combinatorial grouping rather than partial sums. The primary approach is preferable because it produces a concrete subset via sequential accumulation, requires no global rearrangement, and provides an explicit construction applicable to any $n$ and arbitrary order of numbers.