Классы
Предметы

Комбинаторика

Этот видеоурок доступен по абонементу
Подробнее об абонементе, платных и бесплатных уроках

У вас уже есть абонемент? Войти

Оплатить абонементот 75 руб. в месяц
У вас уже есть абонемент? Войти
Комбинаторика

На этом уроке мы познакомимся с комбинаторикой, узнаем ее основные свойства и научимся применять их в повседневной жизни. Узнаем, как пользоваться «деревом возможностей» и о парадоксе «Монти-Холла».

Введение

Когда футбольный судья, чтобы распределить ворота между командами, подбрасывает монетку, нам кажется это справедливым. То есть вероятность выпадения герба и решки мы считаем одинаковой –  каждая (см. Рис. 1).

 

Рис. 1. Монетка (Источник)

А если бросать не монетку, а игральный кубик? Четное количество очков – одни ворота, нечетное – другие. Будет ли это справедливо? Да, будет. Вероятность четного и нечетного тоже равная – .

А откуда нам это известно?

Тут есть два способа убедиться:

1.                  Долго наблюдать, как подбрасывают монету. И убедиться, что она выпадает решкой и гербом примерно равное число раз. То же самое с кубиком.

2.                  Рассчитать вероятность. Сколько решек у монеты? Одна. А сторон? Две. Чтобы посчитать вероятность, нужно число подходящих вариантов поделить на общее число. То есть .

У кубика 6 сторон, а сторон с четным количеством очков – 3. То есть, чтобы посчитать вероятность четного количества очков, делим 3:6 =  (см. Рис. 2).

Рис. 2. Кубик в развороте (Источник)

Для расчета нам нужно считать количество вариантов. Иногда это совсем просто – как с монеткой или кубиком, а иногда нужно подумать.

Например, у малыша 5 кубиков разных цветов. Сколько разных башен можно из них построить?

Еще один пример. Сколько существует разных автомобильных номеров вида п126од? Хватит ли их на все машины в городе? А в стране?

И тут нам на помощь приходит комбинаторика.

Слово «комбинаторика» происходит от слова «комбинация». Занимается она как раз вычислением количества комбинаций или способов сделать что-нибудь.

Она использует очень простые принципы, которыми мы и так пользуемся в обычной жизни. Давайте обсудим некоторые.

Закон умножения

Представьте, что у вас 3 сорта масла и 4 сорта сыра. Вы хотите намазать хлеб маслом и положить кусочек сыра. Сколько вариантов у вас существует?

Решение.

Логика очень простая. Мажем первым сортом масла. После этого можно положить 4 разных сорта сыра. То есть 4 типа бутербродов с первым сортом масла.

Аналогично со вторым и третьим.

То есть всего  видов бутербродов.

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

Это правило назовем «Закон умножения» (Закон И – «масло и сыр»).

Закон сложения

Пусть теперь вы хотите бутерброд только с маслом или сыром. Сколько вариантов?

Решение.

Очевидно, нужно сложить количество вариантов сортов масла и сыра.

То есть когда нам нужно только или одно, или другое, нужно сложить количество вариантов каждого.

3 + 4 = 7

Это правило назовем «Закон сложения» (закон ИЛИ «масло или сыр»).

Пример на оба закона

Пусть к трем сортам масла и 4-м сыра появилось еще пять сортов колбасы.

Вы согласны есть бутерброд с маслом и сыром, или просто с колбасой. Сколько вариантов?

Решение:

«С маслом и сыром»: используем закон умножения  .

«Или с колбасой»: закон сложения 

Понятно, что если вы бы делали бутерброды с маслом, сыром и колбасой одновременно, то количество вариантов было бы другое:

Задача 1

Посчитаем теперь количество номеров для автомобилей.

Решение.

Номер выглядит так: буква, три цифры, еще две буквы.

Всего букв 33. Но не используются «Ь», «Ъ», «Ё» и «Й». Остается 29.

Какой закон нужно применять? Нам нужно все три буквы и все три цифры. То есть здесь закон умножения.

Выбрать каждую букву 29 способов, каждую цифру 10 способов.

Считаем:

Ответ: 24 389 000.

Задача 2

Давайте решим задачку с башней из 5 кубиков.

Есть пять разных кубиков, сколько разных башен можно из них построить?

Решение.

Ставим первый кубик. Сколько существует вариантов? 5.

Так как нам нужно поставить все кубики (все этажи), то есть и первый, и второй, и так далее, то используем закон умножения (закон И). Сколько вариантов для второго кубика? 4 – у нас всего столько кубиков осталось. Потом 3, 2, и наконец, для последнего кубика уже остался один вариант.

Перемножаем -  вариантов.

А если башню можно строить любой высоты от одного до пяти этажей?

Решение:

Вот здесь уже понадобится в том числе закон ИЛИ, закон сложения. Ведь нас устраивает 1 этаж или два этажа и так далее 5 этажей.

Считаем по отдельности количество вариантов для разных этажей, а потом складываем.

5 этажей:

4 этажа:

Не надо удивляться, что получилось одинаково, ведь последний кубик выбирался одним способом и не добавлял вариантов.

3 этажа:

2 этажа:

1 этаж : 5

Теперь считаем, сколько всего:

То есть из 5 кубиков, только ставя один кубик на другой, можно построить 325 разных башен, различающихся высотой или последовательностью цветов кубиков.

