At a state with \(u\) unfair coins and \(f\) fair coins still in the box, one of the \(u+f\) remaining coins is selected uniformly at random. Therefore the current coin is unfair with prior probability
$$p=\frac{u}{u+f}.$$
Before making the final classification, the player may toss that same coin as many times as desired. Every toss costs \(1\) point. The final classification pays \(+20\) if the type is identified correctly and \(-50\) if it is identified incorrectly. After that reveal, the coin is removed and the next round starts.
The task is to maximize the expected total score when the box initially contains \(N\) unfair and \(N\) fair coins. The solution naturally splits into two layers: an optimal stopping problem for a single selected coin, and a second dynamic program for the changing composition of the box.
Let \(E(p)\) be the optimal expected score contributed by the current coin when the prior probability of being unfair is \(p\). Let \(B(u,f)\) be the optimal expected total score from a box that still contains \(u\) unfair and \(f\) fair coins. The implementations first compute \(E(p)\) and then plug it into the recurrence for \(B(u,f)\).
If we stop immediately, the best action is to guess the more likely type. Guessing “unfair” gives expected value
$$20p-50(1-p)=70p-50,$$
while guessing “fair” gives
$$20(1-p)-50p=20-70p=70(1-p)-50.$$
Hence the best immediate value is
$$E_{\mathrm{stop}}(p)=\max\{70p-50,\;70(1-p)-50\}=70\max\{p,1-p\}-50.$$
When \(p\) is close to \(1/2\), this quantity is negative, so blind guessing is worse than collecting evidence from tosses.
If we toss the current coin once, the probability of a head is
$$q_H=\frac{3}{4}p+\frac{1}{2}(1-p)=\frac{1}{2}+\frac{p}{4},$$
and the probability of a tail is
$$q_T=1-q_H=\frac{1}{2}-\frac{p}{4}.$$
Bayes' rule turns these observations into posterior probabilities
$$p_H=\frac{\frac{3}{4}p}{q_H}=\frac{3p}{2+p},\qquad p_T=\frac{\frac{1}{4}p}{q_T}=\frac{p}{2-p}.$$
So if we continue for one more toss, the expected value is
$$E_{\mathrm{cont}}(p)=-1+q_H E(p_H)+q_T E(p_T).$$
The optimal single-coin value is therefore
$$E(p)=\max\{E_{\mathrm{stop}}(p),\;E_{\mathrm{cont}}(p)\}.$$
This recursion is exact, but it is infinite-horizon. The implementations turn it into a numerically stable finite-horizon dynamic program.
Let the prior odds be
$$O_0=\frac{p_0}{1-p_0}.$$
A head multiplies the odds by
$$\frac{3/4}{1/2}=\frac{3}{2},$$
while a tail multiplies them by
$$\frac{1/4}{1/2}=\frac{1}{2}.$$
After \(n\) tosses with \(h\) heads and \(n-h\) tails, the odds are
$$O_{n,h}=O_0\left(\frac{3}{2}\right)^h\left(\frac{1}{2}\right)^{n-h}=O_0\,3^h\,2^{-n}.$$
Taking logarithms yields
$$\log O_{n,h}=\log O_0-n\log 2+h\log 3.$$
Therefore the posterior depends only on the pair \((n,h)\), not on the exact order of the tosses. Recovering the posterior from the odds uses
$$p_{n,h}=\frac{O_{n,h}}{1+O_{n,h}}.$$
This state compression is the key reason the single-coin problem can be solved with a triangular dynamic-programming table.
The implementations use a depth cap \(D=220\). At depth \(D\), they force the process to stop and use the terminal value
$$E_{D,h}=E_{\mathrm{stop}}(p_{D,h}).$$
Then they sweep backward through the triangle with
$$E_{n,h}=\max\left\{E_{\mathrm{stop}}(p_{n,h}),\;-1+q_{n,h}E_{n+1,h+1}+(1-q_{n,h})E_{n+1,h}\right\},$$
where
$$q_{n,h}=\frac{1}{2}+\frac{p_{n,h}}{4}.$$
This is a standard optimal stopping recursion: at every posterior state, compare the payoff of guessing now with the payoff of paying one more point for more information.
The depth cap is effective because extra tosses always cost \(1\), while repeated evidence pushes the posterior probability rapidly toward \(0\) or \(1\), making immediate stopping optimal after sufficiently many observations.
Now return to the box with \(u\) unfair and \(f\) fair coins remaining. The selected coin is unfair with probability
$$p=\frac{u}{u+f}.$$
The current round contributes \(E(p)\) in expectation. After the coin is eventually revealed and removed, the future state is \((u-1,f)\) if the coin was unfair and \((u,f-1)\) if it was fair. Therefore
$$B(u,f)=\frac{u}{u+f}B(u-1,f)+\frac{f}{u+f}B(u,f-1)+E\left(\frac{u}{u+f}\right).$$
The boundary states are immediate:
$$B(u,0)=20u,\qquad B(0,f)=20f,$$
because once only one type remains, every remaining classification is certain and no tosses are useful. The required answer is
$$S(N)=B(N,N).$$
With one unfair coin and one fair coin, the first selected coin has prior probability
$$p_0=\frac{1}{2}.$$
Immediate stopping gives
$$E_{\mathrm{stop}}\left(\frac{1}{2}\right)=70\cdot\frac{1}{2}-50=-15,$$
so tossing is essential.
After one head, the posterior becomes
$$p_H=\frac{3(1/2)}{2+1/2}=\frac{3}{5},$$
and after one tail it becomes
$$p_T=\frac{1/2}{2-1/2}=\frac{1}{3}.$$
Stopping after exactly one toss is still unprofitable, because the immediate values are \(-8\) and \(-10/3\). But stronger evidence quickly changes the decision. After three consecutive heads, the odds are \(27/8\), so
$$p=\frac{27}{35},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{27}{35}-50=4.$$
After two consecutive tails, the odds are \(1/4\), so
$$p=\frac{1}{5},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{4}{5}-50=6.$$
The backward dynamic program decides exactly where that stop/continue boundary lies. For the starting prior \(1/2\), it yields
$$E\left(\frac{1}{2}\right)\approx 0.558591.$$
The other coin then becomes known with certainty and contributes \(20\), so
$$S(1)=\frac{1}{2}\cdot 20+\frac{1}{2}\cdot 20+0.558591=20.558591,$$
which matches the numerical checkpoint used by the implementation.
The C++, Python, and Java implementations first solve the single-coin problem for every prior of the form \(u/(u+f)\) with \(1\le u,f\le N\). For each prior they build the last row of the depth-\(220\) triangle from immediate-stop values, then sweep backward one row at a time until they reach the starting state. The computation is performed in log-odds form so that repeated Bayesian updates do not overflow or underflow numerically.
When the log-odds become larger than \(50\) or smaller than \(-50\), the posterior is treated as numerically indistinguishable from \(1\) or \(0\). That avoids expensive exponentials in states where the decision is already effectively certain. The single-coin values are stored in a two-dimensional table indexed by the remaining numbers of unfair and fair coins.
After that precomputation, the implementation fills a second table for the box recursion. The first row and first column hold the certainty boundaries \(20u\) and \(20f\). Every interior cell applies the weighted transition to the two possible next box states and adds the optimal expected value of the current coin. The final cell corresponding to \((N,N)\) is printed with six digits after the decimal point.
Let \(D\) be the depth cap for the single-coin backward induction. One evaluation of \(E(p)\) fills a triangular table with
$$1+2+\cdots+(D+1)=O(D^2)$$
states, so it costs \(O(D^2)\) time. The implementations only keep one row of that triangle at a time, so the extra memory for the single-coin stage is \(O(D)\).
This evaluation is repeated for every pair \((u,f)\) with \(1\le u,f\le N\), which gives \(O(N^2D^2)\) time for the single-coin precomputation. The outer box dynamic program adds only \(O(N^2)\) time and stores two \((N+1)\times(N+1)\) tables of floating-point values.
Therefore the full method uses
$$O(N^2D^2)\text{ time},\qquad O(N^2+D)\text{ memory}.$$
For the actual parameters \(N=50\) and \(D=220\), this is easily practical.
In einem Zustand mit \(u\) unfairen und \(f\) fairen Münzen in der Box wird eine der \(u+f\) verbleibenden Münzen gleichverteilt ausgewählt. Damit ist die aktuelle Münze mit Prior-Wahrscheinlichkeit
$$p=\frac{u}{u+f}$$
unfair. Bevor der endgültige Typ geraten wird, darf genau diese Münze beliebig oft geworfen werden. Jeder Wurf kostet \(1\) Punkt. Die Endentscheidung bringt \(+20\) bei richtiger Klassifikation und \(-50\) bei falscher Klassifikation. Danach wird die Münze entfernt und die nächste Runde beginnt.
Gesucht ist der maximale Erwartungswert der Gesamtsumme, wenn anfangs \(N\) unfaire und \(N\) faire Münzen vorhanden sind. Die Lösung zerfällt in zwei Ebenen: ein Optimal-Stopping-Problem für eine einzelne ausgewählte Münze und eine zweite dynamische Programmierung für die sich verändernde Zusammensetzung der Box.
Sei \(E(p)\) der optimale erwartete Beitrag der aktuellen Münze, wenn ihre Prior-Wahrscheinlichkeit für „unfair“ gleich \(p\) ist. Sei \(B(u,f)\) der optimale erwartete Gesamtwert für eine Box mit \(u\) unfairen und \(f\) fairen Münzen. Zuerst wird \(E(p)\) berechnet, anschließend wird dieser Wert in die Rekursion für \(B(u,f)\) eingesetzt.
Wenn wir sofort stoppen, sollten wir den wahrscheinlicheren Typ raten. Die Erwartung beim Tipp „unfair“ ist
$$20p-50(1-p)=70p-50,$$
und beim Tipp „fair“ ist sie
$$20(1-p)-50p=20-70p=70(1-p)-50.$$
Also gilt für den besten Sofortwert
$$E_{\mathrm{stop}}(p)=\max\{70p-50,\;70(1-p)-50\}=70\max\{p,1-p\}-50.$$
Liegt \(p\) nahe bei \(1/2\), ist dieser Wert negativ. Reines Raten ist dann schlechter als zusätzliche Information durch Würfe.
Bei einem weiteren Wurf ist die Wahrscheinlichkeit für Kopf
$$q_H=\frac{3}{4}p+\frac{1}{2}(1-p)=\frac{1}{2}+\frac{p}{4},$$
und für Zahl
$$q_T=1-q_H=\frac{1}{2}-\frac{p}{4}.$$
Mit Bayes erhält man die Posterior-Wahrscheinlichkeiten
$$p_H=\frac{\frac{3}{4}p}{q_H}=\frac{3p}{2+p},\qquad p_T=\frac{\frac{1}{4}p}{q_T}=\frac{p}{2-p}.$$
Der Erwartungswert eines weiteren Wurfs ist daher
$$E_{\mathrm{cont}}(p)=-1+q_H E(p_H)+q_T E(p_T).$$
Somit ist der optimale Einzelmünzenwert
$$E(p)=\max\{E_{\mathrm{stop}}(p),\;E_{\mathrm{cont}}(p)\}.$$
Diese Gleichung ist exakt, hat aber unendlichen Horizont. Die Implementierungen lösen sie numerisch über eine endliche Rückwärts-DP.
Definiere die Prior-Odds durch
$$O_0=\frac{p_0}{1-p_0}.$$
Ein Kopf multipliziert diese Odds mit
$$\frac{3/4}{1/2}=\frac{3}{2},$$
eine Zahl mit
$$\frac{1/4}{1/2}=\frac{1}{2}.$$
Nach \(n\) Würfen mit \(h\) Köpfen und \(n-h\) Zahlen gilt daher
$$O_{n,h}=O_0\left(\frac{3}{2}\right)^h\left(\frac{1}{2}\right)^{n-h}=O_0\,3^h\,2^{-n}.$$
Logarithmieren liefert
$$\log O_{n,h}=\log O_0-n\log 2+h\log 3.$$
Der Posterior hängt also nur vom Paar \((n,h)\) ab, nicht von der Reihenfolge der Beobachtungen. Aus den Odds folgt
$$p_{n,h}=\frac{O_{n,h}}{1+O_{n,h}}.$$
Genau diese Kompression macht die Einzelmünzen-DP auf einem Dreiecksgitter möglich.
Die Implementierungen verwenden eine Tiefengrenze \(D=220\). In Tiefe \(D\) wird sofort gestoppt, also
$$E_{D,h}=E_{\mathrm{stop}}(p_{D,h}).$$
Danach wird rückwärts gerechnet mit
$$E_{n,h}=\max\left\{E_{\mathrm{stop}}(p_{n,h}),\;-1+q_{n,h}E_{n+1,h+1}+(1-q_{n,h})E_{n+1,h}\right\},$$
wobei
$$q_{n,h}=\frac{1}{2}+\frac{p_{n,h}}{4}.$$
Das ist eine klassische Optimal-Stopping-Rekursion: In jedem Zustand wird der Wert eines sofortigen Tipps mit dem Wert einer weiteren kostenpflichtigen Beobachtung verglichen.
Die endliche Tiefe funktioniert gut, weil jeder zusätzliche Wurf \(1\) Punkt kostet, während die Posterior-Wahrscheinlichkeit durch genügend einseitige Evidenz schnell gegen \(0\) oder \(1\) gedrückt wird.
Nun zur Box mit \(u\) unfairen und \(f\) fairen Münzen. Die gewählte Münze ist mit Wahrscheinlichkeit
$$p=\frac{u}{u+f}$$
unfair. Die aktuelle Runde trägt also im Erwartungswert \(E(p)\) bei. Nach der Aufdeckung und Entfernung der Münze geht die Box in den Zustand \((u-1,f)\) über, falls die Münze unfair war, sonst in \((u,f-1)\). Damit gilt
$$B(u,f)=\frac{u}{u+f}B(u-1,f)+\frac{f}{u+f}B(u,f-1)+E\left(\frac{u}{u+f}\right).$$
Die Randfälle sind sofort klar:
$$B(u,0)=20u,\qquad B(0,f)=20f,$$
denn sobald nur noch ein Typ übrig ist, sind alle restlichen Entscheidungen sicher und zusätzliche Würfe sinnlos. Gesucht ist
$$S(N)=B(N,N).$$
Bei einer unfairen und einer fairen Münze hat die zuerst gezogene Münze die Prior-Wahrscheinlichkeit
$$p_0=\frac{1}{2}.$$
Sofortiges Stoppen liefert
$$E_{\mathrm{stop}}\left(\frac{1}{2}\right)=70\cdot\frac{1}{2}-50=-15,$$
also muss man zunächst beobachten.
Nach einem Kopf wird der Posterior
$$p_H=\frac{3(1/2)}{2+1/2}=\frac{3}{5},$$
nach einer Zahl
$$p_T=\frac{1/2}{2-1/2}=\frac{1}{3}.$$
Selbst nach genau einem Wurf lohnt Stoppen noch nicht, denn die Sofortwerte sind \(-8\) und \(-10/3\). Deutlichere Evidenz kippt die Entscheidung aber schnell. Nach drei Köpfen in Folge gilt
$$p=\frac{27}{35},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{27}{35}-50=4,$$
und nach zwei Zahlen in Folge gilt
$$p=\frac{1}{5},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{4}{5}-50=6.$$
Die Rückwärts-DP bestimmt die genaue Stop-Grenze. Für den Startwert \(1/2\) ergibt sich
$$E\left(\frac{1}{2}\right)\approx 0.558591.$$
Die verbleibende zweite Münze ist dann sicher bekannt und bringt \(20\), also
$$S(1)=\frac{1}{2}\cdot 20+\frac{1}{2}\cdot 20+0.558591=20.558591,$$
genau der Kontrollwert aus der Implementierung.
Die C++-, Python- und Java-Implementierungen lösen zuerst das Einzelmünzenproblem für alle Prior-Werte der Form \(u/(u+f)\) mit \(1\le u,f\le N\). Für jeden Prior wird die letzte Zeile des Dreiecks bei Tiefe \(220\) mit Sofort-Stopp-Werten aufgebaut und anschließend Zeile für Zeile rückwärts gerechnet. Die Bayes-Updates werden in Log-Odds-Form ausgeführt, damit es bei vielen Beobachtungen nicht zu numerischem Über- oder Unterlauf kommt.
Wenn die Log-Odds größer als \(50\) oder kleiner als \(-50\) werden, behandelt die Implementierung den Posterior numerisch als \(1\) beziehungsweise \(0\). Dadurch werden unnötige Exponentialauswertungen in praktisch sicheren Zuständen vermieden. Die resultierenden Einzelmünzenwerte werden in einer zweidimensionalen Tabelle nach den verbleibenden unfairen und fairen Münzen abgelegt.
Danach wird eine zweite Tabelle für die Box-Rekursion gefüllt. Die erste Zeile und die erste Spalte enthalten die sicheren Randwerte \(20u\) und \(20f\). Jede innere Zelle berechnet den gewichteten Folgezustand der beiden möglichen Münztypen und addiert den optimalen Erwartungswert der aktuellen Münze. Die letzte Zelle für \((N,N)\) wird mit sechs Nachkommastellen ausgegeben.
Sei \(D\) die Tiefengrenze der Einzelmünzen-DP. Eine Auswertung von \(E(p)\) füllt ein Dreieck mit
$$1+2+\cdots+(D+1)=O(D^2)$$
Zuständen und kostet daher \(O(D^2)\) Zeit. Da jeweils nur eine Zeile dieses Dreiecks gehalten wird, benötigt die Einzelmünzenphase nur \(O(D)\) Zusatzspeicher.
Diese Berechnung wird für jedes Paar \((u,f)\) mit \(1\le u,f\le N\) wiederholt. Das ergibt \(O(N^2D^2)\) Zeit für die Vorberechnung der Einzelmünzenwerte. Die äußere Box-DP kostet nur \(O(N^2)\) zusätzliche Zeit und speichert zwei \((N+1)\times(N+1)\)-Tabellen mit Gleitkommazahlen.
Insgesamt erhält man also
$$O(N^2D^2)\text{ Zeit},\qquad O(N^2+D)\text{ Speicher}.$$
Für die konkreten Parameter \(N=50\) und \(D=220\) ist das ohne Weiteres praktikabel.
Kutuda \(u\) hileli ve \(f\) adil para kaldığında, mevcut \(u+f\) paradan biri eşit olasılıkla seçilir. Bu yüzden eldeki paranın hileli olma önsel olasılığı
$$p=\frac{u}{u+f}$$
olur. Oyuncu son tip tahminini yapmadan önce aynı parayı istediği kadar atabilir. Her atış \(1\) puan maliyetlidir. Son sınıflandırma doğruysa \(+20\), yanlışsa \(-50\) puan getirir. Ardından para kutudan çıkarılır ve sonraki tur başlar.
Amaç, başlangıçta \(N\) hileli ve \(N\) adil para varken toplam beklenen skoru en büyük yapmaktır. Çözüm iki katmanlıdır: önce seçilmiş tek bir para için optimal durdurma problemi çözülür, sonra kutunun değişen bileşimi için ikinci bir dinamik programlama kurulur.
\(E(p)\), mevcut paranın hileli olma önsel olasılığı \(p\) iken o paradan elde edilebilecek optimal beklenen skoru göstersin. \(B(u,f)\) ise kutuda \(u\) hileli ve \(f\) adil para kaldığında oyunun geri kalanının optimal beklenen toplam skoru olsun. Uygulama önce \(E(p)\)'yi hesaplar, sonra bunu \(B(u,f)\) bağıntısında kullanır.
Hemen durursak daha olası olan tipi tahmin etmek en iyisidir. “Hileli” tahmininin beklenen değeri
$$20p-50(1-p)=70p-50,$$
“adil” tahmininin beklenen değeri ise
$$20(1-p)-50p=20-70p=70(1-p)-50$$
olur. Dolayısıyla anında durmanın en iyi değeri
$$E_{\mathrm{stop}}(p)=\max\{70p-50,\;70(1-p)-50\}=70\max\{p,1-p\}-50.$$
\(p\) değeri \(1/2\)'ye yakınsa bu ifade negatiftir; yani kanıt toplamadan kör tahmin yapmak iyi değildir.
Mevcut parayı bir kez daha atarsak yazı gelme olasılığı
$$q_H=\frac{3}{4}p+\frac{1}{2}(1-p)=\frac{1}{2}+\frac{p}{4},$$
tura gelme olasılığı ise
$$q_T=1-q_H=\frac{1}{2}-\frac{p}{4}.$$
Bayes kuralı yeni önseli şu artçı olasılıklara dönüştürür:
$$p_H=\frac{\frac{3}{4}p}{q_H}=\frac{3p}{2+p},\qquad p_T=\frac{\frac{1}{4}p}{q_T}=\frac{p}{2-p}.$$
Bu yüzden bir atış daha yapmanın beklenen değeri
$$E_{\mathrm{cont}}(p)=-1+q_H E(p_H)+q_T E(p_T)$$
olur. Böylece tek para için optimal değer
$$E(p)=\max\{E_{\mathrm{stop}}(p),\;E_{\mathrm{cont}}(p)\}$$
şeklindedir. Denklem tamdır, ancak ufuk sonsuzdur; uygulama bunu sayısal olarak sonlu ufuklu bir geri DP ile çözer.
Başlangıç odds değeri
$$O_0=\frac{p_0}{1-p_0}$$
olsun. Bir yazı odds'u
$$\frac{3/4}{1/2}=\frac{3}{2}$$
ile, bir tura ise
$$\frac{1/4}{1/2}=\frac{1}{2}$$
ile çarpar. Böylece \(n\) atış sonunda \(h\) kez yazı geldiyse
$$O_{n,h}=O_0\left(\frac{3}{2}\right)^h\left(\frac{1}{2}\right)^{n-h}=O_0\,3^h\,2^{-n}.$$
Logaritma alınca
$$\log O_{n,h}=\log O_0-n\log 2+h\log 3$$
elde edilir. Yani artçı olasılık yalnızca \((n,h)\) çiftine bağlıdır; atışların sırası önemli değildir. Odds'tan olasılığa dönüşüm
$$p_{n,h}=\frac{O_{n,h}}{1+O_{n,h}}$$
ile yapılır. Tek para problemi bu yüzden üçgensel bir DP tablosuna indirgenir.
Uygulamalar derinlik sınırı olarak \(D=220\) kullanır. Bu derinlikte süreç zorla durdurulur ve terminal değer
$$E_{D,h}=E_{\mathrm{stop}}(p_{D,h})$$
olarak alınır. Sonra üçgen geriye doğru şu bağıntıyla doldurulur:
$$E_{n,h}=\max\left\{E_{\mathrm{stop}}(p_{n,h}),\;-1+q_{n,h}E_{n+1,h+1}+(1-q_{n,h})E_{n+1,h}\right\},$$
burada
$$q_{n,h}=\frac{1}{2}+\frac{p_{n,h}}{4}.$$
Bu klasik bir optimal durdurma bağıntısıdır: her artçı durumda şimdi tahmin etmenin değeri ile bir puan ödeyip bir gözlem daha almanın değeri karşılaştırılır.
Derinlik sınırı işe yarar; çünkü her ek atış \(1\) puan götürür, buna karşılık yeterince tek taraflı gözlem sonrası artçı olasılık hızla \(0\) veya \(1\)'e yaklaşır ve durmak optimal hale gelir.
Şimdi kutuda \(u\) hileli ve \(f\) adil para kaldığı duruma dönelim. Seçilen para
$$p=\frac{u}{u+f}$$
olasılıkla hilelidir. O halde mevcut turun beklenen katkısı \(E(p)\)'dir. Para sonunda açığa çıkıp çıkarıldığında, para hileliyse gelecek durum \((u-1,f)\), adilse \((u,f-1)\) olur. Bu nedenle
$$B(u,f)=\frac{u}{u+f}B(u-1,f)+\frac{f}{u+f}B(u,f-1)+E\left(\frac{u}{u+f}\right).$$
Sınır durumları hemen bellidir:
$$B(u,0)=20u,\qquad B(0,f)=20f,$$
çünkü kutuda tek tip para kaldığında bütün kalan sınıflandırmalar kesindir ve ek atışların faydası yoktur. İstenen sonuç
$$S(N)=B(N,N)$$
olur.
Bir hileli ve bir adil para varken ilk seçilen paranın önsel olasılığı
$$p_0=\frac{1}{2}$$
olur. Hemen durursak
$$E_{\mathrm{stop}}\left(\frac{1}{2}\right)=70\cdot\frac{1}{2}-50=-15,$$
yani gözlem yapmak zorunludur.
Bir yazı sonrası artçı olasılık
$$p_H=\frac{3(1/2)}{2+1/2}=\frac{3}{5},$$
bir tura sonrası ise
$$p_T=\frac{1/2}{2-1/2}=\frac{1}{3}$$
olur. Yalnızca bir atıştan sonra durmak hâlâ kârlı değildir; anlık değerler \(-8\) ve \(-10/3\)'tür. Fakat daha kuvvetli kanıt kararı hızla değiştirir. Üç ardışık yazı sonrası
$$p=\frac{27}{35},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{27}{35}-50=4,$$
iki ardışık tura sonrası ise
$$p=\frac{1}{5},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{4}{5}-50=6$$
olur. Geriye doğru DP tam durma sınırını hesaplar. Başlangıç önseli \(1/2\) için
$$E\left(\frac{1}{2}\right)\approx 0.558591$$
bulunur. Kalan diğer para artık kesin olarak bilindiğinden \(20\) puan getirir ve
$$S(1)=\frac{1}{2}\cdot 20+\frac{1}{2}\cdot 20+0.558591=20.558591$$
elde edilir. Bu da uygulamadaki sayısal kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları önce \(1\le u,f\le N\) için \(u/(u+f)\) biçimindeki tüm önsel değerlerde tek para problemini çözer. Her önsel için derinlik \(220\)'deki son satır anlık durma değerleriyle kurulur, sonra tablo satır satır geriye doğru doldurulur. Bayes güncellemeleri log-odds biçiminde yapıldığı için çok fazla gözlemden sonra sayısal taşma veya aşırı küçük değer problemi oluşmaz.
Log-odds değeri \(50\)'den büyük ya da \(-50\)'den küçük olduğunda artçı olasılık sayısal olarak sırasıyla \(1\) veya \(0\) kabul edilir. Bu, kararın zaten pratikte kesin olduğu durumlarda gereksiz üstel hesaplamaları ortadan kaldırır. Elde edilen tek para değerleri, kutuda kalan hileli ve adil para sayılarına göre iki boyutlu bir tabloda saklanır.
Daha sonra kutu bağıntısı için ikinci bir tablo doldurulur. İlk satır ve ilk sütun, kesinlik sınırları olan \(20u\) ve \(20f\) değerlerini taşır. Her iç hücre, iki olası sonraki kutu durumunun ağırlıklı ortalamasını alır ve buna mevcut paranın optimal beklenen katkısını ekler. \((N,N)\) hücresi sonuç olarak altı ondalık basamakla yazdırılır.
\(D\), tek para geri DP'sindeki derinlik sınırı olsun. Bir \(E(p)\) hesabı
$$1+2+\cdots+(D+1)=O(D^2)$$
durumlu üçgensel bir tabloyu doldurur; dolayısıyla zaman maliyeti \(O(D^2)\)'dir. Uygulama bu üçgenin her an sadece tek bir satırını tuttuğu için tek para aşamasındaki ek bellek \(O(D)\) olur.
Bu hesap \(1\le u,f\le N\) olan her çift için tekrarlandığından, tek para önhesaplamasının toplam zamanı \(O(N^2D^2)\) olur. Dıştaki kutu DP'si yalnızca \(O(N^2)\) ek zaman harcar ve \((N+1)\times(N+1)\) boyutlu iki kayan nokta tablosu tutar.
Sonuç olarak toplam maliyet
$$O(N^2D^2)\text{ zaman},\qquad O(N^2+D)\text{ bellek}$$
şeklindedir. Gerçek parametreler \(N=50\) ve \(D=220\) için yöntem rahatlıkla uygulanabilir.
En un estado con \(u\) monedas sesgadas y \(f\) monedas justas aún dentro de la caja, se selecciona una de las \(u+f\) monedas restantes de manera uniforme. Por tanto, la moneda actual es sesgada con probabilidad previa
$$p=\frac{u}{u+f}.$$
Antes de hacer la clasificación final, el jugador puede lanzar esa misma moneda tantas veces como quiera. Cada lanzamiento cuesta \(1\) punto. La clasificación final paga \(+20\) si el tipo es correcto y \(-50\) si es incorrecto. Después de revelar el tipo, la moneda se retira y comienza la siguiente ronda.
El objetivo es maximizar la puntuación total esperada cuando la caja empieza con \(N\) monedas sesgadas y \(N\) monedas justas. La solución se divide en dos capas: un problema de parada óptima para una sola moneda seleccionada y una segunda programación dinámica para la composición cambiante de la caja.
Sea \(E(p)\) la contribución esperada óptima de la moneda actual cuando su probabilidad previa de ser sesgada es \(p\). Sea \(B(u,f)\) la puntuación total esperada óptima para una caja que todavía contiene \(u\) monedas sesgadas y \(f\) monedas justas. Primero se calcula \(E(p)\) y luego se usa dentro de la recurrencia para \(B(u,f)\).
Si paramos de inmediato, conviene adivinar el tipo más probable. Adivinar “sesgada” tiene valor esperado
$$20p-50(1-p)=70p-50,$$
mientras que adivinar “justa” tiene valor
$$20(1-p)-50p=20-70p=70(1-p)-50.$$
Por tanto, el mejor valor instantáneo es
$$E_{\mathrm{stop}}(p)=\max\{70p-50,\;70(1-p)-50\}=70\max\{p,1-p\}-50.$$
Cuando \(p\) está cerca de \(1/2\), esta cantidad es negativa, así que adivinar sin observar es mala idea.
Si lanzamos la moneda una vez más, la probabilidad de cara es
$$q_H=\frac{3}{4}p+\frac{1}{2}(1-p)=\frac{1}{2}+\frac{p}{4},$$
y la probabilidad de cruz es
$$q_T=1-q_H=\frac{1}{2}-\frac{p}{4}.$$
La regla de Bayes produce las probabilidades posteriores
$$p_H=\frac{\frac{3}{4}p}{q_H}=\frac{3p}{2+p},\qquad p_T=\frac{\frac{1}{4}p}{q_T}=\frac{p}{2-p}.$$
Así, el valor esperado de continuar un lanzamiento más es
$$E_{\mathrm{cont}}(p)=-1+q_H E(p_H)+q_T E(p_T).$$
El valor óptimo para una sola moneda queda entonces
$$E(p)=\max\{E_{\mathrm{stop}}(p),\;E_{\mathrm{cont}}(p)\}.$$
La ecuación es exacta, pero de horizonte infinito. Las implementaciones la resuelven mediante una DP hacia atrás con horizonte finito y suficiente profundidad numérica.
Definimos las odds iniciales por
$$O_0=\frac{p_0}{1-p_0}.$$
Una cara multiplica esas odds por
$$\frac{3/4}{1/2}=\frac{3}{2},$$
y una cruz las multiplica por
$$\frac{1/4}{1/2}=\frac{1}{2}.$$
Después de \(n\) lanzamientos con \(h\) caras y \(n-h\) cruces, se obtiene
$$O_{n,h}=O_0\left(\frac{3}{2}\right)^h\left(\frac{1}{2}\right)^{n-h}=O_0\,3^h\,2^{-n}.$$
Tomando logaritmos,
$$\log O_{n,h}=\log O_0-n\log 2+h\log 3.$$
Así, la posterior depende solo del par \((n,h)\), no del orden exacto de los resultados. La conversión de odds a probabilidad usa
$$p_{n,h}=\frac{O_{n,h}}{1+O_{n,h}}.$$
Esta compresión del estado es la razón por la que el problema de una moneda se puede resolver sobre una tabla triangular.
Las implementaciones usan un límite de profundidad \(D=220\). En la capa \(D\), el proceso se fuerza a parar y se toma
$$E_{D,h}=E_{\mathrm{stop}}(p_{D,h}).$$
Luego se retrocede con la relación
$$E_{n,h}=\max\left\{E_{\mathrm{stop}}(p_{n,h}),\;-1+q_{n,h}E_{n+1,h+1}+(1-q_{n,h})E_{n+1,h}\right\},$$
donde
$$q_{n,h}=\frac{1}{2}+\frac{p_{n,h}}{4}.$$
Esto es una recurrencia clásica de parada óptima: en cada estado posterior se compara el valor de decidir ahora con el valor de pagar un punto por una observación adicional.
El truncamiento funciona bien porque cada lanzamiento extra cuesta \(1\), mientras que la evidencia repetida empuja rápidamente la posterior hacia \(0\) o hacia \(1\).
Volvamos al estado de la caja con \(u\) monedas sesgadas y \(f\) justas. La moneda elegida es sesgada con probabilidad
$$p=\frac{u}{u+f}.$$
La ronda actual aporta \(E(p)\) en esperanza. Cuando se revela y se retira la moneda, el futuro queda en \((u-1,f)\) si la moneda era sesgada, o en \((u,f-1)\) si era justa. Por ello,
$$B(u,f)=\frac{u}{u+f}B(u-1,f)+\frac{f}{u+f}B(u,f-1)+E\left(\frac{u}{u+f}\right).$$
Las fronteras son inmediatas:
$$B(u,0)=20u,\qquad B(0,f)=20f,$$
porque si solo queda un tipo, todas las clasificaciones restantes son seguras y no hace falta lanzar más. La respuesta pedida es
$$S(N)=B(N,N).$$
Con una moneda sesgada y una justa, la primera moneda seleccionada tiene probabilidad previa
$$p_0=\frac{1}{2}.$$
Parar inmediatamente da
$$E_{\mathrm{stop}}\left(\frac{1}{2}\right)=70\cdot\frac{1}{2}-50=-15,$$
así que conviene observar.
Tras una cara, la posterior pasa a ser
$$p_H=\frac{3(1/2)}{2+1/2}=\frac{3}{5},$$
y tras una cruz pasa a
$$p_T=\frac{1/2}{2-1/2}=\frac{1}{3}.$$
Parar exactamente después de un lanzamiento sigue siendo malo, porque los valores inmediatos son \(-8\) y \(-10/3\). Sin embargo, una evidencia más fuerte cambia pronto la decisión. Después de tres caras consecutivas,
$$p=\frac{27}{35},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{27}{35}-50=4,$$
y después de dos cruces consecutivas,
$$p=\frac{1}{5},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{4}{5}-50=6.$$
La DP hacia atrás fija con precisión la frontera entre parar y continuar. Para el prior inicial \(1/2\) obtiene
$$E\left(\frac{1}{2}\right)\approx 0.558591.$$
La otra moneda queda entonces determinada con certeza y aporta \(20\), de modo que
$$S(1)=\frac{1}{2}\cdot 20+\frac{1}{2}\cdot 20+0.558591=20.558591,$$
exactamente el valor de control usado por la implementación.
Las implementaciones en C++, Python y Java resuelven primero el problema de una sola moneda para todos los priors de la forma \(u/(u+f)\) con \(1\le u,f\le N\). Para cada prior construyen la última fila del triángulo de profundidad \(220\) con valores de parada inmediata y luego retroceden fila por fila hasta llegar al estado inicial. Todo se hace en forma de log-odds para evitar problemas numéricos cuando las actualizaciones bayesianas producen razones muy grandes o muy pequeñas.
Cuando el logaritmo de las odds supera \(50\) o baja de \(-50\), la posterior se trata numéricamente como \(1\) o \(0\). Eso elimina exponenciales innecesarias en estados donde la decisión ya es prácticamente segura. Los valores óptimos para una moneda se almacenan en una tabla bidimensional indexada por la cantidad restante de monedas sesgadas y justas.
Después se llena una segunda tabla para la recurrencia de la caja. La primera fila y la primera columna contienen las fronteras seguras \(20u\) y \(20f\). Cada celda interior aplica la transición ponderada a los dos posibles estados siguientes de la caja y añade el valor esperado óptimo de la moneda actual. La celda final correspondiente a \((N,N)\) se imprime con seis cifras decimales.
Sea \(D\) el límite de profundidad de la DP para una moneda. Una evaluación de \(E(p)\) rellena un triángulo con
$$1+2+\cdots+(D+1)=O(D^2)$$
estados, por lo que cuesta \(O(D^2)\) tiempo. Como la implementación solo conserva una fila del triángulo cada vez, la memoria adicional de esta fase es \(O(D)\).
Esta evaluación se repite para cada par \((u,f)\) con \(1\le u,f\le N\), lo que da \(O(N^2D^2)\) tiempo para la precomputación de los valores de una moneda. La DP externa de la caja añade solo \(O(N^2)\) tiempo y guarda dos tablas \((N+1)\times(N+1)\) de números en coma flotante.
Por lo tanto, el método completo usa
$$O(N^2D^2)\text{ tiempo},\qquad O(N^2+D)\text{ memoria}.$$
Con los parámetros reales \(N=50\) y \(D=220\), el coste es perfectamente manejable.
当盒子里还剩 \(u\) 枚偏置硬币和 \(f\) 枚公平硬币时，会从这 \(u+f\) 枚硬币中等概率随机抽出一枚。因此，当前这枚硬币是偏置硬币的先验概率为
$$p=\frac{u}{u+f}.$$
在做最终分类之前，玩家可以把这同一枚硬币重复抛掷任意多次。每次抛掷要付出 \(1\) 分的代价。最终判断正确得到 \(+20\) 分，判断错误得到 \(-50\) 分。该硬币的真实类型揭示后，它会被移出盒子，然后进入下一轮。
目标是在初始状态有 \(N\) 枚偏置硬币和 \(N\) 枚公平硬币时，使总期望得分最大。这个问题可以自然地拆成两层：第一层是“对当前这一枚硬币应当何时停止继续观察”的最优停止问题；第二层是在盒子组成不断变化时，对整局游戏做动态规划。
记 \(E(p)\) 为当前硬币在先验概率为 \(p\) 时能够贡献的最优期望分数。记 \(B(u,f)\) 为盒子里还剩 \(u\) 枚偏置硬币和 \(f\) 枚公平硬币时，后续整局游戏的最优期望总分。实现先计算 \(E(p)\)，再把它代入 \(B(u,f)\) 的递推式。
如果现在立刻停止观察，那么最合理的做法是猜更可能的那一类。猜“偏置”的期望收益为
$$20p-50(1-p)=70p-50,$$
猜“公平”的期望收益为
$$20(1-p)-50p=20-70p=70(1-p)-50.$$
因此立刻停止时的最佳价值是
$$E_{\mathrm{stop}}(p)=\max\{70p-50,\;70(1-p)-50\}=70\max\{p,1-p\}-50.$$
当 \(p\) 接近 \(1/2\) 时，这个值是负的。这说明如果几乎没有信息，直接猜测并不划算，继续抛掷收集证据才有意义。
如果把当前硬币再抛一次，出现正面的概率是
$$q_H=\frac{3}{4}p+\frac{1}{2}(1-p)=\frac{1}{2}+\frac{p}{4},$$
出现反面的概率是
$$q_T=1-q_H=\frac{1}{2}-\frac{p}{4}.$$
由贝叶斯公式，观察到正面或反面之后的后验概率分别为
$$p_H=\frac{\frac{3}{4}p}{q_H}=\frac{3p}{2+p},\qquad p_T=\frac{\frac{1}{4}p}{q_T}=\frac{p}{2-p}.$$
所以，再观察一次的期望价值为
$$E_{\mathrm{cont}}(p)=-1+q_H E(p_H)+q_T E(p_T).$$
于是单枚硬币的最优值满足
$$E(p)=\max\{E_{\mathrm{stop}}(p),\;E_{\mathrm{cont}}(p)\}.$$
这个递推式本身是精确的，但它是无限期的。实现采用足够深的有限视野反向动态规划来做数值求解。
设初始赔率为
$$O_0=\frac{p_0}{1-p_0}.$$
看到一个正面时，赔率会乘上
$$\frac{3/4}{1/2}=\frac{3}{2},$$
看到一个反面时，赔率会乘上
$$\frac{1/4}{1/2}=\frac{1}{2}.$$
因此，在抛了 \(n\) 次、其中有 \(h\) 次正面的情况下，赔率变成
$$O_{n,h}=O_0\left(\frac{3}{2}\right)^h\left(\frac{1}{2}\right)^{n-h}=O_0\,3^h\,2^{-n}.$$
取对数后得到
$$\log O_{n,h}=\log O_0-n\log 2+h\log 3.$$
这说明后验概率只取决于 \((n,h)\) 这对参数，而不取决于正反面的出现顺序。由赔率恢复概率的公式是
$$p_{n,h}=\frac{O_{n,h}}{1+O_{n,h}}.$$
正是这种压缩，使得单枚硬币问题可以用一个三角形动态规划表来解决。
实现采用深度上限 \(D=220\)。在第 \(D\) 层，强制停止，终止值取为
$$E_{D,h}=E_{\mathrm{stop}}(p_{D,h}).$$
然后从后往前递推：
$$E_{n,h}=\max\left\{E_{\mathrm{stop}}(p_{n,h}),\;-1+q_{n,h}E_{n+1,h+1}+(1-q_{n,h})E_{n+1,h}\right\},$$
其中
$$q_{n,h}=\frac{1}{2}+\frac{p_{n,h}}{4}.$$
这就是标准的最优停止递推：在每一个后验状态上，都比较“现在就猜”与“再花 1 分换取更多信息”哪个更值。
之所以可以安全地截断，是因为额外抛掷永远有固定成本 \(1\)，而一旦证据足够偏向某一边，后验概率会很快逼近 \(0\) 或 \(1\)，此时继续观察几乎不会带来额外收益。
回到盒子的状态。如果还剩 \(u\) 枚偏置硬币和 \(f\) 枚公平硬币，那么当前抽中的硬币是偏置硬币的概率为
$$p=\frac{u}{u+f}.$$
当前这一轮的期望贡献就是 \(E(p)\)。等这枚硬币的真实类型最终揭晓并从盒子里移除后，如果它是偏置硬币，后续状态变成 \((u-1,f)\)；如果它是公平硬币，后续状态变成 \((u,f-1)\)。因此有
$$B(u,f)=\frac{u}{u+f}B(u-1,f)+\frac{f}{u+f}B(u,f-1)+E\left(\frac{u}{u+f}\right).$$
边界情况非常直接：
$$B(u,0)=20u,\qquad B(0,f)=20f,$$
因为当盒子里只剩下一种类型时，之后的每一次判断都是确定无误的，完全没有必要再抛掷。题目要求的答案就是
$$S(N)=B(N,N).$$
当盒子里只有一枚偏置硬币和一枚公平硬币时，第一枚被抽中的硬币先验概率为
$$p_0=\frac{1}{2}.$$
如果马上停止并猜测，则
$$E_{\mathrm{stop}}\left(\frac{1}{2}\right)=70\cdot\frac{1}{2}-50=-15,$$
显然不值得，所以必须先观察。
若第一次抛出正面，则后验变成
$$p_H=\frac{3(1/2)}{2+1/2}=\frac{3}{5},$$
若第一次抛出反面，则后验变成
$$p_T=\frac{1/2}{2-1/2}=\frac{1}{3}.$$
只抛一次就停止仍然不划算，因为此时立刻猜测的价值分别只有 \(-8\) 和 \(-10/3\)。但更强的证据会很快改变判断。连续三个正面后，
$$p=\frac{27}{35},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{27}{35}-50=4,$$
而连续两个反面后，
$$p=\frac{1}{5},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{4}{5}-50=6.$$
反向动态规划会自动找出应当停止还是继续的精确分界。对初始先验 \(1/2\)，它得到
$$E\left(\frac{1}{2}\right)\approx 0.558591.$$
这之后剩下的另一枚硬币类型就完全确定了，贡献 \(20\) 分，因此
$$S(1)=\frac{1}{2}\cdot 20+\frac{1}{2}\cdot 20+0.558591=20.558591,$$
与实现中使用的校验值一致。
C++、Python 和 Java 实现都会先对所有形如 \(u/(u+f)\) 的先验概率求解单枚硬币问题，其中 \(1\le u,f\le N\)。对每一个先验，它们先在深度 \(220\) 的最底层填入“立即停止”的价值，然后按行向后回推，直到起始状态。整个过程使用对数赔率而不是直接连乘概率比，这样可以避免数值上的上溢和下溢。
当对数赔率大于 \(50\) 或小于 \(-50\) 时，后验概率在数值上已经与 \(1\) 或 \(0\) 几乎无异，于是实现直接把它视为确定状态。这可以省掉那些实际上已经没有区分意义的指数运算。得到的单枚硬币最优值会存入一个二维表，按剩余偏置硬币数和公平硬币数索引。
之后，实现再填第二个二维表来处理整盒硬币的递推。第一行和第一列对应确定边界 \(20u\) 与 \(20f\)。其余每个内部状态都按两种可能的下一状态做加权，再加上当前硬币的最优期望收益。最后输出 \((N,N)\) 这个终点状态，并保留六位小数。
设单枚硬币反向动态规划的深度上限为 \(D\)。一次 \(E(p)\) 的求值需要填充一个包含
$$1+2+\cdots+(D+1)=O(D^2)$$
个状态的三角形表，因此时间复杂度为 \(O(D^2)\)。由于实现每次只保留这个三角形的一行，所以单枚硬币阶段的额外空间只需 \(O(D)\)。
这样的求值要对所有 \(1\le u,f\le N\) 的组合重复一次，因此单枚硬币预计算部分总共需要 \(O(N^2D^2)\) 时间。外层盒子动态规划只额外增加 \(O(N^2)\) 时间，并保存两个 \((N+1)\times(N+1)\) 的浮点表。
因此，总复杂度为
$$O(N^2D^2)\text{ 时间},\qquad O(N^2+D)\text{ 空间}.$$
在实际参数 \(N=50\)、\(D=220\) 下，这个代价完全可行。
Пусть в коробке осталось \(u\) нечестных и \(f\) честных монет. Одна из оставшихся \(u+f\) монет выбирается равновероятно, поэтому для текущей монеты априорная вероятность быть нечестной равна
$$p=\frac{u}{u+f}.$$
До окончательного решения о типе этой монеты игрок может подбрасывать именно её сколько угодно раз. Каждый бросок стоит \(1\) очко. Окончательная классификация даёт \(+20\), если тип определён верно, и \(-50\), если неверно. После раскрытия типа монета удаляется, и начинается следующий раунд.
Нужно максимизировать ожидаемый суммарный результат, если изначально в коробке лежат \(N\) нечестных и \(N\) честных монет. Решение естественно распадается на два уровня: задача оптимальной остановки для одной выбранной монеты и отдельная динамика по составу коробки.
Обозначим через \(E(p)\) оптимальный ожидаемый вклад текущей монеты при априорной вероятности \(p\) быть нечестной. Через \(B(u,f)\) обозначим оптимальное ожидаемое суммарное значение игры, если в коробке ещё осталось \(u\) нечестных и \(f\) честных монет. Сначала вычисляется \(E(p)\), а затем этот результат подставляется в рекурсию для \(B(u,f)\).
Если остановиться сразу, разумно угадывать более вероятный тип. Если сказать «нечестная», то матожидание равно
$$20p-50(1-p)=70p-50,$$
а если сказать «честная», то
$$20(1-p)-50p=20-70p=70(1-p)-50.$$
Значит, лучший немедленный результат равен
$$E_{\mathrm{stop}}(p)=\max\{70p-50,\;70(1-p)-50\}=70\max\{p,1-p\}-50.$$
Когда \(p\) близко к \(1/2\), это значение отрицательно, так что угадывать без наблюдений невыгодно.
Если подбросить текущую монету ещё раз, то вероятность орла равна
$$q_H=\frac{3}{4}p+\frac{1}{2}(1-p)=\frac{1}{2}+\frac{p}{4},$$
а вероятность решки равна
$$q_T=1-q_H=\frac{1}{2}-\frac{p}{4}.$$
По формуле Байеса получаем апостериорные вероятности
$$p_H=\frac{\frac{3}{4}p}{q_H}=\frac{3p}{2+p},\qquad p_T=\frac{\frac{1}{4}p}{q_T}=\frac{p}{2-p}.$$
Поэтому ожидаемая ценность продолжения на один бросок равна
$$E_{\mathrm{cont}}(p)=-1+q_H E(p_H)+q_T E(p_T).$$
Следовательно, оптимальное значение для одной монеты задаётся формулой
$$E(p)=\max\{E_{\mathrm{stop}}(p),\;E_{\mathrm{cont}}(p)\}.$$
Это точная рекурсия, но с бесконечным горизонтом. В реализации она заменяется устойчивой численной схемой с большим конечным горизонтом.
Пусть начальные odds равны
$$O_0=\frac{p_0}{1-p_0}.$$
Орел умножает odds на
$$\frac{3/4}{1/2}=\frac{3}{2},$$
а решка умножает их на
$$\frac{1/4}{1/2}=\frac{1}{2}.$$
После \(n\) бросков, среди которых \(h\) орлов и \(n-h\) решек, имеем
$$O_{n,h}=O_0\left(\frac{3}{2}\right)^h\left(\frac{1}{2}\right)^{n-h}=O_0\,3^h\,2^{-n}.$$
Логарифмирование даёт
$$\log O_{n,h}=\log O_0-n\log 2+h\log 3.$$
Значит, апостериорное распределение зависит только от пары \((n,h)\), а не от конкретного порядка выпадений. Обратное преобразование в вероятность имеет вид
$$p_{n,h}=\frac{O_{n,h}}{1+O_{n,h}}.$$
Именно поэтому задачу для одной монеты можно решать на треугольной таблице динамики.
В реализациях используется ограничение глубины \(D=220\). На слое \(D\) процесс принудительно останавливается, и берётся значение
$$E_{D,h}=E_{\mathrm{stop}}(p_{D,h}).$$
Далее выполняется обратный проход по формуле
$$E_{n,h}=\max\left\{E_{\mathrm{stop}}(p_{n,h}),\;-1+q_{n,h}E_{n+1,h+1}+(1-q_{n,h})E_{n+1,h}\right\},$$
где
$$q_{n,h}=\frac{1}{2}+\frac{p_{n,h}}{4}.$$
Это стандартная рекурсия оптимальной остановки: в каждом состоянии сравнивается ценность решения сейчас и ценность ещё одного платного наблюдения.
Ограничение по глубине работает хорошо, потому что каждый новый бросок всегда стоит \(1\), а накопление однотипных наблюдений быстро делает апостериорную вероятность почти равной \(0\) или \(1\).
Вернёмся к коробке с \(u\) нечестными и \(f\) честными монетами. Текущая монета нечестная с вероятностью
$$p=\frac{u}{u+f}.$$
Текущий раунд вносит в среднем \(E(p)\). После раскрытия типа и удаления монеты будущим состоянием будет \((u-1,f)\), если монета была нечестной, и \((u,f-1)\), если честной. Поэтому
$$B(u,f)=\frac{u}{u+f}B(u-1,f)+\frac{f}{u+f}B(u,f-1)+E\left(\frac{u}{u+f}\right).$$
Граничные случаи очевидны:
$$B(u,0)=20u,\qquad B(0,f)=20f,$$
потому что если остался только один тип монет, то все дальнейшие решения становятся полностью определёнными. Требуемый ответ равен
$$S(N)=B(N,N).$$
Если в коробке одна нечестная и одна честная монета, то для первой выбранной монеты
$$p_0=\frac{1}{2}.$$
Немедленная остановка даёт
$$E_{\mathrm{stop}}\left(\frac{1}{2}\right)=70\cdot\frac{1}{2}-50=-15,$$
поэтому сначала нужно собирать информацию.
После одного орла получаем
$$p_H=\frac{3(1/2)}{2+1/2}=\frac{3}{5},$$
после одной решки получаем
$$p_T=\frac{1/2}{2-1/2}=\frac{1}{3}.$$
Остановка сразу после одного броска всё ещё невыгодна, так как значения равны \(-8\) и \(-10/3\). Но более сильная последовательность наблюдений быстро меняет ситуацию. После трёх орлов подряд имеем
$$p=\frac{27}{35},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{27}{35}-50=4,$$
а после двух решек подряд имеем
$$p=\frac{1}{5},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{4}{5}-50=6.$$
Обратная динамика сама находит точную границу между продолжением и остановкой. Для исходного prior \(1/2\) получается
$$E\left(\frac{1}{2}\right)\approx 0.558591.$$
Оставшаяся вторая монета после этого уже известна точно и приносит \(20\), так что
$$S(1)=\frac{1}{2}\cdot 20+\frac{1}{2}\cdot 20+0.558591=20.558591,$$
что совпадает с численной проверкой в реализации.
Реализации на C++, Python и Java сначала решают задачу для одной монеты для всех priors вида \(u/(u+f)\), где \(1\le u,f\le N\). Для каждого такого prior строится последняя строка треугольника глубины \(220\) из значений немедленной остановки, после чего таблица проходится назад строка за строкой до стартового состояния. Байесовские обновления ведутся в форме log-odds, чтобы избежать численных переполнений и потери точности.
Когда log-odds становятся больше \(50\) или меньше \(-50\), апостериорная вероятность численно уже практически неотличима от \(1\) или \(0\), поэтому реализация сразу использует эти крайние значения. Это убирает лишние вычисления экспоненты в почти детерминированных состояниях. Полученные оптимальные значения для одной монеты складываются в двумерную таблицу по числу оставшихся нечестных и честных монет.
После этого заполняется вторая таблица для рекурсии по коробке. Первая строка и первый столбец задают детерминированные границы \(20u\) и \(20f\). Каждая внутренняя клетка берёт взвешенное среднее двух возможных следующих состояний коробки и прибавляет оптимальный ожидаемый вклад текущей монеты. Итоговая клетка \((N,N)\) выводится с шестью знаками после запятой.
Пусть \(D\) — ограничение глубины в динамике для одной монеты. Одно вычисление \(E(p)\) заполняет треугольную таблицу с
$$1+2+\cdots+(D+1)=O(D^2)$$
состояниями, так что время равно \(O(D^2)\). При этом хранится только одна строка таблицы, поэтому дополнительная память на этой стадии равна \(O(D)\).
Такое вычисление повторяется для всех пар \((u,f)\) с \(1\le u,f\le N\), откуда получается \(O(N^2D^2)\) времени на предвычисление значений для одной монеты. Внешняя динамика по коробке добавляет лишь \(O(N^2)\) времени и хранит две таблицы размера \((N+1)\times(N+1)\) с вещественными числами.
Итак, полный метод требует
$$O(N^2D^2)\text{ времени},\qquad O(N^2+D)\text{ памяти}.$$
Для реальных параметров \(N=50\) и \(D=220\) это вполне практично.
إذا بقي في الصندوق \(u\) عملات غير عادلة و\(f\) عملات عادلة، فإن عملة واحدة من العملات \(u+f\) المتبقية تُختار باحتمال متساوٍ. لذلك فإن احتمال أن تكون العملة الحالية غير عادلة يساوي
$$p=\frac{u}{u+f}.$$
قبل اتخاذ القرار النهائي بشأن نوع هذه العملة، يمكن للاعب أن يرمي العملة نفسها أي عدد يشاء من المرات. كل رمية تكلف \(1\) نقطة. التصنيف النهائي يعطي \(+20\) إذا كان صحيحًا و\(-50\) إذا كان خاطئًا. بعد كشف النوع تُزال العملة من الصندوق وتبدأ الجولة التالية.
المطلوب هو تعظيم القيمة المتوقعة للمجموع الكلي عندما يبدأ الصندوق وفيه \(N\) عملات غير عادلة و\(N\) عملات عادلة. والحل ينقسم طبيعيًا إلى مستويين: مسألة توقف أمثل لعملة واحدة مختارة، ثم برمجة ديناميكية ثانية تتابع تغيّر تركيب الصندوق.
لنرمز بـ \(E(p)\) إلى القيمة المتوقعة المثلى التي تضيفها العملة الحالية عندما يكون الاحتمال القبلي لكونها غير عادلة هو \(p\). ولنرمز بـ \(B(u,f)\) إلى القيمة المتوقعة المثلى لبقية اللعبة عندما يبقى \(u\) عملات غير عادلة و\(f\) عملات عادلة. تبدأ الطريقة بحساب \(E(p)\)، ثم تستخدمه داخل العلاقة التراجعية الخاصة بـ \(B(u,f)\).
إذا توقفنا فورًا، فيجب أن نخمن النوع الأكثر احتمالًا. إذا خمّنا أن العملة «غير عادلة» فالقيمة المتوقعة هي
$$20p-50(1-p)=70p-50,$$
أما إذا خمّنا أنها «عادلة» فالقيمة المتوقعة هي
$$20(1-p)-50p=20-70p=70(1-p)-50.$$
إذن أفضل قيمة للتوقف الفوري هي
$$E_{\mathrm{stop}}(p)=\max\{70p-50,\;70(1-p)-50\}=70\max\{p,1-p\}-50.$$
وعندما يكون \(p\) قريبًا من \(1/2\)، تكون هذه القيمة سالبة، أي إن التخمين من دون جمع معلومات إضافية ليس قرارًا جيدًا.
إذا رمينا العملة الحالية مرة أخرى، فإن احتمال ظهور الوجه هو
$$q_H=\frac{3}{4}p+\frac{1}{2}(1-p)=\frac{1}{2}+\frac{p}{4},$$
واحتمال ظهور الظهر هو
$$q_T=1-q_H=\frac{1}{2}-\frac{p}{4}.$$
وبحسب قاعدة بايز تصبح الاحتمالات البعدية
$$p_H=\frac{\frac{3}{4}p}{q_H}=\frac{3p}{2+p},\qquad p_T=\frac{\frac{1}{4}p}{q_T}=\frac{p}{2-p}.$$
ومن ثم فإن القيمة المتوقعة للاستمرار رميةً واحدةً إضافية هي
$$E_{\mathrm{cont}}(p)=-1+q_H E(p_H)+q_T E(p_T).$$
إذًا تحقق العملة الواحدة العلاقة
$$E(p)=\max\{E_{\mathrm{stop}}(p),\;E_{\mathrm{cont}}(p)\}.$$
هذه علاقة دقيقة، لكنها ذات أفق لا نهائي. لذلك تعالجها التطبيقات عدديًا بواسطة برمجة ديناميكية عكسية ذات عمق نهائي كبير.
لنكتب الأرجحية الابتدائية على الصورة
$$O_0=\frac{p_0}{1-p_0}.$$
إذا ظهرت نتيجة وجه، تُضرب الأرجحية في
$$\frac{3/4}{1/2}=\frac{3}{2},$$
وإذا ظهرت نتيجة ظهر، تُضرب في
$$\frac{1/4}{1/2}=\frac{1}{2}.$$
وبعد \(n\) رميات ظهر فيها \(h\) أوجه و\(n-h\) ظهور، تصبح الأرجحية
$$O_{n,h}=O_0\left(\frac{3}{2}\right)^h\left(\frac{1}{2}\right)^{n-h}=O_0\,3^h\,2^{-n}.$$
وأخذ اللوغاريتم يعطي
$$\log O_{n,h}=\log O_0-n\log 2+h\log 3.$$
وبذلك يعتمد الاحتمال البعدي فقط على الزوج \((n,h)\)، لا على ترتيب النتائج نفسه. أما استرجاع الاحتمال من الأرجحية فيكون عبر
$$p_{n,h}=\frac{O_{n,h}}{1+O_{n,h}}.$$
وهذا الاختزال في الحالة هو السبب في أن مسألة العملة الواحدة تُحل على جدول مثلثي صغير نسبيًا.
تستخدم التطبيقات حدًا للعمق مقداره \(D=220\). عند هذا العمق يُفرض التوقف وتُستعمل القيمة النهائية
$$E_{D,h}=E_{\mathrm{stop}}(p_{D,h}).$$
ثم يُجرى المرور العكسي وفق العلاقة
$$E_{n,h}=\max\left\{E_{\mathrm{stop}}(p_{n,h}),\;-1+q_{n,h}E_{n+1,h+1}+(1-q_{n,h})E_{n+1,h}\right\},$$
حيث
$$q_{n,h}=\frac{1}{2}+\frac{p_{n,h}}{4}.$$
هذه هي صيغة التوقف الأمثل المعيارية: في كل حالة بعدية نقارن بين منفعة التخمين الآن ومنفعة دفع نقطة واحدة للحصول على مشاهدة إضافية.
ويكون القطع عند عمق محدود فعالًا لأن كل رمية إضافية تكلف دائمًا \(1\)، بينما يؤدي تراكم الأدلة المنحازة إلى دفع الاحتمال البعدي سريعًا نحو \(0\) أو \(1\)، فيصبح التوقف هو القرار الأفضل.
نعود الآن إلى الصندوق الذي يحتوي على \(u\) عملات غير عادلة و\(f\) عملات عادلة. تكون العملة المختارة غير عادلة باحتمال
$$p=\frac{u}{u+f}.$$
لذلك تسهم الجولة الحالية في المتوسط بمقدار \(E(p)\). وبعد أن يُكشف نوع العملة وتزال، تصبح الحالة التالية \((u-1,f)\) إذا كانت العملة غير عادلة، و\((u,f-1)\) إذا كانت عادلة. ومن ثم
$$B(u,f)=\frac{u}{u+f}B(u-1,f)+\frac{f}{u+f}B(u,f-1)+E\left(\frac{u}{u+f}\right).$$
أما الحواف فتعطى مباشرةً بـ
$$B(u,0)=20u,\qquad B(0,f)=20f,$$
لأنه عندما يبقى نوع واحد فقط تصبح جميع التصنيفات اللاحقة مؤكدة تمامًا ولا حاجة لأي رميات إضافية. والجواب المطلوب هو
$$S(N)=B(N,N).$$
إذا كان في الصندوق عملة غير عادلة واحدة وعملة عادلة واحدة، فإن العملة الأولى المختارة لها احتمال قبلي
$$p_0=\frac{1}{2}.$$
والتوقف فورًا يعطي
$$E_{\mathrm{stop}}\left(\frac{1}{2}\right)=70\cdot\frac{1}{2}-50=-15,$$
ولذلك لا بد من الملاحظة قبل التخمين.
بعد وجه واحد يصبح الاحتمال البعدي
$$p_H=\frac{3(1/2)}{2+1/2}=\frac{3}{5},$$
وبعد ظهر واحد يصبح
$$p_T=\frac{1/2}{2-1/2}=\frac{1}{3}.$$
حتى بعد رمية واحدة فقط يبقى التوقف غير مربح، لأن القيم الفورية هي \(-8\) و\(-10/3\). لكن الأدلة الأقوى تغيّر القرار بسرعة. بعد ثلاثة أوجه متتالية نحصل على
$$p=\frac{27}{35},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{27}{35}-50=4,$$
وبعد ظهرين متتاليين نحصل على
$$p=\frac{1}{5},\qquad E_{\mathrm{stop}}(p)=70\cdot\frac{4}{5}-50=6.$$
البرمجة الديناميكية العكسية هي التي تحدد بدقة أين يكون الحد بين التوقف والاستمرار. وعند prior ابتدائي يساوي \(1/2\) نجد أن
$$E\left(\frac{1}{2}\right)\approx 0.558591.$$
بعد ذلك تصبح العملة الأخرى معروفة النوع يقينًا وتضيف \(20\)، وبالتالي
$$S(1)=\frac{1}{2}\cdot 20+\frac{1}{2}\cdot 20+0.558591=20.558591,$$
وهو نفس المقدار العددي المستخدم كقيمة تحقق في التنفيذ.
تبدأ تطبيقات C++ وPython وJava بحل مسألة العملة الواحدة لكل prior من الصورة \(u/(u+f)\) حيث \(1\le u,f\le N\). ولكل prior تُبنى آخر طبقة من المثلث عند العمق \(220\) من قيم التوقف الفوري، ثم يُجرى مسح عكسي صفًا بعد صف حتى الوصول إلى الحالة الابتدائية. وتُنفذ تحديثات بايز بصيغة لوغاريتم الأرجحية كي لا تظهر مشاكل عددية عند تضخم نسب الاحتمالات أو تضاؤلها.
وعندما تصبح قيمة لوغاريتم الأرجحية أكبر من \(50\) أو أصغر من \(-50\)، يُتعامل مع الاحتمال البعدي عدديًا على أنه \(1\) أو \(0\). هذا يلغي حسابات الأسّ غير الضرورية في الحالات التي أصبحت فيها النتيجة محسومة عمليًا. وتُخزَّن القيم المثلى للعملة الواحدة في جدول ثنائي الأبعاد بحسب عدد العملات غير العادلة والعادلة المتبقية.
بعد ذلك تُملأ مصفوفة ثانية لتطبيق علاقة الصندوق. الصف الأول والعمود الأول يحتويان على القيم الحدية المؤكدة \(20u\) و\(20f\). وكل خلية داخلية تأخذ المتوسط الموزون للحالتين التاليتين الممكنتين للصندوق، ثم تضيف القيمة المتوقعة المثلى للعملة الحالية. وأخيرًا تُطبع الخلية الموافقة للحالة \((N,N)\) مع ست خانات عشرية.
ليكن \(D\) هو حد العمق في البرمجة الديناميكية الخاصة بالعملة الواحدة. إن تقييمًا واحدًا لـ \(E(p)\) يملأ جدولًا مثلثيًا يحوي
$$1+2+\cdots+(D+1)=O(D^2)$$
حالة، ولذلك تكون كلفة الزمن \(O(D^2)\). ولأن التنفيذ يحتفظ في كل لحظة بصف واحد فقط من هذا المثلث، فإن الذاكرة الإضافية في هذه المرحلة تساوي \(O(D)\).
ويعاد هذا التقييم لكل زوج \((u,f)\) بحيث \(1\le u,f\le N\)، فتكون كلفة التحضير الخاصة بالعملة الواحدة \(O(N^2D^2)\) زمنًا. أما البرمجة الديناميكية الخارجية للصندوق فتضيف فقط \(O(N^2)\) زمنًا إضافيًا وتخزن جدولين من الحجم \((N+1)\times(N+1)\) من القيم العشرية.
إذًا تكون الكلفة الكلية
$$O(N^2D^2),\qquad O(N^2+D).$$
أي \(O(N^2D^2)\) في الزمن و\(O(N^2+D)\) في الذاكرة.
ومع القيم الفعلية \(N=50\) و\(D=220\)، فإن هذه الكلفة عملية تمامًا.