Problem 481: Chef Showdown

Mathematical Foundation

Definition 1 (Game state). A state is a pair $(\mathcal{S}, \tau)$ where $\mathcal{S} \subseteq \{1, \ldots, n\}$ is the set of remaining chefs with $|\mathcal{S}| = m \geq 1$, and $\tau$ is the index within the ordered set $\mathcal{S}$ indicating whose turn begins the next round.

Theorem 1 (Geometric round structure). Let the turn order within state $(\mathcal{S}, \tau)$ be $(c_1, c_2, \ldots, c_m)$, and define $q_i = 1 - S(c_i)$ for each $i$. A round consists of all $m$ chefs attempting a dish in sequence. Then:

(i) The probability that no chef succeeds in a full round is

(ii) The probability that chef $c_j$ is the first to succeed in a given round is

(iii) These probabilities satisfy $\sum_{j=1}^{m} P_j(\mathcal{S}) = 1 - Q(\mathcal{S})$.

(iv) The number of completely failed rounds before the first success is geometrically distributed with parameter $1 - Q(\mathcal{S})$.

Proof. Each chef’s success is an independent Bernoulli trial with parameter $S(c_i)$.

For (i): a complete failure occurs if and only if every chef fails, which has probability $\prod_{i=1}^{m} q_i$ by independence.

For (ii): chef $c_j$ is the first to succeed in a round if and only if $c_1, \ldots, c_{j-1}$ all fail and $c_j$ succeeds. By independence, this has probability $S(c_j) \prod_{i=1}^{j-1} q_i$.

For (iii): we verify

This is proved by induction on $m$. For $m = 1$: $S(c_1) = 1 - q_1$. Assuming it holds for $m - 1$ chefs, adding the $m$-th chef contributes $S(c_m) \prod_{i=1}^{m-1} q_i$, and the sum becomes $(1 - \prod_{i=1}^{m-1} q_i) + (1 - q_m) \prod_{i=1}^{m-1} q_i = 1 - \prod_{i=1}^{m} q_i$.

For (iv): rounds are independent (each round’s outcome depends only on fresh Bernoulli trials), so the count of completely failed rounds before the first success follows $\text{Geom}(1 - Q(\mathcal{S}))$. $\square$

Corollary 1. Conditioned on the first success occurring in some round, the probability that chef $c_j$ is the one to succeed is

Proof. Immediate from the law of total probability and the memoryless property of the geometric distribution. $\square$

Theorem 2 (Optimal elimination strategy). For each state $(\mathcal{S}, \tau)$ and each chef $c_j \in \mathcal{S}$, define $W(c_j, \mathcal{S}, \tau)$ as the probability that $c_j$ ultimately wins. When $c_j$ succeeds and must choose whom to eliminate, the optimal target is

with ties broken by choosing the chef whose turn comes soonest after $c_j$ in the cyclic order, where $\tau'(t)$ denotes the appropriate starting index in $\mathcal{S} \setminus \{t\}$.

Proof. By backward induction on $|\mathcal{S}|$.

Base case: $|\mathcal{S}| = 1$. The remaining chef wins with probability 1; no elimination decision is required.

Inductive step: Suppose the winning probabilities $W(\cdot, \mathcal{S}', \cdot)$ are uniquely determined for all states $\mathcal{S}'$ with $|\mathcal{S}'| < |\mathcal{S}|$. When chef $c_j$ succeeds in state $(\mathcal{S}, \tau)$, eliminating target $t$ transitions the game to state $(\mathcal{S} \setminus \{t\}, \tau'(t))$, where $\tau'(t)$ is determined by the cyclic turn order (the next chef after $c_j$ who is not $t$). A rational agent maximizes $W(c_j, \mathcal{S} \setminus \{t\}, \tau'(t))$ over all valid targets $t$. This is well-defined by the inductive hypothesis. The tie-breaking rule is deterministic and consistent. $\square$

Theorem 3 (Expected dish count). The expected number of dishes cooked from state $(\mathcal{S}, \tau)$ satisfies the recurrence

where $E_{\text{partial}}(\mathcal{S}, \tau) = \sum_{j=1}^{m} j \cdot P_j(\mathcal{S})$ is the expected number of dishes cooked within the successful round, $t_j^*$ is the optimal elimination target for chef $c_j$, and $\tau_j'$ is the resulting starting index.

Equivalently, combining the first two terms:

with the base case $E(\{c\}, \cdot) = 0$ for any single chef $c$.

Proof. Condition on the geometric number of failed rounds $R \sim \text{Geom}(1 - Q(\mathcal{S}))$. In each of the $R$ failed rounds (expected count $Q/(1-Q)$), exactly $m$ dishes are cooked, contributing $m \cdot Q/(1-Q)$ in expectation. In the successful round, chef $c_j$ succeeds at position $j$ (i.e., after $j$ dishes in that round), with conditional probability $P_j/(1-Q)$. This gives the partial-round expected dish count $E_{\text{partial}}/(1-Q)$.

