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

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

Галактический дальнобойщик

«Путь неблизкий... и опасный» — вдохнул капитан грузового космического корабля. Ему поступил большой заказ. Сначала надо посетить звездное скопление Омега Центавра, забрать груз и доставить на окраину галактики Андромеда.

Из Млечного Пути на Омегу Центавра есть 3 основных звездных маршрута. А из Омега Центавры в Андромеду 4. Некоторые пути быстрее, но и вероятность встретить пиратов там больше. Какой же путь выбрать?

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

Если мы полетим по верхнему пути до Омеги Центавра, то потом у нас будет 4 варианта из нее попасть в Андромеду. Но также 4 варианта у нас будет, если до Омеги Центавра мы доберемся по среднему пути, да и по нижнему тоже. Значит всего существует 12 возможных маршрутов:

\underbrace{4}_{\text{Верхний}} + \underbrace{4}_{\text{Средний}} + \underbrace{4}_{\text{Нижний}} = 12

Заметим, что мы складываем число способов попасть в Андромеду (4) с самим собой столько раз, сколько у нас есть вариантов попасть на Омегу Центавра (3). Это можно записать короче, через умножение:

\underbrace{3}_{\text{Омега Центавра}} \times \underbrace{4}_{\text{Андромеда}} = 12

Получается интересная ситуация. Вне зависимости от того, какой из 3 путей мы использовали, чтобы добраться до Омеги Центавра, после этого у нас есть 4 способа добраться до Андромеды. А количество всех возможных маршрутов для выполнения заказа получается с помощью умножения: $3 \cdot 4 = 12$ .

Обновление гардероба

Елена собралась обновить свой гардероб. В местном магазине одежды продаются юбки, штаны, футболки и блузки. По цветам любой элементы одежды может быть черным, белым или же цветным. Денег у Лены хватит только на покупку одной вещи. Сколько разных вариантов закупиться у нее есть?

Эту и другие похожие задачи можно довольно удобно решить с помощью построения таблицы. По горизонтали расположим цвета одежды, а по вертикали тип одежды. Тогда в ячейках таблицы мы и получим возможные варианты покупок. Всего их 12.

	Черный	Белый	Цветной
Юбка	ЮЧ	ЮБ	ЮЦ
Штаны	ШЧ	ШБ	ШЦ
Футболка	ФЧ	ФБ	ФЦ
Блузка	БЧ	ББ	БЦ

Но такой же результат можно получить и другим образом. Выбрать цвет можно 3 разными способами. Но любой из этих 3-х способов приведет к 4 возможным вариантам типа одежды. 4 типа черной одежды, 4 белой и 4 цветной. Опять возвращаемся к умножению:

\underbrace{3}_{\text{Цвет}} \times \underbrace{4}_{\text{Одежда}} = 12

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

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

Если эти рассуждения записать строгим языком, то мы получим правило умножения (или правило произведения) — одно из самых важных правил в комбинаторике. На нем основан вывод многих других формул в этом разделе математики.

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

Если объект из группы A можно выбрать a разными способами, и при любом сделанном выборе объект из группы B можно выбрать b способами, то есть всего $a\cdot b$ вариантов выбрать пару объектов (один из A, второй из B).

Другими словами, выбор «A и B» можно сделать $a\cdot b$ способами.

Красивый забор

Строительная фирма специализируется на изготовлении красивых заборов. Она предлагает на выбор 5 расцветок и 6 узоров. Сколько разных видов заборов может построить эта фирма?

Решение

На выбор есть 5 цветов. Любой из 5 выбранных цветов приводит к выбору из 6 узоров. По правилу умножения получаем $5\cdot 6 = 30$ видов заборов.

Летим дальше

Вернемся к нашему комическому дальнобойщику. Усложим ему жизнь, добавив еще одну точку, которую он должен посетить — созвездие Кассиопея. Отправится туда он должен из Андромеды, по двум возможным путям.

Попасть в Омегу Центавра он может тремя способами, и, вне зависимости от выбранного пути, после этого у него есть четыре пути в Андромеду. По правилу умножения получаем всего $3 \cdot 4 = 12$ вариантов попасть в Андромеду.

Всего 12 вариантов попасть в Андромеду. Каждый из этих 12 вариантов превращается в 2 способа попасть в Кассиопею. Берем «12 раз по 2». Получается всего 24 варианта попасть в нее:

\underbrace{2 + 2 + 2 + \ldots + 2}_{12 \text{ раз, за каждый путь в Андромеду}} = 12 \cdot 2 = 24

Можно записать и так:

\underbrace{3}_{\text{Омега Центавра}} \times \underbrace{4}_{\text{Андромеда}} \times \underbrace{2}_{\text{Кассиопея}} = 24

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

Обобщенное правило умножения

Если элемент $a_1$ можно выбрать $n_1$ способами, после любого выбора элемент $a_2$ можно выбрать $n_2$ способами, $\ldots$ после любого выбора предыдущих $k-1$ элементов элемент $a_k$ можно выбрать $n_k$ способами, то все эти k элементов можно выбрать $n_1 \cdot n_2 \cdot \ldots \cdot n_k$ способами.

