Сказка о тысяче принцев

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

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

Формализуем задачу. Допустим, к королевскому двору прибыли n женихов. Они в случайном порядке по одному знакомятся с принцессой и предлагают ей свою руку и сердце. При знакомстве принцесса видит, лучше ли текущий кандидат № К тех, с кем она уже знакома – другими словами, она может определить его место в рейтинге первых К принцев. Принцесса может принять предложение, и тогда все остальные принцы сразу же разъезжаются, и народ празднует королевскую свадьбу. Принцесса может отказать претенденту, который после этого уже не возвращается, все же принцы – люди гордые. В этом случае отбор продолжается. Вот только в сказках свадьба должна быть обязательно, поэтому отказать последнему оставшемуся принцу принцесса не может – кого-нибудь выбрать надо в любом случае. Итак, в этих непростых условиях нам необходим алгоритм, чтобы выбрать первого в рейтинге всех n принцев.

Очевидно, что ни для одного из первых n - 1 принцев нельзя сказать с полной уверенностью, что он – лучший, ведь всегда возможен вариант, что лучший – последний. И все же ждать последнего кандидата неразумно, ведь вероятность этого варианта довольно низкая – 1/n. Скорректируем нашу цель: нужно найти стратегию, которая поможет с наибольшей вероятностью выбрать лучшего принца.

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

Давайте рассмотрим k-того принца. Вероятность того, что он лучше всех предыдущих – 1/k. Но для того, чтобы он мог добраться до принцессы, необходимо, чтобы все предыдущие принцы, начиная с p + 1, не становились первыми в рейтинге. Вероятность этого равна

То есть, принцесса может выбрать k-того принца с вероятностью

Получаем, что итоговая вероятность выбрать лучшего принца на k-том шаге составляет

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

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

Настало время скучных алгебраических преобразований. Распишем подробно для первого неравенства:

И точно также получим для второго неравенства:

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

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

А для наших неравенств это будет выглядеть так:

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

Итак, подведем итоги. Для того, чтобы выбрать лучшего принца, принцессе нужно отказать первым n/e кандидатам, и выбрать первого из последующих, который окажется лучше всех предыдущих. Такая стратегия позволит принцессе выбрать самого достойного с вероятностью 1/e. Для тысячи принцев искомый номер p будет равен 368. Осталось только завершить сказку королевской свадьбой!

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