Задача 481
Шоу поваров

Группа поваров (пронумерованных №1, №2 и т.д.) участвует в пошаговом соревновании по стратегической готовке. Каждый повар на свой ход готовит свое наилучшее блюдо и отдает его на оценку жюри. Пусть S(k) обозначает навык готовки повара №k (значение публично известно). Точнее, S(k) равно вероятности того, что блюдо повара №k будет положительно оценено жюри (в любой/все ходы). Если блюдо получает положительную оценку, то приготовивший его повар должен выбрать, кто из остальных поваров будет исключен из соревнования. Последний оставшийся повар становится победителем.

Игра всегда начинается с повара №1. Ход переходит к следующему по номеру повару, еще не выбывшему из соревнования. Цикл начинается заново с участника с самым маленьким номером. Каждый повар стремится оптимизировать свои шансы на победу в рамках вышеупомянутых правил соревнования и предполагает, что все остальные повара поступают также. В случае, если у повара есть несколько одинаково оптимальных выборов, кого исключить из игры, положим, что будет выбран повар, чей следующий ход наступит скорее всего.

Определим Wn(k) как вероятность того, что повар №k победит соревнование с n поварами. Если S(1) = 0.25, S(2) = 0.5 и S(3) = 1, то W3(1) = 0.29375.

Далее, зададим S(k) = Fk/Fn+1 для всех 1 ≤ kn, где Fk - число Фибоначчи: Fk = Fk-1 + Fk-2 с начальными значениями F1 = F2 = 1. Тогда, например, в соревновании n = 7 поваров, мы получим W7(1) = 0.08965042, W7(2) = 0.20775702, W7(3) = 0.15291406, W7(4) = 0.14554098, W7(5) = 0.15905291, W7(6) = 0.10261412 и W7(7) = 0.14247050, каждое значение округлено до 8 знака после запятой.

Пусть E(n) будет ожидаемым количеством блюд, приготовленных в течение соревнования n поваров. Например, E(7) = 42.28176050.

Найдите E(14), округленное до 8 знака после запятой.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net