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

Комбинаторика. Теория вероятностей

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

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

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

На этом уроке мы поговорим о том, как вычисляют количество различных комбинаций (от автомобильных номеров до расписания рейсов) и как это используется в окружающем нас мире (в частности, при решении различных задач логистики). Кроме того, мы обсудим роль случая в жизни человека и то, с помощью каких математических инструментов можно оценить вероятность наступления того или иного события.

Логистика

Представьте, что нам нужно организовать доставку почты с помощью авиасообщения между несколькими городами. Для двух городов решение очевидное: должно быть два рейса (из  в , из  в ) (см. рис. 1).

Рис. 1. Схема для двух городов

Для трех городов можно решить задачу разными способами. Самый простой вариант – организовать маршруты между всеми городами – шесть рейсов (см. рис. 2).

Рис. 2. Схема для трех городов

Но можно обойтись и , если города  и , например, будут сообщаться через город  (см. рис. 3).

Рис. 3. Схема для трех городов (сообщение через город )

Немного сложнее организовать систему (нужно, чтобы самолет с почтой из  прилетел в , там его разгрузили, забрали часть почты, которая предназначается для города , погрузили на самолет с почтой из  в , и только после этого полетел этот самолет; аналогичная ситуация с самолетом из  в ), зато эта система может оказаться экономически более выгодной – все-таки экономия в  рейса.

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

Рис. 4. Схема для десяти городов (сообщение  городов друг с другом через )

Рис. 5. Схема для десяти городов (соединение между собой всех  городов)

При дальнейшем увеличении городов схема работы хаба станет сложной и неэффективной (возможна путаница, неудобные стыковки рейсов и т. д.). Поэтому, скорее всего, нужно будет искать компромисс – например, делать несколько хабов, которые будут сообщаться между собой (см. рис. 6).

Рис. 6. Схема для большого количества городов (несколько хабов)

Поиском оптимальных решений таких задач, как организация доставки почты между городами, занимается специальная наука – логистика. А математика является одним из ее важнейших инструментов.


 

Примеры хабов

На самом деле, мы встречаемся с примерами хабов гораздо чаще, чем это замечаем.

Например, саммиты глав государств – это тоже своего рода использование модели хаба. На саммит  приезжают главы  государств. Представьте, сколько времени и перелетов им бы понадобилось, чтобы увидеться и поговорить, если бы они летали друг к другу. А так нужно всего  рейсов ( глав поочередно слетаются к одному главе страны-хозяйки и потом улетают обратно) и несколько дней, за которые можно провести необходимые двух-, трех- и многосторонние встречи.

Для большой структуры один хаб неэффективен: он будет слишком перегружен, а объекты на периферии слабо связаны друг с другом. Поэтому используют несколько хабов. Иногда эти хабы общаются через один или несколько суперхабов и т. д.

Именно поэтому государства обычно делятся на регионы, например области, которые, в свою очередь, делятся на районы и т. д. Такая система позволяет достаточно эффективно управлять деятельностью всех субъектов и контролировать ее.

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

Есть и менее очевидные примеры хабов. Например, деньги. Если вы производите ложки, а я – вилки, то как нам ими обмениваться? Сколько ложек стоит одна вилка? А наоборот? А представьте, что товаров сотни. Деньги – это универсальный эквивалент. Я продаю вилки и на вырученные деньги покупаю у вас ложки. Согласитесь, идея та же, что и у транспортного хаба.


 

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

В примере с  городами мы сказали, что для соединения всех  городов между собой понадобится  рейсов. Как это посчитать?

Из города  в каждый из  остальных должен летать  рейс, т. е.  рейсов для города  (см. рис. 7).

Рис. 7. Из города  в каждый из  остальных должен летать  рейс

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

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

Рассмотрим еще несколько примеров ситуаций, в которых нужно вычислить количество различных вариантов. Задумывались ли вы когда-нибудь о том, почему в телефонных номерах столько цифр? Первые цифры означают код страны, затем идет код города или мобильного оператора из  цифр, затем номер из  цифр. Почему именно ? Если бы в номере было меньше цифр (), то его было бы легче запомнить.

