занятие 5

Тема: Комбинаторика

     Сколькими способами можно проехать из города А в город В? Сколько разных слов в языке племени Мумбо-Юмбо? Сколько существует "симпатичных" четырехзначных чисел? Сколько...? Такие и некоторые другие, похожие на них, вопросы будут обсуждаться в этой теме.

     Начнем с нескольких простых задач.

     Задача 1. В магазине "Всё для чая" есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем? (да-да, некоторым из вас эти задачи хорошо знакомы, остается только воспроизвести решение) 

     Решение. Выберем чашку. В комплект к ней можно выбрать любое из трех блюдец. Поэтому есть 3 разных комплекта, содержащих выбранную чашку. Поскольку чашек всего 5, то число различных комплектов равно 15 (15 = 5 • 3).
     Задача 2. В магазине "Всё для чая" есть еще 4 чайные ложки. Сколькими способами можно купить комплект из чашки, блюдца, ложки?

     Решение. Выберем любой из 15 комплектов предыдущей задачи. его можно дополнить ложкой четырьмя различными способами. Поэтому общее число возможных комплктов равно 60 (60 = 15 • 4 = 5 • 3 • 4).
     Задача 3. В Стране Чудес есть три города: А, Б и В. Из города А в город Б ведёт 6 дорог, а из города Б в город В - 4 дороги. Сколькими способами можно проехать от А до В?

     Ответ: 24 = 6 • 4

     Задача 4. В Стране Чудес построили еще один город - Г и несколько новых дорог. Сколькими способами можно теперь добраться из города А в город В?

     Решение: выделим два случая: путь проходит через город Б или через город Г. В каждом из этих случаев легко сосчитать количество возможных маршрутов: в первом - 24, во втором - 6. Складывая, получаем общее количество маршрутов: 30.

     Задача 5. В магазине "Всё для чая" по-прежнему продается 5 чашек, 3 блюдца и 4 чайные ложки. Сколькими способами можно купить два предмета с разными названиями?

     Решение. Возможны три разных случая: первый - покупаются чашка с блюдцем, второй - чашка с ложкой, третий - блюдце и ложка. В каждом из этих случаев считаем количество возможных вариантов методом умножения (в первом - 15, во втором - 20, в третьем - 12). Складывая, получаем общее число возможных вариантов: 47.

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

Задачи для самостоятельного решения.

      Задача 6. В киоске "Роспечать" продаются 5 видов конвертов и 4 вида марок. Сколькими способами можно купить конверт с маркой?

     Задача 7. Сколькими способами можно выбрать гласную и согласную буквы из слова "КРУЖОК"?

     Задача 8. На доске написаны 7 существительных, 5 глаголов и 2 прилагательных. Для предложения нужно выбрать по одному слову каждой из этих частей речи. Сколькими способами это можно сделать?

     Задача 9. У двух начинающих коллекционеров по 20 марок и по 10 значков. Честным обменом называется обмен одной марки на одну марку или одного значка на один значок. Сколькими способами коллекционеры могут осуществить честный обмен?

     Задача 10. Сколько существует 6-значных чисел, все цифры которых имеют одинаковую чётность?

     Задача "не в тему". В Стране Чудес проводилось следствие об украденной муке. На суде Мартовский Заяц заявил, что муку украл Болванщик. В свою очередь, Болванщик и Соня дали показания, которые по каким-то причинам не были записаны. В ходе судебного заседания выяснилось, что муку украл лишь один из подсудимых и что только он дал правдивые показания. Кто украл муку?

   

Ответы и решения   

     Задача 6.  К каждому конверту одна из 4 марок, а конвертов - 5, значит, 5 • 4 = 20.

     Задача 7. Обратите внимание, что различных согласных в этом слове 3, а не 4! И, значит, решение будет таким: 3 • 2 = 6.

     Задача 8. 7 • 5 • 2 = 70.

     Задача 9. Обмен марками: 20 • 20 = 400 вариантов, обмен значками:  10 • 10 = 100 вариантов, а всего получается 400 + 100 = 500 способов честного обмена.

     Задача 10. В этой задаче нужно рассмотреть 2 возможных ситуации: все цифры четные и все цифры нечетные, затем просуммировать полученные результаты. Количество чисел с четными и нечетными числами будет различным, потому что 0 не может быть первой цифрой числа. Итак, используем метод точек для случая с нечетными цифрами:  •     •     •     •     •     •

                                          5    5    5    5     5    5

Ведь на любом месте может стоять любая из 5 нечетных цифр, таких чисел будет 5⁶.

Теперь используем метод точек для случая с четными цифрами:

•     •     •     •     •     •

4    5    5    5     5    5

Если исключить 0, то для выбора первой цифры остается только 4 варианта, а для остальных цифр - по 5 вариантов. Всего таких чисел будет 4 • 5⁵.

Подсчитываем общее количество 6-значных чисел, все цифры которых имеют одинаковую четность: 5⁶  + 4 • 5⁵  = 15625 + 12500 = 28125.

     Задача "не в тему". Если бы украл Мартовский Заяц, то его показания должны быть правдой, но ведь он утверждал, что вор - Болванщик, получается 2 вора, пришли к противоречию. Если бы украл Болванщик, то показание Зайца оказывается правдой, а по условию правду сказал именно вор. Еще одно противоречие. Таким образом, методом исключения получаем, что муку украла Соня, и совсем неважно, какие показания она давала.