МОШ 2023, 9 класс, задача 6

Решение. Обозначим через двоичную запись числа ; например, . Обозначим число, троичная запись которого совпадает с , через ; например, . Докажем индукцией по , что .

База индукции () дана в определении. Переход: пусть для всех троичная запись числа совпадает с . Необходимо доказать, что, во-первых, число не образует триплета с какими-нибудь и для и, во-вторых, никакое меньшее число не удовлетворяет этому условию.

Предположим, что найдутся такие числа и , что , и . Заметим, что при сложении чисел и в троичной системе счисления не возникает переходов через разряд, поэтому, если в результате получилось число , то на всех позициях, где в строке стоит единица, в обеих строках и также стоят единицы, а на всех остальных позициях в этих строках стоят нули. Таким образом, , из чего следует, что . Противоречие.

Докажем теперь, что любое число, меньшее (и большее ), образует триплет с какими-нибудь и . Рассмотрим произвольное число , удовлетворяющее неравенству . Поскольку и — это два соседних числа, чья троичная запись состоит из нулей и единиц, в троичной записи числа есть двойка.

Пусть троичная запись числа — это строка . Построим строки и , состоящие из нулей и единиц и имеющие такую же длину, что и , по следующему принципу: единицы в стоят ровно на тех позициях, где в строке стоят единицы; единицы в стоят ровно на тех позициях, где в строке стоят ненулевые цифры. Возьмём в качестве число с двоичной записью , а в качестве — число с двоичной записью . Пусть , и — цифры в какой-то позиции строк , и соответственно. Тогда заметим, что, во-первых, , а во-вторых, . Более того, в тех позициях, где в строке стоит двойка, выполняется цепочка строгих неравенств . Значит, , и числа образуют триплет, что и требовалось доказать.

Поскольку , имеем, что в троичной записи числа не больше цифр, ни одна из которых не превосходит . Значит,

Замечание. На самом деле .