7.4 Перебор вариантов

6 класс · Данные◷ 50–60 минут◇ БазаНужно знать: умножение натуральных чисел, деление на 2, аккуратная запись

В школьном буфете три напитка (чай, какао, сок) и два бутерброда (с сыром, с джемом). Завтрак — это один напиток и один бутерброд.

Спрашивать «сколько получится завтраков» бесполезно, пока не научился считать надёжно. Выписывать наугад — верный способ что-нибудь потерять. Вопрос урока: как перечислить все варианты так, чтобы ни один не пропал и ни один не повторился?

◎ После урока ты сможешь

• перечислять варианты систематически, а не наугад
• строить дерево вариантов и читать по нему готовый список
• применять правило умножения для подсчёта числа вариантов
• считать число пар, в которых порядок не важен

Прогноз

Три напитка и два бутерброда. Назови число завтраков, не выписывая их. Затем проверь себя: если бы напитков стало четыре, ответ вырос бы на $1$ или изменился как-то иначе?

Порядок вместо наугад

Систематический перебор устроен просто: зафиксируй первый выбор и перебери все продолжения; потом переходи к следующему первому выбору.

• чай + сыр, чай + джем;
• какао + сыр, какао + джем;
• сок + сыр, сок + джем.

Шесть завтраков. Каждый напиток встретился ровно один раз в паре с каждым бутербродом, поэтому пропусков нет, а повторов — тем более.

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

Тот же порядок удобно нарисовать. Из точки «начало» выходит по ветви на каждый напиток; из каждого напитка — по ветви на каждый бутерброд. Готовый вариант читается как путь от начала до конца ветви, а число вариантов равно числу листьев дерева.

Лаборатория перебора

Дерево вариантов и правило умножения

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

n₁ · n₂ · …

Шаг 1

Название шага

Варианты через запятую 3Не больше 4 вариантов на шаг.

Шаг 2

Название шага

Варианты через запятую 2Не больше 4 вариантов на шаг.

Добавить шагУбрать последний шагСбросить пример

Систематический перебор: первый шаг меняется медленнее всех

№	Напиток	Бутерброд
1	чай	с сыром
2	чай	с джемом
3	какао	с сыром
4	какао	с джемом
5	сок	с сыром
6	сок	с джемом

·

3 · 2 = 6 вариантов.Правило умножения: число вариантов на каждом шаге перемножается, потому что от каждой ветви отходит одинаковый набор продолжений.

∴ Правило умножения

Если выбор делается за несколько шагов и на первом шаге есть $n_1$ вариантов, на втором — $n_2$, …, на последнем — $n_k$, причём число вариантов на каждом шаге не зависит от предыдущего выбора, то всего получится

$N=n_1\cdot n_2\cdot\ldots\cdot n_k$

вариантов. На дереве это видно сразу: от каждой из $n_1$ ветвей отходит одинаковый пучок из $n_2$ ветвей.

Для завтрака: $3\cdot2=6$. Если добавить ещё выбор из двух булочек, станет $3\cdot2\cdot2=12$.

У этого правила есть и второе имя: в 9 классе его называют правилом произведения и ставят рядом с правилом суммы, которое отвечает на вопрос «или» (правила подсчёта). Название другое, формула та же.

Двузначные числа из цифр 1, 2, 3Разбираем вместе

Без повторения цифр. Первую цифру можно выбрать тремя способами. После этого одна цифра уже занята, поэтому на вторую остаётся два варианта:

$3\cdot2=6.$

Систематический список: $12$, $13$, $21$, $23$, $31$, $32$.

С повторением цифр. Занятость первой цифры больше не мешает, вторую тоже выбираем из трёх:

$3\cdot3=9.$

Список: $11$, $12$, $13$, $21$, $22$, $23$, $31$, $32$, $33$.

Важно, что в обоих случаях число вариантов на втором шаге одинаково для всех веток ($2$ и $2$ и $2$ либо $3$ и $3$ и $3$) — именно поэтому правило умножения работает.

Проверка понимания

В кафе 3 вида блинов и 4 вида начинок. Сколько разных блинов с одной начинкой можно заказать?

• А. 7
• Б. 12
• В. 34

Когда порядок не важен

Пять команд играют друг с другом по одному разу. Сколько будет матчей?

Каждая из $5$ команд встречается с $4$ соперниками — получается $5\cdot4=20$. Но матч «Астра — Барс» и матч «Барс — Астра» — это один и тот же матч, посчитанный дважды. Значит, ответ вдвое меньше:

$\frac{5\cdot4}{2}=10.$

Лаборатория перебора

Все пары без повторов

Перечисли объекты: лаборатория соберёт все пары, в которых порядок не важен.

n(n − 1) : 2

Объекты через запятую 5От 2 до 8 названий.

