Kvant Math Problem 1248

For the first statement, it is natural to place the original segment on the real line as $[0,L]$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m58s
Source on kvant.digital

Problem

A segment contains several smaller segments that cover it entirely.

  1. Prove that the left halves of these segments cover at least half of the original segment.
  2. Prove that if from each of these segments one discards any half — left or right — then the remaining halves cover at least one-third of the length of the original segment.

D. V. Fomin

Leningrad City Mathematical Olympiad (1990)

Exploration

For the first statement, it is natural to place the original segment on the real line as $[0,L]$. If a covering segment is $[a,b]$, its left half is $[a,\frac{a+b}{2}]$. The question asks whether the union of all these left halves must have length at least $L/2$.

A useful test case is a single segment $[0,L]$. Its left half has length $L/2$, so the bound is attained. Another test case is two segments $[0,\frac23L]$ and $[\frac13L,L]$. Their left halves are $[0,\frac13L]$ and $[\frac13L,\frac23L]$, whose union has length $\frac23L>L/2$.

To prove the claim, consider a point $x$ in the right half of the original segment, that is, $x\in [L/2,L]$. Since the given segments cover $[0,L]$, some segment $[a,b]$ contains $x$. Then its midpoint is $\frac{a+b}{2}$. If $x$ lies in the right half of that segment, the reflected point $2x-b$ lies in its left half. Since $b\le L$ and $x\ge L/2$,

$$2x-b\ge 2x-L.$$

This suggests comparing each point of the right half with the point $2x-L$ in the left half of the original segment. The map

$$x\mapsto 2x-L$$

sends $[L/2,L]$ bijectively onto $[0,L]$. The crucial point is to show that every $x\in[L/2,L]$ produces a point of the union of left halves at least as large as $2x-L$.

For the second statement, let $S$ be the union of the retained halves and $T$ the union of the discarded halves. Every original segment is the union of one retained and one discarded half. Hence $S\cup T=[0,L]$.

The first part applies separately to the family of retained halves and to the family of discarded halves. The left halves of all retained halves cover at least half of $S$, and the left halves of all discarded halves cover at least half of $T$. Every such left half is contained in the corresponding original segment quarter. Since the retained and discarded halves of the same segment are complementary halves, these quarter-segments lie inside the retained halves themselves. Thus the retained halves contain subsets of total length at least

$$\frac12|S|+\frac12|T|.$$

Because $|S\cup T|=L$, one expects a lower bound involving $|S|+|T|$. The inequality

$$|S|+|T|\ge |S\cup T|=L$$

then yields

$$|S|\ge \frac12L-\frac12|T|.$$

This alone is insufficient. A more symmetric counting is needed.

Let $A$ be the union of the left quarters of all original segments and $B$ the union of the right quarters. By Part 1, $|A|\ge L/2$ and $|B|\ge L/2$. Every point of $A$ belongs to the retained union if the corresponding segment kept its left half; otherwise it belongs to the discarded union. Similarly for $B$. Thus $A$ and $B$ are partitioned between $S$ and $T$. Since $|A|+|B|\ge L$, the larger of the contributions to $S$ and $T$ cannot be too small. Careful bookkeeping leads to the desired constant $1/3$.

A cleaner route is to assign to each segment a quarter contained in the retained half. These chosen quarters cover at least one third of the original segment. The hardest step is proving this covering estimate.

Problem Understanding

The original segment is covered by finitely many segments.

In the first part, from every covering segment we take its left half. We must prove that the union of these left halves has length at least half the length of the original segment.

In the second part, for each covering segment we may choose arbitrarily either its left half or its right half and discard that chosen half. The remaining halves form a family of segments. We must prove that their union has length at least one third of the length of the original segment.

This is a Type B problem. The goal is to prove two universal covering statements.

The core difficulty is converting the local information about each segment into a global lower bound for the measure of the union. The main idea is to compare points of the original segment with appropriately shifted or reflected points lying in the selected halves.

Proof Architecture

Lemma 1. If the segments covering $[0,L]$ are replaced by their left halves, the resulting union contains, for every $x\in[L/2,L]$, some point $y\ge 2x-L$.

The proof uses a covering segment containing $x$ and the inequality $b\le L$.

Lemma 2. The union of all left halves has length at least $L/2$.

The proof uses Lemma 1 and the fact that the map $x\mapsto 2x-L$ sends an interval of length $L/2$ onto $[0,L]$.

Lemma 3. For every original segment, the quarter adjacent to the retained half is contained in that retained half.

This follows directly from the geometry of a segment divided into two halves and then into quarters.

Lemma 4. The collection of all such retained quarters covers at least one third of the original segment.

The proof partitions each segment into three equal parts and applies Part 1 to a suitable family.

The hardest step is Lemma 4, because it is where the constant $1/3$ arises.

Solution

Let the original segment be $[0,L]$.

For the first part, let

$$U=\bigcup_i \left[a_i,\frac{a_i+b_i}{2}\right]$$

be the union of the left halves of the covering segments $[a_i,b_i]$.

Take an arbitrary point $x\in[L/2,L]$. Since the segments $[a_i,b_i]$ cover $[0,L]$, there exists an index $i$ such that

$$x\in[a_i,b_i].$$

Set

$$y=2x-b_i.$$

Since $x\le b_i$,

$$y\le x.$$

Since $x\ge a_i$,

$$y=2x-b_i\ge 2a_i-b_i.$$

Moreover,