Или такой вопрос: почему более длинный пароль считается более надежным? А если использовать не только цифры, но еще и буквы, и специальные символы, то надежность увеличивается?

В каждом из вопросов ответ кроется в количестве комбинаций, которые можно создать из цифр или букв. Если в номере будет меньше  цифр, то количества различных комбинаций цифр может не хватить всем абонентам. А при увеличении длины пароля и количества используемых символов увеличивается количество комбинаций, которые можно из них составить. Соответственно, мошенникам сложнее подобрать пароль, он становится более надежным.

Раздел математики, который занимается подсчетом количества различных комбинаций, так и называется – комбинаторика.

Правила сложения и умножения

С помощью инструментов комбинаторики, которые мы изучим на сегодняшнем уроке, можно ответить на множество практических вопросов. Например, стоит ли покупать лотерейный билет? Какой шанс выиграть? Оказывается, что если в лотерейном билете нужно угадать  номеров из , то шанс оказаться счастливчиком –  из .

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

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

 

Задача 1. В гардеробе ученика есть  рубашки и  футболок. Сколько существует вариантов выбрать одежду для прогулки?

Решение.

Задача решается устно: ответ .

Можно выбрать одну из  рубашек или одну из  футболок:

Ответ: .

В общем виде, если есть  рубашек и  футболок, то вариантов выбора будет:

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

Задача 2. В гардеробе ученицы есть  платья и  пар туфель. Сколько всего есть вариантов выбрать платье и туфли?

Решение.

Посчитаем абсолютно все варианты сочетаний: к первому платью можно выбрать  пар туфель (см. рис. 8); ко второму – тоже , и к третьему .

Рис. 8. Иллюстрация к задаче 2

Получаем всего  вариантов. Или более коротко это можно записать с помощью умножения:

Ответ: .

В общем виде: если есть  платьев и  пар туфель, то платье и туфли можно выбрать  способами.

Обобщим и эту задачу, сформулировав правило умножения: при независимом выборе нескольких элементов необходимо умножить количество вариантов выбора. Это правило иногда называют «правилом И», ведь мы выбирали и платье, и туфли.


 

Задача на применение правил умножения и сложения

В меню есть  различных комплексных обеда (в них входит первое и второе): вида первого блюда,  вида второго и  вида напитков. Сколько существует способов выбрать обед, состоящий из первого, второго и напитка? (Считаем, что первые и вторые блюда, которые встречаются в комплексном обеде, отдельно не продаются.)

Решение.

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

(комплексный обед И напиток) ИЛИ (первое И второе И напиток)

Еще это можно изобразить графически (см. рис. 9):

Рис. 9. Иллюстрация к задаче

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

Ответ:  вариантов выбора.

Обратите внимание: если бы не было сказано, что первые и вторые блюда в комплексных обедах и отдельно не пересекаются, то у нас варианты из двух разных наборов могли бы совпасть («суп  пюре  чай» и «суп  пюре  чай»). И в этом случае без дополнительных условий мы бы решить задачу не смогли. Единственный вывод, который мы бы смогли сделать: не больше  вариантов выбора.

Как видите, если вы правильно переформулируете задачу, используя «ИЛИ» и «И», то вычисления будут очень простыми.


Задача 3. Семья решила выбраться за город на машине. Папа едет за рулем. Сколькими способами можно рассадить оставшихся  членов семьи в машине (см. рис. 10)?

Рис. 10. Иллюстрация к задаче 3

Решение.

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

На переднее место можно выбрать одного из членов семьи:  варианта. Далее одного мы уже выбрали, осталось трое. Значит, вариантов выбора, кто сядет за водителем, у нас :

Осталось рассадить двоих. Т. е. для центрального места будет  варианта:

И на последнее место останется лишь  вариант:

Получим ответ:  варианта.

Ответ: .


 

Уточнение условия задачи

Решая задачу именно таким образом, мы по умолчанию предположили, что все изображенные варианты рассадки – различны и возможны. Но может быть такое, что нам не важно, в каком порядке размещены пассажиры на заднем сидении. В таком случае нам достаточно выбрать пассажира, который будет сидеть на переднем сидении:  варианта. Остальные, соответственно, будут на заднем сидении в любом порядке. Получим в итоге ответ .

