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

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

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

а) Может ли быть 40 различных чисел в последовательности?

б) Может ли быть 80 различных чисел в последовательности?

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

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

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

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

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

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

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

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

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

  1. Возьмём все нечётные числа от 169169 до 8181 с шагом −2-2 (их 4545), затем удвоим последнее: 81→16281\to162, и пойдём по чётным с шагом −2-2: 162,160,…,94162, 160, \ldots, 94 (ещё 3535 чисел). Всего 45+35=8045+35=80 различных чисел; удвоение допустимо, так как 162≤170162\le 170.

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

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

  1. Пусть удвоение происходит у нечётного числа ee. Нечётные числа до удвоения идут только вниз (шаг −2-2 или повтор), поэтому все они лежат между ee и 169169, не более 169−e2+1\frac{169-e}{2}+1 различных. После удвоения идёт чётное число 2e2e; дальше чётные числа можно уменьшать на 22 и удваивать чётные x≤85x\le 85 (получаем числа до 168168). Поэтому все чётные числа лежат между 8080 и max⁡(2e,168)\max(2e,168) (число 170170 достигается только из e=85e=85). Посчитаем:

    e=81: нечётных 45 (81,…,169); чётных 45 (80,…,168); всего 90e=81:\ \allowbreak\text{нечётных }45\ (81,\ldots,169);\ \allowbreak\text{чётных }45\ (80,\ldots,168);\ \allowbreak\text{всего }90e=83: нечётных 44 (83,…,169); чётных 45 (80,…,168); всего 89e=83:\ \allowbreak\text{нечётных }44\ (83,\ldots,169);\ \allowbreak\text{чётных }45\ (80,\ldots,168);\ \allowbreak\text{всего }89e=85: нечётных 43 (85,…,169); чётных 46 (80,…,170); всего 89e=85:\ \allowbreak\text{нечётных }43\ (85,\ldots,169);\ \allowbreak\text{чётных }46\ (80,\ldots,170);\ \allowbreak\text{всего }89

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

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

  3. Пример: нечётные 169,167,…,81169, 167, \ldots, 81; затем 162162 (удвоили 8181); чётные вниз 162,160,…,84162, 160, \ldots, 84; затем удвоили 8484 и получили 2⋅84=1682\cdot84=168; и чётные вниз 168,166,…,80168, 166, \ldots, 80. Все числа в границах, различных чисел 9090.

Ответ в): 9090

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

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