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

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

Так как количество способов (не сами способы, они каждый раз разные, а именно количество) выбрать следующий фрагмент не зависит от выбора предыдущего фрагмента, мы можем использовать правило умножения для нахождения всех вариантов составить слово:

24

Ученика из первого из двух классов можно выбрать 30 разными способами. Вне зависимости от сделанного выбора, второго ученика из второго класса тоже можно выбрать 30-ю способами. По правилу умножения получаем всего $30 \cdot 30 = 900$ способов выбрать пару учеников для уборки в столовой.

900

Всего в многоугольнике 12 вершин. Стало быть, первую вершину можно выбрать 12-ю способами.

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

Итак, вне зависимости от первой выбранной вершины, вторую можно всегда выбрать только двумя способами. По правилу умножения получаем $12 \cdot 2 = 24$ способа выбрать две вершины так, чтобы они принадлежали одной стороне.

24

Сначала выбираем одну из 7 дорог в B. Вне зависимости от сделанного выбора, после этого можно выбрать одну из 10 дорог в C. По правилу умножения получаем всего $7 \cdot 10 = 70$ возможных путей.

70

По правилу умножения получаем $6 \cdot 4 = 24$ вида посохов.

24

В слове «редактор» есть 5 согласных и 3 гласные. По правилу умножения получается $5 \cdot 3 = 15$ способов выбрать согласную и гласную буквы.

В слове «преступление» 7 согласных, но только 6 разных. Также 5 гласных, 3 из которых разные. Мы не можем использовать повторящиеся буквы, так как они дадут повторяющиеся пары букв. Поэтому используем только уникальные буквы: $6 \cdot 3 = 18$.

15 способов для слова «редактор» и 18 для слова «преступление».

Первую цифру можно выбрать 8 способами, потому что она не может быть ни восьмеркой, ни нулем!

Первую цифру трехзначного числа можно выбрать 8 способами (все цифры кроме 0 и 8). Ноль использовать нельзя, потому что тогда мы получим двузначное число.

Вне зависимости от выбранной первой цифры, вторую можно выбрать 9 способами (все цифры кроме 8). Ну и третью цифру тоже можно выбрать 9 способами. По правилу умножения находим количество всех чисел:

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

Медика можно выбрать 7 способами. Командира — 3 способами.

Количество способов выбрать двух воинов для отряда можно определить прямым перебором, где уже разбиралась аналогичная задача. Обозначим воинов цифрами и выпишем все возможные пары цифр. Для удобства выписывать будем по возрастанию:

Получется, у нас есть 6 способов выбрать пару воинов.

Итак, выбрать пару воинов можно 6 способами. Вне зависимости от выбранной пары воинов, медика можно выбрать 7 способами, а командира 3. По правилу умножения есть всего $6 \cdot 7 \cdot 3 = 126$ способов собрать отряд.

126

Разбейте все варианты составить отряд на классы: «без универсала», «универсал воин», «универсал медик» и «универсал командир». Затем используйте правило суммы.

Кризис правила умножения

Универсал вносит зависимость от выбора в результат. Если из уже 8 способов выбрать медика взять кого-то, кроме универсала, то командира можно выбрать 4-мя способами (3 командира + 1 универсал). Но если медиком выбрать именно универсала, то командира после этого можно выбрать только 3 способами.

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

Классы спешат на помощь

Выделим в отдельный класс «без универсала» все варианты составить отряд без учета универсала. Мы уже посчитали ранее, что их 126.

Дальше выделим три класса в зависимости от того, какую роль выполняет универсал: «универсал воин», «универсал медик» и «универсал командир».

В классе «универсал медик» есть $6\cdot 1 \cdot 3 = 18$ способов собрать отряд. В классе «универсал командир» есть $6 \cdot 7 \cdot 1 = 42$ способа собрать отряд.

Для класса «универсал воин» пару воинов можно выбрать 4-мя способами — 1 универсал и любой из 4 воинов. В целом в классе выходит $4\cdot 7 \cdot 3 = 84$ способа собрать отряд.

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

Вот таким образом всего один универсал в два раза увеличил количество вариантов собрать отряд: с 126 до 270.

522

6 маршрутов на вершину горы. Вне зависимости от выбранного маршрута далее спутиться можно тоже по одному из 6 маршрутов. По правилу умножения получаем $6 \cdot 6 = 36$ способов совершить восхождение и спутиться.

Если же спуститься тем же маршрутом нельзя, то после любого выбранного пути наверх остается только 5 путей вниз: $6 \cdot 5 = 30$.

36 способов подняться и спуститься. 30, если использовать один и тот же путь нельзя.

По правилу умножения имеем $21 \cdot 17 = 357$ способов выбрать трубу и пластину. Если такой выбор уже был сделан, то осталось лишь 20 труб и 16 пластин, что дает $20 \cdot 16 = 320$ способов.

357 изначальных способов и 320 способов выбрать еще раз.

Используйте тот факт, что в любой строке и любом столбце шахматной доски есть 4 черных и 4 белых поля.

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

В любой строке и любом столбце есть по 4 белых поля, поэтому после сделанного выбора из 32 белых полей осталось только 32 - 8 = 24. По правилу умножения получаем $32 \cdot 24 = 768$ способов выбрать черное и белое поля.

768

Если Петя купит напиток, то у Насти по правилу умножения у насти есть $9 \cdot 7 = 63$ способа совершить покупку. Если же он купит батончик, то у Насти остается всего $10 \cdot 6 = 60$ способов. Большая свобода выбора у Насти будет, если Петя купит напиток.

У Насти будет больше вариантов совершить выбор, если Петя купит напиток.

Выбрать воина можно 20 способами. Вне зависимости от сделанного выбора, после этого есть 13 способов выбрать мага. Опять же, вне зависимости от выбранной пары «воин, маг», есть 5 способов выбрать лучника. Так же и со жрецом.

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

Всего 3900 способов собрать ударный отряд.

3900

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

Иная ситуация, если нельзя допускать повторения символов. Тогда первый можно выбрать 12 способами, как и раньше. Второй уже 11, так как один символ мы уже использовали. И так далее:

$20 \ 736$ паролей с повторениями и $11 \ 880$ без.

Первое место может занять любой из 4-х друзей. Вне зависимости от того, кто это будет, на второе место может сесть один из 3-х оставшихся, а на последнее один из двух. Последний же может выбрать, к кому из 3 своих друзей сесть на колени. По правилу произведения находим $4 \cdot 3 \cdot 2 \cdot 3 = 72$ способа рассадить 4-х друзей.

72

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

Разные флаги

Цвет первой полоски можно выбрать 5 способами. Вне зависимости от выбранного цвета первой полоски, цвет второй можно выбрать 4 способами, а третьей тремя. По правилу умножения находим все возможные варианты флагов:

С красной полоской

Если один из цветов должен быть красным, то его можно выбрать для любой из 3 полосок. Вне зависимости от выбранной для красного цвета полоски, вторую полоску можно будет покрасить 4 способами, а третью 3. Используем правило умножения:

С повторяющимися цветами

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

Всего 5 вариантов выбрать один цвет для верхней и нижней полосок. Вне зависимости от выбранного цвета, полоску по середине можно будет покрасить в один из 4 цветов. Используем правило умножения:

То есть 60 флагов с разными цветами и еще 20 флагов с повторяющимися цветами. Всего 60 + 20 = 80 флагов.

Всего 60 флагов с различными цветами, 36 флагов с красной полоской и 80 флагов с условием, что цвета могут повторяться.

Начните с конца.

Начнем с самой последней, четвертой ноты в мелодии. Ее можно выбрать 4-мя способами, потому что три из семи нот в концовке быть не могут. Вне зависимости от выбранной ноты, третью ноту можно выбрать 6 способами (все ноты кроме той, что мы уже использовали). И так далее. По правилу умножения:

Решение через классы

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

Разделим все мелодии на 4 класса. В первом классе будут все мелодии в которых вообще не используются 3 запрещенные ноты. Таких мелодий по правилу произведения наберется $4\cdot 3\cdot 2\cdot 1 = 24$ штуки.