Или же нам важен порядок посадки, но мама точно хочет поехать на заднем сидении. Тогда вариантов выбрать пассажира на переднее сидение будет  (один из троих детей). На место за водителем – тоже  (мама и два оставшихся ребенка). На остальные места, соответственно,  и . Ответ, в таком случае, будет:  вариантов. При решении любой задачи необходимо учитывать все условия, чтобы правильно посчитать всевозможные варианты.


 

Задача Эйлера про мосты

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

Но иногда модель сводится к эквивалентной математической задаче, которая оказывается важнейшим инструментом для решения целого класса других, совершенно непохожих, на первый взгляд, задач. Одним из таких примеров является задача Эйлера про мосты.

Издавна среди жителей Кенигсберга (сейчас – Калининграда) была распространена такая загадка: как пройти по всем городским мостам (через реку Преголя), не проходя ни по одному из них дважды (см. рис. 11)?

Рис. 11. Иллюстрация к задаче Эйлера про мосты

В  задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера (см. рис. 12). Он доказал, что сделать это нельзя.

Рис. 12. Леонард Эйлер

Но важно, конечно, не само решение этой шуточной задачи, а то, что, решая ее, Эйлер свел ее к эквивалентной формулировке, которая помогла разработать принципиально новый математический инструмент – теорию графов, которая сейчас повсеместно используется, например в программировании.

Основная идея Эйлера: нам не важны размеры мостов, значит, их можно считать линиями, а также размеры частей города – их можно считать точками (см. рис. 13). Тогда задача сводится к такой: можно ли нарисовать такой граф, не отрывая карандаша от бумаги.

Рис. 13. Мосты можно считать линиями, а города – точками, т. к. их размеры не важны

Решая задачу про  мостов, Эйлер вывел несколько важных теорем, касающихся различных графов. Одна из них говорила, что граф с более чем двумя нечетными вершинами (т. е. вершинами, к которым ведет нечетное число ребер) нельзя начертить одним росчерком.

Интуитивное доказательство этого утверждения несложное: рисуя граф, не отрывая руки, мы должны входить и выходить из каждой точки одинаковое количество раз, т. е. в точке должно сходиться только четное количество ребер (см. рис. 14).

Рис. 14. Чтобы граф можно было нарисовать, не отрывая руки, у него должно быть не более двух  нечетных вершин

Исключение составляют две вершины – начало (из этой точки мы выходим на один раз больше, чем входим) и конец (для него все наоборот). Если же таких вершин больше, то начертить граф одним росчерком не получится. У графа из задачи про  мостов все  вершины нечетные (см. рис. 15), поэтому задача не имеет решения.

Рис. 15. У графа из задачи про  мостов все  вершины нечетные

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


 

 

Факториал

Если пронумеровать места в машине, то объяснение выйдет намного короче: на первое место 4 варианта выбора, на второе – 3, на третье – 2, на четвертое – 1:

Интересно, что такое решение подойдет к множеству подобных задач: «сколько четырехзначных чисел можно составить из цифр , если каждую цифру можно использовать ровно 1 раз» или «сколькими способами можно переставить буквы в слове «парк» » и т. д.

Подобные задачи называются «задачами на перестановки», ведь в них мы, по сути, считаем количество вариантов переставить некоторые различные элементы. Только что мы рассчитали количество перестановок четырех элементов (см. рис. 16):

Рис. 16. Количество перестановок четырех элементов

В общем случае, если у нас будет  элементов, то, применяя правило умножения, мы получим:  (и т. д. до ). Сокращенно это произведение обозначают и записывают так (а называют «эн факториал»):


 

Свойства факториала

Поскольку факториал – новый для нас математический объект, то стоит сказать несколько слов о его свойствах, которые нам пригодятся при решении задач.

Во-первых, для удобства считают, что:

Во-вторых, при сокращении часто используют следующее свойство факториала, прямо следующее из его определения:

Поэтому, сокращая, например, выражение:

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


 

Повторения в задачах на перестановки

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