After the elimination, the game transitions to state $(\mathcal{S} \setminus \{t_j^*\}, \tau_j')$ and the expected remaining dishes are $E(\mathcal{S} \setminus \{t_j^*\}, \tau_j')$, weighted by the conditional probability $P_j/(1-Q)$.

The base case $E(\{c\}, \cdot) = 0$ holds because no more dishes are cooked once a single chef remains. $\square$

Editorial

Chef k has skill S(k) = F_k / F_{n+1} (Fibonacci ratio). Chefs eliminate each other optimally. Compute E(14), the expected number of dishes cooked. Method: bitmask DP over game states (remaining chefs, start index). For each state, compute winning probabilities via Theorem 2 (backward induction on optimal elimination) and expected dishes via Theorem 3 (geometric round structure + recursive decomposition).

Pseudocode

    Compute Fibonacci numbers F[1..n+1]
    S[k] = F[k] / F[n+1] for k = 1..n

    States are (bitmask of remaining chefs, start index within the ordered set)

    For each each state (mask, start_idx) in order of increasing popcount(mask):
        If popcount(mask) == 1 then
            W[mask][start_idx][lone_chef] = 1.0
            E[mask][start_idx] = 0.0
            continue

        chefs = sorted list of set bits in mask
        m = len(chefs)
        Reorder chefs cyclically starting at start_idx
        Compute Q, P[j], and reach probabilities p_reach[j]

        For each chef c_j, find optimal target t_j* via argmax of W
        (with tie-breaking by cyclic distance)

        Compute W[mask][start_idx][k] for all k via weighted sum
        Compute E[mask][start_idx] via Theorem 3

    Return E[full_mask][0]

Complexity Analysis

• Time: $O(n^2 \cdot 2^n)$. There are $O(n \cdot 2^n)$ states (mask, start); for each state with $m$ chefs, evaluating all elimination choices costs $O(m)$ per chef, yielding $O(m^2)$ per state. Summing over all masks: $\sum_{\text{masks}} m^2 = O(n^2 \cdot 2^n)$. For $n = 14$, this is approximately $14^2 \times 16384 \approx 3.2 \times 10^6$ operations.
• Space: $O(n \cdot 2^n)$ for storing winning probabilities $W[\text{mask}][\text{start}][\text{chef}]$ and expected dishes $E[\text{mask}][\text{start}]$.

Answer

