тема 7 из 7

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

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

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

Перебор целых чисел
—В аналитике

Организованный перебор

Перебор доказывает ответ, если в решении видно, откуда взялся конечный список кандидатов и что каждый кандидат проверен.

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

Сначала границы, потом проверка

Условие часто связывает число с величиной, которая меняется мало: сумма цифр четырёхзначного числа не больше 36, остаток при делении на $m$ — от 0 до $m - 1$ . Отсюда получается короткий отрезок для неизвестного. Числа этого отрезка отсеивают условием на остаток, а оставшиеся проверяют по одному.

Пример

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

1. $n < 2043$ , поэтому $S(n) \le 1 + 9 + 9 + 9 = 28$ и $n \ge 2043 - 28 = 2015$ .
2. $n$ и $S(n)$ дают одинаковые остатки при делении на 9 (сумма цифр), поэтому 2043 даёт тот же остаток, что $2n$ . 2043 делится на 9, значит, $2n$ делится на 9, и $n$ делится на 9.
3.От 2015 до 2042 на 9 делятся 2016, 2025 и 2034.
4.Проверка: $2016 + 9 = 2025$ , $2025 + 9 = 2034$ , $2034 + 9 = 2043$ . Подходит только 2034.

Ответ: 2034

Подсчёт по первой цифре

Чтобы сосчитать числа с условием на цифры, зафиксируйте первую цифру и сосчитайте варианты остальных. Две цифры от 0 до 9 с суммой $s$ образуют $s + 1$ упорядоченных пар при $s \le 9$ и $19 - s$ пар при $10 \le s \le 18$ : цифра не больше 9 отсекает часть пар.

Пример

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

1.Первая цифра $a$ — от 1 до 9, две другие цифры дают в сумме $15 - a$ .
2. $a = 1, \ldots, 5$ : сумма $15 - a$ от 14 до 10, пар $19 - (15 - a) = a + 4$ : 5, 6, 7, 8, 9.
3. $a = 6, \ldots, 9$ : сумма $15 - a$ от 9 до 6, пар $16 - a$ : 10, 9, 8, 7.
4.Всего $5 + 6 + 7 + 8 + 9 + 10 + 9 + 8 + 7 = 69$ .

Ответ: 69

Перебор раскладов цифр

Когда числа составляют из данных цифр, перебирайте не числа, а расклады цифр. Сначала признаки делимости отсекают почти все расклады: последняя цифра — по признаку делимости на 5 или на 2, сумма цифр каждого числа — по признаку делимости на 9 (признаки). Оставшиеся расклады выпишите все, а внутри каждого расставьте цифры по убыванию, чтобы получить наибольшее число.

Так же разбирают вычеркнутую цифру: случаев столько, сколько цифр в числе, и каждый случай записывают через разряды (вычеркнутая цифра).

Пример

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

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

Ответ: 1575

Перебор как обоснование в пункте в)

В пункте в) перебор заменяет оценку, только если он полный. Сначала докажите, что кандидатов конечное число: в задаче о сумме цифр трёхзначного числа это числа от 1 до 27. Потом разбейте кандидатов на группы и посчитайте каждую группу. Пропущенный случай — пробел в обосновании.

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

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

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

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

Решение

а) Пример: $S(2009) = 11$ , $S(11) = 2$ , числа 2009, 11, 2 различны, $2009 + 11 + 2 = 2022$ . Ответ: да.
б) Число и сумма его цифр дают одинаковые остатки при делении на 3 (сумма цифр). Все три числа дают один остаток $r$ , а их сумма — тот же остаток, что $3r$ : сумма делится на 3.
Сумма цифр 2021 равна 5, поэтому 2021 на 3 не делится. Ответ: нет.
в) Первое число трёхзначное, поэтому второе — его сумма цифр — от 1 до 27. Сумма цифр второго числа равна 2, поэтому второе число 2, 11 или 20.
Второе число не равно 2: иначе третье тоже 2, а числа различны. Остаются 11 и 20, и каждое первое число даёт одну тройку.
Сумма цифр 11: при первой цифре $a$ две другие дают $11 - a$ . При $a = 1$ сумма 10, пар 9. При $a = 2, \ldots, 9$ пар $12 - a$ : $10 + 9 + \ldots + 3 = 52$ . Всего 61 число.
Сумма цифр 20: две другие цифры дают $20 - a \le 18$ , поэтому $a \ge 2$ , и пар $19 - (20 - a) = a - 1$ . Всего $1 + 2 + \ldots + 8 = 36$ чисел.
Троек $61 + 36 = 97$ . Ответ: а) да; б) нет; в) 97.

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

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

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

Решать