Например, как мы уже знаем, в слове «парк» можно переставить буквы 24 различными способами. Попробуем сделать то же самое со словом «пара».

Обратите внимание, что у нас есть одинаковые буквы. Получив ответ 24, мы посчитали каждую из них по 2 раза (см. рис. 17). На самом деле, различных перестановок будет ровно в 2 раза меньше – 12 (см. рис. 18).

Рис. 17. Количество перестановок букв в слове «пара» с повторениями

Рис. 18. Количество перестановок букв в слове «пара» без повторений

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

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

Первую букву можно выбрать 3 способами (п, р, а), вторую букву…, а вот тут и непонятно: если мы выбрали первой букву «а», то у нас по-прежнему 3 варианта («п, р, а»). Если «п» или «р», то останется только 2 варианта («а, р» и «а, п» соответственно). В таком случае придется рассмотреть отдельно эти варианты. Чтобы не запутаться в них, лучше изобразить выбор графически (см. рис. 19).

Рис. 19. Количество перестановок в слове «пара»

Получим:

Более подробно такие задачи мы разберем во время практического занятия.

Перестановки, размещения, сочетания

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

1. С одним из них мы уже познакомились – это расчет количества перестановок различных элементов (см. рис. 20). Число перестановок  элементов принято обозначать  («пэ из эн»). Значение этой величины мы уже вычислили:

Рис. 20. Перестановка элементов

2. Выбор  элементов из  различных элементов, причем элементы могут повторяться: число возможных вариантов будет . Например, сколько различных пин-кодов из  цифр можно придумать для банковской карты (см. рис. 21):

Рис. 21. Варианты различных пин-кодов из  цифр для банковской карты

3. Размещение в определенном порядке без повторений некоторого количества элементов из множества (см. рис. 22). Если мы выбираем  элементов из общего количества  различных элементов, то всего вариантов размещения будет:

Величина  («а из эн по ка»), соответственно, называется числом размещений.

Рис. 22. Размещение элементов

4. Выбор в любом порядке некоторого количества элементов из множества (см. рис. 23). При выборе  элементов из  элементов, вариантов выбора будет:

Величина  («це из эн по ка») называется числом сочетаний.

Рис. 23. Сочетание элементов

Разница между размещениями и сочетаниями в следующем. При размещении важен порядок элементов, т. е. наборы  и  считаются различными. При сочетании порядок элементов не важен. Т. е. такие наборы считаются одинаковыми.

Например, при подсчете количества комбинаций при розыгрыше лотереи в начале урока ( номеров из ) нужно использовать формулу:

Использовали именно эту формулу, потому что порядок, в котором вы отметите  номеров в билете, не важен.

Если бы выигрыш зависел еще и от порядка, то шанс победы в лотерее уменьшился бы еще в раз:

Подробнее о выводе этих формул ниже.


 

Вывод формул

1. При выборе  элементов из общего количества  с повторениями расчет простой: первый элемент выбираем  способами, второй – тоже , аналогичной третий и т. д. до k-го. Получим:

2. Рассмотрим задачу на размещение элементов. Всего у нас есть  элементов, нужно разместить  из них (см. рис. 24).

Рис. 24. Всего есть  элементов, нужно разместить  из них

Первый элемент можно выбрать  способами. Теперь у нас осталось  элементов (см. рис. 25).

Рис. 25. Первый элемент можно выбрать  способами, осталось  элементов

Следующий элемент мы можем выбрать  способом (см. рис. 26) и т. д.

Рис. 26. Второй элемент можно выбрать  способами, осталось  элементов

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

Здесь же у нас выбираются не все, а только  элементов. После выбора элемента у нас останется  элемент. Таким образом, последний, k-й, элемент мы можем выбрать  способом. Произведение будет иметь вид:

Умножим и разделим это выражение на :

В числителе получили не что иное, как произведение всех натуральных чисел от  до , т. е. :

3. Задача подсчета числа сочетаний похожа на расчет числа размещений. Мы выбираем  элементов из  элементов, но только здесь нам не важен порядок. Мы можем посчитать число размещений . Но поскольку нам не важен порядок, то некоторые варианты мы посчитали по несколько раз.

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

