# Interval [0;1] is divided into 2*n sub-intervals, each smaller than ½, find two intervals with index difference n, containing points with distance ½

Given division of interval $$[0;1]$$ into $$2n$$ consecutive sub-intervals of nonzero length, each smaller than $$\frac12$$ in length, $$I_{1}, …, I_{2n}$$, we can always find a pair of intervals with index difference $$n$$ (like $$I_1$$ and $$I_{n+1}$$), such,that they contain in their inner parts two points at distance $$\frac12.$$

• Don't try to fit the whole question in the title - it leads to bad MathJax compromises, and the goal of the title should be to quickly give a reader an idea of whether they can help you or not. Commented May 2 at 15:26
• agree! but still tempting... Commented May 2 at 16:12

Here's a proof sketch. Feel free to fill in the details, but all the tools you need are introduced here.

For each interval $$I$$, define $$F(I) = [\inf I, \sup I)$$. For instance, $$F((a,b]) = [a,b)$$. Here, we note that

• the interior of $$I_i$$ is the same as the interior of $$F(I_i)$$.
• $$F(I_1), F(I_2),\ldots, F(I_{2n})$$ are nonempty intervals which partition $$[0,1)$$
• If $$i\neq j$$ and $$x \in F(I_i), y \in F(I_j)$$, then $$x < y \iff i < j$$.

Define the function $$\varphi : [0,1) \to \{1,2,\ldots, 2n\}$$ by $$\varphi(x) = i \iff x \in F(I_i)$$. (equivalently, $$x \in F(I_{\varphi(x)})$$)

Then define the function $$g : [0,1/2) \to \mathbb{Z}$$ by $$g(x) = \varphi(x+1/2) - \varphi(x) - n$$.

The function $$g$$ satisfies three properties:

• $$g(0) + \lim_{x\to 1/2^-} g(x) \in \{0,-1\}$$
• For any $$x\in [0,1/2)$$, $$\left|g(x) - \lim_{y\to x^-} g(y)\right| \leq 1$$.
• For any $$x\in [0,1/2)$$, $$\lim_{y\to x^+} g(y) = g(x)$$.

By the third bullet point, it suffices to show $$g$$ has some zero (rather than a zero in the interiors of the intervals). By the first bullet point, either $$g(0) = 0$$ or $$\lim_{x\to1/2^-}g(x)=0$$ or $$g$$ changes signs somewhere in $$[0,1/2)$$. By the second bullet point, $$g$$ cannot skip an integer.

As a result, $$g$$ has a zero, so we're finished.

• OK Thanks! I see that this Lemma statement is surely correct... Commented May 2 at 19:43

Let's denote $$I_i = [b_i, e_i]$$ and the "image" of that interval $$Im(I_i) = [b_i + \frac{1}{2}, e_i + \frac{1}{2}]$$ (this is the set off all points that differ by $$\frac{1}{2}$$ from the points of $$I_i$$).

Let's observe at first, that there is some interval, that contains number $$\frac{1}{2}$$. By symmetry we can asssume that it happens for some interval $$I_j$$, where $$j \leqslant n$$. We can see that $$1 \in Im(I_j)$$ so $$Im(I_j) \cap I_{2n} \neq \varnothing$$. Consider now the least index (let's say $$k$$) for which we have $$Im(I_j) \cap I_k \neq \varnothing$$.

Now if $$k \leqslant j + n$$ then we are done, because this tells us that $$Im(I_j) \cap I_{j+n} \neq \varnothing$$, so there are two numbers that differ by $$\frac{1}{2}$$ in sets $$I_j$$ and $$I_{j + n}$$.

If not, then we can observe that either $$Im(I_{j-1}) \cap I_k \neq \varnothing$$ or if $$Im(I_{j-1}) \cap I_k = \varnothing$$ then $$Im(I_{j-1}) \cap I_{k-1} \neq \varnothing$$ but then we have also $$k - 1 > j - 1 + n$$. Thus we can repeat the reasoning for the index $$j - 1$$ and so on. We will eventually find some index (for convenience called $$j$$) for which $$k$$ (defined as above) satisfies $$k \leqslant j + n$$, beacuse eventually we have $$Im(I_1) \cap I_j \neq \varnothing$$ and $$j < n + 1$$.

