Танины числа (В часы заката на бульваре Мирдамад)

[Ktina]

В часы заката на бульваре Мирдамад Таня записала на доске числа 0 и 1. Раз в минуту она выписывает на доску
наименьшее натуральное число, которое не составляет ни с какими двумя уже
написанными арифметическую прогрессию и не было выписано ранее.
Доказать, что число 2017 не будет написано на доске.

[gris]

Получается, что последовательность однозначно определена и будет возрастающей? Вот так: $0\; 1\; 3\; 4\; 9\;10\;12\;13...$
Тогда надо набраться терпения и выписать её до надлежащего члена. Мне кажется, что это быстрее, чем доказывать.

[12d3]

Если рассматривать эти числа в девятеричной системе счисления, то на доске будут записаны все числа, состоящие из цифр $0,1,3,4$(назовем такие числа хорошими), и только они. Это следует из двух утверждений.
1) Сумма двух различных хороших чисел не может быть равна удвоенному хорошему, т.к. при сложении двух хороших чисел переноса разряда нет, удвоенное хорошее состоит из цифр $0,2,6,8$ , а если в сумме двух хороших в каком-то разряде стоит $0,2,6,8$, то у слагаемых в этом разряде стоят одинаковые цифры (тут требуется маленький перебор).
2) Для каждого числа $x$ можно найти не большее его хорошее число $y$, чтобы их сумма была удвоенным хорошим. Строить $y$ будем поразрядно по такому правилу: если в каком-то разряде $x$ находится $0,1,3,4$, то в $y$ ставим в этом разряде ту же цифру. Если в $x$ цифра $5$ или $7$, то в $y$ в том же разряде будет $1$. Если в $x$ цифра $2,6,8$, то в $y$ в этом разряде будет $0$. Из построения следует, что сумма $x$ и $y$ состоит из цифр $0,2,6,8$, причем если $x$ нехорошее, то $y < x$.
Остается выяснить про 2017. $2017_{10} = 2681_9$. Нехорошее.

[maxal]

12d3 в сообщении #1252288 писал(а):

Если рассматривать эти числа в девятеричной системе счисления, то на доске будут записаны все числа, состоящие из цифр $0,1,3,4$(назовем такие числа хорошими), и только они.

Это то же самое, что в троичной с.с. числа состоящие из цифр 0,1. Цитата из A005836:

Цитата:

This is the lexicographically earliest increasing sequence of nonnegative numbers that contains no arithmetic progression of length 3.

[Ktina]

gris
12d3
maxal
Большое спасибо!