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

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

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

Примечания

Ссылки

• С. М. Гусейн-Заде Разборчивая невеста. — МЦНМО, 2003. — Т. 25. — 20 с. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-076-3
• С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. Малый мехмат, МГУ, 30.11.2002.