Kvant Math Problem 825
Let the segments be
Verified: yes
Verdicts: PASS + PASS
Solve time: 17m20s
Source on kvant.digital
Problem
The set $M$ consists of $k$ pairwise disjoint segments lying on the same line. It is known that any segment of length not greater than 1 can be placed on the line so that its endpoints belong to the set $M$. Prove that the sum of the lengths of the segments comprising $M$ is at least $\dfrac1k$.
E. I. Khukhro
All-Union Mathematical Olympiad for School Students (1983, Grade 10)
Exploration
Let the segments be
$$I_1,\dots,I_k,$$
pairwise disjoint and lying on one line. Let
$$L=\sum_{i=1}^k |I_i|$$
be their total length.
The condition says that for every $t\in[0,1]$ there exists a placement of a segment of length $t$ whose endpoints both belong to $M$. Since all points lie on one line, this means that for every $t\in[0,1]$ there exist $x,y\in M$ with
$$|x-y|=t.$$
Hence the difference set
$$D={|x-y|:x,y\in M}$$
contains the whole interval $[0,1]$.
The problem becomes: if $M$ is a union of $k$ disjoint intervals of total length $L$, and $D\supset[0,1]$, prove $L\ge 1/k$.
For $k=1$, $M$ itself is one interval. Then $D=[0,L]$, so $L\ge1$, which matches $1/k$.
A natural idea is to estimate the length of $D$. If $M$ is a union of $k$ intervals, then for each pair $I_i,I_j$, the set
$$D_{ij}={|x-y|:x\in I_i,\ y\in I_j}$$
is an interval. Its length equals $|I_i|+|I_j|$. There are $k^2$ ordered pairs $(i,j)$. Thus $D$ is covered by $k^2$ intervals whose total length is
$$\sum_{i,j}(|I_i|+|I_j|) =2kL.$$
Since $D$ contains $[0,1]$, its measure is at least $1$. Hence $2kL\ge1$, giving only $L\ge1/(2k)$, which is not enough.
The factor $2$ is the obstacle. The reason is that distances are nonnegative. If instead we consider the signed difference set
$$S=M-M={x-y:x,y\in M},$$
then $S$ contains $[-1,1]$, because every $t\in[0,1]$ occurs and then so does $-t$. The set $S$ is covered by the intervals
$$I_i-I_j,$$
each having length $|I_i|+|I_j|$. The total length of this cover is again $2kL$. But now $S$ contains an interval of length $2$, namely $[-1,1]$. Therefore
$$2\le 2kL,$$
which yields exactly
$$L\ge \frac1k.$$
The step most likely to hide an error is the claim that every $I_i-I_j$ is an interval of length $|I_i|+|I_j|$. That must be checked carefully.
Problem Understanding
We are given a set $M$ consisting of $k$ pairwise disjoint segments on one line. Every segment of length at most $1$ can be positioned so that both of its endpoints lie in $M$. Equivalently, for every $t\in[0,1]$ there exist points $x,y\in M$ with $|x-y|=t$.
We must prove that the total length of all segments forming $M$ is at least $1/k$.
This is a Type B problem, a pure proof.
The core difficulty is to convert the geometric condition about realizing all distances from $0$ to $1$ into a quantitative lower bound on the total length of a union of $k$ intervals.
Proof Architecture
First, define the signed difference set $S=M-M={x-y:x,y\in M}$ and prove that $[-1,1]\subset S$.
Second, show that if $I=[a,b]$ and $J=[c,d]$, then
$$I-J=[a-d,; b-c],$$
hence $I-J$ is an interval of length $|I|+|J|$.
Third, write $M=\bigcup_{i=1}^k I_i$. Then
$$S=\bigcup_{i,j}(I_i-I_j),$$
so $S$ is covered by $k^2$ intervals whose total lengths sum to $2kL$.
Fourth, use the fact that $[-1,1]\subset S$, hence the length of $S$ is at least $2$. Since the measure of a union does not exceed the sum of the measures of a covering family,
$$2\le 2kL.$$
The hardest point is verifying precisely the structure and length of each difference interval $I_i-I_j$.
Solution
Let
$$M=I_1\cup I_2\cup\cdots\cup I_k,$$
where $I_1,\dots,I_k$ are pairwise disjoint segments. Denote
$$L=\sum_{i=1}^k |I_i|,$$
the total length of the segments.
Consider the signed difference set
$$S=M-M={x-y:x,y\in M}.$$
We first show that
$$[-1,1]\subset S.$$
Take any $t\in[0,1]$. By the hypothesis, a segment of length $t$ can be placed so that its endpoints belong to $M$. Hence there exist $x,y\in M$ with
$$|x-y|=t.$$
If $x-y=t$, then $t\in S$; if $x-y=-t$, then $-t\in S$. Interchanging $x$ and $y$ gives the opposite sign as well. Thus both $t$ and $-t$ belong to $S$. Since this holds for every $t\in[0,1]$,
$$[-1,1]\subset S.$$
Now let
$$I_i=[a_i,b_i],\qquad I_j=[a_j,b_j].$$
Then
$$I_i-I_j={x-y:x\in I_i,\ y\in I_j}.$$
The smallest possible value of $x-y$ is obtained from $x=a_i$, $y=b_j$, and equals $a_i-b_j$. The largest possible value is obtained from $x=b_i$, $y=a_j$, and equals $b_i-a_j$. Since $x-y$ varies continuously with $x$ and $y$,
$$I_i-I_j=[a_i-b_j,; b_i-a_j].$$
Therefore $I_i-I_j$ is an interval whose length is
$$(b_i-a_j)-(a_i-b_j) =(b_i-a_i)+(b_j-a_j) =|I_i|+|I_j|.$$
Because
$$M=\bigcup_{i=1}^k I_i,$$
we have
$$S=\bigcup_{i=1}^k\bigcup_{j=1}^k (I_i-I_j).$$
The measure of a union does not exceed the sum of the measures of the covering sets. Hence
$$|S| \le \sum_{i=1}^k\sum_{j=1}^k |I_i-I_j| = \sum_{i=1}^k\sum_{j=1}^k (|I_i|+|I_j|).$$
Computing the double sum,
$$\sum_{i,j}(|I_i|+|I_j|) = k\sum_i |I_i| + k\sum_j |I_j| = 2kL.$$
Thus
$$|S|\le 2kL.$$
On the other hand, $[-1,1]\subset S$, so
$$|S|\ge 2.$$
Combining the two inequalities,
$$2\le |S|\le 2kL.$$
Therefore
$$L\ge \frac1k.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is proving $[-1,1]\subset S$. The hypothesis gives only the existence of points $x,y\in M$ with $|x-y|=t$. If $x-y=t$, then $t\in S$. Reversing the order of the same pair gives $y-x=-t\in S$. Thus both signs occur. Without this symmetry one would obtain only $[0,1]\subset S$, leading to the weaker bound $L\ge1/(2k)$.
The second delicate step is the formula
$$I_i-I_j=[a_i-b_j,; b_i-a_j].$$
The endpoints must be checked directly. The minimum of $x-y$ over a rectangle $a_i\le x\le b_i$, $a_j\le y\le b_j$ occurs at $x=a_i$, $y=b_j$; the maximum occurs at $x=b_i$, $y=a_j$. The length then equals
$$(b_i-a_j)-(a_i-b_j) = |I_i|+|I_j|.$$
The third delicate point is the estimate of the measure of $S$. The intervals $I_i-I_j$ may overlap heavily, so their lengths cannot be added to obtain $|S|$. What is valid is the inequality
$$|S| \le \sum_{i,j}|I_i-I_j|,$$
which follows from subadditivity of measure. This is exactly the direction needed.
Alternative Approaches
A related approach works with the nonnegative distance set
$$D={|x-y|:x,y\in M}.$$
Since $D\supset[0,1]$, its measure is at least $1$. The set $D$ is covered by the intervals $D_{ij}$ arising from pairs of components. Estimating their total length yields
$$1\le 2kL.$$
This gives only $L\ge1/(2k)$, so the method loses a factor of $2$.
The signed difference set avoids that loss. Passing from distances to signed differences doubles the interval forced to lie inside the set, from length $1$ to length $2$, while the covering estimate remains unchanged. This produces the sharp inequality $L\ge1/k$ immediately.