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

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

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

Сегодня убираешься ты

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

Решение

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

Ответ

900

Мы на одной стороне

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

Решение

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

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

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

Ответ

24

Небольшая поездка

Из города A в город B ведут 7 дорог, а из B в C10. Сколько есть путей из города A в город C, которые проходят через B.

Решение

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

Ответ

70

Волшебных дел мастер

В волшебной мастерской делают посохи для колдунов. Есть 6 видов древесины, из которых может быть изготовлен посох. Затем незаряженный посох можно напитать силой одной из 4-х стихий. Сколько разных видов посохов может изготовить эта мастерская?

Решение

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

Ответ

24

Читай по буквам

Сколькими способами можно выбрать согласную и гласную буквы из слова «редактор»? А из слова «преступление»?

Решение

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

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

Ответ

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

Боязнь восьмерок

Сколько существует трехзначных чисел, не содержащих цифры 8?

Указание

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

Решение

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

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

899=6488\cdot 9 \cdot 9 = 648
Ответ
899=6488\cdot 9 \cdot 9 = 648

Фантастическая четверка

Для сражения с драконом нужно собрать отряд из 4 человек: двух воинов, медика и командира. Сколькими способами можно собрать отряд, если быть добровольцами вызвались 4 воина, 7 медиков и 3 командира?

Указание

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

Решение

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

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

121314232434 \begin{array}{} 12 & 13 & 14 \\ & 23 & 24 \\ && 34 \end{array}

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

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

Ответ

126

Фантастический универсал

Как изменится результат задачи «Фантастическая четверка», если в добровольцы запишется универсал, который может выполнить роль воина, медика или командира?

Указание

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

Решение

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

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

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

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

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

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

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

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

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

126+18+42+84=270126 + 18 + 42 + 84 = 270

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

Ответ

522

Покоритель гор

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

Решение

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

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

Ответ

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

Железный человек

Перед инженером лежит куча металлолома, состоящего из 21 трубы и 17 пластин (все разных размеров). Сколькими способами он может выбрать одну трубу и одну пластину? Если такой выбор уже сделан, сколько есть способов сделать его еще раз?

Решение

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

Ответ

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

Отдай доску!

Сколькими способами можно выбрать на шахматной доске черное и белое поля, не лежащие на одной горизонтали или одной вертикали?

Указание

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

Решение

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

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

Ответ

768

Свобода выбора

В торговом автомате продается 10 видов газированных напитков и 7 видов шоколадных батончиков. Петя покупает газированный напиток или шоколадный батончик, а Настя берет и напиток, и батончик. В каком случае Настя имеет большую свободу выбора: если Петя купил напиток, или если он купил батончик?

Решение

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

Ответ

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

Ударный отряд

На сражение против монстров записалось 20 воинов, 13 магов, 5 лучников и 3 жреца. Сколькими способами можно составить ударный отряд из 4 человек так, чтобы у каждого была своя роль?

Решение

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

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

201353=390020 \cdot 13 \cdot 5 \cdot 3 = 3900

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

Ответ

3900

Секретный пароль

Ольга хочет установить пароль на свой телефон. В пароле должно быть 4 символов. Годятся любые цифры от 0 до 9, а также символы звездочки «*» и решетки «#».

Сколько разных паролей можно составить? А сколько останется вариантов, если каждый символ можно использовать только один раз?

Решение

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

12121212=20 73612 \cdot 12 \cdot 12 \cdot 12 = 20 \ 736

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

1211109=11 88012 \cdot 11 \cdot 10 \cdot 9 = 11 \ 880
Ответ

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

Забитый автобус

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

Решение

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

Ответ

72

Символ государства

Сколькими способами можно сделать трехцветный флаг (с тремя горизонтальными полосами), если меется материя пяти различных цветов? А если один из цветов должен быть красным? А если цвета могут повторяться, но не рядом (полосы должны быть различимы)?

Указание

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

Решение

Разные флаги

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