Почему именно число ? Мы получили это число, рассмотрев перестановки трех букв (, , , , , ):

Таким образом:

Или в общем виде:

Подставив посчитанные ранее выражения для  и , получим:


Решим задачу с использованием этих формул.

 

Задача 4. В классе 20 учеников. Найти количество способов:

а) выбрать команду из 6 человек на интеллектуальный турнир;

б) выбрать старосту и заместителя старосты класса;

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

Решение.

а) необходимо выбрать 6 человек из 20 учеников. При этом порядок выбора не важен, важен сам набор участников. Это число сочетаний из 20 по 6:

Ответ можно упростить:

б) Выбирая старосту и его заместителя нам важен порядок, т. к. роли отличаются. Т. е. Петров – староста, Иванов – заместитель и Иванов – староста, Петров – заместитель – это разные варианты. Можно описать еще так: роль старосты – это «место 1», роль заместителя – «место 2». Нам нужно на этих местах разместить 2 учеников из 20. Это :

в) Нужно выбрать  учеников из . Причем один и тот же ученик может выходить к доске несколько раз. Это выбор из  по  с повторениями. Всего будет вариантов:

Ответ: .

Использование полученного количества всевозможных вариантов выбора

Кроме решения классических задач, формулы для числа перестановок, сочетаний и размещений могут быть использованы как часть решения более сложных комбинаторных задач. Решением таких задач мы займемся на практическом занятии.

Решив комбинаторную задачу, мы узнаем количество всевозможных вариантов выбора. Но как это можно использовать? Например, в тех вопросах, о которых мы говорили в начале. Так, если в номере телефона абонента будет всего 6 цифр, то из них можно составить:  комбинаций (6цифр из 10 с повторениями). Но количество абонентов мобильных операторов исчисляется десятками миллионов, и всем им бы просто-напросто не хватило бы номеров.

Для подбора пароля из 4 цифр нужно перебрать  вариантов. А если длина пароля будет 7 символов и вы будете использовать еще и латинские буквы (всего 36 символов), то количество вариантов станет  – почти в 8 миллионов раз больше.

Как мы говорили в начале урока, логистические задачи часто связаны с анализом и сравнением эффективности большого количества различных вариантов.

Если вариантов много, то процесс выбора оптимального может занять огромное количество времени. Более того, некоторые из задач даже современные компьютеры не в состоянии решить перебором всех вариантов.

Это связано с тем, что количество всевозможных вариантов растет пропорционально , а скорость роста  очень велика. Для сравнения:  – приблизительное количество атомов в 1 миллиграмме воды;  – приблизительное количество атомов в наблюдаемой вселенной.

 


 

Трансвычислительные задачи

Может показаться странным, что мы сказали о задачах, которые не в состоянии решить даже современные компьютеры. Действительно, их быстродействие для нас может казаться практически безграничным. Но это, конечно, не так.

Самый простой пример, о котором слышал практически каждый, – игра в шахматы. Если бы компьютеру удалось перебрать всевозможные варианты партий (а их огромное, но конечное число), то он мог бы определить выигрышную стратегию (если она есть) и игра человека с компьютером потеряла бы всякий смысл.

Другой пример, который мы приводили ранее, – задача факторизации числа (разложения на произведение простых чисел). Даже если известно, что данное число является произведением двух простых, то для достаточно больших чисел сейчас не существует эффективных алгоритмов, которые позволяли бы компьютеру подобрать эти простые числа за относительно небольшое время. На этом факте основаны многие современные способы шифрования.

В обоих примерах мы говорим о конечном времени. Может показаться, что достаточно взять самый мощный компьютер, запустить и ждать – через  или через  лет он справится и с этими задачами. Оказывается, все не так просто. Есть целый класс задач, которые называются трансвычислительными.

Трансвычислительная задача – задача, для решения которой требуется обработка более чем  бит информации. Число , называемое «пределом Бремерманна», представляет собой общее число бит, обрабатываемых гипотетическим компьютером размером с Землю за период времени, равный общему времени существования Земли.

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

