0
$\begingroup$

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.$

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented May 2 at 15:26
  • $\begingroup$ agree! but still tempting... $\endgroup$
    – Vladimir_U
    Commented May 2 at 16:12

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ OK Thanks! I see that this Lemma statement is surely correct... $\endgroup$
    – Vladimir_U
    Commented May 2 at 19:43
1
$\begingroup$

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]$.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Vladimir_U
    Commented May 2 at 17:06
  • $\begingroup$ This can be border point but must belong to the interval $\endgroup$ Commented May 2 at 17:31
  • $\begingroup$ 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 $\endgroup$
    – Vladimir_U
    Commented May 2 at 19:41
0
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .