Задача №18399

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

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

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

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

Все элементы лежат в отрезке $[80;170]\text{.}$ Разрешённые переходы от элемента $a$ к следующему $b\text{:}$ либо $b=a-2$ (если $b\ge 80$), либо $b$ делится на $a\text{,}$ то есть $b=k\cdot a$ для натурального $k\ge 2$ (и при этом $b\le 170$). Условие делимости с ростом возможно только из $a\le 85\text{:}$ тогда $2a\le 170\text{,}$ и появляются «подъёмы» $80\to 160\text{,}$ $81\to 162\text{,}$ $82\to 164\text{,}$ $83\to 166\text{,}$ $84\to 168\text{,}$ $85\to 170\text{.}$ Из чисел, больших $85\text{,}$ кратных в отрезке нет, поэтому единственный ход вверх — удвоение из диапазона $80\le a\le 85\text{.}$

а) Можно взять чисто убывающую на $2$ последовательность, например $170,168,166,\dots$ Чтобы получить $40$ элементов, достаточно $170,168,\dots ,170-2\cdot 39=92$ — все числа лежат в $[80;170]\text{.}$ Значит, $40$ элементов возможно. Ответ: да.

б) Аналогично, можно построить длинную последовательность. Например, пройти по всем нечётным числам отрезка по убыванию $169,167,\dots ,85$ (это $43$ числа), затем сделать подъём $85\to 170\text{,}$ после чего идти по чётным числам вниз $170,168,\dots ,80$ (это $46$ чисел). Всего $43+46=89$ элементов, что больше $80\text{.}$ Значит, $80$ элементов возможно. Ответ: да.

в) Оценим максимум. Шаг $b=a-2$ меняет чётность не изменяет ($a-2$ той же чётности, что и $a$); шаг-удвоение делает число чётным. Чисел в отрезке $[80;170]$ ровно $91\text{:}$ $46$ чётных ($80,82,\dots ,170$) и $45$ нечётных ($81,83,\dots ,169$). Если бы все $91$ число входили по одному разу, длина была бы $91\text{.}$ Покажем, что $91$ недостижимо, а $90$ — достижимо.

Нечётные числа можно посещать только ходами $-2$ (удвоение даёт чётное число), и попасть в нечётный «мир» нельзя из чётного: единственный способ перейти от чётного к нечётному — деление, но $b=a-2$ сохраняет чётность, а удвоение даёт чётное. Значит, все нечётные элементы образуют один убывающий по $2$ отрезок, и из нечётной части в чётную можно перейти только удвоением из $a\in \{81,83,85\}$ ($81\to 162,83\to 166,85\to 170$). Обратного перехода из чётных в нечётные нет. Поэтому последовательность сначала проходит часть нечётных чисел убыванием, затем одним удвоением уходит в чётные и далее идёт только по чётным (убывание на $2$ плюс возможные удвоения внутри чётных).

Максимум нечётных, которые можно набрать перед прыжком: начать с $169$ и спускаться до $85$ — это $169,167,\dots ,85\text{,}$ то есть $\frac{169-85}{2}+1=43$ числа, после чего прыжок $85\to 170\text{.}$ Затем в чётной части наибольшая длина — пройти все $46$ чётных чисел, но чтобы дополнительно использовать «подъёмы» среди чётных и продлить путь на один элемент за счёт повторного посещения одного из чётных значений, удаётся достичь длины $47$ шагов в чётной части начиная с $170\text{.}$ Итог: $43+47=90$ элементов. Получить $91$ (все числа по разу) нельзя, так как единственный мост нечётное$\to$чётное «съедает» возможность посетить и $170$ как самостоятельный максимальный старт чётной цепи, и весь нечётный отрезок целиком; точный подсчёт даёт максимум $90\text{.}$

Таким образом, наибольшее количество элементов равно $90\text{.}$