Одна из самых известных трансвычислительных задач – задача коммивояжера. Она заключается в поиске пути обхода заданного списка городов, имеющего минимальную стоимость (см. рис. 27).

Рис. 27. Иллюстрация к задаче коммивояжера

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

Этот результат может показаться удивительным: получается, что даже для 67 городов мы не можем составить оптимальный маршрут для одного несчастного коммивояжера. Как же работают компании, у которых в одном городе может быть больше пунктов доставки товаров?

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

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


Кроме того, зная общее число возможных вариантов, мы можем рассчитать вероятность того или иного события. Именно о вероятностях мы сейчас и поговорим.

Случайные события

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

Погода на улице, результаты спортивных соревнований, результаты лотереи – все это случайные события. Да, можно сделать прогноз погоды, основываясь на данных о давлении и температуре, или сказать, что фаворит выиграет у аутсайдера. Но нельзя гарантировать, что в точности так это и произойдет.

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

Классическим примером случайного события является подбрасывание монетки и выпадение «орла» или «решки». И здесь можно попробовать рассчитать, что выпадет: смоделировать физическую ситуацию, сделать расчет. Но результат будет напрямую зависеть от начальных условий: высоты над поверхностью и скорости броска. А эти условия случайны: чуть сильнее бросил, чуть выше отпустил – и уже вместо «орла» выпадает «решка».

Базовые понятия о вероятности необходимы каждому человеку. Они помогут понять, что даже зимой крайне мала вероятность, что все учителя заболеют и вам не придется идти в школу. А знания элементарных формул теории вероятности объяснят, что не стоит ставить в лотерее  рублей, если можно выиграть миллион с вероятностью одна миллионная.


 

Вероятность и предсказуемость

Часто говорят: с вероятностью   выигрывает у . Но вдруг оказывается, что  выиграл у . Причем дважды подряд. Нет ли здесь какой-то ошибки?

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

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

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

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

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

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

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

В формулировке парадокса речь идет именно о совпадении дней рождения у каких-либо двух членов группы. Одно из распространенных заблуждений состоит в том, что этот случай путают с другим случаем, на первый взгляд похожим, когда из группы выбирается один человек и оценивается вероятность того, что день рождения каких-либо других членов группы совпадет с днем рождения выбранного человека. В последнем случае вероятность совпадения значительно ниже.

Это еще один пример заблуждения, связанного с теорией вероятности. Если миллион человек играют в лотерею, то вероятность, что кто-то один из этого миллиона выиграет, велика. Но вероятность того, что это будет конкретный человек – Вася Петров, – практически равна .

Мы часто заблуждаемся при вероятностной оценке ситуации. Например, на вопрос – если  раз подряд монету подбросили и выпала «решка», что более вероятно на десятый раз – выпадение «орла» или «решки»? – большинство людей отвечает, что «орел». Хотя, если монета не какая-то особая, то правильный ответ – вероятности равны. Ведь у монеты нет памяти и предыдущие броски не влияют на ее поведение при следующем броске. При этом с житейской точки зрения поставить на «орел» действительно кажется более логичным, чем поставить на «решку».

Это, кстати, объясняет, почему люди не могут остановиться в казино. Если человек ушел в минус, ему кажется, что он сейчас обязательно отыграется – не может же все время не везти. Но, даже при абсолютно честной игре со стороны казино, если вероятность победы в игре каждый раз равна , она такой и останется при каждом следующем розыгрыше, независимо от результата предыдущего (см. рис. 28).

Рис. 28. Вероятность победы в игре каждый раз равна

Так что будьте внимательны при оценке вероятности того или иного события.


 

Вычисление вероятности

Как же рассчитать вероятность? Проще всего это сделать для событий, исходы которых равновозможны.  Например, событие – бросок монеты. У него два возможных исхода – выпадет «орел» или «решка». Монета симметрична, поэтому нет оснований полагать, что какой-то из исходов будет встречаться чаще. Поэтому эти исходы называют равновозможными, а выпадение «орла» и «решки» – равновероятными событиями.

Вероятность каждого из событий равна :