Ответ : 120, 325.

Логика перебора

Если вы по какой-то причине не можете понять, какой закон применять в той или иной задаче – сложения или умножения, то можно попробовать просто выписать все существующие варианты и посчитать их количество. Такой прием называется «Логика перебора». Понятно, нужно, чтобы вариантов было не очень много.

Задача 3

Решим задачу.

Сколько можно составить трехбуквенных слов из букв: ОКТИ?

Решение.

Совсем просто: нужно выбрать три буквы. Для первой есть 4 способа, для следующей – уже три, и для третьей – два.

А теперь чуть-чуть изменим задание: сколько можно составить ОСМЫСЛЕННЫХ трехбуквенных слов из букв ОКТИ?

Тут уже не получается воспользоваться простым перемножением, поэтому нужно рассмотреть все возможные варианты.

Первую букву можно выбрать 4-мя способами.

Когда первая буква выбрана, остается 3 способа для второй. Для третьей буквы уже два варианта.

Итак, мы выписали все возможные варианты. Получилось дерево, только растет оно вниз, а не вверх. Его часто называют деревом возможностей (см. Рис. 3).

Рис. 3. Дерево возможностей

Осталось подряд читать все полученные слова сверху вниз и выбирать те, которые имеют смысл.

КОТ   КТО   КИО   КИТ   ТОК   ТКИ   ТИК

Ответ: 7 слов.

Заключение

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

1. чтобы посчитать вероятность наступления того или иного события и принять правильное решение;

2. чтобы дать большому количеству объектов числовые или буквенные имена (номера автомобилей, номера телефонов) нужно понять, хватит ли их на всех.

Приемы счета комбинаций назвали комбинаторикой.

Закон умножения, закон И. Когда нужно взять и то и другое, нужно перемножить количество вариантов одного и другого.

Закон сложения, закон ИЛИ. Когда нужно взять или одно, или другое, нужно сложить количество вариантов того и другого.

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

Парадокс Монти Холла

Давайте посмотрим, как комбинаторика помогает принять нам правильное решение и как ее незнание уменьшает наши шансы на успех.

В игре «Поле Чудес» часто используется парадокс Монти Холла.

Вам выносят три одинаковые шкатулки. В одной из них лежит приз, например, ключ от автомобиля.

Вы выбираете одну шкатулку. Понятно, что если сразу открыть вашу шкатулку, то шансы выиграть у вас – , или примерно 33 %.

Но ведущий, после того как вы выбрали свою шкатулку, делает следующее. Он говорит: «я открою одну пустую шкатулку среди двух оставшихся». И открывает. Он знает, где лежит ключ. И перед вами теперь две закрытые шкатулки – та, что вы выбрали и та из двух оставшихся, которую ведущий не открыл. Теперь вам разрешается передумать и поменять шкатулку, если хотите. Вопрос – нужно ли это делать? Люди думают по-разному.

Одни говорят: «конечно, нужно поменять, ведь у меня был шанс выиграть , значит, все оставшееся – это ».

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

Решим эту задачу с помощью логики перебора, то есть изучим все возможные варианты. Построим дерево возможностей (см. Рис. 4).

Запишем все возможные варианты нашего выбора. Их три: 1, 2 или 3 шкатулка. Обозначим эти варианты В1, В2 и В3 (выбрали 1, выбрали 2, выбрали 3).

В каждом случае ключ может оказаться в одной из трех шкатулок. Обозначим К1, К2 и К3.

Получили 9 веток. Ветка В2К3, например, означает, что мы выбрали 2-ю шкатулку, а ключ лежал в 3-й.

Рис. 4. Дерево возможностей для парадокса Монти Холла

Посчитаем шансы игрока, который не меняет своего начального решения.

Он выиграет во всех случаях, когда сделал изначально правильный выбор. В1К1, В2К2 и В3К3.

То есть в 3 из 9 случаях. Вероятность выигрыша – .

Посчитаем шансы того, кто меняет свое решение.

Он выиграет во всех случаях, когда сначала сделал неверный выбор В1К2, В1К3, В2К1, В2К3, В3К1, В3К2

То есть в 6 из 9 случаях. Вероятность выигрыша – .

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

 

Список литературы

  1. Математика. 5 класс. Зубарева И.И., Мордкович А.Г. 14-е изд., испр. и доп. – М.: 2013. Стр. 249.
  2. Виленкин Н.Я. и др. Математика. 5 кл. – М: Мнемозина, 2013.
  3. Ерина Т.М. Математика 5кл. Раб. тетрадь к уч. Виленкина 2013. – М: Мнемозина, 2013.

  

Дополнительные рекомендованные ссылки на ресурсы сети Интернет

  1. Интернет-портал Festival.1september.ru (Источник).
  2. Интернет-портал anna-kobets.ru (Источник).
  3. Интернет-портал Nsportal.ru (Источник).

 

Домашнее задание

  1. Математика. 5 класс. Зубарева И.И., Мордкович А.Г. 14-е изд., испр. и доп. – М.: 2013. Стр. 255 № 972.
  2. Сколько существует двузначных чисел, составленных из цифр: 0, 6, 9?
  3. В меню столовой на выбор предложены 3 первых блюда, 6 вторых и 4 третьих. Сколько различных вариантов блюд, состоящих из 1 первого, 1 второго, 1 третьего блюда можно составить из предложенного меню?