Во втором классе мелодии с одной запрещенной нотой. Запрещенную ноту можно выбрать 3-мя способами и вставить ее в мелодию можно в одно из 3-х мест. После этого заполнить оставшиеся места в мелодии можно $4 \cdot 3 \cdot 2$ способами:

В третьем классе мелодии с двумя запрещенными нотами. Всего две запрещенные ноты можно выбрать $3 \cdot 2 = 6$ способами. Эти две запрещенные ноты надо расположить в мелодии. Это можно сделать тремя способами. Ну а закончить мелодию можно $4 \cdot 3 = 12$ способами:

Ну а в последнем классе первые три ноты мелодии и будут запрещенными. Всего $3 \cdot 2 \cdot 1$ способов начать мелодию и завершить ее одной из 4 оставшихся незапрещенных нот:

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

480

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

Введем класс $K_1$, в котором будут только покупки отдельных ручек — без комплектов. По правилу умножения получаем $7 \cdot 5 \cdot 4 = 140$ вариантов совершить покупку.

В классе $K_2$ рассмотрим покупки комплекта из синей и черной ручек и отдельно красной ручки. Всего $6 \cdot 4 = 24$ варианта.

В классе $K_3$ рассмотрим покупки отдельно синей ручки и комплекта из черной и красной ручек. $3 \cdot 7 = 21$ вариант.

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

Если учитывать дополнительные условия, то мы получаем еще два класса: $K_4$ с $4 \cdot 5 = 20$ и $K_5$ с 9 способами, что суммарно дает 185 + 20 + 9 = 214 способов совершить покупку.

185 способов совершить покупку.
214 способов, если учитывать дополнительные условия.

Число делится на 2, если последняя его цифра делится на 2.

Первая цифра может быть любой, кроме 0, то есть всего 5 вариантов. Следующие 3 цифры могут быть любыми, то есть по 6 вариантов на каждую. Наконец, чтобы все число делилось на 2, последняя его цифра тоже должна делиться на 2. Таких вариантов всего 3 (цифры 0, 4 и 8). По правилу произведения получаем:

3240

Для ответа на второй вопрос разбейте все варианты падения с условием «хотя бы два на грани с цифрой 2» на классы. Обратите внимание на особый случай, когда все три волчка упали на грань с 2.

Падение одного волчка никак не влияет и не зависит от падения двух других, поэтому мы можем использовать правило произведения, согласно которому волчки могут упасть $6 \cdot 7 \cdot 9 = 378$ разными способами.

Для ответа на второй вопрос поделим все падения на классы. В классе $K_{22x}$ будут все падения, при которых первый и второй волчки упали на грань с цифрой 2, а третий упал на любую грань кроме 2. Раз последний волчок может упасть на любую из девяти граней, кроме 2, то получается у него всего 8 вариантов упасть, что дает 8 способов падений волчков в классе $K_{22x}$.

Аналагично в классе $K_{2x2}$ есть 6 способов, а в классе $K_{x22}$ есть 5 способов падений волчков. Наконец, есть еще один вариант — когда все три волчка упадут на грань с цифрой 2. Этот вариант обозначим классом $K_{222}$.

Итак, имеем четыре класса, которые состоят из уникальных вариантов падения трех волчков. Эти классы не пересекаются, поэтому мы можем применить правило суммы:

Три волчка могут упасть 378 разными способами, в 20 из которых по крайней мере два волчка упадут на грань с цифрой 2.

Разбейте все возможные комбинации имен для англичан на классы по количеству слов.

Разделим все возможные комбинации имен для англичан на три класса по количеству слов.

В классе $K_1$ есть 300 вариантов назвать ребенка одним именем.

В классе $K_2$ для первого имени есть 300 вариантов. Вне зависимости от выбора первого имени, второе всегда можно выбрать 299 способами (не 300, так как одно имя уже использовали). По правилу произведения получаем $300 \cdot 299 = 89 \ 700$ вариантов в классе $K_2$.

В классе $K_3$ при помощи тех же рассуждений получаем:

Итак, имеем три класса с уникальными комбинациями имен. Полного совпадения двух имен из разных классов произойти не может, так как в классе $K_1$ имена состоят из одного слова, в $K_2$ из двух, а в $K_3$ из трех. Раз пересечений нет, мы можем использовать правило суммы:

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

