Сергей, 41 - 13 июня 2009 21:33

Будучи олимпиадником по математике на сборах у нас была задача, которая мне очень запомнилась. Её формулировка проста, а вот решение. Оно сложно для понимания даже подготовленным математикам (на её обобщенном решении небезызвестный олигарх Борис Абрамович Березовский защитил докторскую диссертацию !) ).
В некотором царстве, в некотором государстве пришло время принцессе выбирать себе жениха. В назначенный день явились 1000 царевичей. Их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух претендентов принцесса, познакомившись с ними, может сказать, какой из них лучше. Познакомившись с претендентом, принцесса
может либо принять предложение (и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи гордые и не возвращаются). Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего?

В общем, получается что в случае самой оптимальной стратегии принцесса выберет лучшего жениха с вероятностью 1/е (0.368 ). Для тех кого интересует решение ссылка
http://www.mccme.ru/mmmf-lectures/books/books/book.25.pdf

• 
• 
•