Note We don't necessarily need the intervals of the form $$[a,b]$$ they can also be for example $$[a,b)$$ etc., since we just use the fact that their sum fully covers the interval $$[0,1]$$.

• interval contains number 1/2 - you mean inside or it can be border point? as inventor of this lengthy proof above that i am comfortable with, i am worried about such minor things, maybe yours is also correct, didn't have time to get deeper into it Commented May 2 at 17:06
• This can be border point but must belong to the interval Commented May 2 at 17:31
• OK, thanks! just wanted to make sure you treated my "in their inner parts" correctly, I need this all for other topic where it matters Commented May 2 at 19:41

We define following function $$f(x)$$ on interval $$(0;1)$$: $$(0)f(x) = x + 1/2, x < 1/2; f(x) = x - 1/2, x > 1/2; f(x) = 1/2, x = 1/2$$ Let $$B$$ be a set of all bordering points $$B^1, … , B^{2n-1}$$ between $$2*n$$ intervals. Let $$L^{min}$$ be a minimal length of these $$2*n$$ intervals. Let $$N(x)$$ be a function equal to an index of interval to which x belongs, defined for all $$x$$, belonging to inner parts of $$2*n$$ intervals. We find in inner parts of $$2*n$$ intervals $$2*n$$ points, one point for each interval, which we call $$BeginInt^1, …, BeginInt^{2n}$$ , based on following rules (we can always do so because number of intervals is finite and their lengths are not zero, if some rule for $$BeginInt^j$$ is not satisfied we divide by 2 distance $$BeginInt^j - B^{ j-1}$$ until it satisfies all rules): $$(1) BeginInt^j ≠ ½$$ $$(2) BeginInt^j - B^{ j-1} < L{ min} / 2 ; j > 1$$ $$(3) BeginInt^1 < L{ min} / 2$$ $$(4) f( BeginInt^j ) ∉ B$$ $$(5) ∀ x: x ⊂ (B{ j-1}; BeginInt^j) ⇨ N( f( x ) ) = N( f(BeginInt^j) ) ; j > 1$$ $$(6) ∀ x: x ⊂ (0; BeginInt^1) ⇨ N( f( x ) ) = N( f(BeginInt^1) )$$ We find in inner parts of $$2*n$$ intervals $$2*n$$ points, one point for each interval, which we call $$EndInt^1, …, EndInt^{2n}$$, based on following rules (we can always do so because number of intervals is finite and their lengths are not zero, if some rule for $$EndInt^j$$ is not satisfied we divide by 2 distance $$B^j - EndInt^j$$ until it satisfies all rules): $$(7) EndInt^j ≠ ½$$ $$(8) B^j - EndInt^j < L^{ min} / 2 ; j < 2*n$$ $$(9) 1 - EndInt^{ 2n } < L^{ min} / 2$$ $$(10) f( EndInt^j ) ∉ B$$ $$(11) ∀ x: x ⊂ (EndInt^j; B^j) ⇨ N( f( x ) ) = N( f(EndInt^j) ) ; j < 2*n$$ $$(12) ∀ x: x ⊂ (EndInt^{ 2n};1) ⇨ N( f( x ) ) = N( f(EndInt^{ 2n}) )$$