/*
 * Project Euler Problem 481: Chef Showdown
 *
 * Chef k has skill S(k) = F_k / F_{n+1}. Chefs eliminate each other optimally.
 * Compute E(14) via bitmask DP over game states (remaining chefs, start index).
 *
 * Theorems applied:
 *   - Geometric round structure (Theorem 1): first-success probabilities P_j
 *   - Optimal elimination (Theorem 2): backward induction on win probabilities
 *   - Expected dishes (Theorem 3): geometric + recursive decomposition
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 14;
double fib[MAXN + 2];
double skill[MAXN];

void init_fib(int n) {
    fib[1] = fib[2] = 1;
    for (int i = 3; i <= n + 1; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
}

vector<int> get_chefs(int mask, int n) {
    vector<int> v;
    for (int i = 0; i < n; i++)
        if (mask & (1 << i)) v.push_back(i);
    return v;
}

int find_next_turn(const vector<int>& order, int j, int elim_chef) {
    int m = order.size();
    for (int k = j + 1; k < m; k++)
        if (order[k] != elim_chef) return order[k];
    for (int k = 0; k < j; k++)
        if (order[k] != elim_chef) return order[k];
    return -1;
}

map<pair<int,int>, vector<double>> memo_win;
map<pair<int,int>, double> memo_exp;

vector<double> compute_win(int mask, int start_idx, int n);
double compute_exp(int mask, int start_idx, int n);

vector<double> compute_win(int mask, int start_idx, int n) {
    auto key = make_pair(mask, start_idx);
    auto it = memo_win.find(key);
    if (it != memo_win.end()) return it->second;

    vector<int> chefs = get_chefs(mask, n);
    int m = chefs.size();

    if (m == 1) {
        vector<double> w(n, 0);
        w[chefs[0]] = 1.0;
        return memo_win[key] = w;
    }

    vector<int> order;
    for (int i = start_idx; i < m; i++) order.push_back(chefs[i]);
    for (int i = 0; i < start_idx; i++) order.push_back(chefs[i]);

    vector<double> p_reach(m);
    p_reach[0] = 1.0;
    for (int j = 1; j < m; j++)
        p_reach[j] = p_reach[j - 1] * (1.0 - skill[order[j - 1]]);
    double p_none = p_reach[m - 1] * (1.0 - skill[order[m - 1]]);

    vector<double> result(n, 0);
    for (int j = 0; j < m; j++) {
        double p_j = p_reach[j] * skill[order[j]] / (1.0 - p_none);

        double best_wp = -1;
        int best_e = -1;
        vector<double> best_w;

        for (int e = 0; e < m; e++) {
            if (e == j) continue;
            int elim = order[e];
            int new_mask = mask ^ (1 << elim);
            vector<int> nc = get_chefs(new_mask, n);

            int nxt = find_next_turn(order, j, elim);
            int ns = 0;
            if (nxt >= 0)
                for (int k = 0; k < (int)nc.size(); k++)
                    if (nc[k] == nxt) { ns = k; break; }

            vector<double> w = compute_win(new_mask, ns, n);
            if (w[order[j]] > best_wp + 1e-15) {
                best_wp = w[order[j]];
                best_e = e;
                best_w = w;
            } else if (fabs(w[order[j]] - best_wp) < 1e-15) {
                if ((e - j + m) % m < (best_e - j + m) % m) {
                    best_e = e;
                    best_w = w;
                }
            }
        }

        for (int k = 0; k < n; k++)
            result[k] += p_j * best_w[k];
    }

    return memo_win[key] = result;
}

double compute_exp(int mask, int start_idx, int n) {
    auto key = make_pair(mask, start_idx);
    auto it = memo_exp.find(key);
    if (it != memo_exp.end()) return it->second;

    vector<int> chefs = get_chefs(mask, n);
    int m = chefs.size();

    if (m == 1) return memo_exp[key] = 0;

    vector<int> order;
    for (int i = start_idx; i < m; i++) order.push_back(chefs[i]);
    for (int i = 0; i < start_idx; i++) order.push_back(chefs[i]);

    vector<double> p_reach(m);
    p_reach[0] = 1.0;
    for (int j = 1; j < m; j++)
        p_reach[j] = p_reach[j - 1] * (1.0 - skill[order[j - 1]]);
    double p_none = p_reach[m - 1] * (1.0 - skill[order[m - 1]]);

    double exp_partial = 0;
    for (int j = 0; j < m; j++)
        exp_partial += (j + 1) * p_reach[j] * skill[order[j]];
    exp_partial /= (1.0 - p_none);

    double exp_dishes = p_none / (1.0 - p_none) * m + exp_partial;

    double exp_after = 0;
    for (int j = 0; j < m; j++) {
        double p_j = p_reach[j] * skill[order[j]] / (1.0 - p_none);

        double best_wp = -1;
        int best_e = -1, best_ns = 0, best_nm = 0;

        for (int e = 0; e < m; e++) {
            if (e == j) continue;
            int elim = order[e];
            int new_mask = mask ^ (1 << elim);
            vector<int> nc = get_chefs(new_mask, n);

            int nxt = find_next_turn(order, j, elim);
            int ns = 0;
            if (nxt >= 0)
                for (int k = 0; k < (int)nc.size(); k++)
                    if (nc[k] == nxt) { ns = k; break; }

            vector<double> w = compute_win(new_mask, ns, n);
            if (w[order[j]] > best_wp + 1e-15) {
                best_wp = w[order[j]];
                best_e = e;
                best_ns = ns;
                best_nm = new_mask;
            } else if (fabs(w[order[j]] - best_wp) < 1e-15) {
                if ((e - j + m) % m < (best_e - j + m) % m) {
                    best_e = e;
                    best_ns = ns;
                    best_nm = new_mask;
                }
            }
        }

        exp_after += p_j * compute_exp(best_nm, best_ns, n);
    }

    return memo_exp[key] = exp_dishes + exp_after;
}

int main() {
    int n = 7;
    init_fib(n);
    for (int k = 0; k < n; k++)
        skill[k] = fib[k + 1] / fib[n + 1];
    printf("E(7) = %.8f\n", compute_exp((1 << n) - 1, 0, n));

    memo_win.clear();
    memo_exp.clear();
    n = 14;
    init_fib(n);
    for (int k = 0; k < n; k++)
        skill[k] = fib[k + 1] / fib[n + 1];
    printf("E(14) = %.8f\n", compute_exp((1 << n) - 1, 0, n));

    return 0;
}

"""
Project Euler Problem 481: Chef Showdown

Chef k has skill S(k) = F_k / F_{n+1} (Fibonacci ratio). Chefs eliminate
each other optimally. Compute E(14), the expected number of dishes cooked.

Method: bitmask DP over game states (remaining chefs, start index).
For each state, compute winning probabilities via Theorem 2 (backward
induction on optimal elimination) and expected dishes via Theorem 3
(geometric round structure + recursive decomposition).
"""


def solve(n):
    fib = [0] * (n + 2)
    fib[1] = fib[2] = 1
    for i in range(3, n + 2):
        fib[i] = fib[i - 1] + fib[i - 2]

    skills = [fib[k + 1] / fib[n + 1] for k in range(n)]

    def get_chefs(mask):
        return [i for i in range(n) if mask & (1 << i)]

    cache_win = {}
    cache_exp = {}

    def find_next_turn(order, j, elim_chef):
        """Find the next chef in cyclic order after position j, excluding elim_chef."""
        m = len(order)
        for k in range(j + 1, m):
            if order[k] != elim_chef:
                return order[k]
        for k in range(j):
            if order[k] != elim_chef:
                return order[k]
        return None

    def compute_win(mask, start_idx):
        key = (mask, start_idx)
        if key in cache_win:
            return cache_win[key]

        chefs = get_chefs(mask)
        m = len(chefs)

        if m == 1:
            result = [0.0] * n
            result[chefs[0]] = 1.0
            cache_win[key] = result
            return result

        order = chefs[start_idx:] + chefs[:start_idx]

        p_reach = [0.0] * m
        p_reach[0] = 1.0
        for j in range(1, m):
            p_reach[j] = p_reach[j - 1] * (1.0 - skills[order[j - 1]])
        p_none = p_reach[-1] * (1.0 - skills[order[-1]])

        result = [0.0] * n
        for j in range(m):
            p_j = p_reach[j] * skills[order[j]] / (1.0 - p_none)

            best_win_prob = -1.0
            best_elim = -1
            best_wins = None

            for e in range(m):
                if e == j:
                    continue
                elim_chef = order[e]
                new_mask = mask ^ (1 << elim_chef)
                new_chefs = get_chefs(new_mask)

                next_in_cycle = find_next_turn(order, j, elim_chef)
                new_start = new_chefs.index(next_in_cycle) if next_in_cycle is not None else 0

                w = compute_win(new_mask, new_start)
                if w[order[j]] > best_win_prob + 1e-15:
                    best_win_prob = w[order[j]]
                    best_elim = e
                    best_wins = w
                elif abs(w[order[j]] - best_win_prob) < 1e-15:
                    if (e - j) % m < (best_elim - j) % m:
                        best_elim = e
                        best_wins = w

            for k in range(n):
                result[k] += p_j * best_wins[k]

        cache_win[key] = result
        return result

    def compute_exp(mask, start_idx):
        key = (mask, start_idx)
        if key in cache_exp:
            return cache_exp[key]

        chefs = get_chefs(mask)
        m = len(chefs)
        if m == 1:
            cache_exp[key] = 0.0
            return 0.0

        order = chefs[start_idx:] + chefs[:start_idx]

        p_reach = [0.0] * m
        p_reach[0] = 1.0
        for j in range(1, m):
            p_reach[j] = p_reach[j - 1] * (1.0 - skills[order[j - 1]])
        p_none = p_reach[-1] * (1.0 - skills[order[-1]])

        exp_success = sum(
            (j + 1) * p_reach[j] * skills[order[j]] for j in range(m)
        )
        exp_success /= 1.0 - p_none
        exp_failed = p_none / (1.0 - p_none) * m
        exp_dishes = exp_failed + exp_success

        exp_after = 0.0
        for j in range(m):
            p_j = p_reach[j] * skills[order[j]] / (1.0 - p_none)

            best_win_prob = -1.0
            best_elim = -1
            best_new_mask = 0
            best_new_start = 0

            for e in range(m):
                if e == j:
                    continue
                elim_chef = order[e]
                new_mask = mask ^ (1 << elim_chef)
                new_chefs = get_chefs(new_mask)

                next_in_cycle = find_next_turn(order, j, elim_chef)
                new_start = new_chefs.index(next_in_cycle) if next_in_cycle is not None else 0

                w = compute_win(new_mask, new_start)
                if w[order[j]] > best_win_prob + 1e-15:
                    best_win_prob = w[order[j]]
                    best_elim = e
                    best_new_mask = new_mask
                    best_new_start = new_start
                elif abs(w[order[j]] - best_win_prob) < 1e-15:
                    if (e - j) % m < (best_elim - j) % m:
                        best_elim = e
                        best_new_mask = new_mask
                        best_new_start = new_start

            exp_after += p_j * compute_exp(best_new_mask, best_new_start)

        result = exp_dishes + exp_after
        cache_exp[key] = result
        return result

    full_mask = (1 << n) - 1
    return compute_exp(full_mask, 0)


if __name__ == "__main__":
    E7 = solve(7)
    print(f"E(7) = {E7:.8f}")
    E14 = solve(14)
    print(f"E(14) = {E14:.8f}")