Задача №18416

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

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

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

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

Все члены последовательности лежат в отрезке $[80;170]$ — всего это $91$ натуральное число. Для двух соседних членов $a$ и $b$ выполнено одно из двух условий: либо $a\mid b$ (число $b$ делится на $a$), либо $b=a-2\text{.}$

Разберём, какие переходы вообще возможны.

\emph{Переход «делимости» $a\to b\text{,}$ где $a\mid b$ и $a\ne b\text{.}$} Так как $b$ кратно $a$ и $80⩽a<b⩽170\text{,}$ то $b⩾2a⩾160\text{,}$ а значит $b=2a$ (вариант $b=3a$ уже даёт $b⩾240>170$). Поэтому $a\in \{80,81,82,83,84,85\}\text{,}$ и есть ровно шесть «удваивающих» переходов:

$$80\to 160,81\to 162,82\to 164,83\to 166,84\to 168,85\to 170.$$

Это \emph{единственный} способ \emph{увеличить} значение. Заметим, что цель удвоения всегда чётна.

\emph{Переход «минус два» $a\to a-2\text{.}$} Он \emph{уменьшает} число на $2$ и сохраняет чётность.

Идея. Двигаясь только переходами «минус $2$», мы спускаемся по числам одной чётности с шагом $2\text{.}$ Чтобы «подскочить» вверх и набрать новые числа, нужно воспользоваться удвоением из одного из чисел $80,\dots ,85\text{.}$ Так как цель удвоения всегда чётная, попасть в \emph{нечётное} число можно только спуском по нечётной цепочке (нечётные числа никогда не являются результатом удвоения). Поэтому все встреченные нечётные числа образуют \emph{один} убывающий участок: вернуться вверх к большему нечётному числу нельзя.

а) и б). Покажем, что различных элементов может быть много, например $89$ (см. пункт в), значит тем более возможны $35$ и $60$ различных элементов. Достаточно взять начальный участок построенной ниже последовательности нужной длины. Ответ в обоих пунктах — \emph{да}.

в) Оценка. Среди чисел $[80;170]$ ровно $46$ чётных ($80,82,\dots ,170$) и $45$ нечётных ($81,83,\dots ,169$).

Нечётные числа можно собрать только одним убывающим спуском по нечётной цепочке, после чего (стоя на одном из чисел $81,83,85$) сделать удвоение и навсегда уйти в чётные. Рассмотрим, на каком нечётном числе мы выполняем удвоение.

\begin{itemize}
\item Чтобы получить \emph{все} $46$ чётных, нужно начать чётный спуск с самого большого чётного числа $170\text{;}$ попасть в $170$ можно только удвоением $85\to 170\text{.}$ Значит, спуск по нечётным мы прерываем на $85$ и числа $83,81$ уже не получим. Тогда нечётных не более $\frac{169-85}{2}+1=43\text{,}$ и всего не более $43+46=89\text{.}$
\item Чтобы получить \emph{все} $45$ нечётных, нужно спуститься по ним до $81$ и удвоить $81\to 162\text{.}$ Тогда чётный спуск начинается с $162$ и даёт лишь $\frac{162-80}{2}+1=42$ чётных (числа $164,166,168,170$ уже недостижимы). Всего не более $45+42=87\text{.}$
\end{itemize}
Промежуточные варианты (удвоение из $83\to 166$ и т.п.) дают ещё меньше. Дополнительные удвоения из $80,82,84$ уже ничего не добавляют: их цели $160,164,168$ попадают внутрь чётного спуска. Таким образом, различных элементов \emph{не больше} $89\text{.}$

Построение на $89$ различных элементов. Спустимся по нечётным от $169$ до $85\text{,}$ удвоим $85\to 170$ и спустимся по чётным от $170$ до $80\text{:}$

$$169,167,165,\dots ,87,85,170,168,166,\dots ,82,80.$$

Проверка: переход $85\to 170$ — делимость ($170=2\cdot 85$), все остальные переходы — «минус $2$». Все числа лежат в $[80;170]\text{.}$ Нечётных здесь $\frac{169-85}{2}+1=43\text{,}$ чётных $\frac{170-80}{2}+1=46\text{,}$ итого $43+46=89$ различных элементов.

Ответ: а) да; б) да; в) $89\text{.}$