Задание 19
тема 7 из 7

Перебор целых чисел

Перебор целых чисел становится строгим доказательством, только когда вы заранее ограничили круг всех кандидатов. Сначала диапазон поиска сужают оценкой, делимостью или остатками, а затем проверяют каждый оставшийся случай в строгом порядке.

Реже в задании19На карте навыков

Перебор работает только с доказанными границами

Чтобы перебор засчитали на ЕГЭ, сначала докажите, что за пределами вашего списка решений быть не может, а затем проверьте каждого кандидата.

  • Выпишите все ограничения из условия: разрядность, границы, различие чисел, делимость.
  • Сузьте диапазон с помощью оценки (например, S(n)≤9kS(n) \le 9k) и остатков от деления.
  • Разбейте кандидатов на непересекающиеся случаи — по первой цифре или по одной переменной.
  • Проверьте каждый случай по всем условиям задачи, ничего не пропуская.

Как превратить перебор в доказательство

  1. 1

    Зажмите неизвестное в узкий отрезок

    Оцените величину сверху и снизу через максимум суммы цифр или границы условия — вместо тысяч чисел останутся десятки.

  2. 2

    Отсейте лишнее делимостью

    Проверьте остатки на 2, 3, 5 или 9: обычно после этого остаётся всего 3–5 кандидатов.

  3. 3

    Проверьте оставшихся по порядку

    Подставьте каждого кандидата в условие и явно запишите, подходит он или нет.

Оценка границ перед перебором

Если уравнение связывает число с ограниченной величиной (суммой цифр, остатком, количеством разрядов), замените эту величину её максимумом и минимумом. Вы сразу получите короткий отрезок для неизвестного.

После этого примените делимость — например, связь числа и суммы его цифр по остатку на 9 — и число кандидатов сократится до нескольких штук.

S(n)≤9k,n=M−S(n)≥M−9kS(n) \le 9k,\qquad n = M - S(n) \ge M - 9k

Частая ошибка. Не начинайте перебор наугад: даже если вы угадали все ответы, без доказательства границ эксперт не увидит, почему нет других решений.

Пример

Найдите все натуральные nn, для которых n+S(n)=2043n + S(n) = 2043, где S(n)S(n) — сумма цифр числа nn.

  1. 1.Так как n<2043n < 2043, максимум суммы цифр достигается у 1999: S(n)≤1+9+9+9=28S(n) \le 1 + 9 + 9 + 9 = 28. Отсюда n=2043−S(n)≥2015n = 2043 - S(n) \ge 2015.
  2. 2.Число nn и S(n)S(n) дают одинаковые остатки на 9, поэтому n+S(n)n + S(n) даёт тот же остаток, что и 2n2n. Число 2043 делится на 9, а 2 и 9 взаимно просты — значит, nn делится на 9.
  3. 3.В отрезке от 2015 до 2042 на 9 делятся лишь три числа: 2016, 2025 и 2034.
  4. 4.Проверяем каждого: 2016+9=20252016 + 9 = 2025, 2025+9=20342025 + 9 = 2034, 2034+9=20432034 + 9 = 2043. Подходит только 2034.

Ответ: 2034

Сколько пар цифр дают сумму s?

Готовая формула для двух цифр от 0 до 9 — экономит время при подсчёте чисел по первой цифре.

  • Если сумма s не больше 9

    s+1s + 1 пар

    Первая цифра пары пробегает значения от 00 до ss. Например, сумму 66 дают 77 пар: от (0;6)(0; 6) до (6;0)(6; 0).

  • Если сумма s от 10 до 18

    19−s19 - s пар

    Вторая цифра не больше 9, поэтому первая не меньше s−9s - 9. Например, сумму 1414 дают 55 пар: от (5;9)(5; 9) до (9;5)(9; 5).

Перебор по первой цифре

Чтобы сосчитать количество трёхзначных чисел с заданной суммой цифр ss, зафиксируйте первую цифру aa (от 1 до 9). Тогда сумма двух остальных цифр равна b+c=s−ab + c = s - a.

