Problem 481

Chef Showdown

A group of chefs (numbered #1, #2, etc) participate in a turn-based strategic cooking competition. On each chef’s turn, he/she cooks up a dish to the best of his/her ability and gives it to a separate panel of judges for taste-testing. Let S(k) represent chef #k’s skill level (which is publicly known). More specifically, S(k) is the probability that chef #k’s dish will be assessed favorably by the judges (on any/all turns). If the dish receives a favorable rating, then the chef must choose one other chef to be eliminated from the competition. The last chef remaining in the competition is the winner.

The game always begins with chef #1, with the turn order iterating sequentially over the rest of the chefs still in play. Then the cycle repeats from the lowest-numbered chef. All chefs aim to optimize their chances of winning within the rules as stated, assuming that the other chefs behave in the same manner. In the event that a chef has more than one equally-optimal elimination choice, assume that the chosen chef is always the one with the next-closest turn.

Define W_n(k) as the probability that chef #k wins in a competition with n chefs. If we have S(1) = 0.25, S(2) = 0.5, and S(3) = 1, then W₃(1) = 0.29375.

Going forward, we assign S(k) = F_k/F_n+1 over all 1 ≤ k ≤ n, where F_k is a Fibonacci number: F_k = F_k-1 + F_k-2 with base cases F₁ = F₂ = 1. Then, for example, when considering a competition with n = 7 chefs, we have W₇(1) = 0.08965042, W₇(2) = 0.20775702, W₇(3) = 0.15291406, W₇(4) = 0.14554098, W₇(5) = 0.15905291, W₇(6) = 0.10261412, and W₇(7) = 0.14247050, rounded to 8 decimal places each.

Let E(n) represent the expected number of dishes cooked in a competition with n chefs. For instance, E(7) = 42.28176050.

Find E(14) rounded to 8 decimal places.

厨师一决胜负

一群厨师分别编号为#1，#2，依此类推，参与了一个轮流进行的策略厨艺大赛。在轮到某个厨师时，他必须做一道展现自己最好水平的菜，并将其交给一个独立评审团进行品尝。我们记S(k)是编号#k厨师的水平（事先给定），更具体地说，S(k)指的是厨师#k的菜被评委们认为好吃的概率。如果一道菜被评委认定为好吃，那么这位厨师可以将另一名厨师从比赛中剔除。比赛中最后剩下的那位厨师就是胜利者。

比赛从厨师#1开始，在场上未被剔除的厨师中轮流进行，直到最后一名厨师后，又回到在场的编号最小的一位厨师。所有厨师根据上述规则最大化自己获胜的概率，同时也假定其它厨师采取同样的策略。如果一个厨师有多个同样好的剔除策略，他总是剔除在他之后最近的那个。

记W_n(k)是厨师#k在一场有n个厨师参与的比赛中获胜的概率。如果S(1) = 0.25，S(2) = 0.5，S(3) = 1，那么W₃(1) = 0.29375。

进一步地，如果我们假定对于所有的1 ≤ k ≤ n，S(k) = F_k/F_n+1，其中F_k是以F₁ = F₂ = 1的斐波那契数：F_k = F_k-1 + F_k-2。在这种情况下，例如一场有n = 7个厨师参与的比赛，我们有W₇(1) = 0.08965042，W₇(2) = 0.20775702，W₇(3) = 0.15291406，W₇(4) = 0.14554098，W₇(5) = 0.15905291，W₇(6) = 0.10261412，W₇(7) = 0.14247050，均保留八位小数。

记E(n)为上述假定下一场有n个厨师参与的比赛预期炒制的菜肴数目。例如，E(7) = 42.28176050。

求E(14)，并保留八位小数。