Задача о разборчивой невесте

Задача может быть сформулирована следующим образом[1]:

1. Невеста ищет себе жениха (существует единственное вакантное место).
2. Есть известное число претендентов — ${\displaystyle n}$.
3. Невеста общается с претендентами в случайном порядке, с каждым не более одного раза.
4. Претенденты образуют линейный порядок: асимметричный, транзитивный и любые два сравнимы — о каждом претенденте известно, лучше он или хуже любого из предыдущих.
5. Пообщавшись с претендентом, невеста сравнивает его с предыдущими и либо отказывает, либо принимает его предложение. Если предложение принято, они женятся и процесс останавливается. Если невеста отказывает жениху, то вернуться к нему позже она не сможет.
6. Цель — выбрать лучшего претендента. Даже второй её не устраивает.

В 1963 году Евгений Дынкин предложил решение этой задачи для частного случая. Общее решение было найдено Сабиром Гусейн-Заде в 1966 году.

Этой задаче было уделено много внимания во многом потому, что оптимальная стратегия имеет интересную особенность: если число кандидатов достаточно велико, оптимальная стратегия будет заключаться в том, чтобы отклонить всех первых ${\displaystyle n/e}$ (где ${\displaystyle e=2{,}718\ldots }$ — основание натурального логарифма) претендентов и затем выбрать первого, кто будет лучше всех предыдущих[2]. При увеличении ${\displaystyle n}$ вероятность выбора наилучшего претендента стремится к ${\displaystyle 1/e}$, то есть примерно к 37 %.

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

В диссертации Бориса Березовского, впоследствии члена-корреспондента РАН, на соискание ученой степени доктора наук «Разработка теоретических основ алгоритмизации принятия предпроектных решений и их применения», защищенной в 1983 году, рассматривается обобщение задачи о разборчивой невесте[4].

• С. М. Гусейн-Заде. Разборчивая невеста. — МЦНМО, 2003. — Т. 25. — 20 с. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-076-3.
• С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. Малый мехмат, МГУ, 30.11.2002.
• И. Р. Высоцкий, И. В. Ященко Задачи заочных интернет-олимпиад по теории вероятностей и статистике —  МЦНМО, 2017, с.255, 275 — ISBN 978-5-4439-1136-6
• Steven R. Finch. 5.15 Optimal Stopping Constants // Mathematical constants. — Cambridge University Press, 2003. — ISBN 978-0-521-81805-6. Errata and Addenda.