Задание №53477. Числа и их свойства
Дана конечная последовательность натуральных чисел. Каждое из чисел
последовательности не меньше \(80\), но не больше \(170\). Каждый следующий член
последовательности либо на \(2\) меньше, чем предыдущий, либо делится на предыдущий.
Последовательность может содержать одинаковые числа.
а) Может ли быть \(40\) различных чисел в такой последовательности?
б) Может ли быть \(80\) различных чисел в такой последовательности?
в) Какое наибольшее количество различных чисел может быть в такой последовательности?
Шаг 1. Разберёмся с переходом «следующий делится на предыдущий». Пусть оба числа лежат в промежутке \([80;170]\) и следующее равно \(qx\), где \(q\) натурально.
При \(q=1\) число просто повторяется и новых чисел не даёт.
При \(q=2\) нужно \(2x\leqslant170\), то есть \(x\leqslant85\); условие \(2x\geqslant80\) выполняется само. Значит, \(x\in[80;85]\), а \(2x\in[160;170]\).
При \(q\geqslant3\) было бы \(qx\geqslant3\cdot80=240>170\) — невозможно.
Итак, единственный содержательный переход — удвоение \(x\to2x\) при \(80\leqslant x\leqslant85\).
Шаг 2. Главное наблюдение. Шаг «на \(2\) меньше» чётность сохраняет, а удвоение всегда даёт чётное число. Значит, как только в последовательности появилось чётное число, все следующие тоже чётные. Поэтому все нечётные числа идут в начале, а переход от нечётных к чётным возможен не более одного раза — это удвоение нечётного \(x\in\{81;83;85\}\).
Шаг 3. В промежутке \([80;170]\) ровно \(45\) нечётных чисел (от \(81\) до \(169\)) и \(46\) чётных (от \(80\) до \(170\)).
а) Да. Подойдёт последовательность \(170,\ 168,\ \dots,\ 92\): каждое следующее на \(2\) меньше предыдущего, все числа лежат в \([80;170]\), а их количество равно \(\dfrac{170-92}{2}+1=40\).
б) Да. Возьмём \(169,\ 167,\ \dots,\ 81\) — это \(\dfrac{169-81}{2}+1=45\) чисел, затем переход \(81\to162\) (число \(162=2\cdot81\) делится на \(81\)), затем \(162,\ 160,\ \dots,\ 94\) — ещё \(\dfrac{162-94}{2}+1=35\) чисел. Всего \(45+35=80\) различных чисел.
в) Наибольшее количество равно \(90\).
Оценка. Посмотрим, откуда в последовательности может взяться число \(170\). Шагом «на \(2\) меньше» его не получить: пришлось бы взять \(172>170\). Значит, \(170\) либо стоит первым, либо получено удвоением числа \(85\).
Если \(170\) стоит первым, то вся последовательность состоит из чётных чисел, и различных чисел не больше \(46\).
Если \(170\) получено из \(85\), то нечётная часть обрывается на \(85\), поэтому нечётных чисел не больше, чем от \(169\) до \(85\), то есть \(\dfrac{169-85}{2}+1=43\). Всего не больше \(43+46=89\).
Если же числа \(170\) в последовательности нет, то чётных различных чисел не больше \(45\), и всего не больше \(45+45=90\).
Во всех случаях различных чисел не больше \(90\).
Пример на \(90\) чисел:
\(169,\ 167,\ \dots,\ 81\) — все \(45\) нечётных чисел промежутка;
переход \(81\to162\) (удвоение);
\(162,\ 160,\ \dots,\ 84\) — \(40\) чётных чисел;
переход \(84\to168\) (удвоение);
\(168,\ 166,\ 164,\ 162,\ 160,\ \dots,\ 82,\ 80\) — здесь новыми оказываются \(168,\ 166,\ 164\), а в конце ещё \(82\) и \(80\).
Различных чётных чисел получилось \(40+3+2=45\), нечётных \(45\), всего \(90\).
