How to prove this interval related problem? Let $k \in \mathbb{N}$. Given $k$ pairwise disjoint intervals $I_1,...,I_k \subset [0,1]$. Denote by $S$ their union. We know that for any $d \in [0,1]$ there exist two points $p,q \in S$ such that $dist(p,q)=d$. Prove that $length(I_1)+...+length(I_k) \geq \frac{1}{k}$.
At my first seen, I think that it may be relative to Pigeonhole Principle. I try to assume that $length(I_1)+...+length(I_k) \lt \frac{1}{k}$, and try to use Pigeonhole Principle to infer to a contradiction. I have a vague thought that we can divide $[0,1]$ into $k$ parts, and every parts' length will be $\frac{1}{k}$. However, now, I am stuck in  this point, and have no progress.
Hope that someone can help me with it.
 A: Consider raising this question to a higher dimension. Define rectangles $I_{ij}\subset\mathbb{R}^2$ as $I_{ij}=I_i\times I_j$. Let $\tilde S=\bigcup_{i,j}I_{ij}$. Then let
$$
D=\{d=|p-q|:(p,q)\in\tilde S\}
$$
Verify this (easy):

The statement that the intervals satisfy "$\forall d\in[0,1],\exists p,q\in S,\ d(p,q)=d$" is equivalent to saying "$[0,1]\subset D$".

Note that, by symmetry, we may assume $p\geq q$ and thus obtain yet another equivalent statement
$$
[0,1]\subset D':=\{p-q:(p,q)\in\tilde S,\ p\geq q\}
$$
Let's think what this means geometrically. Take any $(p,q)\in\tilde S$ and note the following:

*

*$(p,q)\in\tilde S$ means it is in one of the rectangles $I_{ij}$

*$p>q$ means it is in some rectangle $I_{ij}$ where $i\geq j$.

*If you draw a straight line through $(p,q)$ parallel to $y=x$, then $p-q$ is the intersection of this line with the $x$-axis. In other words, $p-q$ is the projection of $(p,q)$ on the $x$-axis along the direction parallel to $y=x$.

Now what does $[0,1]\subset D'$ mean? The observations above tell us that it means:

The projections of $\{I_{ij}\cap\mathbb{R}^2_{\{x\geq y\}},\ i\geq j\}$ on the $x$-axis along the direction parallel to $y=x$ must cover the interval $[0,1]$.

Let $P(I_{ij}\cap\mathbb{R}^2_{\{x\geq y\}})$ denote these projections, each of which is clearly an interval. Hence, with the definition of $D'$ and our interpretation of $P(I_{ij}\cap\mathbb{R}^2_{\{x\geq y\}})$ we have
$$
D'=\bigcup_{i\geq j}P(I_{ij}\cap\mathbb{R}^2_{\{x\geq y\}})
$$
Therefore the previous assumption $[0,1]\subset D'$ implies
$$
1\leq\sum_{i\geq j}\left|P(I_{ij}\cap\mathbb{R}^2_{\{x\geq y\}})\right|
$$
It remains to compute the lengths of these projected intervals $P(I_{ij}\cap\mathbb{R}^2_{\{x\geq y\}})$. Note that since the intervals $I_i$ are disjoint, only when $i=j$ does the intersection with $\mathbb{R}^2_{\{x\geq y\}}$ have an effect. Hence,
$$i>j\implies P(I_{ij}\cap\mathbb{R}^2_{\{x\geq y\}})=P(I_{ij})$$
Now let's compute $P(I_{ij}\cap\mathbb{R}^2_{\{x\geq y\}})$.

*

*Case (i): $i=j$. In this case $I_{ii}\cap\mathbb{R}^2_{\{x\geq y\}}$ is a triangle with a right angle. The side of it not adjacent to the right angle is on the straight line $y=x$. Its projection's length is $|I_i|$.


*Case (ii): $i>j$. In this case $I_{ij}$ is a rectangle with side lengths $|I_i|$ and $|I_j|$. Its projection's length is $|I_i|+|I_j|$.
The summation is over $i,j$ such that $k\geq i\geq j\geq1$. Hence,
$$
1\leq k(|I_1|+|I_2|+\cdots+|I_k|)
$$
Q.E.D.
