Комбинаторика.
Что такое комбинаторика и как решать задачи на эту тему, мы изучали на занятии 5. Можно пройти по ссылке и вспомнить уже рассмотренные задачи. На этом занятии мы продолжаем учиться перебирать все варианты и способы сделать что-либо.
Напомним, что такие задачи мы решаем путём упорядоченного перебора всех вариантов, то есть перебора в каком-то определённом порядке, чтобы никакие варианты не пропустить и не посчитать лишний раз одни и те же. При достаточном освоении упорядоченного перебора можно постепенно переходить от перебора вариантов к рассуждениям и соответствующим вычислениям.
Задача 1.
Сколькими способами можно дойти от красной клетки до синей, если двигаться можно только вверх и вправо?
Решение.
1 способ — перебор.
Будем перебирать все пути. Сначала те пути, где первый шаг будет вверх, их 3:
Теперь найдём все пути, где первый шаг делается вправо, их тоже 3:
Таким образом, всего есть 3+3=6 способов добраться от красной клетки до синей.
2 способ — рассуждения и перебор.
Обратим внимание, чтобы добраться из красной клетки в синюю, нужно сделать всего 2 шага вверх и 2 шага вправо в любом порядке. Чтобы найти все пути, нужно перечислить все возможные последовательности из 2 шагов вверх (В) и 2 шагов вправо (П): ВВПП, ППВВ, ВППВ, ПВВП, ВПВП, ПВПВ.
Ответ: 6 способами.
Задача 2.
Женя нарисовал много флажков, состоящих из 3 горизонтальных полосок, и теперь хочет раскрасить эти флажки. У Жени есть красный, жёлтый и зелёный фломастеры. Он хочет раскрасить каждую полоску флажка только одним цветом, и чтобы все полоски в каждом флажке были разными.
а) Сколько разных флажков получится у Жени?
б) Сколько разных флажков получится у Жени, если он не хочет, чтобы средняя полоска была жёлтой?
Решение.
а) 1 способ — перебор.
Будем перечислять все варианты флажков, которые получатся у Жени. Сделаем это в таком порядке: сначала посчитаем флажки, у которых верхняя полоска красная. Тогда средняя и нижняя полоски будут жёлтая и зелёная или, наоборот, зелёная и жёлтая, всего 2 варианта:
Теперь посчитаем флажки, у которых верхняя полоска жёлтая, их тоже 2:
Теперь флажки, у которых верхняя полоска зелёная, их тоже 2:
Никаких других флажков получиться не может, так как мы перечислили все возможные варианты для каждого выбранного цвета верхней полоски. Таким образом, у Жени получится всего 2+2+2=6 разных флажков.
2 способ — рассуждения и вычисления.
Цвет для верхней полоски флажка мы можем выбрать 3 способами. После этого останется два цвета и две нераскрашенные полоски. Значит, цвет для средней полоски мы можем выбрать 2 способами. А всего есть 3*2=6 способов раскрасить верхнюю и среднюю полоски. После этого цвет для нижней полоски можно выбрать только одним способом. Значит, всего есть 3*2*1=6*1=6 способов раскрасить флажок.
б) 1 способ — используем результаты, полученные ранее в части а).
Вычтем из всех найденных вариантов флажков те, в которых средняя полоска жёлтая. Таких флажков всего 2. Значит, флажков, у которых средняя полоска не жёлтая, будет 6-2=4.
2 способ — перебор.
Перечислим все варианты флажков в таком порядке: сначала те флажки, у которых средняя полоска красная, их всего 2:
Теперь те флажки, у которых средняя полоска зелёная, их тоже 2:
Таким образом, всего получится 2+2=4 разных флажка, у которых средняя полоска не жёлтая.
2 способ — рассуждения и вычисления.
Цвет для средней полоски флажка мы можем выбрать 2 способами (красный или зелёный). После этого останется два цвета и две нераскрашенные полоски. Значит, цвет для верхней полоски мы можем выбрать 2 способами, после этого цвет для нижней полоски можно выбрать только 1 способом. Всего есть 2*2*1=4 способа раскрасить флажок так, чтобы средняя полоска была не жёлтая.
Ответ: а) 6 флажков, б) 4 флажка.
Задача 3.
Рита делает открытку для мамы. Она вырезала из бумаги много цветочков с четырьмя лепестками. Теперь ей нужно эти цветочки раскрасить. У Риты есть голубая и розовая краски. Каждый лепесток и серединку цветов она раскрашивает только одним цветом. Сколько разных цветочков получится у Риты?
Решение.
Эту задачу удобнее решать упорядоченным перебором, а не вычислениями.
Посчитаем цветочки с голубой серединкой.
Сначала те, у которых все лепестки одного цвета (все голубые или все розовые, всего 2 варианта):
Теперь те, у которых три лепестка одного цвета, а один лепесток другого цвета, их тоже 2:
Теперь те, у которых 2 лепестка одного цвета и 2 лепестка другого цвета, их тоже 2:
Заметим, что все другие цветочки с голубой серединкой получатся, если повернуть какой-нибудь из перечисленных цветков. Так как все цветочки вырезаны из бумаги, лепестки у них одинаковые, и стеблей у них нет, то цветы, которые отличаются друга от друга только поворотом вокруг серединки, мы считаем одинаковыми. Поэтому других вариантов цветов с голубой серединкой нет.
Всего цветов с голубой серединкой будет 2+2+2=6. И столько же цветов будет с розовой серединкой. Значит, всего получится 6+6=12 разных цветочков.
Ответ: 12 цветочков.
Следующую задачу решим с помощью рассуждений и вычислений.
Задача 4.
В каникулы Оля была на море и привезла оттуда 5 разных красивых камушков и 4 разных ракушки.
а) сколькими способами она может выбрать 1 предмет из этого набора?
б) сколькими способами она может выбрать камушек с ракушкой?
в) сколькими способами она может выбрать 2 предмета, чтобы один подарить маме, а другой бабушке?
г) сколькими способами она может выбрать 2 предмета, чтобы подарить подруге?
Решение.
а) В наборе морских «сокровищ» всего 4+5=9 предметов. Значит, Оля может выбрать любой из них 9 способами.
б) Камушек можно выбрать 5 способами. Для каждого камушка ракушку можно выбрать 4 способами. Значит, Оля может выбрать камушек с ракушкой 5*4=20 способами.
в) Для мамы Оля может выбрать предмет 9 способами (любой из 9). После этого останется 8 предметов. Поэтому для каждого варианта маминого подарка подарок для бабушки можно выбрать 8 способами. Значит, Оля может выбрать 2 предмета (один для мамы, другой для бабушки) 9*8=72 способами.
г) Эта задача очень похожа на пункт в), но теперь Оля выбирает 2 предмета для одной подруги. Первый предмет можно выбрать 9 способами, после этого второй предмет можно выбрать 8 способами. Всего есть 9*8=72 способа выбрать первый и второй предметы. Но, так как оба предмета будут подарены одному человеку, то пары «предмет 1 и предмет 2» и «предмет 2 и предмет 1» — это один и тот же вариант подарка, а мы их посчитали как разные. Значит, на самом деле, Оля может выбрать 2 предмета для одной подруги 9*8:2=36 способами.
Ответ: а) 9 способов, б) 20 способов, в) 72 способа, г) 36 способов.