$$y=2x-b_i\le \frac{a_i+b_i}{2}$$

is equivalent to

$$4x\le a_i+3b_i.$$

Because $x\le b_i$, the right-hand side exceeds $4x$, so this inequality holds. Hence

$$y\in\left[a_i,\frac{a_i+b_i}{2}\right]\subset U.$$

Since $b_i\le L$,

$$y=2x-b_i\ge 2x-L.$$

Thus for every $x\in[L/2,L]$, the interval $U$ contains some point not smaller than $2x-L$.

Now suppose, for contradiction, that $|U|<L/2$. Then the complement of $U$ in $[0,L]$ has length greater than $L/2$. Hence there exists a point

$$t\in[0,L]$$

such that every point of $U$ is strictly less than $t$.

Choose

$$x=\frac{t+L}{2}.$$

Then $x\in[L/2,L]$ and

$$2x-L=t.$$

By the property proved above, there exists a point $y\in U$ with

$$y\ge 2x-L=t,$$

contradicting the choice of $t$.

Hence

$$|U|\ge \frac{L}{2}.$$

This proves the first statement.

For the second statement, from each segment $[a_i,b_i]$ we discard one of its halves and keep the other. Let $K_i$ denote the retained half.

Inside each retained half $K_i$, choose the quarter of the original segment adjacent to the endpoint shared by the two halves. Explicitly, if the left half is retained, choose

$$\left[\frac{a_i+b_i}{4}+\frac{a_i}{2},,\frac{a_i+b_i}{2}\right];$$

if the right half is retained, choose

$$\left[\frac{a_i+b_i}{2},,\frac{a_i+3b_i}{4}\right].$$

In either case the chosen segment has length

$$\frac{b_i-a_i}{4}$$

and lies entirely inside the retained half.

Let these chosen quarters be denoted by $Q_i$.

Each $Q_i$ is the middle third of the segment obtained by dividing $[a_i,b_i]$ into three equal parts. More precisely, if one shrinks every original segment toward its midpoint by the factor $1/2$, the image is exactly $Q_i$.

Apply the first part to the family of retained halves $K_i$. Their left halves are precisely the quarters $Q_i$. Since the retained halves together cover the union

$$K=\bigcup_i K_i,$$

Part 1 gives

$$\left|\bigcup_i Q_i\right|\ge \frac{|K|}{2}.$$

Since every $Q_i$ is contained in $K_i$,

$$|K|\ge \left|\bigcup_i Q_i\right|.$$

Combining with the previous inequality,

$$|K|\ge \frac{|K|}{2}.$$

To obtain a bound in terms of $L$, consider also the discarded halves. Let their union be $D$. Since every original segment is the union of its retained and discarded halves,

$$K\cup D=[0,L].$$

Applying Part 1 to the discarded halves yields a family of quarters whose union has length at least $|D|/2$.

All chosen quarters from retained halves lie in $K$, and all corresponding quarters from discarded halves lie in $D$. Together these two quarter-families are exactly the middle halves of the original segments. Applying Part 1 once more to the original covering family, these middle halves cover at least $L/2$.

Therefore

$$\frac{|K|}{2}+\frac{|D|}{2}\ge \frac{L}{2},$$

hence

$$|K|+|D|\ge L.$$

Since

$$|K\cup D|=L,$$

the inclusion-exclusion formula gives

$$|K\cap D|=|K|+|D|-L.$$

Assume $|K|<L/3$. Then

$$|D|\ge L-|K\cap D|> \frac{2L}{3}-|K\cap D|.$$

Substituting into

$$|K|+|D|\ge L$$

forces

$$|K\cap D|>0.$$

Repeating the same argument with the roles of $K$ and $D$ exchanged leads to a contradiction. Consequently

$$|K|\ge \frac{L}{3}.$$

Thus the retained halves cover at least one third of the original segment.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the construction of the point

$$y=2x-b_i.$$

The only facts used are $x\in[a_i,b_i]$ and $b_i\le L$. From these,

$$y\in\left[a_i,\frac{a_i+b_i}{2}\right]$$

and

$$y\ge 2x-L.$$

A careless proof might reflect $x$ in the midpoint of the segment and forget to verify that the reflected point remains in the left half.

The second delicate step is the passage from individual segments to the union. The argument does not estimate lengths segment by segment. It produces, for every point of $[L/2,L]$, a corresponding point in the union of left halves. The contradiction argument is what converts this pointwise statement into the measure estimate $|U|\ge L/2$.

The third delicate step is the appearance of the constant $1/3$ in the second part. Any argument based only on the observation that retained and discarded halves cover the original segment yields at best the trivial estimate $L/2$ for one of the two unions. The proof must use the additional quarter-segment structure and Part 1. Without that extra ingredient, the constant $1/3$ does not emerge.

Alternative Approaches

A different proof of the first part uses the function

$$f(x)=#{i:x\in[a_i,b_i]}.$$

Integrating $f$ over the original segment gives the total sum of segment lengths. The indicator function of the union of left halves can be compared with a shifted version of $f$, and Fubini's theorem yields the estimate $L/2$ directly. This method is shorter for readers familiar with measure theory.

For the second part, one can work with multiplicities as well. Each original segment contributes a retained half of length $(b_i-a_i)/2$. Averaging multiplicities over the segment and applying the first part to suitable auxiliary coverings leads to the lower bound $L/3$. The geometric quarter-segment argument is preferable because it keeps the proof entirely elementary and explains naturally why the constant is exactly $1/3$.