Assume that Lemma is false. If $$f(BeginInt^1) ∈ Int^{ n+1}$$ our Lemma’s statement is fulfilled, so this cannot be the case. Let’s assume that $$f(BeginInt^1) ∈ Int^{ n+2 } ∪ … ∪ Int^{ 2n }$$, it follows that $$∀j, 1 < j ≤ n: f(BeginInt^j) ∈ Int^{ n+2 } ∪ … ∪ Int^{ 2n }$$, because, if contrarily, we have for some $$1 < j ≤ n: f(BeginInt^j) ∈ Int^1 ∪ … ∪ Int^{ n+1}$$, we cannot have $$f(BeginInt^j) < BeginInt^1$$, as it would mean that we could chose smaller $$BeginInt^1$$, which satisfies $$f(BeginInt^1) = BeginInt^j , j ≤ n$$ (here contradiction with (6)), it is also not possible to have $$f(BeginInt^j) = Begin_Int^1$$, as we have $$j ≤ n, f(BeginInt^1) ∈ Int^{ n+2 } ∪ … ∪ Int^{ 2n }$$, and finally, we cannot have $$f(BeginInt^j) > BeginInt^1$$, as it would mean that we have two intervals, one inside another, namely $$( f(BeginInt^j) ; BeginInt^j ) ⊂ ( BeginInt^1 ; f(BeginInt^1) )$$, they are not the same, because $$f(BegiInt^j) ≠ BeginInt^1$$, and both have length ½ because of definition of $$f(x)$$.

Knowing that $$∀ j, 1 < j ≤ n: f(BeginInt^j) ∈ Int^{ n+2 } ∪ … ∪ Int^{ 2n }$$, we can say that $$f(BegiInt^1) < f(Begin_Int^2) < … < f(BeginInt^n)$$ due to definition of $$f(x)$$.

If $$∀ j, 1 < j ≤ n: f(BeginInt^j) ∈ Int^{ n+2 } ∪ … ∪ Int^{ 2n }$$, we also have $$∀ j, 2 ≤ j ≤ n: f(BeginInt^j) ∈ Int^{ n+2 } ∪ … ∪ Int^{ 2n }$$, it means that we know that the next statement: $$(13) ∀ m ≤ j ≤ n: f(BeginInt^j) ∈ Int^{ n+m } ∪ … ∪ Int^{ 2n }$$ is true for $$m = 2$$, this is our base case in induction on $$m$$, and we aim to prove the above statement (13) for all $$m$$ up to $$n$$. It is easy to see that if $$∀ j, m ≤ j ≤ n: f(BeginInt^j) ∈ Int^{ n+m } ∪ … ∪ Int^{ 2n }$$, because $$f(BeginInt^m) ∉ Int^{ n+m }$$ (otherwise our Lemma’s statement is fulfilled), and because $$f(BeginInt^1) < f(BeginInt^2) < … < f(BeginInt^n)$$, it follows that $$∀ j, m+1 ≤ j ≤ n: f(BeginInt^j) ∈ Int^{ n+m+1 } ∪ … ∪ Int^{ 2n }$$, and we proved by induction that $$f(BeginInt^n) ∈ Int^{ 2n }$$, which is the statement of our Lemma. This means that our assumption that $$f(BeginInt^1) ∈ Int^{ n+2 } ∪ … ∪ Int^{ 2n }$$ is wrong, and we are left with the only possibility that $$f(BeginInt^1) ∈ Int^2 ∪ … ∪ Int^n$$. Consider $$f(EndInt^{ 2n })$$, we can show that $$f(EndInt^{ 2n }) ∈ Int^1 ∪ … ∪ Int^n$$, otherwise we will have $$EndInt^{ 2n } - f(EndInt^{ 2n }) = ½$$ and $$f(EndInt^{ 2n }) - f(BeginInt^1) > ½$$ at the same time, which is not possible because all these points belong to interval $$(0;1)$$. Starting from here the proof for the last case will be the same as it was for already proven case (when $$f(BeginInt^1) ∈ Int^{ n+2 } ∪ … ∪ Int^{ 2n }$$), we just need to change $$BeginInt^…$$ for $$EndInt^…$$ and point on symmetry of the function $$f(x)$$ and rules (1) – (12) with respect to the middle point of interval $$(0;1)$$. Following the same steps as above we are coming to a contradiction, showing that $$f(EndInt^n) ∈ Int^1$$. This completes Lemma’s proof.

• Multi-letter variables makes math so much harder to read. Commented May 2 at 15:29
• I will think about it, of course it doesn't change the meaning Commented May 2 at 16:22