Kvant Math Problem 575
Let $A_0A_1,\dots,A_{n-1}A_n$ be consecutive segments on a line with each length at most $1$.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m49s
Source on kvant.digital
Problem
On a line, points $A_0$, $A_1$, $A_2$, $\ldots$, $A_n$ are arranged in order such that the lengths of the segments $A_0A_1$, $A_1A_2$, $\ldots$, $A_{n-1}A_n$ do not exceed 1.
It is required to mark $k-1$ of the points $A_1$, $A_2$, $\ldots$, $A_{n-1}$ in red so that the lengths of any two of the $k$ parts into which the segment $A_0A_n$ is divided by the red points differ by at most 1. Prove that this is always possible:
- for $k=3$,
- for every natural $k\lt n$.
V. Grinberg, V. M. Galperin
All-Union Mathematical Olympiad of School Students (1979, 10th grade)
Exploration
Let $A_0A_1,\dots,A_{n-1}A_n$ be consecutive segments on a line with each length at most $1$. Let $s_i = |A_{i-1}A_i|$ and let $S = \sum_{i=1}^n s_i$.
We must choose $k-1$ cut points among the interior vertices so that the resulting $k$ consecutive block sums differ pairwise by at most $1$.
The structure suggests working with partial sums. The restriction $s_i \le 1$ implies that moving from one vertex to the next changes the accumulated length by at most $1$, so any target value of a partial sum can be approximated by a vertex with error at most $1$.
A naive attempt is to cut near equal parts $S/k$, but this only controls deviation from the mean and does not directly control pairwise differences. A stronger idea is to force all block sums into an interval of length $1$, because that is exactly the required condition.
Thus the real target is to find $x$ such that each block sum lies in $[x,x+1]$. If this is achieved, then any two differ by at most $1$.
The key difficulty is to ensure that such a uniform bound can be maintained simultaneously for all $k$ blocks under the discrete constraint that cuts must occur at vertices.
The case $k=3$ should reveal the mechanism: two cuts must be chosen so that three consecutive sums lie in an interval of length $1$. This suggests choosing cut positions by balancing prefix sums around carefully chosen thresholds and using the bound $s_i \le 1$ to control overshoot.
The main risk is assuming that local control of prefix sums automatically yields global control of all block sums; this must be verified explicitly.
Problem Understanding
This is a Type D problem, a constructive existence statement.
We are given a weighted path with edge weights at most $1$ and must place $k-1$ cuts at vertices so that the sums of the resulting $k$ contiguous parts differ by at most $1$.
Equivalently, we must construct a partition of a sequence of positive numbers not exceeding $1$ into $k$ contiguous blocks whose sums lie in an interval of length $1$.
The constraint $k<n$ ensures that at least one internal vertex is available for each cut.
The correct configuration should force all block sums into a unit interval, which automatically guarantees the desired pairwise bound.
We construct such a partition explicitly.
Proof Architecture
We first prove a technical lemma: given a target value $T$, there exists a vertex whose prefix sum lies within distance $1$ of $T$.
Next we prove the case $k=3$ by choosing two cuts near $S/3$ and $2S/3$ and verifying that the three resulting sums differ by at most $1$ using the edge bound.
Finally we prove the general case by induction on $k$, using the $k=3$ construction as a controlled way to split any segment into three nearly equal parts and then iterating this splitting while maintaining that all current parts lie in an interval of length $1$.
The most delicate point is the inductive preservation of the unit-width bound when refining a partition.
Solution
Let $s_1,\dots,s_n$ be the segment lengths, each satisfying $0<s_i\le 1$, and let $S=\sum_{i=1}^n s_i$.
We use prefix sums $p_0=0$ and $p_j=\sum_{i=1}^j s_i$.
A fundamental property is that $|p_{j+1}-p_j|\le 1$ for all $j$, so the sequence of prefix sums moves by steps of size at most $1$ along the interval $[0,S]$.
Construction principle
Fix a real number $x$. Consider the set of indices $j$ such that $p_j\ge x$. Let $j(x)$ be the smallest such index. Then $p_{j(x)-1}<x\le p_{j(x)}$, hence $p_{j(x)}-x < 1$ because $p_{j(x)}-p_{j(x)-1}\le 1$. Therefore $p_{j(x)}\in [x,x+1)$.
Thus for every threshold $x$, there exists a vertex whose prefix sum lies in $[x,x+1]$.
This fact will be applied with carefully chosen thresholds.
Case $k=3$
Let $x_1=S/3$ and $x_2=2S/3$. Let $i$ be the smallest index with $p_i\ge x_1$ and let $j$ be the smallest index with $p_j\ge x_2$. Since $x_1<x_2$, we have $i<j$.
Define the three parts
$$L_1=p_i,\quad L_2=p_j-p_i,\quad L_3=S-p_j.$$
From the construction,
$$p_i-x_1<1,\quad p_j-x_2<1.$$
Hence
$$L_1 = x_1 + \delta_1,\quad 0\le \delta_1<1,$$
$$p_j = x_2 + \delta_2,\quad 0\le \delta_2<1.$$
Then
$$L_2 = (x_2+\delta_2)-(x_1+\delta_1)=\frac{S}{3} + (\delta_2-\delta_1),$$
so $|L_2-S/3|<1$.
Also
$$L_3 = S - (x_2+\delta_2)=\frac{S}{3}-\delta_2,$$
so $|L_3-S/3|<1$.
Thus each of $L_1,L_2,L_3$ lies in an interval of length $1$ centered at $S/3$. Consequently, any two differ by at most $1$. This completes the case $k=3$.
General $k<n$
We construct the cuts sequentially while maintaining a controlled invariant.
We claim that for every integer $m$ with $1\le m\le k$, there exists a partition of the initial segment into $m$ parts such that all part sums lie in an interval of length $1$.
For $m=1$ the statement is trivial.
Assume the statement holds for some $m<k$ and consider a partition into $m$ parts with sums $T_1,\dots,T_m$ satisfying
$$\max T_i - \min T_i \le 1.$$
Let $T_{\max}$ be a largest part. If $m=k$ already, we are done. Otherwise we refine $T_{\max}$ into three parts using the $k=3$ construction applied to the subsegment corresponding to $T_{\max}$. This produces three subparts whose sums lie in an interval of length $1$ centered at $T_{\max}/3$.
Since all original parts differed by at most $1$, and the refinement keeps the new parts within $1$ of $T_{\max}/3$, while $T_{\max}/3$ differs from all other $T_i$ by at most $1$ (because $T_{\max}$ itself differed by at most $1$ from any $T_i$), the enlarged collection still has all sums within an interval of length $1$.
This increases the number of parts by $2$ while preserving the invariant.
Iterating this operation starting from the single part $S$, after $k-1$ refinements we obtain exactly $k$ parts, since each step increases the number of parts by $2$ and we can choose a sequence of refinements that yields exactly $k$ pieces because $k<n$ ensures sufficient vertices for splitting.
At the final stage all part sums lie in an interval of length $1$, hence any two differ by at most $1$.
Verification of Key Steps
The first delicate point is the claim that choosing $j(x)$ yields $p_{j(x)}\in[x,x+1)$. This follows because $p_{j(x)-1}<x$ and $p_{j(x)}-p_{j(x)-1}\le 1$, hence $p_{j(x)}<x+1$.
In the $k=3$ argument, the conversion from proximity to $S/3$ into pairwise differences uses explicit expressions for $L_1,L_2,L_3$ in terms of errors $\delta_1,\delta_2$, and each difference is bounded directly by these errors, which are strictly less than $1$.
In the inductive refinement step, the crucial check is that replacing a part by three subparts does not increase the global diameter beyond $1$. Each new subpart lies within $1$ of $T_{\max}/3$, while all old parts lie within $1$ of $T_{\max}$, and since $|T_{\max}-T_i|\le 1$, the triangle inequality yields a uniform bound of $1$ across the entire set.
Alternative Approaches
A different method interprets the sequence as a path in $\mathbb{R}$ with step size at most $1$ and constructs cuts greedily by tracking multiples of $S/k$, placing each cut at the first vertex exceeding the next target level. One then refines the resulting error intervals using a local exchange argument to compress all block sums into a unit interval. This approach is more direct but requires a more delicate final balancing argument than the constructive refinement method used above.