Примерно 40 лет тому назад Мартин Гарднер придумал такую задачу: “В некотором царстве, в некотором государстве пришло время принцессе выбирать себе жениха. В назначенный день явились 1000 царевичей и королевичей, их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух претендентов принцесса, познакомившись с ними, может сказать, какой из них лучше. Познакомившись с претендентом, принцесса может либо принять предложение (и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи и королевичи гордые и не возвращаются). Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего из претендентов?”.

В 1965 году её формулировку и решение рассказал на своём семинаре Е. Б. Дынкин. Но его метод был необобщаем на другие варианты задачи: например, когда целью является выбор не наилучшего, а одного из трёх лучших. В таком виде задача была решена лектором при помощи метода, который легко переносится и на ряд близких задач. Так из полушуточной задачи вырос новый раздел математики — теория оптимальной остановки случайных процессов.

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

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

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

Этой задаче было уделено много внимания во многом потому, что оптимальная стратегия имеет интересную особенность: если число кандидатов достаточно велико (порядка сотни), оптимальная стратегия будет заключаться в том, чтобы отклонить всех первых (где — основание натурального логарифма) претендентов и затем выбрать первого, кто будет лучше всех предыдущих. При увеличении вероятность выбора наилучшего претендента стремится к , то есть примерно к 37%.

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