Комбинаторика
Сегодняшнее занятие посвящено комбинаторике. Комбинаторика это раздел математики, который занимается подсчётом количества вариантов, способов сделать что-либо. Рассмотрим такую задачу.
Задача 1.
Света строит башню из 2 кубиков. У нее в наборе есть зеленые и голубые кубики. Сколько разных башенок она может построить?
Решение. Переберем все варианты.
Получается 4 разных башенки.
В задачах, где нам надо перебрать и посчитать все варианты, важно придумать, в каком порядке их перебирать так, чтобы ничего не пропустить. Рассмотрим пример.
Задача 2.
Раскрась одежду гномов двумя цветами, так чтобы среди 8 гномов не было 2 одинаковых. Каждый предмет одежды — кофту, шапку и брюки — можно красить только одним цветом (то есть не может быть полосатых желто-красных брюк).
Решение.
Если красить наугад, то легко запутаться. Придумаем систему. Пусть сначала мы будем красить шапки только красным. Если кофта тоже красная, то получаем 2 варианта – с красными брюками и с желтыми.
То же самое с желтой кофтой.
А теперь все то же самое с желтой шапкой.
Задача 3.
Из города А в город Б ведут 2 дороги. Из города Б в город В — 3 дороги. И одна дорога ведет из А в В. Сколько существует разных путей из А в В?
Решение.
Нарисуем схему.
Первый путь – это прямой и А в В. Рассмотрим теперь, сколько путей через Б.
Если из А в Б мы идем по зеленой дороге, то у нас 3 варианта пути в В – зеленый-желтый, зеленый-коричневый и зеленый-голубой. Если из А в Б идем по черной, то тоже 3 варианта — черный-желтый, черный-коричневый и черный-голубой. Получаем 6 путей через Б, значит всего 7 путей.
Перебор вариантов помог нам решить предыдущие задачи, но часто вариантов в задаче так много, что перебрать их все очень сложно. Поэтому нам надо научиться считать количество вариантов, не перебирая их.
Задача 3.
У Миши есть 5 кубиков разных цветов (по 1 кубику каждого цвета). Сколько разных башенок из 2 кубиков он может построить?
Решение. Первый кубик Миша может выбрать 5 способами – любой из 5. После того, как он уже выбрал 1 кубик, их осталось только 4. Значит, для любого из 5 первых кубиков он может выбрать 4 варианта второго.
Всего получаем 4*5=20 вариантов.
Задача 4.
У Лизы есть паровозик с 4 вагонами и 4 игрушки – мишка, собачка, кошка и заяц. Сколькими способами она может рассадить игрушки по вагонами?
Решение.
Пассажира для 1 вагона Лиза может выбрать 4 способами – любую из игрушек. Для второго вагона – любого из 3 оставшихся. Для третьего – любого из 2 оставшихся. И в четвертый вагон уже сядет тот, кто останется. Получаем 4*3*2*1=24 способа.