Ограничение на последовательность чисел

Обозначим через $b(n)$ двоичную запись числа $n$; например, $b(13) = 1101$. Обозначим число,троичнаязапись которого совпадает с $b(n)$, через $b(n)_3$; например, $b(13)_3 = 1101_3 = 1 + 9 + 27 = 37$. Докажем индукцией по $n$, что $a_n = b(n)_3$. База индукции ($n\leq 1$) дана в определении. Переход: пусть для всех $i < n$ троичная запись числа $a_i$ совпадает с $b(i)$. Необходимо доказать, что, во-первых, число $b(n)_3$ не образует триплета с какими-нибудь $a_i$ и $a_j$ для $i < j < n$ и, во-вторых, никакое меньшее число не удовлетворяет этому условию.

Предположим, что найдутся такие числа $i$ и $j$, что $0\leq i < j < n$ и $b(i)_3 + b(n)_3 = 2\cdot b(j)_3$. Заметим, что при сложении чисел $b(i)_3$ и $b(n)_3$ в троичной системе счисления не возникает переходов через разряд, поэтому если в результате получилось число $2\cdot b(j)_3$, то на всех позициях, где в строке $b(j)$ стоит единица, в обеих строках $b(i)$ и $b(n)$ также стоят единицы, а на всех остальных позициях в этих строках стоят нули. Таким образом, $b(i) = b(j) = b(n)$, из чего следует, что $i = j = n$. Противоречие.

Докажем теперь, что любое число, меньшее $b(n)3$(и большее$a{n-1}$), образует триплет с какими-нибудь$a_i$и$a_j$. Рассмотрим произвольное число$x$, удовлетворяющее неравенству$b(n-1)_3 < x < b(n)_3$. Поскольку$b(n-1)_3$и$b(n)_3$— это два соседних числа, чья троичная запись состоит из нулей и единиц, в троичной записи числа$x$ есть двойка.

Пусть троичная запись числа $x$ — это строка $s_n$. Построим строки $s_i$ и $s_j$, состоящие из нулей и единиц и имеющие такую же длину, что и $s_n$, по следующему принципу: единицы в $s_i$ стоят ровно на тех позициях, где в строке $s_n$ стоят единицы; единицы в $s_j$ стоят ровно на тех позициях, где в строке $s_n$ стоят ненулевые цифры. Возьмём в качестве $i$ число с двоичной записью $s_i$, а в качестве $j$ — число с двоичной записью $s_j$. Пусть $d_i$, $d_j$ и $d_n$ — цифры в какой-то позиции строк $s_i$, $s_j$ и $s_n$ соответственно. Тогда заметим, что, во-первых, $d_i\leq d_j\leq d_n$, а во-вторых, $2d_j = d_i + d_n$. Более того, в тех позициях, где в строке $s_n$ стоит двойка, выполняется цепочка строгих неравенств $d_i < d_j < d_n$. Значит, $i < j < n$, и числа $(a_i, a_j, x)$ образуют триплет, что и требовалось доказать.

Поскольку $2023 < 2048 = 2^{11}$, имеем, что в троичной записи числа $a_{2023}$ не больше $11$ цифр, ни одна из которых не превосходит $1$. Значит, \begin{align*} a_{2023} & \leq 3^0 + 3^1 + \ldots + 3^{10} = \frac{3^{11} - 1}{2} \leq \frac{243^2\cdot 3}{2} \leq {} \ & \leq \frac{250^2\cdot 3}{2} = 62,500\mkern2mu\cdot \frac{3}{2} < 66,666\mkern2mu\cdot\frac{3}{2} < 100,000 . \end{align*}

Комментарий. На самом деле $a_{2023} = 88,465$.