Решение задач на перебор возможных вариантов.
Предмет: Математика, 5 класс
Автор: Вольфсон Георгий Игоревич

Всем привет! Как вы знаете, существует масса способов решать задачи. Некоторые из них сложнее, некоторые проще. Причём обычно более сложная идея влечёт за собой более короткое решение и наоборот. Условно говоря, если подобрать к задаче ключик – она решится быстро и красиво. Прекрасно! А что бы мы стали делать, если перед нами была бы закрытая на ключ дверь, а перед ней валялось бы штук 15 ключей? Правильно, пришлось бы вставлять каждый и пробовать. Это и есть перебор вариантов, и именно этим мы сегодня будем заниматься. Сразу обратим внимание на то, что есть два типа перебора: полный и неполный. Полный перебор – это когда было 15 ключиков, и мы пробуем один за другим, пока какой-то не подойдёт. Неполный же, если мы перебираем не все ключи, а некоторые сразу отбрасываем, используя некоторые соображения (например, какие-то ключи можно не пробовать, так как они визуально слишком велики или слишком малы для этого замка).

А вот как эта идея работает в задачах.

Задача 1. Сколько трёхзначных чисел можно составить, используя только цифры 0, 1 и 2?

Решение. Разумеется, можно попытаться решить эту задачу комбинаторно, но есть и надежный способ – перебор всех вариантов. Похожую задачу мы разбирали в теме «графы», сейчас я напомню вам про то, что такое дерево вариантов и как его применять. Впрочем, само дерево мы рисовать не будем.

Итак, на первое место можно поставить 1 или 2.

1) Поставим 1. Тогда на второе место можно поставить 0, 1 или 2. Да-да, не забудьте про 1! Никто не говорил, что все цифры надо использовать ровно по разу! Получаем сочетания 10, 11 и 12. Для 10 есть числа 100, 101, 102. Для 11 есть числа 110, 111, 112. Для 12 есть числа 120, 121, 122. Итого, 9 чисел

2) Пусть первая цифра – 2. Тогда дальше может стоять 0, 1 или 2. Опять же, имеем: 200, 201, 202, 210, 211, 212, 220, 221, 222. 9 чисел.

Таким образом, всего получается 18 чисел.

Кстати, во время этого перебора я применил ещё одну идею: каждый раз я шёл от меньшей цифры к большей, чтобы ничего не пропустить. Можно сказать, выстроил числа «по алфавиту». Такой порядок иногда ещё называют лексикографическим, впрочем, чаще это применяют к словам, а не к числам.

И ещё замечание. Разумеется, я мог ограничиться только первым случаем, а во втором заметить, что чисел будет столько же, просто первая цифра будет не 1, а 2! Это и есть неполный перебор, когда мы что-то перебрали, а что-то уже не стали, увидев закономерность.

Задача 2. Какую цифру нужно приписать справа к шестерке, чтобы получить число, в 16 раз большее исходной цифры?

Решение. Итак, нас просят найти цифру. Но цифр всего 10! Значит можно просто перебрать 10 вариантов, проверить каждый и записать ответ. Так и сделаем.

Ответ: 4.

Думаю, теперь вам понятно, почему метод полного перебора иногда ещё называют методом грубой силы? Да-да, мы вообще не думали в этой задаче, а тупо перебрали все варианты. В той аналогии с дверью, можно считать, что мы не искали ключ, а просто выбили дверь ногой, не применив никакого интеллекта. Зато действенно!

Впрочем, можно было, конечно, не перебирать все варианты. Например, можно было заметить, что число, в 16 раз большее нашей цифры – чётно, а значит и приписать к шестёрке надо чётную цифру. Так что перебирать нечётные не нужно было. Можно было и вовсе решить задачу без перебора: заметить, что нам нужно двузначное число, начинающееся на 6 и делящееся на 16, такое число только одно: 64. Делим его на 16, получаем 4 – подходит.

С другой стороны, если других идей нет, то лучше перебор, чем не решить задачу, правда? Так что этот метод тоже следует иметь в виду. Впрочем, иногда вариантов будет 100 или 1000, тут перебор будет уже затруднителен…

Кстати, перебор применяется и в так называемых числовых ребусах. Например, вот в таком.

Задача 3. Найти все решения ребуса: ОДИН + ОДИН = МНОГО.

Решение. В начале комментарий: каждая буква заменяет цифру, при этом разные буквы – это разные цифры. Здесь нам поможет перебор, но лучше, конечно ещё и подумать.

1) Заметим, что М – единица, так как другого перехода через десяток при сложении двух чисел не бывает.

2) Значит, О + О даёт переход через десяток, а тогда О – 5, 6, 7, 8 или 9.

3) Кроме того, Н + Н оканчивается на О, значит, О – чётная цифра. Тогда О – 6 или 8. Разберём эти варианты.

4) О = 6. Тогда получаем: 6ДИН + 6ДИН = 1Н6Г6. Тогда Н может быть 3 или 8.

a. Н = 3. Тогда 6ДИ3 + 6ДИ3 = 136Г6. Чтобы 6 + 6 = 13, нужен переход. Значит, Д хотя бы 5. При этом Д + Д (возможно, с переходом от И) оканчивается на 6. Значит, Д = 8. Тогда перехода быть не должно. Подбираем такие И и Г, что И + И = Г, при этом цифры 1, 3, 6, 8 уже заняты. Остаются только 2 и 4. Окончательно: 6823 + 6823 = 13646.

b. Н = 8. Получаем: 6ДИ8 + 6ДИ8 = 186Г6. Но 6 + 6 не равно 18 даже с учётом переноса 1.

5) О = 8. Тогда получаем: 8ДИН + 8ДИН = 1Н8Г8. Тогда Н может быть 4 или 9. Но тогда 8 + 8, возможно, ещё с переходом, равно 14 или 19, что невозможно.

Ответ: 6823 + 6823 = 13646.

Вот так перебор помог решить задачу. Впрочем, он был неполным: если бы мы перебирали все варианты каждой буквы – не закончили бы и завтра. А вот урок мы закончили. До встречи!

Дополнительная информация

Рекомендуемые тренажёры:

1. В племени ЫУЫ в алфавите есть всего две буквы: У и Ы. Сколько различных слов из трёх букв существует в словаре племени? Ответ: 8.

2. Какую цифру надо вписать между 1 и 9, чтобы получить число, на 133 большее квадрата искомой цифры? Ответ: 6.

3. Найти хотя бы одно решение ребуса: КОЗА + КОЗА = СТАДО. Ответ: Например, 5673 + 5673 = 10346.

Рекомендуемые тесты:

1. В племени ХРЮ в алфавите есть всего три буквы: Х, Р и Ю. Сколько различных слов из двух букв существует в словаре племени? Ответ: 9.

2. Какую цифру надо вписать между 2 и 5, чтобы получить число, на 221 большее увосьмерённой искомой цифры? Ответ: 8.

3. Найти все решения ребуса: КНИГА + КНИГА + КНИГА = НАУКА. Ответ: 28 375 + 28 375 + 28 375 = 85 125.