Задание 19 ЕГЭ профиль: Наибольшее число различных членов

19.27.1.1.3 Числа и их свойства › Последовательности по правилу

В конечной последовательности натуральных чисел каждое число не меньше 60 и не больше 130. Известно, что каждый следующий член последовательности либо делится на предыдущий, либо меньше предыдущего на 2. В последовательности могут встретиться одинаковые числа.

а) Может ли быть 35 различных членов?

б) Может ли быть 60 различных членов?

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

Источник: ЕГЭ 2026, резервная волна, Центр
Ответ и решение
  1. Выясним, какие переходы возможны. Следующее число, либо на 22 меньше предыдущего, либо делится на него, то есть равно kxkx, где xx это предыдущее, k≥1k\ge1. При k≥3k\ge3 имеем kx≥3⋅60=180>130kx\ge 3\cdot60=180>130, что невозможно. Значит, возможны только три перехода: x→x−2x\to x-2, x→xx\to x (число повторяется) и x→2xx\to 2x при 2x≤1302x\le 130, то есть x≤65x\le 65.

    Авторский приём: в учебниках перечня этот шаг полностью не изложен.

  2. Чётность. Переходы x→x−2x\to x-2 и x→xx\to x не меняют чётности, а x→2xx\to 2x даёт чётное число. Значит, из чётного числа нельзя перейти к нечётному; нечётное число можно сменить на чётное только удвоением x→2xx\to2x, а это возможно для нечётных xx от 6161 до 6565: 6161, 6363, 6565. Поэтому в последовательности сначала идут нечётные числа, затем (после одного удвоения) только чётные.

    Инвариант — величина, которая не изменяется в результате некоторых операций … Если инвариант различает два положения, то от одного нельзя перейти к другому. В качестве инварианта может использоваться чётность или раскраска.
    Учебные материалы. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи, под ред. В. О. Бугаенко, МЦНМО, 2008, Инварианты, с. 29
    Многие задачи легко решаются, если заметить, что некоторая величина имеет определённую чётность. Из этого следует, что ситуации, в которых эта величина имеет другую чётность, невозможны.
    Учебные материалы. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи, под ред. В. О. Бугаенко, МЦНМО, 2008, Чётность, с. 13

а) Может ли быть 3535 различных чисел?

  1. Подходит последовательность нечётных чисел с шагом −2-2: 129,127,…,61129, 127, \ldots, 61 это 3535 различных чисел, все в границах, каждое следующее на 22 меньше предыдущего.

Ответ а): да\text{да}

б) Может ли быть 6060 различных чисел?

  1. Возьмём все нечётные числа от 129129 до 6161 с шагом −2-2 (их 3535), затем удвоим последнее: 61→12261\to122, и пойдём по чётным с шагом −2-2: 122,120,…,74122, 120, \ldots, 74 (ещё 2525 чисел). Всего 35+25=6035+25=60 различных чисел; удвоение допустимо, так как 122≤130122\le 130.

Ответ б): да\text{да}

в) Наибольшее количество различных чисел

  1. Пусть удвоение происходит у нечётного числа ee. Нечётные числа до удвоения идут только вниз (шаг −2-2 или повтор), поэтому все они лежат между ee и 129129, не более 129−e2+1\frac{129-e}{2}+1 различных. После удвоения идёт чётное число 2e2e; дальше чётные числа можно уменьшать на 22 и удваивать чётные x≤65x\le 65 (получаем числа до 128128). Поэтому все чётные числа лежат между 6060 и max⁡(2e,128)\max(2e,128) (число 130130 достигается только из e=65e=65). Посчитаем:

    e=61: нечётных 35 (61,…,129); чётных 35 (60,…,128); всего 70e=61:\ \allowbreak\text{нечётных }35\ (61,\ldots,129);\ \allowbreak\text{чётных }35\ (60,\ldots,128);\ \allowbreak\text{всего }70e=63: нечётных 34 (63,…,129); чётных 35 (60,…,128); всего 69e=63:\ \allowbreak\text{нечётных }34\ (63,\ldots,129);\ \allowbreak\text{чётных }35\ (60,\ldots,128);\ \allowbreak\text{всего }69e=65: нечётных 33 (65,…,129); чётных 36 (60,…,130); всего 69e=65:\ \allowbreak\text{нечётных }33\ (65,\ldots,129);\ \allowbreak\text{чётных }36\ (60,\ldots,130);\ \allowbreak\text{всего }69

    Авторский приём: в учебниках перечня этот шаг полностью не изложен.

  2. Если удвоения нет, все числа одной чётности: нечётных не более 3535, чётных не более 3636. Итак, наибольшее возможное значение равно 7070 (при e=61e=61).

  3. Пример: нечётные 129,127,…,61129, 127, \ldots, 61; затем 122122 (удвоили 6161); чётные вниз 122,120,…,64122, 120, \ldots, 64; затем удвоили 6464 и получили 2⋅64=1282\cdot64=128; и чётные вниз 128,126,…,60128, 126, \ldots, 60. Все числа в границах, различных чисел 7070.

Ответ в): 7070

Ответ: а) да; б) да; в) 70\text{а) да; б) да; в) }70

Учебные материалы: Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи, под ред. В. О. Бугаенко, МЦНМО, 2008, Инварианты; Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи, под ред. В. О. Бугаенко, МЦНМО, 2008, Чётность