Detailed mathematical approach

Problem Summary

There are \(n\) chefs arranged in cyclic order \(1,2,\dots,n\). Chef \(k\) succeeds on any chosen target with probability

$p_k=\frac{F_k}{F_{n+1}},\qquad k=1,\dots,n,$

where \(F_1=F_2=1\). Every turn produces exactly one dish. The current chef chooses one surviving opponent, tries to eliminate that opponent, and then the turn passes to the next surviving chef after the current one. On success the chosen target is removed; on failure nobody is removed. The game ends when only one chef remains.

For each game state we want both the whole vector of eventual win probabilities and the expected number of remaining dishes. The Project Euler quantity is

$E(n)=D_{\{1,2,\dots,n\},1},$

the expected number of dishes from the full table when chef \(1\) moves first.

Mathematical Approach

The key idea is to solve the game by dynamic programming over alive-sets. Once smaller sets are known, the best target in every larger state is also known, and the remaining equations form a single cyclic linear system.

Step 1: Describe a State Precisely

Let \(M\subseteq\{1,\dots,n\}\) be the set of surviving chefs and let \(t\in M\) be the chef whose turn it is. Define

$\mathbf W_{M,t}=\bigl(W_{M,t}(1),\dots,W_{M,t}(n)\bigr),$

where \(W_{M,t}(i)\) is the probability that chef \(i\) is the eventual winner when play starts from state \((M,t)\). Also define

$D_{M,t}$

for the expected number of additional dishes from state \((M,t)\).

If only one chef is alive, the game is already finished. Thus for \(M=\{i\}\) we have

$W_{\{i\},i}(i)=1,\qquad W_{\{i\},i}(k)=0\ (k\ne i),\qquad D_{\{i\},i}=0.$

Let \(\operatorname{next}_M(t)\) denote the next surviving chef after \(t\) in cyclic order, wrapping around when necessary.

Step 2: The Optimal Target Comes from Smaller Alive-Sets

Suppose \(|M|\ge 2\). If chef \(t\) chooses target \(j\in M\setminus\{t\}\), then with probability \(p_t\) the game moves to

$\left(M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)\right),$

and with probability \(1-p_t\) it moves to

$\left(M,\operatorname{next}_M(t)\right).$

The failure branch is the same for every target. Therefore chef \(t\) only needs to maximize the success-branch value

$W_{M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)}(t).$

If several targets give the same value, the implementation uses the smallest positive cyclic distance from \(t\) as the deterministic tie-break. This matters because it fixes a unique successor for every state.

Most importantly, every candidate success state has one fewer surviving chef, so its probabilities are already known once smaller subsets have been solved.

Step 3: Write the Recurrence for One Fixed Alive-Set

Fix one alive-set \(M\) with \(q=|M|\ge 2\), and list its members in cyclic order as

$m_0,m_1,\dots,m_{q-1}.$

For each position \(r\), let

$X_r=\mathbf W_{M,m_r},\qquad Y_r=D_{M,m_r}.$

After the best target of chef \(m_r\) has been chosen, let \(U_r\) be the already-known winner-probability vector of the corresponding success state, and let \(V_r\) be the already-known expected number of remaining dishes there. Then one turn gives

$X_r=p_{m_r}U_r+(1-p_{m_r})X_{r+1},$

$Y_r=1+p_{m_r}V_r+(1-p_{m_r})Y_{r+1},$

where the indices are taken modulo \(q\). The constant \(1\) appears because every turn produces exactly one new dish before the next state is reached.

Step 4: Solve the Cycle Analytically

Set

$A_r=p_{m_r}U_r,\qquad C_r=1+p_{m_r}V_r,\qquad b_r=1-p_{m_r}.$

Then the recurrences become

$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$

Unrolling the first equation once around the entire cycle gives

$X_0=A_0+b_0A_1+b_0b_1A_2+\cdots+\left(\prod_{i=0}^{q-2}b_i\right)A_{q-1}+\left(\prod_{i=0}^{q-1}b_i\right)X_0.$

Therefore

$X_0=\frac{\displaystyle\sum_{r=0}^{q-1}\left(\prod_{i=0}^{r-1}b_i\right)A_r}{\displaystyle 1-\prod_{i=0}^{q-1}b_i}.$

Exactly the same algebra yields

$Y_0=\frac{\displaystyle\sum_{r=0}^{q-1}\left(\prod_{i=0}^{r-1}b_i\right)C_r}{\displaystyle 1-\prod_{i=0}^{q-1}b_i}.$