Это же можно записать, используя проценты (:

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

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

Рассмотрим несколько примеров вычисления вероятностей.

1. Если перемешать колоду карт, то все исходы вытаскивания карты будут равновозможны. Посчитаем вероятность вытащить туза из колоды в  карт. Всевозможных исходов  ( карт), благоприятных исходов –  ( из  тузов). Тогда вероятность вытащить из колоды туза будет равна:

2. Посчитаем вероятность выпадения на кубике четного числа. Всего  возможных исходов, благоприятных –  (выпала , или ):

3. Рассмотрим следующее событие: «на кубике выпало целое число». Очевидно, на кубике могут выпадать только целые числа. Такое событие, которое всегда происходит при проведении некоторого испытания, называют достоверным. Вероятность достоверного события равна  (или ). Это понятно и по смыслу: происходит всегда, со  вероятностью, это можно подтвердить и формулой. Всего  возможных исходов, благоприятных – :

4. Событие, которое не произойдет в опыте ни при каких условиях, называется невозможным. Например, это выпадение числа  на кубике. Вероятность такого события равна нулю, ведь благоприятных исходов нет:

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

Статистический подход

Итак, если мы проводим испытание с равновозможными исходами, то вероятность можно вычислить по формуле:

где  число благоприятных исходов,  –общее число возможных исходов.

Числа  и  мы можем вычислить с помощью формул комбинаторики, и нам даже не надо производить сам опыт.

А как быть с вероятностями событий, где исходы не равновозможны? Здесь обычно применяют статистический подход: смотрят статистику и считают, сколько всего произошло событий  и сколько среди них «благоприятных» . Тогда можно оценить вероятность того, что в дальнейшем произойдет «благоприятное» событие:

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

Используя статистический подход, можно понять, почему не стоит ставить в лотерее  рублей, если можно выиграть миллион с вероятностью одна миллионная. Ведь вероятность выиграть  значит, что если мы будем участвовать в лотерее  раз (общее количество событий ), то выиграем, скорее всего, только  раз (число благоприятных событий ). За это время мы поставим  рублей, а выиграем всего . Итог: за  участий мы в среднем потеряем  рублей. За одно участие, соответственно, в среднем мы теряем  рублей.

Свойства вероятностей

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

1. Если два события  и  несовместны, т. е. появление одного из них полностью исключает появление другого, то вероятность, что произойдет одно из них, равна сумме вероятностей этих событий:

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

2. Вероятность противоположного события , т. е. вероятность того, что событие А не произойдет, равна:

3. Если два события  и  независимы, т. е. появление одного из них не влияет на вероятность появления второго, то вероятность, что произойдут оба события одновременно, равна произведению вероятностей этих событий:

Пользуясь последним соотношением, можно понять, что даже если вероятность, что один учитель заболеет, равна , то вероятность, что заболеют все , которые ведут у вас сегодня уроки, крайне мала (если, конечно, мы считаем, что заболевший учитель не заразил своих коллег и, таким образом, не повлиял на их вероятность заболеть):

 

Заключение

Мы еще займемся решением различных задач и применением различных свойств вероятности на практике.

 

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

  1. Никольский С.М., Решетников Н.Н., Потапов М.К., Шевкин А.В. Алгебра, 9 класс. Учебник. ФГОС. –М: «Просвещение», 2018.
  2. Дорофеев Г.В., Суворова С.Б., Бунимович Е.А. Алгебра, 9 класс. Учебник. – М: «Просвещение», 2018.
  3. Макарычев Ю.Н., Миндюк Н.Г., Нешков К.И., Суворова С.Б. Алгебра, 9 класс. Учебник. – М:«Просвещение», 2018.

 

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

  1. Интернет-портал math-prosto.ru (Источник)
  2. Интернет-портал mathprofi.ru (Источник)
  3. Интернет-портал yaklass.ru (Источник)

 

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

1. a. Команде предлагают футболки -х цветов и шорты -х цветов. Сколько вариантов выбрать форму есть у команды?

б. В классе  мальчиков и  девочек. Сколько существует способов составить пару для танцев из одного мальчика и одной девочки?

2. Вычислить:

3. Сколько двузначных чисел можно составить из цифр , если в получаемом числе цифры не могут повторяться?