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.
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.
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.
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.
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.
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.
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.
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\).
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.
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\).
Es gibt \(n\) Köche in zyklischer Reihenfolge \(1,2,\dots,n\). Koch \(k\) trifft ein gewähltes Ziel mit Wahrscheinlichkeit
$$p_k=\frac{F_k}{F_{n+1}},\qquad k=1,\dots,n,$$
wobei \(F_1=F_2=1\) gilt. Jeder Zug erzeugt genau ein Gericht. Der aktuelle Koch wählt einen noch lebenden Gegner, versucht ihn zu eliminieren, und danach geht der Zug an den nächsten noch lebenden Koch nach dem aktuellen weiter. Bei Erfolg wird das gewählte Ziel entfernt, bei Misserfolg bleibt die Spielermenge unverändert. Das Spiel endet, sobald nur noch ein Koch lebt.
Für jeden Spielzustand interessieren uns sowohl der gesamte Vektor der Endgewinnwahrscheinlichkeiten als auch die erwartete Zahl verbleibender Gerichte. Die gesuchte Project-Euler-Größe ist
$$E(n)=D_{\{1,2,\dots,n\},1},$$
also die erwartete Zahl der Gerichte vom Vollzustand aus, wenn Koch \(1\) beginnt.
Die zentrale Idee ist eine dynamische Programmierung über Teilmengen der noch lebenden Köche. Sobald kleinere Mengen gelöst sind, ist auch die beste Zielwahl in jedem größeren Zustand bekannt, und die restlichen Gleichungen bilden ein einziges zyklisches lineares System.
Sei \(M\subseteq\{1,\dots,n\}\) die Menge der noch lebenden Köche und \(t\in M\) der Koch am Zug. Wir definieren
$$\mathbf W_{M,t}=\bigl(W_{M,t}(1),\dots,W_{M,t}(n)\bigr),$$
wobei \(W_{M,t}(i)\) die Wahrscheinlichkeit ist, dass Koch \(i\) am Ende gewinnt, wenn das Spiel im Zustand \((M,t)\) startet. Zusätzlich definieren wir
$$D_{M,t}$$
für die erwartete Zahl zusätzlicher Gerichte ab dem Zustand \((M,t)\).
Lebt nur noch ein Koch, ist das Spiel bereits beendet. Für \(M=\{i\}\) gilt daher
$$W_{\{i\},i}(i)=1,\qquad W_{\{i\},i}(k)=0\ (k\ne i),\qquad D_{\{i\},i}=0.$$
Mit \(\operatorname{next}_M(t)\) bezeichnen wir den nächsten noch lebenden Koch nach \(t\) in zyklischer Reihenfolge, bei Bedarf mit Umlauf zum Anfang.
Sei \(|M|\ge 2\). Wählt Koch \(t\) ein Ziel \(j\in M\setminus\{t\}\), dann geht das Spiel mit Wahrscheinlichkeit \(p_t\) in den Zustand
$$\left(M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)\right)$$
über und mit Wahrscheinlichkeit \(1-p_t\) in den Zustand
$$\left(M,\operatorname{next}_M(t)\right).$$
Der Misserfolgszweig ist für jedes Ziel gleich. Deshalb muss Koch \(t\) nur den Erfolgswert maximieren, also
$$W_{M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)}(t).$$
Liefern mehrere Ziele denselben Wert, benutzt die Implementierung als deterministischen Tie-Break die kleinste positive zyklische Distanz von \(t\). So wird für jeden Zustand genau ein Nachfolger festgelegt.
Entscheidend ist: Jeder mögliche Erfolgszustand hat genau einen Überlebenden weniger. Sobald kleinere Teilmengen gelöst sind, ist die optimale Zielwahl also sofort verfügbar.
Fixiere nun eine Menge \(M\) mit \(q=|M|\ge 2\) und schreibe ihre Mitglieder in zyklischer Reihenfolge als
$$m_0,m_1,\dots,m_{q-1}.$$
Für jede Position \(r\) setzen wir
$$X_r=\mathbf W_{M,m_r},\qquad Y_r=D_{M,m_r}.$$
Nachdem für Koch \(m_r\) das beste Ziel bestimmt wurde, sei \(U_r\) der bereits bekannte Gewinnwahrscheinlichkeitsvektor des zugehörigen Erfolgszustands und \(V_r\) die dort bereits bekannte erwartete Restzahl an Gerichten. Dann gilt für einen Zug
$$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},$$
wobei die Indizes modulo \(q\) gelesen werden. Die Konstante \(1\) erscheint, weil jeder Zug genau ein neues Gericht erzeugt.
Setze
$$A_r=p_{m_r}U_r,\qquad C_r=1+p_{m_r}V_r,\qquad b_r=1-p_{m_r}.$$
Dann werden die Rekursionen zu
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
Rollt man die erste Gleichung einmal um den gesamten Ring ab, erhält man
$$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.$$
Daraus folgt
$$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}.$$
Genau dieselbe Rechnung liefert
$$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}.$$
Dabei ist das leere Produkt für \(r=0\) gleich \(1\). Weil alle Trefferwahrscheinlichkeiten positiv sind, gilt \(\prod b_i<1\), also ist der Nenner ungleich null. Die Formel für \(X_0\) ist vektorwertig, aber jede Komponente folgt demselben skalaren Koeffizientenmuster.
Sind \(X_0\) und \(Y_0\) bekannt, ergeben sich die übrigen Zustände derselben Maske per Rückwärtseinsetzen:
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
So wird die zyklische Abhängigkeit ohne allgemeine Matrixinversion aufgelöst.
Alle Masken mit nur einem lebenden Koch bilden die Basisfälle. Danach werden die Lebendmengen in aufsteigender Größe \(1,2,\dots,n\) bearbeitet. Wenn eine Menge \(M\) an der Reihe ist, ist jeder Erfolgszustand \(M\setminus\{j\}\) bereits gelöst. Deshalb ist die beste Zielwahl jedes aktiven Kochs sofort bekannt, und die Formeln aus Schritt 4 lassen sich direkt anwenden.
Das ist Teilmengen-DP, aber jeder Zustand speichert mehr als nur einen Skalar: Er enthält einen gesamten Gewinnwahrscheinlichkeitsvektor und zusätzlich einen Erwartungswert.
Dieses Beispiel ist besonders nützlich, weil es als numerischer Kontrollpunkt der Implementierung dient. Der Startzustand ist \((\{1,2,3\},1)\).
Zuerst lösen wir die Zustände mit zwei Köchen. Für die Köche \(1\) und \(2\) gilt bei Zug von Koch \(1\)
$$W_{\{1,2\},1}(1)=\frac{\frac14}{1-\frac34\cdot\frac12}=0.4.$$
Damit folgt
$$W_{\{1,2\},2}(1)=\left(1-\frac12\right)\cdot 0.4=0.2.$$
Ebenso erhält man
$$W_{\{1,3\},1}(1)=0.25,\qquad W_{\{2,3\},2}(2)=0.5.$$
Nun bestimmen wir die optimalen Ziele in der Drei-Koch-Maske. Koch \(1\) greift lieber Koch \(3\) an, denn ein Erfolg lässt das Duell \(\{1,2\}\) mit Koch \(2\) am Zug zurück, wo Koch \(1\) Gewinnwahrscheinlichkeit \(0.2\) hat; das Eliminieren von Koch \(2\) würde dagegen Koch \(3\) den nächsten Zug geben und liefert Erfolgswert \(0\).
Koch \(2\) bevorzugt ebenfalls Koch \(3\), weil der Erfolgszweig dann \(\{1,2\}\) mit Koch \(1\) am Zug ergibt, wo Koch \(2\) Gewinnwahrscheinlichkeit \(0.6\) besitzt, also mehr als die Alternative \(0\).
Koch \(3\) wählt Koch \(2\), denn ein sicherer Erfolg führt zum Duell \(\{1,3\}\) mit Koch \(1\) am Zug, und dort beträgt die Gewinnwahrscheinlichkeit von Koch \(3\) gleich \(0.75\), also mehr als die \(0.5\) nach dem Eliminieren von Koch \(1\).
Bezeichne jetzt mit \(x_r\) die Endgewinnwahrscheinlichkeit von Koch \(1\), wenn aktuell Koch \(r\) am Zug ist. Die gewählten Ziele liefern
$$x_1=\frac14\cdot 0.2+\frac34x_2,$$
$$x_2=\frac12\cdot 0.4+\frac12x_3,$$
$$x_3=1\cdot 0.25.$$
Also
$$x_3=0.25,\qquad x_2=0.325,\qquad x_1=0.05+0.75\cdot 0.325=0.29375,$$
genau der veröffentlichte Kontrollwert \(W_3(1)=0.29375\).
Die Implementierungen in C++, Python und Java erzeugen zunächst die Fibonacci-basierten Trefferwahrscheinlichkeiten und gruppieren alle Lebendmengen nach ihrer Größe. Für jede Lebendmenge werden die überlebenden Köche in zyklischer Reihenfolge aufgelistet. Zustände mit nur einem Überlebenden werden direkt als Basisfälle gefüllt.
Für jeden nichttrivialen Zustand prüft die Implementierung jedes mögliche Ziel des aktuellen Kochs. Da jeder Erfolgszustand einen Überlebenden weniger besitzt, ist sein Gewinnwahrscheinlichkeitsvektor bereits bekannt. Gewählt wird das Ziel, dessen Erfolgszweig dem aktiven Koch die größte Endgewinnwahrscheinlichkeit gibt; Gleichstände werden mit der zyklischen Distanz aufgelöst.
Sobald diese besten Ziele für die gesamte Lebendmenge feststehen, baut die Implementierung die Erfolgsbeiträge \(A_r\) und \(C_r\) auf, speichert die Misserfolgsfaktoren \(b_r=1-p_{m_r}\), wertet die geschlossenen Zyklusformeln aus und rekonstruiert anschließend per Rückwärtseinsetzen alle Zugzustände dieser Maske. Gespeichert werden sowohl die vollständigen Gewinnwahrscheinlichkeitsvektoren als auch die erwarteten Restzahlen an Gerichten.
Am Ende ist der gesuchte Project-Euler-Wert einfach der Erwartungswert der Vollmaske, wenn Koch \(1\) als Erster zieht.
Für eine Maske mit \(m\) lebenden Köchen kostet die Zielwahl \(O(m^2)\), während Aufbau und Fortpflanzung der Gewinnwahrscheinlichkeitsvektoren \(O(mn)\) benötigen. Über alle Masken summiert ergibt das
$$\sum_{m=0}^{n}\binom{n}{m}(m^2+mn)=O(n^2 2^n).$$
Die gespeicherten Gewinnwahrscheinlichkeitsvektoren dominieren den Speicherbedarf, daher benötigt die exakte Methode auch
$$O(n^2 2^n)$$
Speicher. Deshalb ist der exakte Solver nur für relativ kleine \(n\) praktisch.
\(n\) tane şef, \(1,2,\dots,n\) biçiminde döngüsel sırayla dizilidir. \(k\). şefin seçtiği hedefi vurma olasılığı
$$p_k=\frac{F_k}{F_{n+1}},\qquad k=1,\dots,n,$$
şeklindedir; burada \(F_1=F_2=1\) alınır. Her tur tam bir yemek üretir. Sıradaki şef yaşayan rakiplerden birini seçer, onu eleme girişiminde bulunur ve sonra sıra mevcut şeften sonraki yaşayan şefe geçer. Başarılı olursa seçilen hedef oyundan çıkar, başarısız olursa kimse elenmez. Oyun yalnızca bir şef kalana kadar sürer.
Her oyun durumu için hem tüm kazanma olasılıkları vektörünü hem de kalan yemek sayısının beklenen değerini hesaplamak isteriz. Project Euler'de istenen büyüklük
$$E(n)=D_{\{1,2,\dots,n\},1},$$
yani tüm şefler hayattayken ve ilk hamleyi şef \(1\) yaparken beklenen yemek sayısıdır.
Ana fikir, yaşayan şef kümeleri üzerinde altküme DP yapmaktır. Daha küçük kümeler çözüldüğünde daha büyük her durumda en iyi hedef de belirlenmiş olur; geriye tek bir döngüsel lineer denklem sistemi kalır.
\(M\subseteq\{1,\dots,n\}\) yaşayan şefler kümesi, \(t\in M\) ise hamle sırası gelen şef olsun. Şunu tanımlayalım:
$$\mathbf W_{M,t}=\bigl(W_{M,t}(1),\dots,W_{M,t}(n)\bigr),$$
burada \(W_{M,t}(i)\), oyun \((M,t)\) durumundan başlarsa sonunda kazananın şef \(i\) olma olasılığıdır. Ayrıca
$$D_{M,t}$$
\((M,t)\) durumundan itibaren oluşacak ek yemek sayısının beklenen değeri olarak tanımlansın.
tanımını yapalım. Eğer yalnızca bir şef hayattaysa oyun zaten bitmiştir. Bu yüzden \(M=\{i\}\) için
$$W_{\{i\},i}(i)=1,\qquad W_{\{i\},i}(k)=0\ (k\ne i),\qquad D_{\{i\},i}=0$$
olur. \(\operatorname{next}_M(t)\), \(t\)'den sonra döngüsel sırada gelen bir sonraki yaşayan şefi göstersin.
\(|M|\ge 2\) olsun. Eğer şef \(t\), \(j\in M\setminus\{t\}\) hedefini seçerse oyun \(p_t\) olasılığıyla
$$\left(M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)\right)$$
durumuna, \(1-p_t\) olasılığıyla da
$$\left(M,\operatorname{next}_M(t)\right)$$
durumuna geçer. Başarısızlık kolu hangi hedefin seçildiğine bağlı değildir. Dolayısıyla şef \(t\)'nin büyütmesi gereken tek şey başarı kolundaki öz değerdir:
$$W_{M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)}(t).$$
Birden fazla hedef aynı değeri verirse uygulama deterministik bağ bozma kuralı olarak \(t\)'den olan en küçük pozitif döngüsel uzaklığı seçer. Böylece her durum için tekil bir ardıl durum belirlenir.
Önemli nokta şudur: Her başarı durumu bir şef eksiktir. Yani daha küçük altkümeler çözüldüğü anda en iyi hedef seçimi de hazırdır.
\(q=|M|\ge 2\) olan sabit bir \(M\) kümesi seçelim ve üyelerini döngüsel sırada
$$m_0,m_1,\dots,m_{q-1}$$
şeklinde yazalım. Her \(r\) için
$$X_r=\mathbf W_{M,m_r},\qquad Y_r=D_{M,m_r}$$
olsun. Şef \(m_r\) için en iyi hedef belirlendikten sonra, karşılık gelen başarı durumunun zaten bilinen kazanma olasılığı vektörüne \(U_r\), zaten bilinen beklenen kalan yemek sayısına da \(V_r\) diyelim. O zaman bir tur şu denklemleri verir:
$$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},$$
burada indisler mod \(q\) alınır. İkinci denklemdeki \(1\), her tur bir yemek üretildiği için vardır.
Şöyle yazalım:
$$A_r=p_{m_r}U_r,\qquad C_r=1+p_{m_r}V_r,\qquad b_r=1-p_{m_r}.$$
Böylece denklemler
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}$$
olur. İlk denklemi bir tam tur açarsak
$$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$$
elde edilir. Buradan
$$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}$$
çıkar. Aynı cebir
$$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}$$
sonucunu verir. Burada \(r=0\) için boş çarpım \(1\)'dir. Bütün beceri olasılıkları pozitif olduğu için \(\prod b_i<1\), yani payda sıfır değildir. \(X_0\) vektör değerli olsa da her bileşen aynı skaler katsayı zincirini izler.
\(X_0\) ve \(Y_0\) bulunduktan sonra aynı maskenin öteki durumları geri yerine koyma ile elde edilir:
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
Böylece döngüsel bağımlılık genel amaçlı matris terslemesine gerek kalmadan çözülür.
Tek şefli maskeler taban durumlardır. Sonra yaşayan kümeler \(1,2,\dots,n\) artan büyüklük sırasıyla işlenir. Bir \(M\) maskesi ele alındığında, her başarı durumu \(M\setminus\{j\}\) zaten çözülmüştür. Bu yüzden her aktif şefin en iyi hedefi hemen bilinir ve Adım 4'teki formüller doğrudan uygulanır.
Bu klasik bir altküme DP'sidir; fakat her durum tek bir skaler değil, tam bir kazanma olasılığı vektörü ve bir beklenti değeri saklar.
Bu küçük örnek pratiktir çünkü uygulamanın sayısal kontrol noktalarından biridir. Başlangıç durumu \((\{1,2,3\},1)\)'dir.
Önce iki şefli durumları çözelim. Şef \(1\) ve şef \(2\) için, sıra şef \(1\)'deyse
$$W_{\{1,2\},1}(1)=\frac{\frac14}{1-\frac34\cdot\frac12}=0.4$$
olur. Dolayısıyla
$$W_{\{1,2\},2}(1)=\left(1-\frac12\right)\cdot 0.4=0.2.$$
Aynı şekilde
$$W_{\{1,3\},1}(1)=0.25,\qquad W_{\{2,3\},2}(2)=0.5$$
bulunur. Şimdi üç şefli maskede en iyi hedefleri belirleyelim. Şef \(1\), şef \(3\)'ü hedeflemeyi tercih eder; çünkü başarı durumunda sıra şef \(2\)'de olan \(\{1,2\}\) düellosu kalır ve burada şef \(1\)'in kazanma olasılığı \(0.2\)'dir. Eğer şef \(2\)'yi eleyebilseydi başarı kolu şef \(3\)'ün sırasına gider ve değer \(0\) olurdu.
Şef \(2\) de şef \(3\)'ü hedefler; çünkü başarı kolunda sıra şef \(1\)'de olan \(\{1,2\}\) düellosu kalır ve burada şef \(2\)'nin nihai kazanma olasılığı \(0.6\)'dır. Bu, diğer seçeneğin verdiği \(0\)'dan büyüktür.
Şef \(3\) ise şef \(2\)'yi hedefler; çünkü kesin başarıdan sonra sıra şef \(1\)'de olan \(\{1,3\}\) düellosu başlar ve burada şef \(3\)'ün kazanma olasılığı \(0.75\)'tir. Şef \(1\)'i elemek ise yalnızca \(0.5\) verir.
Şimdi \(x_r\), sıradaki oyuncu şef \(r\) iken şef \(1\)'in nihai kazanma olasılığı olsun. Seçilen hedefler
$$x_1=\frac14\cdot 0.2+\frac34x_2,$$
$$x_2=\frac12\cdot 0.4+\frac12x_3,$$
$$x_3=1\cdot 0.25$$
denklemlerini verir. Buradan
$$x_3=0.25,\qquad x_2=0.325,\qquad x_1=0.05+0.75\cdot 0.325=0.29375$$
elde edilir; bu da yayınlanan \(W_3(1)=0.29375\) kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları önce Fibonacci tabanlı beceri olasılıklarını üretir ve tüm yaşayan kümeleri eleman sayılarına göre gruplar. Her küme için hayatta kalan şefler döngüsel sırada listelenir. Tek şefli durumlar doğrudan taban durum olarak doldurulur.
Her önemsiz olmayan durumda uygulama, sıradaki şefin seçebileceği tüm hedefleri dener. Her başarı durumu bir kişi daha küçük olduğu için, o durumun kazanma olasılığı vektörü zaten önceden hesaplanmıştır. Başarı kolunda aktif şefe en büyük nihai kazanma olasılığını veren hedef seçilir; eşitliklerde döngüsel uzaklık kuralı kullanılır.
Bu en iyi hedefler tüm maske için sabitlendikten sonra uygulama \(A_r\) ve \(C_r\) başarı katkılarını kurar, \(b_r=1-p_{m_r}\) başarısızlık katsayılarını saklar, yukarıdaki kapalı döngü formüllerini değerlendirir ve geri yerine koyma ile o maskenin tüm sıra durumlarını elde eder. Hem tam kazanma olasılığı vektörleri hem de kalan yemek sayılarının beklentileri depolanır.
Sonunda gereken Project Euler değeri, tüm şefler hayattayken ilk hamleyi şef \(1\)'in yaptığı durum için saklanan beklentidir.
\(m\) yaşayan şef içeren bir maske için hedef seçimi \(O(m^2)\), kazanma olasılığı vektörlerini kurma ve yayma ise \(O(mn)\) maliyetlidir. Tüm maskeler üzerinde toplam
$$\sum_{m=0}^{n}\binom{n}{m}(m^2+mn)=O(n^2 2^n)$$
olur. Bellek kullanımını esas olarak saklanan kazanma olasılığı vektörleri belirlediği için, kesin yöntem
$$O(n^2 2^n)$$
bellek de kullanır. Bu nedenle kesin çözücü ancak nispeten küçük \(n\) için pratiktir.
Hay \(n\) chefs colocados en orden cíclico \(1,2,\dots,n\). El chef \(k\) elimina al objetivo que elige con probabilidad
$$p_k=\frac{F_k}{F_{n+1}},\qquad k=1,\dots,n,$$
donde \(F_1=F_2=1\). Cada turno produce exactamente un plato. El chef actual elige a un oponente vivo, intenta eliminarlo y después el turno pasa al siguiente chef vivo después del actual. Si acierta, el objetivo elegido desaparece; si falla, nadie es eliminado. La partida termina cuando solo queda un chef.
Para cada estado del juego queremos tanto el vector completo de probabilidades finales de victoria como la esperanza del número de platos restantes. La cantidad pedida por Project Euler es
$$E(n)=D_{\{1,2,\dots,n\},1},$$
la esperanza del número de platos desde el estado inicial completo cuando el chef \(1\) mueve primero.
La idea central es resolver el juego con programación dinámica sobre subconjuntos de chefs vivos. Una vez resueltos los subconjuntos más pequeños, también queda determinada la mejor elección de objetivo en cualquier estado mayor, y las ecuaciones restantes forman un único sistema lineal cíclico.
Sea \(M\subseteq\{1,\dots,n\}\) el conjunto de chefs vivos y \(t\in M\) el chef cuyo turno es. Definimos
$$\mathbf W_{M,t}=\bigl(W_{M,t}(1),\dots,W_{M,t}(n)\bigr),$$
donde \(W_{M,t}(i)\) es la probabilidad de que el chef \(i\) sea el ganador final cuando el juego empieza en el estado \((M,t)\). Además definimos
$$D_{M,t}$$
como la esperanza del número adicional de platos a partir del estado \((M,t)\).
Si solo queda un chef vivo, la partida ya terminó. Por tanto, para \(M=\{i\}\) se cumple
$$W_{\{i\},i}(i)=1,\qquad W_{\{i\},i}(k)=0\ (k\ne i),\qquad D_{\{i\},i}=0.$$
Denotemos por \(\operatorname{next}_M(t)\) al siguiente chef vivo después de \(t\) en orden cíclico, con vuelta al inicio cuando haga falta.
Supongamos \(|M|\ge 2\). Si el chef \(t\) elige como objetivo a \(j\in M\setminus\{t\}\), entonces con probabilidad \(p_t\) el juego pasa a
$$\left(M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)\right),$$
y con probabilidad \(1-p_t\) pasa a
$$\left(M,\operatorname{next}_M(t)\right).$$
La rama de fallo es la misma para cualquier objetivo. Por eso el chef \(t\) solo tiene que maximizar el valor de la rama de éxito, es decir
$$W_{M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)}(t).$$
Si varios objetivos dan el mismo valor, la implementación rompe el empate eligiendo la menor distancia cíclica positiva desde \(t\). Así queda fijado un sucesor único para cada estado.
Lo decisivo es que cada posible estado de éxito tiene un superviviente menos. Por tanto, cuando los subconjuntos más pequeños ya están resueltos, la mejor elección de objetivo también queda conocida.
Fijemos un conjunto \(M\) con \(q=|M|\ge 2\), y escribamos sus miembros en orden cíclico como
$$m_0,m_1,\dots,m_{q-1}.$$
Para cada posición \(r\), definimos
$$X_r=\mathbf W_{M,m_r},\qquad Y_r=D_{M,m_r}.$$
Una vez elegido el mejor objetivo del chef \(m_r\), sea \(U_r\) el vector de probabilidades del estado de éxito correspondiente, ya conocido, y sea \(V_r\) la esperanza de platos restantes en ese mismo estado. Entonces un turno satisface
$$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},$$
donde los índices se toman módulo \(q\). La constante \(1\) aparece porque cada turno añade exactamente un plato antes de pasar al siguiente estado.
Definamos
$$A_r=p_{m_r}U_r,\qquad C_r=1+p_{m_r}V_r,\qquad b_r=1-p_{m_r}.$$
Así, las recurrencias quedan
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
Si desplegamos la primera ecuación alrededor de todo el ciclo, obtenemos
$$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.$$
Por tanto,
$$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}.$$
La misma cuenta produce
$$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}.$$
Aquí el producto vacío para \(r=0\) vale \(1\). Como todas las probabilidades de acierto son positivas, \(\prod b_i<1\), así que el denominador no se anula. La fórmula de \(X_0\) es vectorial, pero cada componente sigue exactamente la misma cadena escalar de coeficientes.
Una vez conocidos \(X_0\) y \(Y_0\), los demás estados del mismo subconjunto se recuperan por sustitución hacia atrás:
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
De este modo la dependencia cíclica se resuelve sin invertir matrices generales.
Los subconjuntos con un solo chef son los casos base. Después se procesan los conjuntos vivos en orden de tamaño creciente \(1,2,\dots,n\). Cuando se resuelve un conjunto \(M\), todo estado de éxito \(M\setminus\{j\}\) ya está calculado. Eso significa que la mejor elección de objetivo para cada chef activo ya se conoce, y las fórmulas del Paso 4 pueden aplicarse de inmediato.
Esto es programación dinámica sobre subconjuntos, pero cada estado guarda más que un escalar: almacena un vector completo de probabilidades de victoria y una esperanza adicional.
Este ejemplo es útil porque coincide con uno de los puntos de control numéricos de la implementación. El estado inicial es \((\{1,2,3\},1)\).
Primero resolvemos los estados con dos chefs. Para los chefs \(1\) y \(2\), si mueve el chef \(1\), entonces
$$W_{\{1,2\},1}(1)=\frac{\frac14}{1-\frac34\cdot\frac12}=0.4.$$
Por tanto,
$$W_{\{1,2\},2}(1)=\left(1-\frac12\right)\cdot 0.4=0.2.$$
De forma análoga,
$$W_{\{1,3\},1}(1)=0.25,\qquad W_{\{2,3\},2}(2)=0.5.$$
Ahora fijamos los objetivos óptimos en la máscara de tres chefs. El chef \(1\) prefiere eliminar al chef \(3\), porque entonces la rama de éxito deja el duelo \(\{1,2\}\) con turno del chef \(2\), donde la probabilidad de victoria del chef \(1\) es \(0.2\). En cambio, eliminar al chef \(2\) dejaría al chef \(3\) con el siguiente turno y daría valor \(0\).
El chef \(2\) también prefiere apuntar al chef \(3\), porque la rama de éxito deja \(\{1,2\}\) con turno del chef \(1\), donde la probabilidad final de victoria del chef \(2\) es \(0.6\), superior a la alternativa \(0\).
El chef \(3\) prefiere apuntar al chef \(2\), porque un éxito seguro deja el duelo \(\{1,3\}\) con turno del chef \(1\), y allí la probabilidad de victoria del chef \(3\) es \(0.75\), mayor que el \(0.5\) que obtiene al eliminar al chef \(1\).
Sea ahora \(x_r\) la probabilidad final de victoria del chef \(1\) cuando el jugador actual es el chef \(r\). Las elecciones óptimas producen
$$x_1=\frac14\cdot 0.2+\frac34x_2,$$
$$x_2=\frac12\cdot 0.4+\frac12x_3,$$
$$x_3=1\cdot 0.25.$$
Entonces
$$x_3=0.25,\qquad x_2=0.325,\qquad x_1=0.05+0.75\cdot 0.325=0.29375,$$
que reproduce exactamente el valor de control publicado \(W_3(1)=0.29375\).
Las implementaciones en C++, Python y Java generan primero las probabilidades de habilidad basadas en Fibonacci y agrupan todos los conjuntos vivos por su tamaño. Para cada conjunto vivo enumeran a los chefs supervivientes en orden cíclico. Los estados con un solo superviviente se rellenan directamente como casos base.
Para cada estado no trivial, la implementación prueba todos los objetivos posibles del chef actual. Como cada estado de éxito tiene un superviviente menos, su vector de probabilidades de victoria ya ha sido calculado. Se elige el objetivo cuya rama de éxito da al jugador activo la mayor probabilidad final de ganar, usando la distancia cíclica para romper empates.
Una vez fijados esos mejores objetivos para todo el conjunto vivo, la implementación construye las contribuciones de éxito \(A_r\) y \(C_r\), guarda los factores de fallo \(b_r=1-p_{m_r}\), evalúa las fórmulas cerradas del ciclo y luego recupera todos los estados de turno de esa máscara por sustitución hacia atrás. Se almacenan tanto los vectores completos de probabilidades de victoria como las esperanzas del número de platos restantes.
Al final, el valor requerido por Project Euler es simplemente la esperanza asociada al conjunto completo de chefs cuando el chef \(1\) mueve primero.
Para una máscara con \(m\) chefs vivos, la selección del objetivo cuesta \(O(m^2)\), mientras que construir y propagar los vectores de probabilidades de victoria cuesta \(O(mn)\). Sumando sobre todas las máscaras se obtiene
$$\sum_{m=0}^{n}\binom{n}{m}(m^2+mn)=O(n^2 2^n).$$
Los vectores de probabilidades almacenados dominan el uso de memoria, así que el método exacto también requiere
$$O(n^2 2^n)$$
de memoria. Por eso el solucionador exacto solo es práctico para valores relativamente pequeños de \(n\).
有 \(n\) 位厨师按 \(1,2,\dots,n\) 的循环顺序站立。第 \(k\) 位厨师成功淘汰自己所选目标的概率为
$$p_k=\frac{F_k}{F_{n+1}},\qquad k=1,\dots,n,$$
其中 \(F_1=F_2=1\)。每一回合恰好会产生一道菜。当前行动的厨师会从仍然存活的对手中选择一人进行攻击，然后回合交给当前厨师之后的下一位存活者。如果攻击成功，被选中的目标出局；如果失败，则没有人出局。游戏在只剩一位厨师时结束。
对每一个游戏状态，我们既要知道所有厨师最终获胜概率组成的向量，也要知道从该状态继续下去还会做出多少道菜的期望值。Project Euler 真正要求的是
$$E(n)=D_{\{1,2,\dots,n\},1},$$
也就是全体厨师都还活着且由厨师 \(1\) 先手时的期望做菜次数。
核心思路是对“仍然存活的厨师集合”做子集动态规划。只要较小的存活集合已经求出，较大的状态中每位厨师该攻击谁也就能确定；接下来同一存活集合内部只剩一个环形线性方程组需要求解。
设 \(M\subseteq\{1,\dots,n\}\) 表示当前还活着的厨师集合，\(t\in M\) 表示当前轮到谁行动。定义
$$\mathbf W_{M,t}=\bigl(W_{M,t}(1),\dots,W_{M,t}(n)\bigr),$$
其中 \(W_{M,t}(i)\) 表示从状态 \((M,t)\) 开始游戏时，厨师 \(i\) 最终成为唯一幸存者的概率。再定义
$$D_{M,t}$$
表示从状态 \((M,t)\) 开始还会额外产生多少道菜的期望值。
如果只剩下一位厨师，那么游戏已经结束。于是当 \(M=\{i\}\) 时有
$$W_{\{i\},i}(i)=1,\qquad W_{\{i\},i}(k)=0\ (k\ne i),\qquad D_{\{i\},i}=0.$$
记 \(\operatorname{next}_M(t)\) 为在集合 \(M\) 中按循环顺序位于 \(t\) 之后的下一位存活厨师；如果到达末尾，则回到开头。
现在假设 \(|M|\ge 2\)。如果当前厨师 \(t\) 选择攻击 \(j\in M\setminus\{t\}\)，那么以概率 \(p_t\) 游戏会进入
$$\left(M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)\right),$$
而以概率 \(1-p_t\) 游戏会进入
$$\left(M,\operatorname{next}_M(t)\right).$$
注意失败分支与目标 \(j\) 无关，因为失败时没有人出局。因此当前厨师真正需要最大化的只是成功分支中“自己最终夺冠”的概率，也就是
$$W_{M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)}(t).$$
如果多个目标给出相同结果，程序使用“从当前厨师出发沿循环方向的最小正距离”作为确定性的平局规则。这样每个状态就只有一个明确的最优成功后继。
这一步之所以可行，是因为所有候选成功状态都比当前状态少一名存活者。也就是说，当较小的子集都已经算完以后，较大状态中的目标选择自然就知道了。
固定一个存活集合 \(M\)，设 \(q=|M|\ge 2\)，并把其中成员按循环顺序写成
$$m_0,m_1,\dots,m_{q-1}.$$
对于每个位置 \(r\)，定义
$$X_r=\mathbf W_{M,m_r},\qquad Y_r=D_{M,m_r}.$$
当厨师 \(m_r\) 的最优目标已经确定以后，记对应成功状态中已经算出的获胜概率向量为 \(U_r\)，已经算出的剩余菜品期望为 \(V_r\)。那么一次行动就满足
$$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},$$
这里下标按模 \(q\) 理解。第二个方程中的常数 \(1\) 正是“每一回合一定会多做一道菜”这一规则带来的。
令
$$A_r=p_{m_r}U_r,\qquad C_r=1+p_{m_r}V_r,\qquad b_r=1-p_{m_r}.$$
那么递推可写成
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
把第一个方程沿着整个环展开一圈，可以得到
$$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.$$
因此
$$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}.$$
完全相同的代数操作给出
$$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}.$$
这里约定 \(r=0\) 时空积等于 \(1\)。由于每个 \(p_k\) 都是正数，所以 \(\prod b_i<1\)，分母不会为零。虽然 \(X_0\) 是向量，但它的每一个分量都遵循同一条标量系数链。
一旦 \(X_0\) 与 \(Y_0\) 求出，同一存活集合中其他“当前行动者不同”的状态都可以通过回代得到：
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
这样就把环形依赖化成了一个显式分母，而不需要做通用矩阵求逆。
只有一名厨师存活的所有状态都是基本情形。之后按照存活人数 \(1,2,\dots,n\) 递增的顺序处理所有集合。当处理某个集合 \(M\) 时，每个成功状态 \(M\setminus\{j\}\) 都已经算过了，因此每位当前行动者的最优目标也已经明确，步骤 4 的闭式公式便可以直接应用。
这本质上是子集动态规划，只不过每个状态保存的不是一个单独的标量，而是一个完整的获胜概率向量外加一个期望值。
这个例子很适合展示方法，因为它正是程序使用的数值检查点之一。起始状态是 \((\{1,2,3\},1)\)。
先解两人状态。对厨师 \(1\) 和厨师 \(2\) 来说，如果当前轮到厨师 \(1\)，则
$$W_{\{1,2\},1}(1)=\frac{\frac14}{1-\frac34\cdot\frac12}=0.4.$$
于是
$$W_{\{1,2\},2}(1)=\left(1-\frac12\right)\cdot 0.4=0.2.$$
同理可以得到
$$W_{\{1,3\},1}(1)=0.25,\qquad W_{\{2,3\},2}(2)=0.5.$$
接下来决定三人状态中的最优攻击目标。厨师 \(1\) 会选择攻击厨师 \(3\)，因为一旦成功，留下的是由厨师 \(2\) 先手的 \(\{1,2\}\) 对决，此时厨师 \(1\) 的获胜概率是 \(0.2\)；如果改为淘汰厨师 \(2\)，则下一手轮到厨师 \(3\)，成功分支对厨师 \(1\) 的价值变成 \(0\)。
厨师 \(2\) 同样更愿意攻击厨师 \(3\)，因为成功后留下的是由厨师 \(1\) 先手的 \(\{1,2\}\) 对决，厨师 \(2\) 的最终胜率为 \(0.6\)，优于另一种选择给出的 \(0\)。
厨师 \(3\) 则会攻击厨师 \(2\)，因为它一旦成功，就会留下由厨师 \(1\) 先手的 \(\{1,3\}\) 对决，在那里厨师 \(3\) 的胜率是 \(0.75\)，大于淘汰厨师 \(1\) 时只能得到的 \(0.5\)。
现在令 \(x_r\) 表示当前行动者为厨师 \(r\) 时，厨师 \(1\) 最终获胜的概率。根据上面的最优选择，有
$$x_1=\frac14\cdot 0.2+\frac34x_2,$$
$$x_2=\frac12\cdot 0.4+\frac12x_3,$$
$$x_3=1\cdot 0.25.$$
因此
$$x_3=0.25,\qquad x_2=0.325,\qquad x_1=0.05+0.75\cdot 0.325=0.29375,$$
这就精确复现了检查点数值 \(W_3(1)=0.29375\)。
C++、Python 和 Java 实现首先生成基于 Fibonacci 比值的能力概率，然后按存活人数对所有状态分组。对于每个存活集合，程序按循环顺序列出所有幸存厨师。只有一名幸存者的状态可以直接作为基本情形写入。
对于每个非平凡状态，程序枚举当前厨师可以攻击的所有目标。由于每个成功状态都少一名存活者，对应的获胜概率向量早已在前面的子问题中算出。程序选择那个能让当前厨师在成功分支中获得最大最终胜率的目标；若出现并列，则按循环距离规则打破平局。
当某个存活集合中所有行动者的最优目标都确定后，程序构造成功贡献 \(A_r\) 与 \(C_r\)，记录失败系数 \(b_r=1-p_{m_r}\)，利用上面的闭式环形公式求出该集合中第一个 turn-state，再通过回代恢复同一集合中的其他 turn-state。程序会同时保存完整的获胜概率向量和剩余菜品数量的期望。
最终答案就是全体厨师存活且由厨师 \(1\) 先手时所对应的那个期望值。
对于一个含有 \(m\) 位存活厨师的集合，选择最优目标需要 \(O(m^2)\)，而构造并传播获胜概率向量需要 \(O(mn)\)。对所有集合求和后得到
$$\sum_{m=0}^{n}\binom{n}{m}(m^2+mn)=O(n^2 2^n).$$
内存主要消耗在保存获胜概率向量上，因此精确算法同样需要
$$O(n^2 2^n)$$
级别的空间。这也解释了为什么这种精确求解只适用于较小的 \(n\)。
Есть \(n\) шефов, расположенных в циклическом порядке \(1,2,\dots,n\). Вероятность того, что шеф \(k\) успешно выбьет выбранную цель, равна
$$p_k=\frac{F_k}{F_{n+1}},\qquad k=1,\dots,n,$$
где \(F_1=F_2=1\). Каждый ход создаёт ровно одно блюдо. Активный шеф выбирает одного живого соперника, пытается его устранить, а затем ход переходит к следующему живому шефу после текущего. При успехе выбранная цель выбывает; при неудаче никто не выбывает. Игра заканчивается, когда остаётся только один шеф.
Для каждого состояния игры нужны и полный вектор итоговых вероятностей победы, и математическое ожидание числа оставшихся блюд. Искомая величина Project Euler равна
$$E(n)=D_{\{1,2,\dots,n\},1},$$
то есть ожидаемому числу блюд из полного стартового состояния, когда первым ходит шеф \(1\).
Главная идея состоит в динамическом программировании по множествам живых шефов. Как только решены меньшие множества, оптимальная цель в любом большем состоянии тоже уже определяется, а оставшиеся уравнения образуют одну циклическую линейную систему.
Пусть \(M\subseteq\{1,\dots,n\}\) — множество живых шефов, а \(t\in M\) — шеф, чей сейчас ход. Определим
$$\mathbf W_{M,t}=\bigl(W_{M,t}(1),\dots,W_{M,t}(n)\bigr),$$
где \(W_{M,t}(i)\) — вероятность того, что шеф \(i\) окажется единственным победителем, если игра стартует из состояния \((M,t)\). Кроме того, введём
$$D_{M,t}$$
как математическое ожидание числа дополнительных блюд, начиная из состояния \((M,t)\).
Если жив только один шеф, игра уже завершена. Поэтому для \(M=\{i\}\) имеем
$$W_{\{i\},i}(i)=1,\qquad W_{\{i\},i}(k)=0\ (k\ne i),\qquad D_{\{i\},i}=0.$$
Обозначим через \(\operatorname{next}_M(t)\) следующего живого шефа после \(t\) в циклическом порядке с переходом через конец при необходимости.
Пусть \(|M|\ge 2\). Если шеф \(t\) выбирает цель \(j\in M\setminus\{t\}\), то с вероятностью \(p_t\) игра переходит в состояние
$$\left(M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)\right),$$
а с вероятностью \(1-p_t\) — в состояние
$$\left(M,\operatorname{next}_M(t)\right).$$
Ветка неудачи одинакова для любой цели. Следовательно, шефу \(t\) нужно максимизировать только значение успешной ветви, то есть
$$W_{M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)}(t).$$
Если несколько целей дают одинаковый результат, реализация использует детерминированное правило: выбирается цель с наименьшим положительным циклическим расстоянием от \(t\). Это делает успешного наследника однозначным.
Ключевой факт: каждый возможный успешный переход уменьшает число живых на единицу. Значит, когда меньшие подмножества уже решены, оптимальный выбор цели тоже уже известен.
Зафиксируем множество \(M\) размера \(q=|M|\ge 2\) и выпишем его элементы в циклическом порядке:
$$m_0,m_1,\dots,m_{q-1}.$$
Для каждой позиции \(r\) положим
$$X_r=\mathbf W_{M,m_r},\qquad Y_r=D_{M,m_r}.$$
После того как оптимальная цель для шефа \(m_r\) выбрана, обозначим через \(U_r\) уже известный вектор вероятностей победы в соответствующем состоянии успеха, а через \(V_r\) — уже известное математическое ожидание числа оставшихся блюд там. Тогда один ход удовлетворяет соотношениям
$$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},$$
где индексы понимаются по модулю \(q\). Константа \(1\) во втором уравнении отражает то, что каждый ход всегда добавляет одно блюдо.
Введём обозначения
$$A_r=p_{m_r}U_r,\qquad C_r=1+p_{m_r}V_r,\qquad b_r=1-p_{m_r}.$$
Тогда рекурсии переписываются как
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
Если развернуть первое уравнение по всему циклу, получим
$$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.$$
Следовательно,
$$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}.$$
Та же самая алгебра даёт
$$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}.$$
Здесь пустое произведение при \(r=0\) считается равным \(1\). Поскольку все вероятности успеха положительны, имеем \(\prod b_i<1\), так что знаменатель не обращается в ноль. Формула для \(X_0\) векторная, но каждый компонент подчиняется одной и той же скалярной цепочке коэффициентов.
После нахождения \(X_0\) и \(Y_0\) остальные состояния для той же маски восстанавливаются обратной подстановкой:
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
Тем самым циклическая зависимость снимается без обращения общей матрицы.
Все маски с одним живым шефом являются базовыми случаями. После этого множества живых шефов обрабатываются в порядке возрастания размера \(1,2,\dots,n\). Когда рассматривается множество \(M\), каждое состояние успеха \(M\setminus\{j\}\) уже вычислено. Значит, оптимальная цель каждого активного шефа уже известна, и формулы из шага 4 можно применять сразу.
Это стандартное DP по подмножествам, но в каждом состоянии хранится не один скаляр, а целый вектор вероятностей победы плюс одно математическое ожидание.
Этот пример удобен тем, что он совпадает с одним из численных контрольных тестов реализации. Стартовое состояние равно \((\{1,2,3\},1)\).
Сначала решим состояния с двумя шефами. Для шефов \(1\) и \(2\), если ходит шеф \(1\), то
$$W_{\{1,2\},1}(1)=\frac{\frac14}{1-\frac34\cdot\frac12}=0.4.$$
Отсюда следует
$$W_{\{1,2\},2}(1)=\left(1-\frac12\right)\cdot 0.4=0.2.$$
Аналогично получаем
$$W_{\{1,3\},1}(1)=0.25,\qquad W_{\{2,3\},2}(2)=0.5.$$
Теперь определим оптимальные цели в маске из трёх шефов. Шеф \(1\) предпочитает атаковать шефа \(3\), потому что тогда при успехе остаётся дуэль \(\{1,2\}\), в которой первым ходит шеф \(2\), а вероятность победы шефа \(1\) равна \(0.2\). Если же убрать шефа \(2\), следующий ход достанется шефу \(3\), и ценность успешной ветви для шефа \(1\) будет равна \(0\).
Шеф \(2\) тоже предпочитает целиться в шефа \(3\), потому что ветвь успеха оставляет дуэль \(\{1,2\}\) с первым ходом шефа \(1\), где итоговая вероятность победы шефа \(2\) равна \(0.6\), что лучше альтернативного \(0\).
Шеф \(3\) выбирает шефа \(2\), потому что после гарантированного успеха остаётся дуэль \(\{1,3\}\) с первым ходом шефа \(1\), а вероятность победы шефа \(3\) там равна \(0.75\), что больше, чем \(0.5\) при устранении шефа \(1\).
Обозначим через \(x_r\) вероятность итоговой победы шефа \(1\), если текущий игрок — шеф \(r\). Тогда из оптимальных выборов следует система
$$x_1=\frac14\cdot 0.2+\frac34x_2,$$
$$x_2=\frac12\cdot 0.4+\frac12x_3,$$
$$x_3=1\cdot 0.25.$$
Следовательно,
$$x_3=0.25,\qquad x_2=0.325,\qquad x_1=0.05+0.75\cdot 0.325=0.29375,$$
что в точности воспроизводит контрольное значение \(W_3(1)=0.29375\).
Реализации на C++, Python и Java сначала строят вероятности навыков на основе отношений Fibonacci, а затем группируют все множества живых шефов по их размеру. Для каждого такого множества живые шефы перечисляются в циклическом порядке. Состояния с одним выжившим заполняются сразу как базовые.
Для каждого нетривиального состояния реализация перебирает все возможные цели текущего шефа. Поскольку каждое состояние успеха имеет на одного выжившего меньше, его вектор вероятностей победы уже был вычислен раньше. Выбирается та цель, чья успешная ветвь даёт активному игроку максимальную итоговую вероятность победы; при равенстве используется правило циклического расстояния.
Когда оптимальные цели зафиксированы для всего множества живых, реализация строит вклады успеха \(A_r\) и \(C_r\), сохраняет коэффициенты неудачи \(b_r=1-p_{m_r}\), вычисляет замкнутые формулы для цикла и затем обратной подстановкой восстанавливает все turn-state для этой маски. Сохраняются и полные векторы вероятностей победы, и ожидания числа оставшихся блюд.
В конце искомое значение Project Euler — это просто ожидание для полной маски, когда первым ходит шеф \(1\).
Для маски с \(m\) живыми шефами выбор цели стоит \(O(m^2)\), а построение и распространение векторов вероятностей победы стоит \(O(mn)\). Сумма по всем маскам даёт
$$\sum_{m=0}^{n}\binom{n}{m}(m^2+mn)=O(n^2 2^n).$$
Основной объём памяти занимают сохранённые векторы вероятностей победы, поэтому точный метод требует также
$$O(n^2 2^n)$$
памяти. Именно поэтому точное решение practically применимо только для сравнительно небольших \(n\).
يوجد \(n\) من الطهاة مرتبين ترتيبًا دائريًا \(1,2,\dots,n\). احتمال أن ينجح الشيف \(k\) في إقصاء الهدف الذي يختاره هو
$$p_k=\frac{F_k}{F_{n+1}},\qquad k=1,\dots,n,$$
حيث \(F_1=F_2=1\). كل دور ينتج طبقًا واحدًا بالضبط. يختار الشيف صاحب الدور خصمًا ما زال حيًا، ويحاول إقصاءه، ثم ينتقل الدور إلى الشيف الحي التالي بعد الشيف الحالي. عند النجاح يُزال الهدف المختار، وعند الفشل لا يُزال أحد. وتنتهي اللعبة عندما يبقى شيف واحد فقط.
في كل حالة من حالات اللعبة نريد شيئين: متجه احتمالات الفوز النهائي لكل الطهاة، والمتوسط المتوقع لعدد الأطباق المتبقية. والكمية المطلوبة في Project Euler هي
$$E(n)=D_{\{1,2,\dots,n\},1},$$
أي العدد المتوقع للأطباق من الحالة الكاملة عندما يبدأ الشيف \(1\) اللعب.
الفكرة الأساسية هي استخدام برمجة ديناميكية على مجموعات الطهاة الأحياء. ما إن نحل المجموعات الأصغر، تصبح أفضل ضربة ممكنة في الحالات الأكبر معلومة أيضًا، وما يتبقى داخل كل مجموعة أحياء هو نظام خطي دوري واحد.
لتكن \(M\subseteq\{1,\dots,n\}\) مجموعة الطهاة الأحياء، وليكن \(t\in M\) هو الشيف الذي عليه الدور. نعرّف
$$\mathbf W_{M,t}=\bigl(W_{M,t}(1),\dots,W_{M,t}(n)\bigr),$$
حيث تمثل \(W_{M,t}(i)\) احتمال أن يكون الشيف \(i\) هو الفائز النهائي إذا بدأت اللعبة من الحالة \((M,t)\). ونعرّف أيضًا
$$D_{M,t}$$
بوصفه العدد المتوقع للأطباق الإضافية ابتداءً من الحالة \((M,t)\).
إذا كان هناك شيف واحد فقط على قيد الحياة فاللعبة منتهية أصلًا. لذلك عندما \(M=\{i\}\) يكون
$$W_{\{i\},i}(i)=1,\qquad W_{\{i\},i}(k)=0\ (k\ne i),\qquad D_{\{i\},i}=0.$$
ولنرمز بـ \(\operatorname{next}_M(t)\) إلى الشيف الحي التالي بعد \(t\) في الترتيب الدائري مع الالتفاف إلى البداية عند الحاجة.
افترض أن \(|M|\ge 2\). إذا اختار الشيف \(t\) الهدف \(j\in M\setminus\{t\}\)، فإن اللعبة تنتقل باحتمال \(p_t\) إلى الحالة
$$\left(M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)\right),$$
وتنتقل باحتمال \(1-p_t\) إلى الحالة
$$\left(M,\operatorname{next}_M(t)\right).$$
فرع الفشل متماثل مهما كان الهدف المختار. لذلك يكفي أن يعظّم الشيف \(t\) قيمة النجاح الخاصة به، أي
$$W_{M\setminus\{j\},\operatorname{next}_{M\setminus\{j\}}(t)}(t).$$
إذا أعطت عدة أهداف القيمة نفسها، فالتنفيذ يستخدم أصغر مسافة دائرية موجبة انطلاقًا من \(t\) كقاعدة حسم ثابتة. وبهذا يصبح لكل حالة تابع نجاح محدد وحيد.
النقطة الحاسمة أن كل حالة نجاح محتملة تحتوي شيفًا حيًا أقل من الحالة الحالية. ولهذا، ما إن تُحل المجموعات الأصغر حتى تصبح أفضل ضربة في الحالة الحالية معروفة.
لنثبت الآن مجموعة أحياء \(M\) بحيث \(q=|M|\ge 2\)، ولنكتب عناصرها وفق الترتيب الدائري بالشكل
$$m_0,m_1,\dots,m_{q-1}.$$
ولكل موضع \(r\) نضع
$$X_r=\mathbf W_{M,m_r},\qquad Y_r=D_{M,m_r}.$$
بعد تحديد الهدف الأمثل للشيف \(m_r\)، نرمز بـ \(U_r\) إلى متجه احتمالات الفوز في حالة النجاح الموافقة، وهو متجه معلوم مسبقًا، ونرمز بـ \(V_r\) إلى العدد المتوقع للأطباق المتبقية في تلك الحالة. عندئذ يحقق كل دور العلاقتين
$$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},$$
حيث تُؤخذ المؤشرات بترديد \(q\). والعدد \(1\) في المعادلة الثانية يظهر لأن كل دور ينتج طبقًا جديدًا قبل الانتقال إلى الحالة التالية.
لنعرّف
$$A_r=p_{m_r}U_r,\qquad C_r=1+p_{m_r}V_r,\qquad b_r=1-p_{m_r}.$$
فتصبح العلاقات
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
وبفك المعادلة الأولى دورةً كاملة نحصل على
$$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.$$
ومن ثم
$$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}.$$
والحساب الجبري نفسه يعطي
$$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}.$$
هنا يُعتبر حاصل الضرب الفارغ عندما \(r=0\) مساويًا لـ \(1\). وبما أن جميع احتمالات النجاح موجبة، فإن \(\prod b_i<1\)، ولهذا لا ينعدم المقام. وصيغة \(X_0\) متجهية، لكن كل مركبة فيها تتبع السلسلة العددية نفسها من المعاملات.
بعد معرفة \(X_0\) و\(Y_0\)، يمكن استرجاع بقية حالات الدور ضمن المجموعة نفسها بالرجوع الخلفي:
$$X_r=A_r+b_rX_{r+1},\qquad Y_r=C_r+b_rY_{r+1}.$$
وهكذا تُحل العلاقة الدورية من دون حاجة إلى قلب مصفوفة عامة.
كل حالة لا يبقى فيها إلا شيف واحد هي حالة أساس. بعد ذلك تُعالَج مجموعات الأحياء حسب أحجامها تصاعديًا \(1,2,\dots,n\). وعندما نصل إلى مجموعة \(M\)، تكون كل حالة نجاح من الشكل \(M\setminus\{j\}\) قد حُلّت مسبقًا. لذلك تصبح أفضل ضربة لكل شيف نشط معلومة مباشرة، ويمكن تطبيق صيغ الخطوة الرابعة فورًا.
هذه برمجة ديناميكية على المجموعات الجزئية، لكن كل حالة تخزن أكثر من قيمة واحدة: فهي تحتفظ بمتجه كامل لاحتمالات الفوز بالإضافة إلى قيمة توقع واحدة.
هذا المثال مفيد لأنه يطابق أحد الاختبارات العددية التي يستخدمها التنفيذ. حالة البداية هي \((\{1,2,3\},1)\).
نبدأ بحل حالات الشيفين. بالنسبة إلى الشيفين \(1\) و\(2\)، إذا كان الدور على الشيف \(1\) فإن
$$W_{\{1,2\},1}(1)=\frac{\frac14}{1-\frac34\cdot\frac12}=0.4.$$
ومن ثم
$$W_{\{1,2\},2}(1)=\left(1-\frac12\right)\cdot 0.4=0.2.$$
وبالمثل نحصل على
$$W_{\{1,3\},1}(1)=0.25,\qquad W_{\{2,3\},2}(2)=0.5.$$
نحدد الآن الأهداف المثلى في حالة الطهاة الثلاثة. يفضّل الشيف \(1\) مهاجمة الشيف \(3\)، لأن النجاح يترك مبارزة \(\{1,2\}\) مع كون الدور التالي للشيف \(2\)، وعندها يكون احتمال فوز الشيف \(1\) مساويًا لـ \(0.2\). أما إزالة الشيف \(2\) فتجعل الشيف \(3\) هو التالي في اللعب وتعطي للشيف \(1\) قيمة نجاح تساوي \(0\).
ويفضّل الشيف \(2\) كذلك استهداف الشيف \(3\)، لأن فرع النجاح يترك مبارزة \(\{1,2\}\) مع الشيف \(1\) لاعبًا تاليًا، وفي هذه الحالة يكون احتمال فوز الشيف \(2\) النهائي \(0.6\)، وهو أفضل من البديل \(0\).
أما الشيف \(3\) فيختار الشيف \(2\)، لأن النجاح المؤكد يترك مبارزة \(\{1,3\}\) مع بدء الشيف \(1\)، وهناك يكون احتمال فوز الشيف \(3\) مساويًا لـ \(0.75\)، وهو أكبر من \(0.5\) التي يحصل عليها إذا أزال الشيف \(1\).
لنرمز الآن بـ \(x_r\) إلى احتمال فوز الشيف \(1\) في النهاية عندما يكون اللاعب الحالي هو الشيف \(r\). عندئذ تعطي الأهداف المثلى
$$x_1=\frac14\cdot 0.2+\frac34x_2,$$
$$x_2=\frac12\cdot 0.4+\frac12x_3,$$
$$x_3=1\cdot 0.25.$$
وبالتالي
$$x_3=0.25,\qquad x_2=0.325,\qquad x_1=0.05+0.75\cdot 0.325=0.29375,$$
وهو تمامًا مقدار نقطة التحقق المنشورة \(W_3(1)=0.29375\).
تبدأ تطبيقات C++ وPython وJava بتوليد احتمالات المهارة المبنية على نسب Fibonacci، ثم تجمع جميع مجموعات الأحياء بحسب عدد عناصرها. ولكل مجموعة تُسرد أسماء الطهاة الأحياء وفق الترتيب الدائري. أما الحالات التي لا يبقى فيها إلا ناجٍ واحد فتُملأ مباشرةً كحالات أساس.
في كل حالة غير تافهة، يجرّب التنفيذ كل هدف ممكن للشيف الحالي. وبما أن كل حالة نجاح تحتوي شيفًا حيًا أقل، فإن متجه احتمالات الفوز الخاص بها يكون قد حُسب بالفعل. ثم يُختار الهدف الذي يمنح الشيف النشط أكبر احتمال نهائي للفوز في فرع النجاح، مع استخدام قاعدة المسافة الدائرية لحسم التعادل.
بعد تثبيت هذه الأهداف المثلى على مستوى مجموعة الأحياء كلها، يبني التنفيذ مساهمات النجاح \(A_r\) و\(C_r\)، ويخزن معاملات الفشل \(b_r=1-p_{m_r}\)، ويطبق الصيغ المغلقة للدورة، ثم يستخدم الرجوع الخلفي لاستعادة جميع حالات الدور التابعة للقناع نفسه. ويجري تخزين كل من متجهات احتمالات الفوز الكاملة وتوقعات عدد الأطباق المتبقية.
وفي النهاية تكون قيمة Project Euler المطلوبة هي قيمة التوقع المرتبطة بالمجموعة الكاملة عندما يبدأ الشيف \(1\) اللعب.
إذا احتوى القناع على \(m\) طهاة أحياء، فإن اختيار الهدف الأمثل يكلف \(O(m^2)\)، بينما يكلف بناء متجهات احتمالات الفوز ونشرها \(O(mn)\). وبجمع ذلك على جميع الأقنعة نحصل على
$$\sum_{m=0}^{n}\binom{n}{m}(m^2+mn)=O(n^2 2^n).$$
وتسيطر متجهات احتمالات الفوز المخزنة على استهلاك الذاكرة، لذلك تحتاج الطريقة الدقيقة أيضًا إلى
$$O(n^2 2^n)$$
من الذاكرة. ولهذا يبقى الحل الدقيق عمليًا فقط عندما تكون \(n\) صغيرة نسبيًا.