Here the empty product for \(r=0\) equals \(1\). Because every skill probability is positive, \(\prod b_i<1\), so the denominator is nonzero. The formula for \(X_0\) is vector-valued, but every component follows the same scalar coefficient pattern.

Once \(X_0\) and \(Y_0\) are known, the remaining turn-states of the same mask follow by backward substitution:

$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$

So the cyclic dependency is resolved without generic matrix inversion.

Step 5: Process Subsets in Increasing Size

All one-chef masks are base cases. After that, alive-sets are processed in order of increasing size \(1,2,\dots,n\). When a mask \(M\) is handled, every success state \(M\setminus\{j\}\) has already been solved. That means the best target of every acting chef is immediately known, and the formulas from Step 4 can be applied directly.

This is subset dynamic programming, but each state stores more than one scalar: it stores an entire winner-probability vector and one expectation.

Worked Example: Three Chefs with \(\left(\frac14,\frac12,1\right)\)

This example is practical because it is one of the numerical checkpoints used by the implementation. The start state is \((\{1,2,3\},1)\).

First solve the two-chef states. For chefs \(1\) and \(2\), if chef \(1\) is to move, then

$W_{\{1,2\},1}(1)=\frac{\frac14}{1-\frac34\cdot\frac12}=0.4.$

Hence

$W_{\{1,2\},2}(1)=\left(1-\frac12\right)\cdot 0.4=0.2.$

Likewise

$W_{\{1,3\},1}(1)=0.25,\qquad W_{\{2,3\},2}(2)=0.5.$

Now determine the optimal targets inside the three-chef mask. Chef \(1\) prefers eliminating chef \(3\), because success then leaves the duel \(\{1,2\}\) with chef \(2\) to move, where chef \(1\)'s win probability is \(0.2\); eliminating chef \(2\) instead would leave chef \(3\) to move next and gives chef \(1\) success-branch value \(0\).

Chef \(2\) also prefers targeting chef \(3\), because the success branch then leaves \(\{1,2\}\) with chef \(1\) to move, where chef \(2\)'s eventual win probability is \(0.6\), better than the alternative \(0\).

Chef \(3\) prefers targeting chef \(2\), because a certain success leaves the duel \(\{1,3\}\) with chef \(1\) to move, and chef \(3\)'s win probability there is \(0.75\), larger than the \(0.5\) obtained by removing chef \(1\).

Now let \(x_r\) be chef \(1\)'s eventual win probability when the current player is chef \(r\). The chosen targets give

$x_1=\frac14\cdot 0.2+\frac34x_2,$

$x_2=\frac12\cdot 0.4+\frac12x_3,$

$x_3=1\cdot 0.25.$

Therefore

$x_3=0.25,\qquad x_2=0.325,\qquad x_1=0.05+0.75\cdot 0.325=0.29375,$

which matches the published checkpoint \(W_3(1)=0.29375\).

How the Code Works

The C++, Python, and Java implementations first generate the Fibonacci-based skill probabilities and group all alive-sets by population. For each alive-set they list the surviving chefs in cyclic order. Single-survivor states are filled directly as base cases.

For every nontrivial state, the implementation tests every possible target of the current chef. Since each success state has one fewer survivor, its winner-probability vector has already been computed. The target whose success branch gives the acting chef the largest eventual win probability is selected, using the cyclic distance rule to break ties.

Once those best targets are fixed for the entire alive-set, the implementation builds the success contributions \(A_r\) and \(C_r\), stores the failure factors \(b_r=1-p_{m_r}\), evaluates the closed-form cycle formulas above, and then back-substitutes to recover all turn-states for that mask. Both the full winner-probability vectors and the expected numbers of remaining dishes are stored.

At the end, the required Project Euler value is simply the expectation associated with the full alive-set when chef \(1\) acts first.

Complexity Analysis

For a mask with \(m\) surviving chefs, target selection costs \(O(m^2)\), while constructing and propagating the winner-probability vectors costs \(O(mn)\). Summing over all masks gives

$\sum_{m=0}^{n}\binom{n}{m}(m^2+mn)=O(n^2 2^n).$

The stored winner-probability vectors dominate memory use, so the exact method also requires

$O(n^2 2^n)$

memory. That is why the exact solver is practical only for relatively small \(n\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=481
2. Fibonacci numbers: Wikipedia - Fibonacci number
3. Dynamic programming: Wikipedia - Dynamic programming
4. Markov decision process: Wikipedia - Markov decision process
5. Expected value: Wikipedia - Expected value