Чарльз Мостеллер - Пятьдесят занимательных вероятностных задач с решениями

Но эта сумма есть разложение ( x + y )³ при х = −1, y = 1 и, значит, равна нулю, так как (-1 + 1)³ = 0³ = 0. Этот факт имеет место при каждом значении i + j = r , r = 1, 2, ...., n , так что соответствующие суммы равны нулю. Лишь при r = 0 получаем единственный член (-1) 0/(0!·0!) = 1. Следовательно, решение (3) удовлетворяет уравнению (2).

Ясно, что других решений у (2) нет. Это может быть доказано методом индукции, так как P (0/ n ) выражается через P (0/1), P (0/2), ..., P (0/ n − 1).

Из (1) и (3), наконец, выводим

Если n − r велико, то выражение в скобках близко к e −1и

если только n − r достаточно велико. Итак, действительно, вероятности r совпадений в нашей задаче близки к пуассоновским со средним 1. Однако для этой близости необходимо, чтобы разность n − r была велика, а не только само n , как казалось в начале.

Вероятность того, что нет ни одного совпадения, при больших n стремится к e −1≈ 0.368.

Любопытно узнать — на много ли шансы мудреца на успех больше 1/100? Многие предлагают следующую стратегию: пропустить первую половину билетов и затем выбрать первую сумму, превосходящую все предыдущие, если таковая найдется. Это достаточно разумно, но такая стратегия не является оптимальной. Очень немногие представляют себе порядок величины вероятности выигрыша.

Мы начнем с рассмотрения нескольких примеров. Поскольку мы ничего не знаем о суммах, проставленных на билетах, то можем рассматривать лишь номера билетов при их упорядочении согласно величинам сумм, записанных на них. Если, например, у нас имеется три билета с номерами 1, 2, 3, то билету 3 отвечает наибольшее приданое. Для одного или двух билетов задача тривиальна: мудрец делает правильный выбор при одном билете, и его шансы на выигрыш равны 1/2 при двух билетах.

При трех билетах имеем шесть возможных способов вытаскивания:

123 231*

132* 312

213* 321

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

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

1234 2134 3124*+ 4123

1243+ 2143*+ 3142*+ 4132

1324+ 2314+ 3214*+ 4213

1342+ 2341+ 3241*+ 4231

1423* 2413* 3412* 4312

1432* 2431* 3421* 4321

Кажется разумным пропустить первый билет и остановиться на следующем наибольшем номере, если он есть. Назовем этот план стратегия 1. Звездочки в нашем списке указывают на случай выигрыша этой стратегии. Вероятность правильного решения равна здесь 11/24, что гораздо лучше, чем случайное решение с вероятностью выигрыша 1/4.

Стратегия 2пропускает первые два номера и затем выбирает первый номер, их превосходящий. 10 перестановок, в которых эта стратегия дает выигрыш, отмечены крестиком. Видно, что стратегия 1 выигрывает чаще.

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

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

Покажем теперь, что оптимальная стратегия — пропустить s − 1 билетов и выбрать первый максимальный номер после них. Мы выберем максимальное приданое на i -м шагу, если вероятность того, что оно наибольшее среди всех имеющихся, превосходит вероятность правильного решения при оптимальной стратегии и более позднем вытягивании. Формально: остановимся на максимальном номере при i -м вытягивании, если

Р (выиграть при i -м вытягивании) > Р (выиграть при оптимальной стратегии, начиная с i + 1 вытягивания). (1)