Интуитивно это вполне понятное обобщение. Есть $n_1$ способов выбрать элемент $a_1$ . Каждый из $n_1$ способов порождает еще $n_2$ способов выбрать элемент $a_2$ . То есть уже имеем $n_1 \cdot n_2$ способов выбрать $a_1$ и $a_2$ . Каждый из $n_1 \cdot n_2$ способов выбрать пару элементов $a_1$ и $a_2$ порождает еще $n_3$ способов выбрать элемент $a_3$ , что дает в целом уже $n_1 \cdot n_2 \cdot n_3$ способов выбрать тройку элементов. И так далее...

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

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

Бесконечность не предел!

Все это время мы рассматривали задачи, которые можно за пару минут решить прямым перебором комбинаций. Сейчас же предлагаю насладиться примерами, которые продемонстрируют, насколько правило умножения мощный и полезный инструмент. Инструмент, который позволяет фантастически быстро получать ответ там, где потребовались бы часы, дни и годы ручного перебора.

Стань кем угодно...

В ролевой компьютерной игре есть редактор, в котором игрок создает главного героя. Можно выбрать пол и одну из 4 рас: человек, эльф, дворф или орк. Еще можно выбрать один из 8 оттенков кожи, 5 вариантов лица, 20 типов причесок. Сколько разных персонажей можно создать с помощью такого редактора?

Решение

2 варианта выбрать пол, 4 расы, 8 оттенков кожи, 5 вариантов лица и 20 причесок. Применяем правило умножения:

2 \cdot 4 \cdot 8 \cdot 5 \cdot 20 = 6 \ 400

Итак, в игре можно создать 6400 разных персонажей.

Поиграем в слова!

Сколько любых (даже бессмысленных) слов содержащих 5 букв можно составить из 33 букв русского алфавита так, чтобы любые две соседние буквы были различны?

Решение

На место первой буквы в слове годится любая из 33 букв алфавита. Вне зависимости от выбранной первой буквы, дальше может быть любая буква алфавита кроме той, что мы использовали для первого места. Поэтому есть 32 варианта выбрать букву для второго места в слове. Третья буква опять же может быть любой, кроме той, что стоит на втором месте в слове, то есть снова 32 варианта. И так далее.

По правилу умножения версии получаем:

33 \cdot 32 \cdot 32 \cdot 32 \cdot 32 = 34 \ 603 \ 008

Итак, используя 33 буквы без повторения соседних можно выписать почти 35 миллионов слов содержащих 5 букв!

Графическое представление

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

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

Математическая пиццерия

Пиццерия испекла 4 вкусные пиццы, которые нужно доставить заказчикам. Для этого пиццы распределяют между 5 курьерами, причем каждый курьер доставляет только одну пиццу. Сколькими способами можно отправить пиццу заказчикам?

Решение

Доставить надо все 4 пиццы, поэтому можно их изобразить как 4 вакантных места в виде «кружочков» с обозначением $P_i$ , где P — «пицца», а i — ее номер.

Первую пиццу можно отдать любому из пяти курьеров, поэтому в первом кружочке пишем 5. Вне зависимости от первого выбора, вторую пиццу всегда можно отдать четырьмя способами — любому из оставшихся четырех курьеров, поэтому во втором кружке пишем 4 и так далее.

Теперь просто проставляем между вакантными местами («кружками») знаки умножения. Получаем цепочку умножений, которая и появляется в результате применения правила умножения. Ответ — 120.

Конструктор чисел

Сколько существует четырехзначных чисел, в разряде десятков которых находится цифра 3? Примеры:

1538 \quad 4932 \quad 8734 \quad 1131 \quad 9937

Решение

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

Первая цифра числа не может начинаться с 0, поэтому в первый квадрат можно записать любую из 9 оставшихся цифр. Во втором квадрате, то есть в разряде сотен, можно написать любую из 10 цифр. В третьем квадрате всегда стоит цифра 3, то есть в нем всегда используется одна цифра. Наконец, в последнем квадрате можно использовать любую из 10 цифр:

Проставляем знаки умножения между вакантными местами («квадратами») и получаем то, как будет выглядеть правило умножения. Ответ — 900.

Суть метода

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

Не все так просто

Заметили, что говоря о правиле умножения как в его определении, так и в примерах, постоянно повторяются слова «при любом выборе получаем x способов сделать следующий выбор» и другие их вариации?

Эти слова там не просто для красоты. Дело в том, что правило умножения будет работать только если выполняется условие одинаковости количества следующих выборов. В противном случае можно получить неправильные результаты.

План на день

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

Решение

На первый взгляд задача элементарно решается через правило умножения. У нас есть 5 разных дел, которые можно выполнить в первую очередь. После этого останется 4 дела. Всего $5 \cdot 4 = 20$ способов составить план?

Нет. Проблема в том, что есть дело (помощь сестре), после выполнения которого останется не 4 доступных дела, а всего 3 (домашнее задание сделать не получится).

Применив правило умножения мы среди 20 планов в том числе получили такой план:

Помочь сестре
Сделать домашнее задание

И еще такой:

Сделать домашнее задание
Помочь сестре

А из условия мы знаем, что эти два дела исключают друг друга. Эти два плана учитывать нельзя. Поэтому правильный ответ у этой задачи — 18.

Применимость правила умножения

Правило умножения не работает, если существуют выборы первого элемента, которые приводят к разному количеству способов выбрать второй элемент!

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