543=605\cdot 4\cdot 3 = 60

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

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

3(43)=363\cdot (4\cdot 3) = 36

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

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

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

54=205 \cdot 4 = 20

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

Ответ

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

Звучание комбинаторики

В музыке, как известно, есть семь чистых нот: «до», «ре», «ми», «фа», «соль», «ля», «си». Вадим хочет создать мелодию из 4 неповторяющихся нот. Причем мелодия не должна заканчиваться на нотах «до», «ре» и «си». Сколько мелодий может создать Вадим?

Указание

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

Решение

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

4654=4804 \cdot 6 \cdot 5 \cdot 4 = 480

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

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

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

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

3Нота3Позиция432Остальное=216\underbrace{3}_{\text{Нота}} \cdot \underbrace{3}_{\text{Позиция}} \cdot \underbrace{4 \cdot 3 \cdot 2}_{\text{Остальное}} = 216

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

32Две ноты3Позиция43Остальное=216\underbrace{3 \cdot 2}_{\text{Две ноты}} \cdot \underbrace{3}_{\text{Позиция}} \cdot \underbrace{4 \cdot 3}_{\text{Остальное}} = 216

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

321Запретные ноты4Концовка=24\underbrace{3 \cdot 2 \cdot 1}_{\text{Запретные ноты}} \cdot \underbrace{4}_{\text{Концовка}} = 24

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

24+216+216+24=48024 + 216 + 216 + 24 = 480
Ответ

480

Гроза конспектов

В магазине канцелярских товаров продается 7 разных видов синих ручек, 5 видов черных и 4 вида красных ручек. Кроме того, есть 6 комплектов из двух ручек: синей и черной и 3 вида комплектов из черной и красной ручек. Сколько есть способов совершить покупку, содержащую по одной ручке каждого цвета?

А если в этом магазине есть еще 4 комплекта из синей и красной ручек и 9 комплектов из трех ручек разных цветов?

Указание

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

Решение

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

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

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

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

140K1+24K2+21K3=185\underbrace{140}_{K_1} + \underbrace{24}_{K_2} + \underbrace{21}_{K_3} = 185

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

Ответ

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

Числовой архитектор

Сколько различных пятизначных чисел, делящихся на 2, можно составить из цифр 0, 3, 4, 7, 8, 9?

Указание

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

Решение

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

56663=32405 \cdot 6 \cdot 6 \cdot 6 \cdot 3 = 3240
Ответ

3240

Бегай там крутись...

Имеются три волчка с 6, 7 и 9 гранями соответственно. Их одновременно запустили. Сколькими различными способами они могут упасть? Сколько среди них способов, при которых по крайней мере два волчка упали на сторону, помеченную цифрой 2?

Указание

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

Решение

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

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

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

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

8K22x+6K2x2+5Kx22+1K222=20\underbrace{8}_{K_{22x}} + \underbrace{6}_{K_{2x2}} + \underbrace{5}_{K_{x22}} + \underbrace{1}_{K_{222}} = 20
Ответ

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

Тот, кого нельзя называть

У англичан принято давать ребенку несколько имен. Сколькими способами в Англии можно назвать ребенка, если общее число имен равно 300, а ему дают не более трех имен? Хватит ли этих наборов на всех англичан (57 млн чел.) или непременно найдутся англичане с одинаковыми именами?

Указание

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

Решение

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

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

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

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

300299298=26 730 600300 \cdot 299 \cdot 298 = 26 \ 730 \ 600

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

300K1+89 700K2+26 730 600K3=26 820 600\underbrace{300}_{K_1} + \underbrace{89 \ 700}_{K_2} + \underbrace{26 \ 730 \ 600}_{K_3} = 26 \ 820 \ 600

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

Ответ

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

Считатель чисел

Сколько есть чисел от 0 до 99 99999 \ 999, в которых нет двух рядом стоящих одинаковых цифр?

Указание

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

Решение

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

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

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

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

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

