In Peter Winkler's book "Mathematical Puzzles, A Connoisseur's Collection" I've found this one originating from 17th All Soviet Union Mathematical Competition:
$X$ is a union of $k$ disjoint intervals of the real line. It has the property that for any $h < 1$ we can find two points of $X$ which are a distance $h$ apart. Show that the sum of the lengths of the intervals in $X$ is at least $\frac{1}{k}$.
Although the author gives his proof of this theorem, I'm not convinced it's correct. I believe it is possible to obtain a set $X$ with such property, with total length of intervals lower than $1/k$.
If we divide an interval $[0,1]$ into $2^k – 1$ equal intervals of equal length and we take $ X = \bigcup\limits_{i=1}^{k} A_i$, where $A_i = \left[\frac{2^i-2}{2^k-1}, \frac{2^i-1}{2^k-1}\right]$ then $X$ satisfies the property given in the puzzle. To see that, notice that it is possible to obtain all intervals of length $d \in \left[\frac{2^{i-1}-1}{2^k-1},\frac{2^i-1}{2^k-1}\right]$ by choosing the right-end point in the interval $A_i$ and left-end point in some other interval $A_j, j<i$. Notice that $\bigcup\limits_{i=1}^{k} \left[\frac{2^{i-1}-1}{2^k-1},\frac{2^i-1}{2^k-1}\right] = [0,1]$. Moreover the total length of $k$ selected intervals is $\frac{k}{2^k-1}$, which goes to zero as $k$ goes to infinity. Specifically it is less then $\frac{1}{k}$ for every $k > 4$.
Is this a valid construction?
Best Answer
Let $k=4$, then your $X=\frac1{15}([0,1]\cup[2,3]\cup[6,7]\cup[14,15])$ (to abuse notation a bit). What are two points with distance $10/15$?