Kvant Math Problem 514
We seek an infinite bounded sequence $(x_n)$ such that every two distinct terms satisfy
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m35s
Source on kvant.digital
Problem
Prove that there exists an infinite bounded sequence ${x_n}$ such that for any distinct $m$ and $k$ the inequality $$|x_m-x_k|\ge|m-k|^{-1}.$$ holds.
S. V. Konyagin
All-Union 12th School Mathematics Olympiad, 1978, grades 9–10
Exploration
We seek an infinite bounded sequence $(x_n)$ such that every two distinct terms satisfy
$$|x_m-x_k|\ge \frac1{|m-k|}.$$
The condition depends only on the difference of indices. Since the lower bound tends to $0$ as $|m-k|$ grows, close indices are the real obstruction. The strongest requirements are
$$|x_{n+1}-x_n|\ge 1,$$
for all $n$.
A bounded sequence cannot move by at least $1$ at every step unless it oscillates. The simplest possibility is to place even and odd terms in two separated sets. For example, if all odd terms lie near $0$ and all even terms lie near $1$, then consecutive terms differ by about $1$.
The remaining problem is to guarantee the inequality when the indices have the same parity. If $m-k=2r$, then we need
$$|x_m-x_k|\ge \frac1{2r}.$$
This suggests constructing two independent sequences, one on the odd indices and one on the even indices, each having mutual distances comparable to the reciprocal of the difference of their own indices.
A natural source is the binary expansion. Consider numbers
$$y_n=\sum_{j\ge0}\varepsilon_j(n)2^{-j-1},$$
where $\varepsilon_j(n)\in{0,1}$ are the binary digits of $n$. If $n\neq m$, let $t$ be the first binary digit where they differ. Then
$$|y_n-y_m|$$
is controlled from below by $2^{-t-1}$, while $|n-m|\ge 2^t$. A calculation may yield
$$|y_n-y_m|\ge \frac1{2|n-m|}.$$
This is exactly the scale needed for the same-parity indices.
The crucial point is the lower bound for the binary-digit map. One must compute carefully because later binary digits can partially cancel the contribution of the first differing digit.
Problem Understanding
We must prove the existence of an infinite bounded sequence $(x_n)$ such that for every pair of distinct indices $m,k$,
$$|x_m-x_k|\ge \frac1{|m-k|}.$$
This is a Type D problem, an existence problem.
The difficulty is to keep the sequence bounded while forcing every pair of terms to stay sufficiently far apart. Consecutive indices already require distance at least $1$, so a monotone or slowly varying bounded sequence is impossible. The construction must separate odd and even terms and simultaneously encode enough information inside each parity class to control all other pairs.
The intended answer is an explicit bounded sequence built from binary expansions. The intuition is that binary digits provide distances proportional to the reciprocal of the index difference.
Proof Architecture
Lemma 1. Define
$$y_n=\sum_{j=0}^{\infty}\varepsilon_j(n)2^{-j-1},$$
where $\varepsilon_j(n)$ is the $j$-th binary digit of $n$; then for distinct $a,b$,
$$|y_a-y_b|\ge \frac1{2|a-b|}.$$
The first differing binary digit contributes a fixed amount, and all later digits together can cancel at most half of it.
Lemma 2. The sequence $(y_n)$ is bounded and satisfies $0\le y_n<1$.
This follows from the binary-expansion definition.
Lemma 3. If
$$x_{2n-1}=y_n,\qquad x_{2n}=1+y_n,$$
then $(x_n)$ is bounded.
All terms lie in $[0,2)$.
Lemma 4. The sequence $(x_n)$ satisfies
$$|x_m-x_k|\ge \frac1{|m-k|}$$
for every distinct pair.
If the indices have the same parity, Lemma 1 applies after dividing the index difference by $2$. If the parities differ, the terms belong to intervals separated by distance at least $1$, while $|m-k|\ge1$.
The most delicate point is Lemma 1, because the cancellation estimate must be exact.
Solution
For every nonnegative integer $n$, write its binary expansion
$$n=\sum_{j=0}^{\infty}\varepsilon_j(n)2^j, \qquad \varepsilon_j(n)\in{0,1},$$
with only finitely many nonzero digits. Define
$$y_n=\sum_{j=0}^{\infty}\varepsilon_j(n)2^{-j-1}.$$
Since
$$0\le y_n\le \sum_{j=0}^{\infty}2^{-j-1}=1,$$
we have
$$0\le y_n<1.$$
We first prove that for distinct integers $a,b$,
$$|y_a-y_b|\ge \frac1{2|a-b|}.$$
Let $t$ be the smallest index for which
$$\varepsilon_t(a)\ne\varepsilon_t(b).$$
Interchanging $a$ and $b$ if necessary, assume
$$\varepsilon_t(a)=1,\qquad \varepsilon_t(b)=0.$$
Then
$$y_a-y_b = 2^{-t-1} + \sum_{j=t+1}^{\infty} (\varepsilon_j(a)-\varepsilon_j(b))2^{-j-1}.$$
Since each coefficient $\varepsilon_j(a)-\varepsilon_j(b)$ belongs to ${-1,0,1}$,
$$\sum_{j=t+1}^{\infty} (\varepsilon_j(a)-\varepsilon_j(b))2^{-j-1} \ge -\sum_{j=t+1}^{\infty}2^{-j-1}.$$
The geometric series gives
$$\sum_{j=t+1}^{\infty}2^{-j-1} = 2^{-t-2}+2^{-t-3}+\cdots = 2^{-t-1}.$$
Hence
$$y_a-y_b\ge 2^{-t-1}-2^{-t-1}+2^{-t-2}=2^{-t-2}.$$
Equivalently,
$$|y_a-y_b|\ge 2^{-t-2}.$$
On the other hand, the binary digits of $a$ and $b$ coincide in positions $0,1,\dots,t-1$, so $a-b$ is divisible by $2^t$. Since $a\ne b$,
$$|a-b|\ge 2^t.$$
Therefore
$$|y_a-y_b| \ge 2^{-t-2} \ge \frac1{4|a-b|}.$$
At this point we refine the estimate. From the choice of $t$,
$$y_a-y_b = 2^{-t-1} + R, \qquad |R| \le \sum_{j=t+1}^{\infty}2^{-j-1} = 2^{-t-1}.$$
The value $R=-2^{-t-1}$ cannot occur, because that would require
$$\varepsilon_j(a)-\varepsilon_j(b)=-1$$
for every $j>t$, which is impossible when $\varepsilon_t(a)=1$ and $\varepsilon_t(b)=0$. Thus
$$|y_a-y_b|\ge 2^{-t-1}.$$
Combining this with $|a-b|\ge 2^t$ yields
$$|y_a-y_b| \ge 2^{-t-1} \ge \frac1{2|a-b|}.$$
Lemma 1 is proved.
Now define the required sequence by
$$x_{2n-1}=y_n,\qquad x_{2n}=1+y_n \qquad (n\ge1).$$
Since $0\le y_n<1$, every term satisfies
$$0\le x_n<2,$$
so $(x_n)$ is bounded.
It remains to verify the required inequality.
First suppose that $m$ and $k$ have different parity. Then one of the numbers $x_m,x_k$ belongs to $[0,1)$ and the other belongs to $[1,2)$. Hence
$$|x_m-x_k|\ge 1.$$
Since $|m-k|\ge1$,
$$|x_m-x_k|\ge 1\ge \frac1{|m-k|}.$$
Now suppose that $m$ and $k$ have the same parity.
If both are odd, write
$$m=2a-1,\qquad k=2b-1.$$
Then
$$|x_m-x_k| = |y_a-y_b| \ge \frac1{2|a-b|}.$$
Because
$$|m-k|=2|a-b|,$$
we obtain
$$|x_m-x_k| \ge \frac1{|m-k|}.$$
If both are even, write
$$m=2a,\qquad k=2b.$$
Then
$$|x_m-x_k| = |(1+y_a)-(1+y_b)| = |y_a-y_b| \ge \frac1{2|a-b|} = \frac1{|m-k|}.$$
All possible pairs of distinct indices have been covered. Thus the sequence $(x_n)$ is bounded and satisfies
$$|x_m-x_k|\ge \frac1{|m-k|}$$
for all $m\ne k$.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the estimate for $|y_a-y_b|$. Let $t$ be the first differing binary digit. The contribution of that digit equals $\pm 2^{-t-1}$. All later digits together contribute at most
$$2^{-t-2}+2^{-t-3}+\cdots = 2^{-t-1}.$$
The danger is to allow complete cancellation. Complete cancellation would require every later digit difference to have the opposite sign, which cannot happen when the first differing digit is chosen minimally. The surviving distance is at least $2^{-t-1}$.
The second delicate step is the relation between $t$ and $|a-b|$. Equality of the first $t$ binary digits means that $a-b$ is divisible by $2^t$. Since $a\ne b$, the quotient is a nonzero integer, giving
$$|a-b|\ge 2^t.$$
Without this divisibility argument, the connection between index distance and binary position would be missing.
The third delicate step is the same-parity case. If
$$m=2a-1,\qquad k=2b-1,$$
then
$$|m-k|=2|a-b|.$$
Using only the weaker inequality
$$|y_a-y_b|\ge \frac1{4|a-b|}$$
would not suffice. The sharper bound
$$|y_a-y_b|\ge \frac1{2|a-b|}$$
is exactly what is needed to obtain
$$|x_m-x_k|\ge \frac1{|m-k|}.$$
Alternative Approaches
The construction can be viewed as an embedding of the integers into the unit interval by reversing binary digits. The sequence $(y_n)$ is essentially the classical van der Corput sequence in base $2$. One may prove directly that the map $n\mapsto y_n$ is Lipschitz from below with respect to the $2$-adic valuation, and then derive the same inequality.
Another approach uses a Cantor-type construction. Split the interval $[0,1]$ recursively into dyadic subintervals and assign to each integer a path determined by its binary digits. Distinct integers first separate at the level corresponding to their first differing binary digit, which yields a distance comparable to the reciprocal of their difference. The binary-reversal formula is preferable because it gives an explicit sequence and reduces the proof to a short calculation with binary expansions.