Решение простых комбинаторных задач с помощью таблицы вариантов
Таблица вариантов для комбинаций из двух элементов
Допустим, мы бросаем два игральных кубика, и нас интересуют все комбинации, когда сумма выпавших чисел кратна 5.
Каждый из кубиков имеет 6 возможных «состояний»: 1,2,3,4,5,6.
Для того, чтобы описать все возможные комбинации двух кубиков, нужно составить таблицу вариантов:
Второй кубик | |||||||
1 | 2 | 3 | 4 | 5 | 6 | ||
Первый кубик | 1 | 11 | 12 | 13 | 14 | 15 | 16 |
2 | 21 | 22 | 23 | 24 | 25 | 26 | |
3 | 31 | 32 | 33 | 34 | 35 | 36 | |
4 | 41 | 42 | 43 | 44 | 45 | 46 | |
5 | 51 | 52 | 53 | 54 | 55 | 56 | |
6 | 61 | 62 | 63 | 64 | 65 | 66 |
Сумма выпавших чисел на кубиках кратна 5 в 7 случаях (ячейки таблицы закрашены). Общее количество возможных комбинаций – 36.
Правило суммы и правило произведения
Правило суммы: если элемент a можно выбрать m различными способами и независимо от него элемент b можно выбрать n различными способами, то выбрать все различные комбинации элементов «a или b» можно m + n способами.
ИЛИ $\iff$ "+"
Например:
Сколькими способами можно выбрать 1 ИЛИ 2 игроков из трёх кандидатов на участие в соревновании?
Одного игрока из трёх можно выбрать $C_3^1 = 3$ разными способами.
Двух игроков из трёх можно выбрать $C_3^2 = 3$ разными способами.
По правилу суммы у нас 3+3 = 6 способов для выбора.
Правило произведения: если элемент a можно выбрать m различными способами и независимо от него элемент b можно выбрать n различными способами, то все различные комбинации элементов «a и b» можно выбрать $m\cdot n$ способами.
И $\iff "\cdot"$
Например:
Сколько существует различных двузначных кодовых слов, состоящих из одной буквы И одной цифры, если разрешенные символы – это 5 букв «a,b,c,d,e» и 3 цифры «1,2,3»?
По правилу произведения число всех кодовых слов – всех возможных комбинаций: $m \cdot n = 5 \cdot 3 = 15$ слов.
Примеры
Пример 1. При составлении расписания завуч хочет на первый урок поставить алгебру или физику, а на второй – историю, географию или иностранный язык. Сколько существует вариантов расписания для первых двух уроков? Изобразите их с помощью таблицы вариантов.
Для первого урока есть m = 2 варианта.
Для второго урока n = 3 варианта.
По правилу произведения общее число вариантов для двух уроков
$mn = 2 \cdot 3 = 6$ вариантов.
2й урок |
||||
История |
География |
Иностранный язык |
||
1й урок |
Алгебра |
Алгебра История |
Алгебра География |
Алгебра Ин. язык |
Физика |
Физика История |
Физика Геграфия |
Физика Ин. язык |
Ответ: 6 вариантов
Пример 2. Из коробки с 12 фломастерами разного цвета один фломастер берет Коля, а за ним – один фломастер берет Петя. Сколько существует различных вариантов такого выбора фломастеров?
Перед Колей на выбор 12 фломастеров – у него m = 12 вариантов.
Перед Петей остаётся на выбор 11 фломастеров – у него n = 11 вариантов.
По правилу произведения общее число вариантов: $ mn = 12 \cdot 11 = 132$
Ответ: 132 варианта
Пример 3. Сколько различных трёхзначных чисел можно записать с помощью цифр 0,1,2,3,4,5, если а) цифры могут повторяться; б) цифры не повторяются.
а) цифры могут повторяться
В разряде сотен могут быть цифры 1,2,3,4,5, всего m=5 вариантов
В разряде десятков могут быть цифры 0,1,2,3,4,5, всего n=6 вариантов
В разряде единиц могут быть цифры 0,1,2,3,4,5, всего k=6 вариантов
По правилу произведения общее количество возможных трёхзначных чисел:
$$ mnk = 5 \cdot 6 \cdot 6 = 180 $$
б) цифры не повторяются
В разряде сотен могут быть цифры 1,2,3,4,5, всего m = 5 вариантов
В разряде десятков не цифра сотен, всего n = 5 вариантов
В разряде единиц не цифра десятков и не цифра сотен, всего k = 4 варианта
Всего $mnk = 5 \cdot 5 \cdot 4 = 100$
Ответ: а) 180; б) 100
Пример 4. Сколькими способами можно рассадить четырёх щенков по четырём углам комнаты?
У первого щенка $m_1 = 4$ варианта углов.
У второго щенка, т.к. один угол уже занят, остаётся $m_2 = 3$ варианта углов.
У третьего щенка, т.к. два угла уже заняты, остаётся $m_3 = 2$ варианта углов.
У четвертого щенка выбора нет, ему остался $m_4 = 1$ угол, без вариантов.
Общее количество способов по правилу произведения:
$$ m_1 \cdot m_2 \cdot m_3 \cdot m_4 = 4 \cdot 3 \cdot 2 \cdot 1 = 24 $$
Ответ: 24 способа
Пример 5. Сколько существует способов занять 1,2 и 3 места на чемпионате, в котором участвуют 10 команд?
Для того, чтобы занять 1-е место существует $m_1 = 10$ претендентов.
Если 1-е место определено, для 2-го места остаётся $m_2 = 9$ претендентов.
Если 1-е и 2-е определено, для 3-го места остаётся $m_3 = 8$ претендентов.
Итого, по правилу произведения:
$m_1 \cdot m_2 \cdot m_3 = 10 \cdot 9 \cdot 8 = 720$ вариантов распределения призовых мест.
Ответ: 720 способов