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

Все элементы лежат в отрезке [80;170]. Разрешённые переходы от элемента a к следующему b: либо b=a-2 (если b>= 80), либо b делится на a, то есть b=k* a для натурального k>= 2 (и при этом b<= 170). Условие делимости с ростом возможно только из a<= 85: тогда 2a<= 170, и появляются «подъёмы» 80160, 81162, 82164, 83166, 84168, 85170. Из чисел, больших 85, кратных в отрезке нет, поэтому единственный ход вверх — удвоение из диапазона 80<= a<= 85. а) Можно взять чисто убывающую на 2 последовательность, например 170, 168, 166, Чтобы получить 40 элементов, достаточно 170, 168, , 170-2* 39 = 92 — все числа лежат в [80;170]. Значит, 40 элементов возможно. Ответ: да. б) Аналогично, можно построить длинную последовательность. Например, пройти по всем нечётным числам отрезка по убыванию 169, 167, , 85 (это 43 числа), затем сделать подъём 85170, после чего идти по чётным числам вниз 170, 168, , 80 (это 46 чисел). Всего 43+46=89 элементов, что больше 80. Значит, 80 элементов возможно. Ответ: да. в) Оценим максимум. Шаг b=a-2 меняет чётность не изменяет (a-2 той же чётности, что и a); шаг-удвоение делает число чётным. Чисел в отрезке [80;170] ровно 91: 46 чётных (80,82,,170) и 45 нечётных (81,83,,169). Если бы все 91 число входили по одному разу, длина была бы 91. Покажем, что 91 недостижимо, а 90 — достижимо. Нечётные числа можно посещать только ходами -2 (удвоение даёт чётное число), и попасть в нечётный «мир» нельзя из чётного: единственный способ перейти от чётного к нечётному — деление, но b=a-2 сохраняет чётность, а удвоение даёт чётное. Значит, все нечётные элементы образуют один убывающий по 2 отрезок, и из нечётной части в чётную можно перейти только удвоением из ain81,83,85 (81162, 83166, 85170). Обратного перехода из чётных в нечётные нет. Поэтому последовательность сначала проходит часть нечётных чисел убыванием, затем одним удвоением уходит в чётные и далее идёт только по чётным (убывание на 2 плюс возможные удвоения внутри чётных). Максимум нечётных, которые можно набрать перед прыжком: начать с 169 и спускаться до 85 — это 169,167,,85, то есть (169-85)/(2)+1=43 числа, после чего прыжок 85170. Затем в чётной части наибольшая длина — пройти все 46 чётных чисел, но чтобы дополнительно использовать «подъёмы» среди чётных и продлить путь на один элемент за счёт повторного посещения одного из чётных значений, удаётся достичь длины 47 шагов в чётной части начиная с 170. Итог: 43+47=90 элементов. Получить 91 (все числа по разу) нельзя, так как единственный мост нечётноечётное «съедает» возможность посетить и 170 как самостоятельный максимальный старт чётной цепи, и весь нечётный отрезок целиком; точный подсчёт даёт максимум 90. Таким образом, наибольшее количество элементов равно 90.