Прямой перебор

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

Статья

Конспект

Задачи

Правила перебора

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

Чтобы этого не происходило, надо выполнять правила перебора:

Правила перебора

1
Каждому элементу дать уникальное и короткое обозначение.
2
Придумать удобный алгоритм перебора и строго ему следовать.

Насыщенный день

Пётр должен убраться в комнате, сделать домашнее задание и поработать над личным проектом. Сделать нужно всё, но Пётр ещё не решил, в какой последовательности. Сколькими способами он может выбрать эту последовательность?

Решение

Обозначим уборку в комнате буквой «У», домашнее задание буквой «Д», а работу над личным проектом буквой «П». Введя эти обозначения, мы выполнили первый пункт правил перебора.

Перебирать будем так: сначала разберем варианты, когда буква «У» стоит первой, потом второй, затем последней. Введя такой порядок мы выполнили второй пункт правил перебора. Приступаем:

\bm{У}\text{ДП} \quad \bm{У}\text{ПД} \\ \text{Д}\bm{У}\text{П} \quad \text{П}\bm{У}\text{Д} \\ \text{ДП}\bm{У} \quad \text{ПД}\bm{У}

Всего 6 способов распланировать 3 дела на день.

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

В поисках чисел

Сколько существует четырехзначных чисел, сумма цифр которых меньше 4?

Решение

Мы работаем с числами, поэтому уникальные обозначения вводить не надо. Но все еще нужно выполнить второе правило перебора — придумать удобный алгоритм.

Чтобы не запутаться, не потерять и лишний раз не засчитать числа, будем указывать их в порядке возрастания: от маленьких к большим. То есть каждое следующее число должно быть больше предыдущего. И помним, что сумма цифр в числе должна быть меньше 4, то есть равна 1, 2 или 3.

1000, \ 1001, \ 1002, \ 1010, \ 1011, \ 1020, \ 1100, \ 1101, \ 1110, \ 1200, \\ 2000, \ 2001, \ 2010, \ 2100, \\ 3000

Дерево вариантов

Часто бывает сложно выполнить второе правило перебора. С этим может помочь универсальный механизм:

Дерево вариантов

Универсальный алгоритм построения и перебора комбинаций.
В этом алгоритме все варианты обозначаются в виде расходящихся «веток дерева».

Лучшие из лучших

Для полета на Марс требуется собрать команду. На место командира есть 4 кандидата: $c_1, c_2, c_3, c_4$ . На место инженера 3 кандидата: $i_1, i_2, i_3$ . На место врача тоже 3 кандидата: $v_1, v_2, v_3$ .

Проверка показала, что командир $c_1$ психологически совместим с инженерами $i_1$ и $i_3$ и врачами $v_2, v_3$ . Командир $c_2$ — с инженерами $i_1, i_2$ и всеми врачами. Командир $c_3$ — с инженерами $i_1, i_2$ и врачами $v_1, v_3$ . Командир $c_4$ — только с инженером $i_3$ и всеми врачами.

Кроме того, инженер $i_1$ психологически несовместим с врачом $v_3$ , инженер $i_2$ — с врачом $v_1$ и инженер $i_3$ — с врачом $v_2$ .

Сколькими способами при этих условиях может быть составлена команда корабля?

Решение

Обратите внимание, что в задаче уже за нас ввели уникальные обозначения для каждого кандидата. То есть первое правило прямого перебора уже выполнено. Осталось только разобраться с алгоритмом и вот тут нам на помощь приходит дерево вариантов.

Из стартового угла в разные стороны добавим четыре ветки первого уровня, по одной на каждого капитана:

Все капитаны, кроме $c_4$ , совместимы с двумя инженерами. Поэтому добавляем по две ветки второго уровня трем капитанам и одну ветку второго уровня четвертому капитану:

Осталось только добавить ветки третьего уровня, которые соответствуют врачам. Делать это надо аккуратно, учитывая психологическую совместимость. Например, к ветке $c_1, i_1$ можно добавить только одну ветку с врачом $v_2$ , так как $c_1$ несовместим с врачом $v_1$ , и оба $c_1$ и $i_1$ не совместимы с врачом $v_3$ .

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

Деревья могут быть любыми

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

Экспериментируйте!

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

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

Источники10

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

Комбинаторика

Виленкин Н.Я., Виленкин А.Н., Виленкин П.А., 7-е издание, МЦНМО, 2019

Почти идеальная подача теории через жизненные примеры. Интересные задачи. Широчайший охват тем, в том числе и из высшей математики.

3. Команда космического корабля

4. Правила суммы и произведения

Задачи 20 и 21

Комбинаторика — олимпиаднику

Материалы по математике. Игорь Вячеславович Яковлев

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

1. Перебор вариантв

Википедия

Свободная энциклопедия