Задача №18413

Дана конечная последовательность натуральных чисел, каждое из которых не меньше $80$ и не больше $170\text{.}$ Каждое следующее число либо делится на предыдущее, либо меньше предыдущего на $2\text{.}$ Числа в последовательности могут повторяться.

а) Может ли быть $40$ различных элементов в последовательности?

б) Может ли быть $80$ различных элементов в последовательности?

в) Найдите наибольшее количество различных элементов последовательности.

а) Да, может. Приведём пример:

$$158,156,154,\dots ,84,82,80.$$

Здесь каждый элемент на $2$ меньше предыдущего.

б) Да, может. Приведём пример:

$$159,157,155,\dots ,85,83,81,162,160,158,\dots ,88,86,84.$$

Здесь первые $40$ элементов получены из числа $159$ уменьшением на $2\text{,}$ $41$-й элемент получен умножением $40$-го на $2\text{,}$ остальные $39$ чисел получены уменьшением предыдущего на $2\text{.}$

в) Начнём составлять последовательность следующим образом:

$$169,167,165,\dots ,89,87,85.$$

Так мы набрали все подходящие нечётные числа, кроме $83$ и $81\text{.}$ Если после $85$ взять $170\text{,}$ после чего пройти по всем чётным числам уменьшением предыдущего на $2\text{,}$ то мы потеряем два числа $83$ и $81\text{,}$ то есть получим $89$ чисел в последовательности.

Тогда продолжим последовательность так:

$$\dots ,85,83,81,162,160,158,\dots ,84,82,80.$$

На данный момент пропущены числа $170\text{,}$ $168\text{,}$ $166$ и $164\text{.}$ Продолжим последовательность:

$$\dots ,80,160,158,156,\dots ,88,86,84,168,166,164.$$

Таким образом, мы получили $90$ различных чисел: все, кроме $170\text{.}$

Если бы число $170$ было в последовательности, то после него обеими операциями мы бы получали только чётные числа: вычитая $2$ из чётного числа, получим чётное, а все числа, кратные чётным, — тоже чётные. Так как $170$ не могло получиться из другого числа уменьшением на $2\text{,}$ то оно могло получиться только из $85$ умножением на $2\text{.}$ Значит, вариант появления $170$ в последовательности был полностью рассмотрен выше.

Тогда наибольшее количество различных чисел в последовательности равно $90\text{,}$ а последовательность имеет вид:

$$169,167,165,\dots ,85,83,81,162,160,158,\dots ,$$ $$\dots ,84,82,80,160,158,156,\dots ,88,86,84,168,166,164.$$