Для каждого aa количество пар (b;c)(b; c) мгновенно находится по формуле выше — остаётся сложить результаты.

b+c=s−a,1≤a≤9b + c = s - a,\qquad 1 \le a \le 9

Пример

Сколько существует трёхзначных чисел с суммой цифр 15?

  1. 1.Обозначим число abc‾\overline{abc}, где 1≤a≤91 \le a \le 9 и b+c=15−ab + c = 15 - a.
  2. 2.При a=1,2,3,4,5a = 1, 2, 3, 4, 5 сумма 15−a15 - a лежит от 14 до 10, поэтому пар 19−(15−a)=a+419 - (15 - a) = a + 4: получаем 5+6+7+8+9=355 + 6 + 7 + 8 + 9 = 35.
  3. 3.При a=6,7,8,9a = 6, 7, 8, 9 сумма 15−a15 - a лежит от 9 до 6, поэтому пар (15−a)+1=16−a(15 - a) + 1 = 16 - a: получаем 10+9+8+7=3410 + 9 + 8 + 7 = 34.
  4. 4.Всего 35+34=6935 + 34 = 69 трёхзначных чисел.

Ответ: 69

Разбиение цифр на группы

Когда числа собирают из заданного набора цифр, перебирают не сами числа, а распределение цифр по группам. Сначала признаки делимости фиксируют последние цифры (на 2 или 5) и суммы цифр в группах (на 3 или 9).

Когда состав каждой группы найден, для максимума расставляйте свободные цифры по убыванию слева направо. Похожий перебор по позициям используют и для вычеркнутой цифры.

Частая ошибка. Расставляя цифры внутри группы, не сдвигайте последнюю цифру, которую зафиксировал признак делимости, и проверяйте, чтобы ноль не оказался на первом месте числа.

Пример

Из цифр 0, 1, 5, 6, 7, 8 составили два трёхзначных числа, каждую цифру использовали ровно один раз. Оба числа делятся на 45. Какое наибольшее значение может принимать сумма этих чисел?

  1. 1.Делимость на 45=5⋅945 = 5 \cdot 9 требует делимости на 5 и на 9. Значит, одно число оканчивается на 0, а другое — на 5.
  2. 2.Сумма всех шести цифр равна 0+1+5+6+7+8=270 + 1 + 5 + 6 + 7 + 8 = 27. Суммы цифр двух чисел кратны 9 и не равны 0, значит, это 9 и 18.
  3. 3.Для числа с последней цифрой 5 две остальные цифры из {1,6,7,8}\{1, 6, 7, 8\} должны дать в сумме 9−5=49 - 5 = 4 (невозможно) или 18−5=1318 - 5 = 13 (только 6 и 7).
  4. 4.Состав групп единственен: {5,6,7}\{5, 6, 7\} и {0,1,8}\{0, 1, 8\}. Для наибольшей суммы ставим старшие цифры по убыванию: 765 и 810. Проверка: 765=45⋅17765 = 45 \cdot 17, 810=45⋅18810 = 45 \cdot 18.
  5. 5.Наибольшая сумма: 765+810=1575765 + 810 = 1575.

Ответ: 1575

Исчерпывающий перебор в пункте в)

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

Частая ошибка. Один забытый случай (например, случай равенства двух чисел или лишний остаток) обнуляет обоснование. Всегда проверяйте, что ваши случаи не пересекаются и покрывают весь диапазон.

Пример задания

Открытый банк ФИПИ

На доске написаны три различных натуральных числа. Второе число равно сумме цифр первого, а третье равно сумме цифр второго.

а) Может ли сумма этих чисел быть равна 2022?
б) Может ли сумма этих чисел быть равна 2021?
в) В тройке чисел первое число трёхзначное, а третье равно 2. Сколько существует таких троек?

Проверьте себя

00

Потренируйте навык

Все задания на этот навык

Решать