Докажите, что существует такая бесконечная ограниченная последовательность $\{x_n\}$, что для любых различных $m$ и $k$ выполнено неравенство
$$
|x_m-x_k|\ge|m-k|^{-1}.
$$
С. В. Конягин
Всесоюзная XII математическая олимпиада школьников, 1978 год, 9-10 классы
Мы приведём два решения задачи, предоставив читателю судить о достоинствах и недостатках каждого из них.
Заметим, что достаточно построить ограниченную последовательность $(x_n)$, удовлетворяющую неравенству
$$
|x_m-x_k|\cdot|m-k|\ge1\quad\text{при}~m\ne k\tag1
$$
для некоторого положительного $\eps$. Разделив все члены такой последовательности на $\eps$, мы получим искомую последовательность.
Первое решение. Попробуем построить на отрезке $[0;1]$ последовательность, удовлетворяющую неравенству (1) для $\eps=\dfrac1{10}$. В этом случае необходимо, чтобы члены последовательности,
номера которых отличаются на 1, отличались бы не менее чем на $\dfrac1{10}$; члены последовательности, номера которых отличаются на 10, отличались бы не менее чем на $\dfrac1{100}$ и т. д. Учитывая это замечание, возьмём $x_0=0$, $x_1=0{,}1$, $x_2=0{,}2$, $\ldots$, $x_9=0{,}9$ (рис. 3). Поместим $x_{10}$ правее $x_0$ на расстоянии $0{,}01$ (это минимальное расстояние, если мы хотим, чтобы выполнялось неравенство (1) для $\eps=\dfrac1{10}$), $x_{11}$ поместим правее $x_1$ на том же расстоянии и т. д.; наконец, $x_{19}$ поместим правее $x_9$ на том же расстоянии (рис. 4). Поместим, далее, $x_{20}$ на расстоянии $0{,}01$ правее $x_{10}$, $x_{21}$ на расстоянии $0{,}01$ правее $x_{11}$ и т. д. (рис. 5). Мы видим, что десятичное разложение числа $x_n$ получается из десятичного разложения числа $n$ «переворачиванием» и приписыванием слева «нуля целых и запятой»:
$$
x_{\overline{a_la_{l-1}\ldots a_2a_1}}=\overline{0{,}a_1a_2\ldots a_{l-1}a_l}.
$$
Рис. 3Рис. 4Рис. 5
Возьмём эту формулу в качестве определения последовательности $(x_n)$. Например, $x_{29}=0{,}921$, $x_{100}=0{,}001$.
Будет ли построенная последовательность $(x_n)$ удовлетворять неравенству (1) для $\eps=\dfrac1{10}$ или вообще для какого-нибудь положительного $\eps$? Ответ на этот вопрос отрицателен. Возьмём, например, $m=1001$ и $k=990$. Тогда $m-k=11$, и $|x_m-x_k|=|0{,}1001-0{,}0990|=0{,}0011$, откуда $|x_m-x_k|\cdot|m-k|=0{,}0121\lt0{,}1$. Аналогично можно взять $m=\underbrace{10\ldots01}_{s~\text{цифр}}$, $k=\underbrace{99\ldots90}_{s-1~\text{цифр}}$, тогда
$$
|x_m-x_k|\cdot|m-k|=11\cdot11\cdot10^{-s}.
$$
Подобные явления возникают из-за того, что числа $m$ и $k$, хотя и записываются совершенно разными цифрами, тем не менее оказываются мало отличающимися друг от друга как «переворачиванием», так и после него. Чтобы избежать этого, подвергнем последовательность $(x_n)$ «шифровке». Каждую цифру каждого члена последовательности $(x_n)$ заменим её «шифром» по следующему правилу:
$$
\begin{aligned}\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|}
\hline
\vphantom{\Big|}\text{цифра}&0&1&2&3&4&5&6&7&8&9\\
\hline
\vphantom{\Big|}\text{шифр}&0&3&6&9&2&5&8&1&4&7\\
\hline
\end{array}\end{aligned}
$$
(этот шифр описывается простым правилом; угадайте каким). Для нас будут существенны три свойства шифра:
шифр цифры $0$ есть цифра $0$;
любая цифра однозначно восстанавливается («дешифруется») по её шифру;
если шифры двух цифр соседние, т. е. отличаются на 1 или на 9, то сами цифры не являются соседними.
Обозначим шифрованную последовательность через $(y_n)$. Докажем, что последовательность $(y_n)$ такова, что для любых различных $m$ и $k$ выполнено неравенство
$$
|y_m-y_k|\cdot|m-k|\ge\dfrac1{100}.
$$
Пусть $m\gt k$, $m=\overline{a_l\ldots a_1}$, $k=\overline{b_l\ldots b_1}$ (мы всегда можем считать, что в $k$ столько же цифр, сколько в $m$, дополнив в случае необходимости число $k$ слева некоторым количеством нулей; при этом согласно 1) число $y_k$ дополнится нулями справа). Пусть
$$
\begin{aligned}
y_m&=\overline{0{,}\alpha_1\ldots\alpha_{s-1}\alpha_s\ldots\alpha_l},\\
y_k&=\overline{0{,}\beta_1\ldots\beta_{s-1}\beta_s\ldots\beta_l}\\
\text{и}~y_m-y_k&=\overline{0{,}0\ldots0{*}{?}\ldots{?}}.
\end{aligned}
$$
(Мы считаем, что $y_m\gt y_k$; звёздочка указывает первую значащую цифру, знаки ? — какие угодно цифры.) Тогда $|y_m-y_k|\ge10^{-s}$. Сравним теперь числа $m$ и $k$. Для этого сравним числа $\overline{a_1\ldots a_{s-1}}$ и $\overline{b_1\ldots b_{s-1}}$. Поскольку в разложении числа $y_m-y_k$ после запятой стоит $s-1$ нулей, эти два числа либо совпадают, либо отличаются на 1.
Случай 1. Если $\overline{\alpha_1\ldots\alpha_{s-1}}=\overline{\beta_1\ldots\beta_{s-1}}$, то $\alpha_s\ne\beta_s$, значит, $a_s\ne b_s$, откуда $|m-k|\ge10^{s-1}$, так как при вычитании $k$ из $m$ получится ненулевое число, кончающееся на $s-1$ нулей.
Случай 2. Если $\overline{\alpha_1\ldots\alpha_{s-1}}=\overline{\beta_1\ldots\beta_{s-1}}+1$, то шифры $\alpha_{s-1}$ и $\beta_{s-1}$ являются соседними. Тогда по свойству 3) цифры $a_{s-1}$ и $b_{s-1}$ не являются соседними, а значит, в десятичном разложении числа $m-k$ цифра, стоящая в разряде $10^{s-2}$, не равна нулю, откуда $|m-k|\ge10^{s-2}$.
В обоих случаях $|y_m-y_k|\cdot|m-k|\ge1$, что и требовалось доказать.
Второе решение. Положим $x_n=n\sqrt2-a_n$, где $a_n$ — наибольшее целое число, не превосходящее $n\sqrt2$. Ясно, что $0\lt x_n\lt1$. Покажем, что для любых $m\gt k\gt1$
$$
|x_m-x_k|\cdot(m-k)\gt\dfrac14,
$$
т. е. что последовательность $(4x_n)$ — искомая.
Числитель — целое число, отличное от нуля (число $\sqrt2$ иррационально), поэтому он не меньше 1. Знаменатель легко оценить, пользуясь тем, что $a_m\lt m\sqrt2$ и $a_k\gt(k-1)\sqrt2-1$:
$$
(m-k)\sqrt2+(a_m-a_k)\lt2(m-k)\sqrt2+\sqrt2-1\lt(m-k)(2\sqrt2+1)\lt4(m-k).
$$
Отсюда получаем $|x_m-x_k|\gt\dfrac1{4(m-k)}$.
