Комбинаторика: дерево вариантов
В уроке «Логические задачи, перебор» вы перебирали варианты по порядку, чтобы ничего не пропустить. Теперь научимся рисовать перебор в виде дерева вариантов: построим дерево из двух ярусов, сосчитаем пути, поймем, почему число вариантов находят умножением, и решим задачи про числа из цифр и расписание.
Вопрос, к которому мы вернемся во втором разделе: в столовой на первое есть 3 супа, на второе — 2 блюда. Сколько разных обедов из одного супа и одного второго блюда можно составить?
Каждый выбор — новый ярус веток
Решавр выбирает обед. Супы: щи, борщ, уха. Вторые блюда: котлета, плов. Он рисует по условию карту своих выборов. Слева ставит точку — это корень, начало выбора. От корня проводит три ветки, по одной на каждый суп: это первый ярус. Конец каждой ветки назовем вершиной: у первого яруса три вершины — щи, борщ, уха.
Теперь второй выбор. Решавр взял щи — к ним можно котлету или плов, значит, от вершины «щи» идут две ветки. Взял борщ — снова две ветки. Взял бы уху — тоже две. Получился второй ярус: по две ветки от каждой вершины первого яруса.
Определение
Дерево вариантов — рисунок, на котором каждый выбор изображен отдельным ярусом веток: ветка — один вариант этого выбора. Конец ветки называется вершиной. Цепочка веток от корня до конца ветки последнего яруса называется путем, каждый путь — один готовый вариант.
Правило
Как построить дерево вариантов:
- Из корня проведите ветки ко всем вариантам первого выбора.
- От каждой вершины первого яруса проведите ветки ко всем вариантам второго выбора.
- Прочитайте пути от корня до концов веток — это и есть все варианты.
Почему ничего не потеряно и ничего не повторилось? Каждый обед — это суп и второе блюдо. Суп указывает ветку первого яруса, второе блюдо — ветку второго яруса, вместе они дают ровно один путь. Разные обеды идут по разным путям, поэтому дерево — полная карта всех вариантов.
Постройте дерево самостоятельно. Есть два напитка: чай и какао, и четыре вида печенья: овсяное, сахарное, ореховое, шоколадное. К каждому напитку можно взять любое печенье. Набор — один напиток и одно печенье. Нарисуйте дерево из двух ярусов, подпишите все ветки и выпишите все наборы, проходя по каждому полному пути. Одного числа наборов недостаточно: проверьте продолжения у каждого напитка.
Подсказка к построению
Скрыть
Первый ярус посвятите напиткам. Для каждой его вершины отдельно проверьте, какие виды печенья разрешает условие. Затем прочитайте каждый путь от корня до конца второго яруса.
Проверка построенного дерева
Скрыть
От корня идут ветки «чай» и «какао». От каждой из этих двух вершин должны идти четыре ветки: «овсяное», «сахарное», «ореховое», «шоколадное».
Полные пути: чай — овсяное, чай — сахарное, чай — ореховое, чай — шоколадное; какао — овсяное, какао — сахарное, какао — ореховое, какао — шоколадное. Всего $2 \cdot 4 = 8$ наборов. Сверьте и подписи веток, и список путей. Если печенье нарисовано только у одного напитка, потеряны все наборы со вторым напитком.
Вариантов столько, сколько путей
Вернемся к вопросу из начала урока. Пройдем по дереву Решавра все пути сверху вниз: щи — котлета, щи — плов, борщ — котлета, борщ — плов, уха — котлета, уха — плов. Концов у веток второго яруса шесть, и путей шесть. Значит, разных обедов 6.
Посмотрим, как устроено дерево: 3 группы веток, в каждой по 2. Сосчитать концы можно не по одному, а группами: $3 \cdot 2 = 6$.
Ошибка
Иксератопс отвечает сразу: «Супов 3, вторых 2, всего $3 + 2 = 5$ обедов».
Проверка на рисунке. На дереве 6 путей, и каждый из них — настоящий обед. Назовите пять обедов Иксератопса — шестой все равно останется. Число 5 — это сколько блюд в меню, а не сколько обедов из них можно составить.
Где сломалось. Сложение подходит, когда выбирают одно блюдо из всех: суп или второе. А обед — это суп и второе: к каждому супу подходит каждое второе блюдо. Поэтому каждый суп дает целую группу обедов, и группы складываются: $2 + 2 + 2 = 3 \cdot 2$.
Ошибка
Вторая ошибка — в самом рисунке. Иксератопс провел ветки «котлета» и «плов» только от вершины «щи», а от борща и ухи забыл. На его дереве всего 2 полных пути: он потерял четыре обеда.
Как проверить. Посчитайте ветки у каждой вершины первого яруса: их должно быть поровну, столько, сколько вариантов второго выбора. Если у какой-то вершины веток нет, дерево недорисовано.
Когда дерево большое, считаем умножением
Дерево удобно, пока веток немного. Но посмотрите, как оно устроено: от каждой вершины первого яруса идет одинаковое число веток. Значит, все пути делятся на равные группы, и их число можно найти умножением, даже не рисуя дерево целиком.
Пример 1
Из деревни в город ведут 3 дороги, из города к озеру — 4 тропинки. Сколькими разными маршрутами можно пройти из деревни к озеру через город?
Решение. Первый выбор — дорога: 3 варианта, это первый ярус. Второй выбор — тропинка: 4 варианта, и подходит любая, какой бы дорогой вы ни пришли. От каждой из 3 вершин идут 4 ветки: 3 группы по 4 пути. Всего $3 \cdot 4 = 12$ маршрутов.
Проверка. Сложение $3 + 4 = 7$ дает число всех дорог и тропинок, а маршрут — это дорога и тропинка.
Ответ: 12 маршрутов.
Правило
Если первый выбор можно сделать $n$ способами, а второй — $m$ способами при любом первом, то вариантов из двух выборов
$$n \cdot m$$
Теперь дерево можно не рисовать. В магазине 8 видов тетрадей и 6 видов обложек. Набор «тетрадь и обложка» можно выбрать $8 \cdot 6 = 48$ способами. Нарисовать 48 путей долго, а умножить — одно действие.
В модели ниже меняйте число супов и вторых блюд: дерево перестраивается, а под ним пересчитываются пути и «счет Иксератопса». Добейтесь, чтобы обедов было 12. Затем найдите настройку, при которой сложение случайно дает верный ответ.
Решение задачи-вызова
Скрыть
12 обедов получится при 4 супах и 3 вторых: $4 \cdot 3 = 12$. В модели можно взять не больше 4 супов и не больше 3 вторых, поэтому других вариантов нет. Счет Иксератопса совпадает с верным только при 2 супах и 2 вторых: $2 + 2 = 4$ и $2 \cdot 2 = 4$. Это совпадение: при любых других числах сложение ошибается.
Вызов: три выбора подряд
Скрыть
Флажок из трех горизонтальных полос. Верхняя полоса — белая или синяя, средняя — белая или красная, нижняя — зеленая или желтая. Сколько разных флажков?
Теперь выборов не два, а три, и у дерева три яруса. От корня — 2 ветки (верхняя полоса). От каждой из них — по 2 ветки (средняя): уже $2 \cdot 2 = 4$ пути. От каждого из этих 4 концов — снова по 2 ветки (нижняя): $4 \cdot 2 = 8$. Каждый новый ярус умножает число путей: $2 \cdot 2 \cdot 2 = 8$ флажков.
Числа из цифр: можно ли повторять цифру
Двузначное число — это тоже два выбора подряд: первая цифра и вторая цифра. Значит, его можно изобразить деревом, где первый ярус — первая цифра, второй ярус — вторая.
Возьмем цифры 1, 2 и 5. Если цифры могут повторяться, от каждой первой цифры идут 3 ветки: 1, 2 и 5. Получаются числа 11, 12, 15, 21, 22, 25, 51, 52, 55 — их $3 \cdot 3 = 9$.
Пример 2
Сколько двузначных чисел можно записать цифрами 1, 2 и 5, если цифры в числе не повторяются?
Решение. Первую цифру выбираем 3 способами. Вторая цифра — любая, кроме уже взятой: остается 2 способа. На дереве от каждой вершины первого яруса идут уже не 3, а 2 ветки: ветки 11, 22 и 55 вычеркнуты. Всего $3 \cdot 2 = 6$ чисел: 12, 15, 21, 25, 51, 52.
Проверка. Из 9 чисел с повторами убрали 3 числа из одинаковых цифр: $9-3 = 6$.
Ответ: 6 чисел.
Правило
Если цифры могут повторяться, во втором ярусе столько же веток, сколько цифр. Если не могут — на одну меньше: взятую цифру второй раз не берем.
Важно
Двузначное число не начинается с нуля: если среди цифр есть 0, в первом ярусе ветки «0» нет. Например, цифры 0, 4, 7 с повторами: первая цифра — 4 или 7, вторая — любая из трех, всего $2 \cdot 3 = 6$ чисел: 40, 44, 47, 70, 74, 77.
Числа 12 и 21 — разные: у них разные первые цифры, и на дереве это разные пути. Перед подсчетом прочитайте условие: можно ли повторять цифры. От этого зависит, сколько веток во втором ярусе.
Запрет в условии вычеркивает ветки
Иногда не все пути подходят: условие что-то запрещает. Тогда Решавр рисует дерево целиком и вычеркивает ветки, которые нарушают условие. Оставшиеся пути и есть ответ.
Пример 3
В субботу у класса два урока, и это два разных предмета из трех: математика, русский язык, музыка. Музыка не может быть первым уроком. Сколько разных расписаний на субботу можно составить?
Решение. 1) Без запрета: первый урок — 3 способа, второй — любой из двух оставшихся предметов: $3 \cdot 2 = 6$ расписаний. 2) Запрет вычеркивает вершину «музыка» первого яруса вместе с ее двумя ветками: $6-2 = 4$. 3) Перечислим оставшиеся пути: математика — русский, математика — музыка, русский — математика, русский — музыка. 4) Можно и по веткам: от «математики» 2 ветки, от «русского» 2, от «музыки» 0, всего $2 + 2 + 0 = 4$.
Проверка. Если сразу не брать музыку первой, первым остаются 2 предмета (математика или русский), вторым — любой из 2 оставшихся: $2 \cdot 2 = 4$.
Ответ: 4 расписания.
Правило
Если условие запрещает часть вариантов, найдите все варианты, а потом вычтите запрещенные. Или сразу не рисуйте запрещенные ветки и посчитайте оставшиеся пути. Когда у вершин разное число веток, считайте пути по каждой вершине отдельно и складывайте.
Вывод
Дерево вариантов помогает, когда нужно сосчитать, сколькими способами можно что-то выбрать: обед, наряд, маршрут, число из цифр, расписание. Нарисуйте выборы ярусами, проверьте, что ветки идут от каждой вершины, и прочитайте пути. Если первый выбор имеет $n$ вариантов, а после каждого первого выбора остается ровно $m$ допустимых продолжений, всего $n \cdot m$ вариантов. Если продолжений разное число, посчитайте их отдельно для каждой ветки и сложите.
| Случай | Что видно на дереве | Как считать |
|---|---|---|
| Два выбора: $n$ первых вариантов, после каждого — ровно $m$ допустимых вторых | $n$ групп по $m$ веток | $n \cdot m$ |
| Выбирают одно из всех: это или то | Один ярус из $n + m$ веток | $n + m$ |
| Три разные ненулевые цифры; повторы разрешены | 3 первые ветки, от каждой — по 3 вторые | $3 \cdot 3 = 9$ |
| Три разные ненулевые цифры; повторы запрещены | 3 первые ветки, от каждой — по 2 вторые | $3 \cdot 2 = 6$ |
| Цифры 0, 4, 7; повторы разрешены | 2 первые ветки, от каждой — по 3 вторые | $2 \cdot 3 = 6$ |
| Цифры 0, 4, 7; повторы запрещены | 2 первые ветки, от каждой — по 2 вторые | $2 \cdot 2 = 4$ |
| Есть запрет | Часть веток вычеркнута | все пути − запрещенные |
Часто задаваемые вопросы
Складывают, когда выбирают одну вещь из всех вместе: суп или второе. Для пары вещей умножают, когда к каждому первому выбору подходит одинаковое число вторых: например, каждый суп можно сочетать с каждым вторым блюдом. Если сомневаетесь, нарисуйте дерево из двух ярусов с маленькими числами и посчитайте пути.
В задаче про меню можно начать со вторых блюд: будет 2 вершины по 3 ветки, и путей снова 6: $2 \cdot 3 = 3 \cdot 2$. Каждый суп можно сочетать с каждым вторым блюдом. В задачах с ограничениями порядок выбора тоже можно менять, но ограничения нужно сохранить за теми же ролями. Например, для двузначных чисел из цифр 0, 4, 7 с повторами можно сначала выбрать единицы (0, 4 или 7), затем десятки (только 4 или 7). Ноль в десятках по-прежнему запрещен: запись 04 не станет двузначным числом. Получатся те же 40, 44, 47, 70, 74, 77 — всего 6 чисел.
Двузначное число не начинается с нуля, поэтому в первом ярусе ветки «0» нет (см. раздел о числах из цифр). Если цифры 0, 4, 7 еще и не повторяются: первая цифра — 4 или 7 (2 способа), вторая — одна из двух оставшихся. Получается $2 \cdot 2 = 4$ числа: 40, 47, 70, 74.
Дерево показывает, почему работает умножение, и помогает в задачах с запретом, где ветки вычеркивают. Когда вариантов немного, по дереву удобно выписать их все и проверить ответ.
Переходите к следующим темам и закрепляйте пройденное на практике.
- Более 330 000 пользователей по всей России, из них 39 000 учителей.
- Повышение среднего балла по предмету до 20 % после месяца занятий.
- Всплеск интереса к учебе и более глубокое понимание предметов.
Создайте бесплатный аккаунт — и откройте больше возможностей:
- Отслеживайте прогресс освоения тем
- Получайте персональные подборки полезных уроков и заданий
- Проводите работу над ошибками после занятий