B некотором государстве принцесса решила, что ей пора найти себе жениха. Созвали царевичей и королевичей со всего света, и явилось 1000 претендентов. Про любых двух когда-либо увиденных принцесса может сказать, кто из них лучше. T.е. если Иван Царевич лучше Василия Царевича, а Василий Царевич лучше Фёдора Царевича, то Иван Царевич лучше Фёдора Царевича. Претенденты входят к принцессе по очереди,по одному, причём их порядок определён случайным образом, т. е. вероятность появления какого-то царевича первым, или пятисотым, или тысячным совершенно одинакова. Принцесса, разумеется, умея их сравнивать, может сказать, что, например, вошедший тридцатым является десятым по качеству, т. е. девять из предыдущих были лучше, а остальные — хуже, и т. д. Цель принцессы — получить самого хорошего жениха, т. е. даже второй её не устраивает. На каждом шаге, т. е. после встречи с каждым из царевичей, она решает, берёт ли она его в мужья. Если берёт, то на этом смотр претендентов заканчивается, они все разъезжаются по домам. Если же принцесса ему отказывает, то царевич, будучи отвергнутым, тут же уезжает домой, потому что все царевичи и королевичи — люди гордые. Показ претендентов на замужество при этом продолжается. Если в конце концов принцесса не получает лучшего, то считается, что она проиграла, выходить замуж вообще не будет, а уйдёт в монастырь.
Спрашивается, как действовать принцессе, чтобы с наибольшей вероятностью получить лучшего жениха.
Oтвет на поставленную задачу выглядит так: принцесса должна сначала пропустить первую 1/e часть женихов (в случае n=1000 это примерно 368 человек), только запоминая их для будущего сравнения, а дальше она должна брать в мужья первого же, который обладает тем свойством, что он лучше всех своих предшественников. При этом вероятность получить в конце концов самого лучшего жениха из всех n претендентов равна примерно 0,368.
Примечание. е - это основание натурального логарифма.
https://ru.wikipedia.org/wiki/E_(число)