Kvant Math Problem 861

Verified: no
Verdicts: SKIP + SKIP
Solve time: 58s
Source on kvant.digital

Problem

Prove that from any $n$ numbers one can select several of them (possibly just one) so that the sum of the selected numbers differs from the nearest integer by at most $\dfrac{1}{n+1}$.

S. Yu. Orevkov

Exploration

Consider small values of $n$ to understand the behavior of the sums modulo $1$. For $n=1$, the claim reduces to selecting a single number and noting that any number differs from the nearest integer by at most $1/2$, which is indeed less than $1/(1+1) = 1/2$. For $n=2$, one can test pairs such as $(0.3, 0.7)$, $(0.1, 0.6)$, or $(0.4, 0.9)$. By checking sums of individual numbers and their pairwise sum, one observes that there is always a subset whose sum is within $1/3$ of an integer. This hints that considering sums modulo $1$ and arranging them in increasing order around the unit interval may be fruitful.

A plausible strategy is to consider all partial sums of the numbers modulo $1$ and use the pigeonhole principle to find two sums that are sufficiently close. The critical insight is that the distance between consecutive points on the circle $\mathbb{R}/\mathbb{Z}$ must be at most $1/(n+1)$ if there are $n+1$ points, allowing us to select a subset corresponding to the difference of these sums. The delicate point is ensuring that the subset can be non-empty and that the argument works for arbitrary real numbers, not just rationals or bounded numbers.

Problem Understanding

We are asked to prove that for any set of $n$ real numbers, there exists a non-empty subset whose sum differs from an integer by at most $1/(n+1)$. This is a Type B problem since the claim is a universal existence statement with a specific bound. The core difficulty is controlling the proximity of a sum of a subset to the nearest integer uniformly for arbitrary real numbers. Intuitively, the statement relies on arranging partial sums modulo $1$ on the unit circle and invoking a spacing argument: if we have $n$ numbers, then $n+1$ sums (including zero) will force some two to be close, and their difference provides the required subset sum. The crucial step is translating this geometric observation into a rigorous combinatorial argument.

Proof Architecture

Lemma 1: Consider the partial sums $s_k = x_1 + x_2 + \dots + x_k$ modulo $1$ for $k=0,1,\dots,n$ with $s_0=0$. This is well-defined and yields $n+1$ points in $[0,1)$.

Lemma 2: Among $n+1$ points on the circle $[0,1)$, the distance between some two of them is at most $1/(n+1)$. This follows from the pigeonhole principle by dividing the circle into $n+1$ equal arcs.

Lemma 3: If two partial sums $s_i$ and $s_j$ satisfy $|s_j - s_i| \le 1/(n+1)$ modulo $1$, then the sum of the consecutive numbers from $x_{i+1}$ to $x_j$ has fractional part at most $1/(n+1)$. This is true because the sum of that subset equals the difference $s_j - s_i$.

The hardest direction is ensuring that the subset is non-empty and properly selected from the difference of partial sums; careless subtraction could yield an empty set.

Solution

Let $x_1, x_2, \dots, x_n$ be the give_