10K1+81K2+729K3+6561K4+59 049K5=66 430\underbrace{10}_{K_1} + \underbrace{81}_{K_2} + \underbrace{729}_{K_3} + \underbrace{6561}_{K_4} + \underbrace{59 \ 049}_{K_5} = 66 \ 430
Ответ

66 43066 \ 430 чисел.

Очень послушный робот

ЕГЭ Информатика

Артем создал робота, который умеет делать три арифметических действия:

  1. Прибавить 1

  2. Прибавить 2

  3. Умножить на 2

Сколько различных цепочек действий можно дать роботу, чтобы он из числа 3 получил число 12 и чтобы в промежуточных вычислениях обязательно оказалось число 8?

Указание

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

Решение

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

Rn=Rn1+Rn2(n нечетное)Rn=Rn1+Rn2+Rn2(n четное) R_n = R_{n-1} + R_{n-2} \quad (n \ \text{нечетное}) \\ R_n = R_{n-1} + R_{n-2} + R_{\frac{n}{2}} \quad (n \ \text{четное})

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

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

R5=R4+R3=1+1=2R6=R5+R4+R3=2+1+1=4R7=R6+R5=4+2=6R8=R7+R6+R4=6+4+1=11 R_5 = R_4 + R_3 = 1 + 1 = 2 \\ R_6 = R_5 + R_4 + R_3 = 2 + 1 + 1 = 4 \\ R_7 = R_6 + R_5 = 4 + 2 = 6 \\ R_8 = R_7 + R_6 + R_4 = 6 + 4 + 1 = 11

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

P10=P9+P8=1+1=2P11=P10+P9=2+1=3P12=P11+P10=3+2=5 P_{10} = P_9 + P_8 = 1 + 1 = 2 \\ P_{11} = P_{10} + P_9 = 2 + 1 = 3 \\ P_{12} = P_{11} + P_{10} = 3 + 2 = 5

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

Ответ

55

Диагональный метод

Сколько диагоналей у шестиугольника? А у n-угольника?

Указание

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

Решение

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

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

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

Общий случай

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

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

n(n3)2\frac{n(n-3)}{2}
Ответ

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

n(n3)2\frac{n(n-3)}{2}

Разделяй и умножай

Нестандартная

Сколько положительных делителей у числа 15400?

Указание

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

Решение

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

15400=2225571115400 = 2 \cdot 2 \cdot 2 \cdot 5 \cdot 5 \cdot 7 \cdot 11

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

15400=23527111115400 = 2^3 \cdot 5^2 \cdot 7^1 \cdot 11^1

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

2,225=20,5711=385,2, \quad 2\cdot 2\cdot 5 = 20, \quad 5 \cdot 7 \cdot 11 = 385, \quad \ldots

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

2=215070110225=2251701102711=215071111 2 = 2^1 \cdot 5^0 \cdot 7^0 \cdot 11^0 \\ 2\cdot 2\cdot 5 = 2^2 \cdot 5^1 \cdot 7^0 \cdot 11^0 \\ 2\cdot 7 \cdot 11 = 2^1 \cdot 5^0 \cdot 7^1 \cdot 11^1

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

{1,0,0,0} для 2{2,1,0,0} для 20{1,0,1,1} для 385 \set{1,0,0,0} \ \text{для} \ 2 \\ \set{2,1,0,0} \ \text{для} \ 20 \\ \set{1,0,1,1} \ \text{для} \ 385

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

4322=484 \cdot 3 \cdot 2 \cdot 2 = 48

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

Ответ

48

Латинский квадрат

Сложная
Исследовательская

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

Указание

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

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

Решение

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

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

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

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

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

ABCD

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

ABCD
B
C
D

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

ABCD
BCDA
CDAB
DABC
ABCD
BADC
CDAB
DCBA
ABCD
BADC
CDBA
DCAB
ABCD
BDAC
CADB
DCBA

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

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

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

966=57696 \cdot 6 = 576

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

Ответ

576

Примечание

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

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

Превью