Перебор целых чисел
Перебор целых чисел становится строгим доказательством, только когда вы заранее ограничили круг всех кандидатов. Сначала диапазон поиска сужают оценкой, делимостью или остатками, а затем проверяют каждый оставшийся случай в строгом порядке.
Перебор работает только с доказанными границами
Чтобы перебор засчитали на ЕГЭ, сначала докажите, что за пределами вашего списка решений быть не может, а затем проверьте каждого кандидата.
- Выпишите все ограничения из условия: разрядность, границы, различие чисел, делимость.
- Сузьте диапазон с помощью оценки (например, ) и остатков от деления.
- Разбейте кандидатов на непересекающиеся случаи — по первой цифре или по одной переменной.
- Проверьте каждый случай по всем условиям задачи, ничего не пропуская.
Как превратить перебор в доказательство
- 1
Зажмите неизвестное в узкий отрезок
Оцените величину сверху и снизу через максимум суммы цифр или границы условия — вместо тысяч чисел останутся десятки.
- 2
Отсейте лишнее делимостью
Проверьте остатки на 2, 3, 5 или 9: обычно после этого остаётся всего 3–5 кандидатов.
- 3
Проверьте оставшихся по порядку
Подставьте каждого кандидата в условие и явно запишите, подходит он или нет.
Оценка границ перед перебором
Если уравнение связывает число с ограниченной величиной (суммой цифр, остатком, количеством разрядов), замените эту величину её максимумом и минимумом. Вы сразу получите короткий отрезок для неизвестного.
После этого примените делимость — например, связь числа и суммы его цифр по остатку на 9 — и число кандидатов сократится до нескольких штук.
Частая ошибка. Не начинайте перебор наугад: даже если вы угадали все ответы, без доказательства границ эксперт не увидит, почему нет других решений.
Пример
Найдите все натуральные , для которых , где — сумма цифр числа .
- 1.Так как , максимум суммы цифр достигается у 1999: . Отсюда .
- 2.Число и дают одинаковые остатки на 9, поэтому даёт тот же остаток, что и . Число 2043 делится на 9, а 2 и 9 взаимно просты — значит, делится на 9.
- 3.В отрезке от 2015 до 2042 на 9 делятся лишь три числа: 2016, 2025 и 2034.
- 4.Проверяем каждого: , , . Подходит только 2034.
Ответ: 2034
Сколько пар цифр дают сумму s?
Готовая формула для двух цифр от 0 до 9 — экономит время при подсчёте чисел по первой цифре.
Если сумма s не больше 9
пар
Первая цифра пары пробегает значения от до . Например, сумму дают пар: от до .
Если сумма s от 10 до 18
пар
Вторая цифра не больше 9, поэтому первая не меньше . Например, сумму дают пар: от до .
Перебор по первой цифре
Чтобы сосчитать количество трёхзначных чисел с заданной суммой цифр , зафиксируйте первую цифру (от 1 до 9). Тогда сумма двух остальных цифр равна .
Для каждого количество пар мгновенно находится по формуле выше — остаётся сложить результаты.
Пример
Сколько существует трёхзначных чисел с суммой цифр 15?
- 1.Обозначим число , где и .
- 2.При сумма лежит от 14 до 10, поэтому пар : получаем .
- 3.При сумма лежит от 9 до 6, поэтому пар : получаем .
- 4.Всего трёхзначных чисел.
Ответ: 69
Разбиение цифр на группы
Когда числа собирают из заданного набора цифр, перебирают не сами числа, а распределение цифр по группам. Сначала признаки делимости фиксируют последние цифры (на 2 или 5) и суммы цифр в группах (на 3 или 9).
Когда состав каждой группы найден, для максимума расставляйте свободные цифры по убыванию слева направо. Похожий перебор по позициям используют и для вычеркнутой цифры.
Частая ошибка. Расставляя цифры внутри группы, не сдвигайте последнюю цифру, которую зафиксировал признак делимости, и проверяйте, чтобы ноль не оказался на первом месте числа.
Пример
Из цифр 0, 1, 5, 6, 7, 8 составили два трёхзначных числа, каждую цифру использовали ровно один раз. Оба числа делятся на 45. Какое наибольшее значение может принимать сумма этих чисел?
- 1.Делимость на требует делимости на 5 и на 9. Значит, одно число оканчивается на 0, а другое — на 5.
- 2.Сумма всех шести цифр равна . Суммы цифр двух чисел кратны 9 и не равны 0, значит, это 9 и 18.
- 3.Для числа с последней цифрой 5 две остальные цифры из должны дать в сумме (невозможно) или (только 6 и 7).
- 4.Состав групп единственен: и . Для наибольшей суммы ставим старшие цифры по убыванию: 765 и 810. Проверка: , .
- 5.Наибольшая сумма: .
Ответ: 1575
Исчерпывающий перебор в пункте в)
В пункте в) перебор засчитывают как строгое решение, только если он исчерпывающий: сначала вы ограничиваете круг всех возможных значений, а затем без пропусков разбираете каждую группу.
Частая ошибка. Один забытый случай (например, случай равенства двух чисел или лишний остаток) обнуляет обоснование. Всегда проверяйте, что ваши случаи не пересекаются и покрывают весь диапазон.
Пример задания
Открытый банк ФИПИ
На доске написаны три различных натуральных числа. Второе число равно сумме цифр первого, а третье равно сумме цифр второго.
а) Может ли сумма этих чисел быть равна 2022?
б) Может ли сумма этих чисел быть равна 2021?
в) В тройке чисел первое число трёхзначное, а третье равно 2. Сколько существует таких троек?
Проверьте себя
00