Проект Эйлера: Задача 339. Передур, сын Эвраука

Проект Эйлера

Задача 339

Передур, сын Эвраука

"...Передур же поехал дальше долиной реки, вдоль которой расстилались луга. И на одном берегу реки он увидел стадо белых овец, а на другом - стадо черных. И как только одна из белых овец блеяла, черная овца переплывала реку и становилась белой. Когда же блеяла черная овца, одна из белых овец переплывала реку и делалась черной."
Мабиногион. Передур, сын Эвраука

Изначально, каждое стадо состоит из n овец. Каждая овца (независимо от цвета) с равной вероятностью может блеять следующей. После того, как овца проблеяла и овца из другого стада пересекла реку, Передур может убрать некоторое число белых овец, чтобы обеспечить в конце максимальное число черных овец. Пусть E(n) - ожидаемое конечное значение числа черных овец, если Передур использует оптимальную стратегию.

Известно, что E(5) = 6.871346 (округлено до 6 знака после десятичной точки).
Найдите E(10 000) и приведите ответ, округлив его до 6 знака после десятичной точки.

Оригинал