Образовательный портал Павла Добряка

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

Здесь m - мощность алфавита, а n - количество ячеек.

Если вы забыли, что такое размещения, перестановки, сочетания и почему именно они применяются для решения задач такого типа, то перечитайте начало параграфа «2.2. Основы комбинаторики».

Первая задача ничем не отличается от задачи на степенную формулу (2.2.1). Во второй, третьей и четвертой задаче задается обязательное количество букв А в слове. 

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

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

mⁿ = 3³ = 9

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

Итак, это комбинированная задача на сочетания и степенную формулу. Мы столкнемся еще с подобной комбинированной задачей на деревья, а также с задачей, где комбинируются размещения (arrangement) и степенная формула – это последняя задача книги («счастливый билет»). 

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

Начнем с буквы А. Её можно разместить по 10 ячейкам 10-ю способами.

На две буквы B остается 9 ячеек. Количество вариантов:  

На три буквы С остается 7 ячеек:     Остальные ячейки заполняются буквами D, то есть это – один вариант.

Результаты надо перемножить:

10 * 36 * 35 12600

Если вы не понимаете, почему происходит умножение, то перечитайте начало параграфа «2.2. Основы комбинаторики».

Ответ: 12600

Будьте внимательны, проверяя крайние случаи. Так, пустая веревка для вымпелов – это тоже сообщение, но вот пустая тарелка салатом не является. 

Задача с вымпелами была придумана мной, а не взята из ЕГЭ, но по сложности она вполне соответствует появляющимся в ЕГЭ задачам последних лет. Поэтому приведем её подробное решение:

Решайте так же, как и другие задачи комбинаторики, вспомните задачу про азбуку Морзе 2.5.1 и задачу про флаги и мачты 2.2.2. Это задача на сумму факториалов.

Рассмотрим способы вывешивания вымпелов, не привязываясь к конкретным цветам мачты:

1) Пустая веревка – это одно сообщение.

2) Если на веревке один вымпел, у нас выбор из четырех цветов – это четыре сообщения.

3) Если на веревке два вымпела. На первый вымпел у нас выбор из четырех цветов:

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

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

Это формула на количество размещений, так как порядок имеет значение:

4) Аналогично случаи с тремя вымпелами и четырьмя:

Результаты складываем и получаем ответ 65.

Ответ: 65

Все эти задачи – на степенную формулу I = mⁿ. Речь идет об кодировании, в котором порядок лампочек, битов и тумблеров имеет значение. Также значения ячеек могут повторяться. Но в разных задачах неизвестны разные величины. То есть задачи являются обратными друг другу. Найдем соответствия в задачах:

В предыдущем задании (7.1.7) мы решали задачи на степенную формулу. Для многих учеников трудно понять, что является мощностью алфавита, ячейками и словами. Есть еще прикладные задачи, в которых остается та же проблема идентификации. Иногда степенная формула – это только одна из формул, нужных для решения задачи. Кроме того, ученики вообще могут не понять, что речь идет о степенной формуле, и применить другую формулу комбинаторики или применить степенную формулу неправильно, получив осмысленный, но не нужный результат. Так, в следующей таблице вы увидите, что если у задачи два вопроса, то вопрос №1 взят из ЕГЭ, а вопрос №2 соответствует тому, что ученик найдет, пойдя по ложному пути.

Выявим «ядро» задач:

Заметим, что мы недорешали задачи, полное решение смотрите в параграфе «2.2. Основы комбинаторики».