Задача №18406

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

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

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

в) Какое наибольшее количество различных чисел может встретиться в такой последовательности?

Обозначим члены последовательности $a_1,a_2,\dots ,a_n\text{.}$ По условию $60\le a_k\le 130\text{,}$ и для каждого перехода выполнено одно из двух:

$$a_{k+1}=a_k-2\text{(шаг «вниз на 2»)}$$ $$a_k\mid a_{k+1}\text{(следующее делится на предыдущее).}$$

Какие переходы возможны. Если $a_k\mid a_{k+1}$ и оба числа лежат в $[60;130]\text{,}$ то $a_{k+1}=m\cdot a_k$ при целом $m\ge 1\text{.}$ При $m=1$ число не меняется. При $m=2$ нужно $2a_k\le 130\text{,}$ то есть $a_k\le 65\text{;}$ тогда $a_k\in \{60,61,62,63,64,65\}$ и $a_{k+1}=2a_k\in \{120,\dots ,130\}\text{.}$ При $m\ge 3$ уже $3\cdot 60=180>130$ — невозможно. Значит, нетривиальных переходов ровно два типа:

$$a_{k+1}=a_k-2\text{и}{a}_{k+1}=2a_k(\text{только если }{a}_k\le 65).$$

Заметим: удвоение $a_{k+1}=2a_k$ всегда даёт чётное число, а шаг «$-2$» сохраняет чётность. Поэтому попасть в нечётное число можно только шагом «$-2$» из другого нечётного числа. Значит, все встречающиеся нечётные числа образуют один убывающий по $2$ блок, а покинуть «нечётный мир» можно лишь удвоением в одной из точек $a_k\in \{61,63,65\}\text{;}$ после этого мы навсегда остаёмся среди чётных (и $-2\text{,}$ и удвоение сохраняют чётность).

а) Уже спуск по всем нечётным $129,127,\dots ,61$ даёт $35$ различных чисел, а с продолжением (см. пункт в) — заметно больше. Значит, более $35$ различных чисел встретиться может. Ответ: да.

б) Ниже строится последовательность с $70$ различными числами; оборвав её на $60$-м по счёту различном значении, получим последовательность ровно с $60$ различными числами. Ответ: да.

в) Всего целых чисел в $[60;130]$ ровно $71\text{:}$ нечётных $61,63,\dots ,129$ — $35$ штук, чётных $60,62,\dots ,130$ — $36$ штук.

Оценка сверху. Покажем, что число $130$ и все $35$ нечётных чисел одновременно встретиться не могут. В отрезке $[60;130]$ попасть в $130$ можно только переходом $65\to 130$ (удвоение): шаг «$-2$» пришёл бы из $132$ — вне отрезка, а удвоением чётного числа получаются лишь $120,124,128$ (из $60,62,64$). Но $65\to 130$ — это и есть то единственное удвоение, которым мы покидаем нечётный блок; следовательно, нечётный блок заканчивается на $65\text{,}$ и нечётные $63$ и $61$ оказываются недостижимы. Поэтому одновременно иметь все $35$ нечётных чисел и число $130$ нельзя.

Остаётся два сценария.

• Сохранить все $35$ нечётных. Тогда удвоение делаем в наименьшем нечётном: $61\to 122\text{.}$ Число $130$ недостижимо, зато все остальные чётные достижимы: спускаясь от $122$ до $64\text{,}$ удваиваем $64\to 128$ и спускаемся до $60\text{,}$ покрывая все чётные $\{60,62,\dots ,128\}$ — $35$ чисел. Итого $35+35=70\text{.}$
• Использовать $130$ (удвоение $65\to 130$). Тогда теряются $61$ и $63\text{:}$ нечётных не больше $33\text{,}$ чётных не больше $36\text{,}$ итого не больше $69\text{.}$

Таким образом, больше $70$ различных чисел получить нельзя.

Построение, дающее $70\text{.}$ Рассмотрим последовательность:

$$129,127,\dots ,63,61,122,120,\dots ,66,64,128,126,\dots ,62,60.$$

Здесь сначала идут все нечётные числа от $129$ до $61$ с шагом $-2$ ($35$ чисел), затем удвоение $61\to 122$ ($122=2\cdot 61$), спуск $122\to \cdots \to 64\text{,}$ удвоение $64\to 128$ ($128=2\cdot 64$) и спуск $128\to \cdots \to 60\text{.}$ Все числа лежат в $[60;130]\text{,}$ каждый переход — либо «$-2$», либо допустимое удвоение. Встречаются все $35$ нечётных и все чётные от $60$ до $128$ ($35$ чисел); не встречается только $130\text{.}$ Различных чисел ровно $35+35=70\text{.}$

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