Как невесте выбрать лучшего принца? #math
Привередливой принцессе надо выбрать лучшего принца среди х кандидатов.
Одно плохо принцы приходят в случайном порядке и требуют ответа да\нет мгновенно. Принцы к тому же гордые, и если их отвергнут они уже не вернуться.
Король тоже человек жесткий и честолюбивый и согласен отдать принцессу замуж лишь если она сделает выбор на лучшем принце.
для простоты предположим, что у каждого принца есть его уровень хорошести, и эти уровни разные среди всех принцев.
Какая стратегия максимизирует шансы принцессы на успех?
Очевидно, что случайный выбор дает вероятность успеха 1\n
Если пропустить первого принца, и потом остановиться на первом кандидате который превзойдет первого принца, то вероятность удачи будет ln n\n , что уже в ln n раз лучше.
Попробуйте найти оптимальную стратегию (сложнее)
И стратегию дающую вероятность удачи 0.25 (легко)
Одно из решений приводится в брошюре Гауде Гусейна разборчивая невеста, используя динамическое программирование, но в этой книжке за деревьями теряется лет.