Pigeon hole principle for continuous spaces

Question

Given a line segment of length L that contains n + 1 points, let D be the length of the shortest segment between consecutive points. What is the maximum value of D over all possible configurations of points?

Note: It is a solved example from Brilliant.org pegion hole principle text can't seem to understand that explanation.

Link to the page: https://brilliant.org/wiki/pigeonhole-principle-definition/ In "Pigeonhole Principle on Continuous Spaces" section.

Solution By Brilliant: First, consider a trivial configuration of the points. Let all points be evenly spaced with one point at each end of the segment. In this case, the points divide up the line into 'n' segments, each of length (L/n).

Using the pigeonhole principle, we can approach the problem as follows: Consider each of the n evenly spaced segments as a "box" and each of the n + 1 points as an item to be placed into the boxes. The pigeonhole principle implies that at least one box (or segment) must have two items (or points), which guarantees that no two consecutive points can be farther apart than L/n.(HOW????)

Answer 1

The answer is $\frac{L}{n}$. Let's assume that the line segment is on the number line, starts at $0$, and ends at $L$. Let's assume that the $n+1$ points are $x_0\leq x_1\leq\dots\leq x_n$.

• Step 1 (Showing that $\frac{L}{n}$ is possible, i.e., $D\geq\frac{L}{n}$): Place the point $x_i$ at $\frac{iL}{n}$. Observe that this choice of $x_i$'s satisfies the inequalities between consecutive points. The distance between consecutive points is $|x_{i+1}-x_i|=\frac{L(i+1)}{n}-\frac{Li}{n}=\frac{L}{n}$. Therefore, it is possible to place the points so that $\frac{L}{n}$ is the minimum distance between points).

• Step 2 (Showing that $\frac{L}{n}$ is the best possible, i.e., that $D\leq\frac{L}{n}$):

  • Sketch (without pigeonhole principle):

    With the order on the $x_i$'s, $|x_{i+1}-x_i|\geq D$ since $D$ is the shortest length between consecutive points. Moreover, observe that $|x_n-x_0|\leq L$ since all points lie on the line. Since the points are ordered on the line, $$ |x_n-x_0|=|x_n-x_{n-1}|+|x_{n-1}-x_{n-2}|+\dots+|x_2-x_1|+|x_1-x_0|. $$ Putting this all together, we have $$ L\geq|x_n-x_0|=|x_n-x_{n-1}|+|x_{n-1}-x_{n-2}|+\dots+|x_2-x_1|+|x_1-x_0|\geq nD. $$ Therefore, $D\leq \frac{L}{n}$.

  • Sketch (with pigeonhole principle):

    Let $L_1,\dots,L_n$ be a subdivision of $L$ into intervals where $L_i=\left[\frac{L(i-1)}{n},\frac{Li}{n}\right)$ for $i\neq n$ and $L_n=\left[\frac{L(n-1)}{n},L\right].$ Consider the map $f:\{0,\dots,n\}$ to $\{1,\dots,n\}$ where $f(i)$ is the index of the interval containing $x_i$. This is a map from $n+1$ numbers to $n$ numbers, so, by the pigeonhole principle, this map is not injective. In other words, there is some pair $i\neq j$ such that $f(i)=f(j)$. In other words, $x_i$ and $x_j$ are in the same interval, say this interval is $L_k$. Then, the distance $|x_i-x_j|$ is at most the length of $L_k$. Since the length of $L_k$ is $\frac{Lk}{n}-\frac{L(k-1)}{n}=\frac{L}{n}$, the minimum distance between points is at most $\frac{L}{n}$, i.e., $D\leq\frac{L}{n}$.