Комбинаторика
Когда футбольный судья, чтобы распределить ворота между командами, подбрасывает монетку, нам кажется это справедливым. То есть вероятность выпадения герба и решки мы считаем одинаковой – 1/2 каждая.
А если бросать не монетку, а игральный кубик? Четное количество очков – одни ворота, нечетное – другие. Будет ли это справедливо? Да, будет. Вероятность четного и нечетного тоже равная – 1/2.
А откуда нам это известно?
Тут есть два способа убедиться:
1. Долго наблюдать, как подбрасывают монету. И убедиться, что она выпадает решкой и гербом примерно равное число раз. То же самое с кубиком.
2. Рассчитать вероятность. Сколько решек у монеты? Одна. А сторон? Две. Чтобы посчитать вероятность, нужно число подходящих вариантов поделить на общее число. То есть .
У кубика 6 сторон, а сторон с четным количеством очков – 3. То есть, чтобы посчитать вероятность четного количества очков, делим 3:6
Для расчета нам нужно считать количество вариантов. Иногда это совсем просто – как с монеткой или кубиком, а иногда нужно подумать.
Например, у малыша 5 кубиков разных цветов. Сколько разных башен можно из них построить?
Еще один пример. Сколько существует разных автомобильных номеров вида п126од? Хватит ли их на все машины в городе? А в стране?
И тут нам на помощь приходит комбинаторика.
Слово «комбинаторика» происходит от слова «комбинация». Занимается она как раз вычислением количества комбинаций или способов сделать что-нибудь.
Она использует очень простые принципы, которыми мы и так пользуемся в обычной жизни. Давайте обсудим некоторые.
Представьте, что у вас 3 сорта масла и 4 сорта сыра. Вы хотите намазать хлеб маслом и положить кусочек сыра. Сколько вариантов у вас существует?
Решение.
Логика очень простая. Мажем первым сортом масла. После этого можно положить 4 разных сорта сыра. То есть 4 типа бутербродов с первым сортом масла.
Аналогично со вторым и третьим.
То есть всего видов бутербродов.
Мы хотели бутерброд с маслом и сыром вместе. Чтобы найти количество комбинаций, нужно было перемножить количество вариантов каждого.
Это правило назовем «Закон умножения» (Закон И – «масло и сыр»).
Пусть теперь вы хотите бутерброд только с маслом или сыром. Сколько вариантов?
Решение.
Очевидно, нужно сложить количество вариантов сортов масла и сыра.
То есть когда нам нужно только или одно, или другое, нужно сложить количество вариантов каждого.
3 + 4 = 7
Это правило назовем «Закон сложения» (закон ИЛИ «масло или сыр»).
Пусть к трем сортам масла и 4-м сыра появилось еще пять сортов колбасы.
Вы согласны есть бутерброд с маслом и сыром, или просто с колбасой. Сколько вариантов?
Решение:
«С маслом и сыром»: используем закон умножения .
«Или с колбасой»: закон сложения
Понятно, что если вы бы делали бутерброды с маслом, сыром и колбасой одновременно, то количество вариантов было бы другое:
Посчитаем теперь количество номеров для автомобилей.
Решение.
Номер выглядит так: буква, три цифры, еще две буквы.
Всего букв 33. Но не используются «Ь», «Ъ», «Ё» и «Й». Остается 29.
Какой закон нужно применять? Нам нужно все три буквы и все три цифры. То есть здесь закон умножения.
Выбрать каждую букву 29 способов, каждую цифру 10 способов.
Считаем:
Ответ: 24 389 000.
Давайте решим задачку с башней из 5 кубиков.
Есть пять разных кубиков, сколько разных башен можно из них построить?
Решение.
Ставим первый кубик. Сколько существует вариантов? 5.
Так как нам нужно поставить все кубики (все этажи), то есть и первый, и второй, и так далее, то используем закон умножения (закон И). Сколько вариантов для второго кубика? 4 – у нас всего столько кубиков осталось. Потом 3, 2, и наконец, для последнего кубика уже остался один вариант.
Перемножаем - вариантов.
А если башню можно строить любой высоты от одного до пяти этажей?
Решение:
Вот здесь уже понадобится в том числе закон ИЛИ, закон сложения. Ведь нас устраивает 1 этаж или два этажа и так далее 5 этажей.
Считаем по отдельности количество вариантов для разных этажей, а потом складываем.
5 этажей:
4 этажа:
Не надо удивляться, что получилось одинаково, ведь последний кубик выбирался одним способом и не добавлял вариантов.
3 этажа:
2 этажа:
1 этаж : 5
Теперь считаем, сколько всего:
То есть из 5 кубиков, только ставя один кубик на другой, можно построить 325 разных башен, различающихся высотой или последовательностью цветов кубиков.
Ответ : 120, 325.
Если вы по какой-то причине не можете понять, какой закон применять в той или иной задаче – сложения или умножения, то можно попробовать просто выписать все существующие варианты и посчитать их количество. Такой прием называется «Логика перебора». Понятно, нужно, чтобы вариантов было не очень много.
Решим задачу.
Сколько можно составить трехбуквенных слов из букв: ОКТИ?
Решение.
Совсем просто: нужно выбрать три буквы. Для первой есть 4 способа, для следующей – уже три, и для третьей – два.
А теперь чуть-чуть изменим задание: сколько можно составить ОСМЫСЛЕННЫХ трехбуквенных слов из букв ОКТИ?
Тут уже не получается воспользоваться простым перемножением, поэтому нужно рассмотреть все возможные варианты.
Первую букву можно выбрать 4-мя способами.
Когда первая буква выбрана, остается 3 способа для второй. Для третьей буквы уже два варианта.
Итак, мы выписали все возможные варианты. Получилось дерево, только растет оно вниз, а не вверх. Его часто называют деревом возможностей.
Осталось подряд читать все полученные слова сверху вниз и выбирать те, которые имеют смысл.
КОТ КТО КИО КИТ ТОК ТКИ ТИК
Ответ: 7 слов.
Итак, существуют ситуации, когда необходимо посчитать количество возможных вариантов:
1. чтобы посчитать вероятность наступления того или иного события и принять правильное решение;
2. чтобы дать большому количеству объектов числовые или буквенные имена (номера автомобилей, номера телефонов) нужно понять, хватит ли их на всех.
Приемы счета комбинаций назвали комбинаторикой.
Закон умножения, закон И. Когда нужно взять и то и другое, нужно перемножить количество вариантов одного и другого.
Закон сложения, закон ИЛИ. Когда нужно взять или одно, или другое, нужно сложить количество вариантов того и другого.
Когда мы не можем применить закон умножения или сложения, мы выписываем все возможные комбинации. Строим дерево возможностей. Потом считаем те, что нас устраивают.
Давайте посмотрим, как комбинаторика помогает принять нам правильное решение и как ее незнание уменьшает наши шансы на успех.
В игре «Поле Чудес» часто используется парадокс Монти Холла.
Вам выносят три одинаковые шкатулки. В одной из них лежит приз, например, ключ от автомобиля.
Вы выбираете одну шкатулку. Понятно, что если сразу открыть вашу шкатулку, то шансы выиграть у вас – , или примерно 33 %.
Но ведущий, после того как вы выбрали свою шкатулку, делает следующее. Он говорит: «я открою одну пустую шкатулку среди двух оставшихся». И открывает. Он знает, где лежит ключ. И перед вами теперь две закрытые шкатулки – та, что вы выбрали и та из двух оставшихся, которую ведущий не открыл. Теперь вам разрешается передумать и поменять шкатулку, если хотите. Вопрос – нужно ли это делать? Люди думают по-разному.
Одни говорят: «конечно, нужно поменять, ведь у меня был шанс выиграть , значит, все оставшееся – это ».
Другие говорят: «нет, перед нами две закрытые шкатулки, ключ в любой из них, вероятности одинаковы. Нет смысла менять решение. Просто моя вероятность выросла с до ». Вроде бы оба мнения логичны. Но они не могут быть оба одновременно верны. В этом и парадокс.
Решим эту задачу с помощью логики перебора, то есть изучим все возможные варианты. Построим дерево возможностей (см. Рис. 4).
Запишем все возможные варианты нашего выбора. Их три: 1, 2 или 3 шкатулка. Обозначим эти варианты В1, В2 и В3 (выбрали 1, выбрали 2, выбрали 3).
В каждом случае ключ может оказаться в одной из трех шкатулок. Обозначим К1, К2 и К3.
Получили 9 веток. Ветка В2К3, например, означает, что мы выбрали 2-ю шкатулку, а ключ лежал в 3-й.
Посчитаем шансы игрока, который не меняет своего начального решения.
Он выиграет во всех случаях, когда сделал изначально правильный выбор. В1К1, В2К2 и В3К3.
То есть в 3 из 9 случаях. Вероятность выигрыша – .
Посчитаем шансы того, кто меняет свое решение.
Он выиграет во всех случаях, когда сначала сделал неверный выбор В1К2, В1К3, В2К1, В2К3, В3К1, В3К2
То есть в 6 из 9 случаях. Вероятность выигрыша – .
Таким образом, мы понимаем, что, когда ведущий открыл пустую коробку, нам надо изменить свое решение, шансы увеличатся в два раза.