Всего $26 \ 820 \ 600$ имен. На всех англичан не хватит.

Разбейте все такие числа на классы по количеству цифр, из которых они состоят.

Введем классы чисел по количеству цифр, из которых они состоят.

В классе $K_1$ у нас 10 чисел — от 0 до 9.

В классе $K_2$ у нас двузначные числа. Первая цифра может быть любой, кроме 0 (иначе получится однозначное число), то есть 9 вариантов. Вторая цифра тоже может быть любой, кроме той, что стоит на первом месте, поэтому тоже 9 вариантов. По правилу умножения всего в $K_2$ имеется $9\cdot 9 = 81$ число.

В классе $K_3$ всего $9\cdot 9 \cdot 9 = 729$ трехзначных чисел. Продолжаем все эти рассуждения вплоть до класса $K_5$ — пятизначных чисел.

Имеем 5 классов уникальных чисел, каждое из которых не содержит двух рядом стоящих одинаковых цифр. Для подсчета всех таких чисел можно использовать правило суммы:

$66 \ 430$ чисел.

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

Выбранные точки поля не должны образовать отрезок, параллельный какой-либо стороне поля.

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

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

Узлов по горизонтали на 1 больше, чем самих клеток, то есть $(n+1)$. Точно так же узлов по вертикали $(m+1)$. Всего $(n+1)(m+1)$ узлов. Под первую вершину можно выбрать любой из них.

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

Значит, «свободными» узлами являются все $(n+1)(m+1)$ узлов, за вычетом $(n+1)$ горизонтальных узлов и $(m+1)$ вертикальных узлов. Но так мы дважды исключили уже выбранный узел, поэтому один раз мы его добавляем:

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

Мы вроде как нашли количество всех возможных прямоугольников. Но каждый из них представлен в виде 4-х дубликатов:

• 2 дубликата из-за того что, две вершины можно выбрать в разном порядке.

• Еще 2 дубликата из-за того, что тот же прямоугольник можно задать и двумя другими вершинами, которые тоже можно выбрать в разном порядке.

Значит, общее количество прямоугольников надо разделить на 4:

Если поле имеет размеры $n \times n$, то есть является квадратным, то формула количества прямоугольников упрощается:

Количество прямоугольников на поле $n \times m$:

Если поле квадратное, то есть размером $n \times n$:

Удивительным образом полученная формула прямоугольников для квадратного поля $n\times n$ совпадает с формулой суммы кубов первых n натуральных чисел!

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

Задание решается практически точно так же, как и аналогичная задача в теме «Правило суммы».

Обозначим за $R_n$ количество цепочек действий, которые дают в результате число n. Формулы для $R_n$ получатся почти такими же, что и в уже разобранной аналогичной задаче.

Получить число 3 можно единственным способом — если не дать роботу никаких команд. Поэтому $R_3 = 1$. Получить 4 можно только одним способом — единожды применив действие (1). Поэтому $R_4 = 1$.

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

Введем теперь обозначение $P_n$, которое показывает количество цепочек действий для попадания из числа 8 в число n. $P_8 = P_9 = 1$ по том же причинам, по которым $R_3 = R_4 = 1$. Действие (3) мы уже не можем использовать, иначе перелетим за 12, поэтому $P_n = P_{n-1} + P_{n-2}$.

Итак, у нас есть 11 способов добраться до числа 8, и при любом выбранном способе затем есть 5 вариантов добраться до числа 12. По правилу умножения получаем $11 \cdot 5 = 55$ возможных цепочек действий.

55

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

Выберем любую из шести вершин шестиугольника, например E. Диагональ можно провести к любой из вершин, кроме самой вершины E и двух ее «соседей» F и D, потому что к ним идут стороны. Остаются только 3 вершины, к которым можно провести диагонали.

Так как подобные рассуждения можно провести с любой из 6-ти вершин и каждая даст по 3 диагонали, то всего получаем 18 диагоналей так? Почти, но не совсем. Дело в том, что считая таким образом мы получаем дубликат каждой диагонали.

