Проблема остановки выбора (разборчивая невеста)

Знаете ли вы, что 33% студенток Гарвардского университета вышли замуж за своих преподавателей в 1901 году? Можно представить себе, что написала бы жёлтая пресса про учителей вроде бы приличного ВУЗа, которые не умеют себя контролировать... Впрочем, если разобраться, то окажется, что в том году в Гарварде было всего три студентки, одна из которых вышла замуж за своего профессора. Утверждение может быть абсолютно корректным, но выглядеть дико, если его «удачно» подать. Поэтому знание математики необходимо обществу, если оно не хочет слепо следовать за первым попавшимся жуликом.

Разберём коротко прошлую задачку о странном любовном треугльнике: Женатый Джек любит Анну, которая влюблена в холостого Джорджа. Вроде бы мы не знаем статус Анны, но давайте рассмотрим оба варианта:
- Если Анна состоит в браке, то она и есть тот человек, который любит холостого.
- Если Анна свободна, то женатый Джек является тем человеком, который любит незамужнюю.
Это означает, что ответ «недостаточно данных» является преждевременным. Похоже, интуиция многим мешает разобрать обе возможные ветки этой задачи. Я тоже чуть было так не ответил, но вовремя сообразил, что «не зря же мне эту задачу предложили». И тогда подумал ещё раз, что и привело к полному пониманию ситуации.

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

Раз у нас нынче идёт неделя вероятностей, женитьб и чисел вида 1/e (речь о парадоксе с раздачей подарков), то имеет смысл вспомнить ещё одну задачку, которая возникла совсем недавно - буквально 50 лет назад. Мы её знаем как задачу о разборчивой невесте или проблему остановки выбора, а зарубежом она обычно называется «secretary problem» или «marriage problem» (конечно, есть ещё масса названий).

Проблема формулируется так:
- есть множество из N претендентов на одну вакансию/руку принцессы;
- про любых двух претендентов есть надёжный способ определить, какой из них лучше (более того, если А лучше Б, а Б лучше В, то А заведомо лучше В);
- наниматель/принцесса общается с претендентами в случайном порядке;
- с каждым претендентом можно поступить одним из двух способов: согласиться (тогда игра заканчивается), отказать ему (но тогда он больше не вернётся, поэтому уже никогда нельзя будет принять его предложение);

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

В чём проблема? А в том, что если принцесса отказала всем, кроме одного, то ей придётся за него выйти. Поэтому слишком большая разборчивость может привести к тому, что она упустит своего самого лучшего принца. Но если она согласится слишком рано, то даже не позволит чемпиону проявить себя. Надо знать меру, но как её найти?

Оказывается, правильная стратегия состоит в следующем:
1. Делим всех N претендентов на две группы: «эксперементальная» (1/e от всех) и «рабочая» (1-1/e от всех).
2. Первой группе (первым N/e претендентам) следует отказать, запоминая, кто из них самый лучший.
3. Представители второй группы уже имеют шансы: следует соглашаться на предложение первого же, кто лучше всех своих предшественников.

Интересно, что при этой стратегии принцесса получит наилучшего принца с вероятностью 1/e (согласитесь, не так уж и мало, учитывая сложность ситуации). Эта задача имеет интересные расширения. Например, если принцесса не слишком привередлива, то она может прожить счастливую жизнь не с самым лучшим принцем, а с тем, кто входит в список «k лучших принцев». Если k=2 (если принцесса согласна на любого из двух самых лучших), то при правильной стратегии она найдёт своего принца с вероятностью 57 процентов.

Рекомендую прочитать интереснейшую книгу на эту тему - Разборчивая невеста (всего 200 килобайт). Это 25-ый выпуск библиотеки «Математическое просвещение» - на двух десятках страниц изложены очень интересные подходы к решению задач (кстати, многие школьники вполне смогут понять этот материал, поэтому стоит попробовать им предложить!). Любители английского языка и противники pdf-файлов найдут статью в википедии (не так подробно, но есть ссылки на близкие по содержанию материалы)

Хорошего дня!