Задача 67188

Темы:    [ Троичная система счисления ] [ Числовые последовательности (прочее) ] [ Индукция (прочее) ]

Сложность: 5 Классы: 8,9,10

Условие

Автор: Бутырин Б.

Назовём тройку чисел триплетом, если одно из них равно среднему арифметическому двух других. Последовательность $(a_n)$ строится следующим образом: $a_0 = 0$, $a_1 = 1$ и при $n > 1$ число $a_n$ — такое минимальное натуральное число, большее $a_{n-1}$, что среди чисел $a_0$, $a_1$, ..., $a_n$ нет трёх, образующих триплет. Докажите, что $a_{2023} \leqslant 100\,000$.

Решение

Обозначим через $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$.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	86
Год	2023
класс
Класс	9
задача
Номер	6