Например, на рисунке изображена диагональ EB, причем «отправной» точкой является E. Но, когда «отправной» точкой станет B, мы лишний раз засчитаем точно такую же диагональ BE. Такой дубликат есть у каждой диагонали, поэтому на самом деле их не 18, а всего 9.

Общий случай

У любого n-угольника есть n вершин. Возьмем любую такую вершину. Мы можем провести диагональ к любой вершине, кроме ее самой и двух соседних, потому что к ним ведут стороны этого n-угольника.

Тогда остается $n-3$ вершин на выбор. По правилу произведения получаем $n\cdot(n-3)$ диагонали. Но среди этих диагоналей каждая имеет свой дубликат, поэтому для получения правильного ответа надо разделить результат правила произведения на 2:

9 диагоналей у шестиугольника.
Формула для количества диагоналей n-угольника:

Разложите число 15400 на простые множители. Запишите разложение с использованием степеней. Найдите связь между показателями степеней простых множителей и делителями числа 15400.

Разложим число 15400 на простые множители. Сначала делим до упора на 2, потом на 3 и так далее. Получится вот что:

Можно записать это в более короткой форме, используя степени:

Любая комбинация простых множителей даст нам делитель:

Но любую из этих комбинаций можно записать через степени:

Получается, любой делитель числа 15400 определяется комбинацией показателей степеней:

Длина комбинации всегда равна 4 (так как у нас 4 простых множителя). Число 2 в разложении можно возвести в любую степень от 0 до 3, то есть всего 4 варианта. Вне зависимости от выбранного первого показателя, число 5 множно возвести в любую степень от 0 до 2, то есть 3 варианта. Числа 7 и 11 можно возвести только в степень 0 и 1, то есть по два варианта. По правилу умножения получаем:

У числа 15400 всего 48 положительных делителей.

48

Задача решается почти так же, как и ее аналог из темы «Прямой перебор».

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

Начнем решение задачи с того, что полностью откажемся от работы с цветами. Вместо них мы будем использовать буквы: A, B, C, D. Четыре цвета — четыре буквы.

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

Строчка букв ABCD может обозначать как цвета БЧКС (белый, черный, красный, синий), так и цвета ЧБСК, ну и любые другие комбинации. По правилу произведения существует всего $4 \cdot 3 \cdot 2 \cdot 1 = 24$ способа «привязать» цвета к буквам. Другими словами, запись ABCD как-бы скрывает в себе сразу все 24 комбинации из четырех цветов.

Заполняем таблицы

В условии нам сказано про квадрат, который разделен на 16 равных квадратов. То есть речь идет про обычную таблицу размерами $4 \times 4$. Верхнюю строчку этой таблицы заполним буквами ABCD:

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

Итак, у нас есть таблица с заполненным «уголком». Опять же не забывайте, что на самом деле это 24 таблицы с цветами вместо букв. Осталось лишь заполнить внутреннюю таблицу $3 \times 3$. Сделать это проще прямым перебором. Получится четыре заполненных таблицы:

Итого, каждую из 24 незаконченных таблиц можно закрасить до конца 4-мя способами. По правилу произведения получаем $24 \cdot 4 = 96$ возможных полных раскрасок таблицы с одинаковым порядком цветов в верхней строке и в левом столбце.

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

Перестановками строк можно получить $3 \cdot 2 \cdot 1 = 6$ разных комбинаций букв в левом столбце таблицы (буква A закреплена в левом верхнем углу и не меняется). Объединяем этот результат с ранее полученными 96 закрасками и находим:

Всего 576 вариантов закрасить цветами таблицу $4 \times 4$ так, чтобы в строках и столбцах цвета не повторялись.

576

Эта и многие похожие задачи имеют общее название — задачи о латинском квадрате. Сам же латинский квадрат — это квадратная таблица размерами $n \times n$. В каждую ячейку ставится один из n уникальных элементов так, чтобы не встречалось повторений ни в строках, ни в столбцах. И совершенно не важно, что это за элементы: цвета (как в этой задаче), буквы, числа, функции, да хоть кролики.

В этой задаче нас просят найти количество латинских квадратов размера 4. Интересно то, что формула точного количества латинских квадратов порядка n неизвестна! На досуге можете поломать голову над этой проблемой. Но не слишком долго 😉