Дана конечная последовательность натуральных чисел, каждое из которых не меньше 80 и не больше 170. Каждое следующее число либо делится на предыдущее, либо меньше предыдущего на 2. Числа в последовательности могут повторяться. а) Может ли быть 35 различных элементов в последовательности? б) Может ли быть 60 различных элементов в последовательности? в) Найдите наибольшее количество различных элементов последовательности.

Все члены последовательности лежат в отрезке [80;170] — всего это 91 натуральное число. Для двух соседних членов a и b выполнено одно из двух условий: либо a b (число b делится на a), либо b = a - 2. Разберём, какие переходы вообще возможны. Переход «делимости» a b, где a b и a != b. Так как b кратно a и 80 a < b 170, то b 2a 160, а значит b = 2a (вариант b = 3a уже даёт b 240 > 170). Поэтому a in 80,81,82,83,84,85, и есть ровно шесть «удваивающих» переходов: 80 160, 81 162, 82 164, 83 166, 84 168, 85 170. Это единственный способ увеличить значение. Заметим, что цель удвоения всегда чётна. Переход «минус два» a a-2. Он уменьшает число на 2 и сохраняет чётность. Идея. Двигаясь только переходами «минус 2», мы спускаемся по числам одной чётности с шагом 2. Чтобы «подскочить» вверх и набрать новые числа, нужно воспользоваться удвоением из одного из чисел 80,,85. Так как цель удвоения всегда чётная, попасть в нечётное число можно только спуском по нечётной цепочке (нечётные числа никогда не являются результатом удвоения). Поэтому все встреченные нечётные числа образуют один убывающий участок: вернуться вверх к большему нечётному числу нельзя. а) и б). Покажем, что различных элементов может быть много, например 89 (см. пункт в), значит тем более возможны 35 и 60 различных элементов. Достаточно взять начальный участок построенной ниже последовательности нужной длины. Ответ в обоих пунктах — да. в) Оценка. Среди чисел [80;170] ровно 46 чётных (80,82,,170) и 45 нечётных (81,83,,169). Нечётные числа можно собрать только одним убывающим спуском по нечётной цепочке, после чего (стоя на одном из чисел 81,83,85) сделать удвоение и навсегда уйти в чётные. Рассмотрим, на каком нечётном числе мы выполняем удвоение. itemize Чтобы получить все 46 чётных, нужно начать чётный спуск с самого большого чётного числа 170; попасть в 170 можно только удвоением 85 170. Значит, спуск по нечётным мы прерываем на 85 и числа 83,81 уже не получим. Тогда нечётных не более (169-85)/(2)+1 = 43, и всего не более 43+46 = 89. Чтобы получить все 45 нечётных, нужно спуститься по ним до 81 и удвоить 81 162. Тогда чётный спуск начинается с 162 и даёт лишь (162-80)/(2)+1 = 42 чётных (числа 164,166,168,170 уже недостижимы). Всего не более 45+42 = 87. itemize Промежуточные варианты (удвоение из 83 166 и т.п.) дают ещё меньше. Дополнительные удвоения из 80,82,84 уже ничего не добавляют: их цели 160,164,168 попадают внутрь чётного спуска. Таким образом, различных элементов не больше 89. Построение на 89 различных элементов. Спустимся по нечётным от 169 до 85, удвоим 85 170 и спустимся по чётным от 170 до 80: 169, 167, 165, , 87, 85, 170, 168, 166, , 82, 80. Проверка: переход 85 170 — делимость (170 = 2* 85), все остальные переходы — «минус 2». Все числа лежат в [80;170]. Нечётных здесь (169-85)/(2)+1 = 43, чётных (170-80)/(2)+1 = 46, итого 43+46 = 89 различных элементов. Ответ: а) да; б) да; в) 89.

а) Да. б) Да. в) \(89\).