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

Обозначим члены последовательности a_1, a_2, , a_n. По условию каждое число удовлетворяет неравенству 60 <= a_k <= 130, и для каждого перехода выполнено одно из двух: a_(k+1) = a_k - 2 (шаг «вниз на 2») a_k a_(k+1) (следующее делится на предыдущее). Разберёмся, какие переходы вообще возможны. Если a_k a_(k+1) и оба числа лежат в [60;130], то a_(k+1) = m* a_k при целом m >= 1. При m = 1 число не меняется (новых различных чисел это не даёт). При m = 2 нужно 2a_k <= 130, то есть a_k <= 65; тогда a_k in 60,61,62,63,64,65 и a_(k+1) = 2a_k in 120,,130. При m >= 3 уже 3* 60 = 180 > 130 — невозможно. Значит, нетривиальных переходов ровно два типа: a_(k+1) = a_k - 2 и a_(k+1) = 2a_k (только если a_k <= 65). Нас интересует количество различных значений среди членов. Повторение значений количество различных не увеличивает, поэтому достаточно рассматривать движение по различным числам отрезка [60;130] с указанными переходами. а) Покажем сразу более сильное — пример с большим числом различных значений (см. пункт в); из него следует, что более 35 различных чисел встретиться может. Ответ: да. б) Так как ниже будет построена последовательность с 69 различными числами, то, оборвав её на 60-м различном числе, получим последовательность ровно с 60 различными числами. Ответ: да. в) Оценка сверху. Всего целых чисел в [60;130] ровно 71: нечётных 61,63,,129 — 35 штук, чётных 60,62,,130 — 36 штук. Покажем, что все 71 число использовать нельзя. Заметим, что переход a_(k+1) = 2a_k всегда даёт чётное число. Значит, попасть в нечётное число можно только шагом «вниз на 2» из другого нечётного числа (a_(k+1) = a_k - 2). Поэтому все встречающиеся нечётные числа образуют один убывающий по 2 блок: как только мы оказались на нечётном числе, дальше по нечётным числам можно только спускаться, а единственный способ покинуть «нечётный мир» — это удвоение, возможное лишь в точках a_k in 61,63,65 (нечётные <= 65). После удвоения мы попадаем на чётное число >= 120, и вернуться к нечётным уже нельзя (удвоение чётного даёт чётное, а -2 сохраняет чётность). Значит, удвоение из «нечётного мира» в «чётный» происходит ровно один раз — в одной из точек 65,63 или 61. Пусть удвоение происходит в точке d in 61,63,65. Тогда среди нечётных мы можем использовать лишь числа от 129 до d, а все нечётные, меньшие d, недостижимы. После удвоения попадаем в 2d и далее спускаемся по чётным. Подсчёт: - d = 65: нечётные 65,67,,129 — 33 числа; удвоение 65 130; чётные 130,128,,60 — 36 чисел. Итого 33 + 36 = 69 различных чисел (не использованы только 61 и 63). - d = 63: попадаем в 126, поэтому чётные 128,130 недостижимы — получаем не более 68. - d = 61: попадаем в 122, недостижимы 124,126,128,130 — получаем не более 67. Во всех случаях различных чисел не больше 69. Следовательно, 69 — верхняя граница. Построение, дающее 69. Рассмотрим последовательность: 129,127,125,,69,67,65, 130,128,126,,64,62,60. Здесь сначала идут все нечётные числа от 129 до 65 с шагом -2 (33 числа), затем переход 65 130 (это удвоение: 130 = 2* 65, 65 130), а затем все чётные числа от 130 до 60 с шагом -2 (36 чисел). Все числа лежат в [60;130]; каждый переход — либо «-2», либо допустимое удвоение. Различных чисел ровно 33 + 36 = 69. Таким образом, наибольшее возможное количество различных чисел равно 69.

а) да; б) да; в) 69.