Сбросить пример

Таблица встреч: отмечаем только клетки выше главной диагонали

С кем	Астра	Барс	Вихрь	Гроза	Дельта
Астра	—	✓	✓	✓	✓
Барс	·	—	✓	✓	✓
Вихрь	·	·	—	✓	✓
Гроза	·	·	·	—	✓
Дельта	·	·	·	·	—

1. 1

   Астра — Барс

2. 2

   Астра — Вихрь

3. 3

   Астра — Гроза

4. 4

   Астра — Дельта

5. 5

   Барс — Вихрь

6. 6

   Барс — Гроза

7. 7

   Барс — Дельта

8. 8

   Вихрь — Гроза

9. 9

   Вихрь — Дельта

10. 10

    Гроза — Дельта

:

5 · 4 : 2 = 10 пар.Каждый объект образует пару с остальными, поэтому упорядоченных пар n · (n − 1). В паре порядок не важен, значит каждая пара посчитана дважды.

∴ Число пар без повторов

Из $n$ различных объектов можно составить

$\frac{n\,(n-1)}{2}$

пар, если порядок внутри пары не имеет значения. Так считают рукопожатия, матчи «каждый с каждым», отрезки между точками, по три из которых не лежат на одной прямой.

! Сложили вместо умножения — или забыли поделить

Две ошибки встречаются чаще всего.

Первая: «$3$ футболки и $4$ шорт — значит, $7$ комплектов». Нет: слово «и» здесь означает выбор на двух шагах, поэтому $3\cdot4=12$.

Вторая: «$6$ человек, каждый жмёт руку каждому — значит, $6\cdot5=30$ рукопожатий». Нет: каждое рукопожатие посчитано с двух сторон, поэтому $30:2=15$.

Проверяй себя вопросом: важен ли порядок? Пара «футболка и шорты» — это выбор разного сорта вещей, порядок неважен, но и повторов нет. Пара «А жмёт руку Б» и «Б жмёт руку А» — один и тот же факт, значит, делим на $2$.

Практика

1. Есть $3$ футболки и $4$ пары шорт. Сколько получится комплектов?
2. В меню $2$ супа, $3$ вторых блюда и $2$ напитка. Сколько разных обедов из трёх блюд можно составить?
3. Составь все двузначные числа из цифр $1$, $2$, $3$ без повторения цифр. Сколько их?
4. То же, но цифры можно повторять. Сколько чисел получится?
5. Составь все двузначные числа из цифр $0$, $1$, $2$ без повторения цифр.
6. В турнире $5$ команд, каждая играет с каждой по одному разу. Сколько матчей?
7. Шесть человек пожали друг другу руки по одному разу. Сколько было рукопожатий?
8. Кодовый замок состоит из трёх окошек, в каждом любая цифра от $0$ до $9$. Сколько разных кодов?
9. На первом шаге дерева $3$ ветви, из каждой на втором шаге выходит по $4$ ветви. Сколько листьев у дерева?
10. Почему систематический перебор надёжнее случайного выписывания?

Ответы и пояснения

1. $3\cdot4=12$ комплектов.
2. $2\cdot3\cdot2=12$ обедов.
3. $3\cdot2=6$: $12$, $13$, $21$, $23$, $31$, $32$.
4. $3\cdot3=9$: $11$, $12$, $13$, $21$, $22$, $23$, $31$, $32$, $33$.
5. Первой цифрой не может быть $0$, поэтому для неё $2$ варианта, а для второй — $2$ оставшиеся цифры: $2\cdot2=4$. Числа: $10$, $12$, $20$, $21$.
6. $\dfrac{5\cdot4}{2}=10$ матчей.
7. $\dfrac{6\cdot5}{2}=15$ рукопожатий.
8. $10\cdot10\cdot10=1000$ кодов: в коде первая цифра тоже может быть нулём.
9. $3\cdot4=12$ листьев.
10. При систематическом переборе есть правило, в каком порядке появляются варианты. Из него видно, что перебраны все продолжения каждого первого выбора, поэтому ничего не потеряно и ничего не повторено. Случайный список такой гарантии не даёт.

Итог

• Систематический перебор фиксирует первый выбор и перебирает все продолжения; порядок делает список полным.
• Дерево вариантов рисует этот порядок: путь от начала до листа — один вариант, число листьев — ответ.
• Правило умножения даёт число вариантов без выписывания: $N=n_1\cdot n_2\cdot\ldots\cdot n_k$.
• Если порядок внутри пары не важен, произведение $n(n-1)$ нужно разделить на $2$.
• Дальше — практикум, где таблицы, диаграммы, среднее и перебор понадобятся в одном проекте.

← Среднее арифметическое · Дальше: практикум →

Закончил урок?

Отметь прогресс — регистрация не нужна.

Отметить пройденным