A gambler starts with capital \(1\). In each of \(n\) fair tosses, the gambler bets the same fixed fraction \(f\) of the current capital. A win triples the stake portion, so total capital is multiplied by \((1+2f)\); a loss destroys the stake portion, so total capital is multiplied by \((1-f)\).
For the original Project Euler problem, \(n=1000\) and the target is \(T=10^9\). The C++ solution keeps both quantities as parameters, so the same derivation works for any \(n\ge 1\) and \(T>1\).
If exactly \(k\) of the \(n\) tosses are wins, then the order of wins and losses does not matter, because multiplication is commutative. The final wealth is therefore
$$W_k(f)=(1+2f)^k(1-f)^{n-k}.$$
So for each possible win count \(k\), the problem is a one-variable optimization over the admissible range \(0\le f<1\).
Directly maximizing \(W_k(f)\) is equivalent to maximizing its logarithm, because \(\ln(x)\) is strictly increasing on \(x>0\). The code therefore works with
$$g_k(f)=\ln W_k(f)=k\ln(1+2f)+(n-k)\ln(1-f).$$
This removes huge intermediate numbers and turns the product into a sum. It also makes the derivative easy to analyze.
Differentiating gives
$$g_k'(f)=\frac{2k}{1+2f}-\frac{n-k}{1-f}.$$
Setting the derivative to zero yields the critical point
$$f_*=\frac{3k-n}{2n}.$$
The second derivative is
$$g_k''(f)=-\frac{4k}{(1+2f)^2}-\frac{n-k}{(1-f)^2}<0,$$
so \(g_k\) is concave and any interior critical point is automatically the global maximum.
This gives exactly the three branches used in minimum_wins_needed:
1. If \(k=n\), then every toss is a win, so \(W_n(f)=(1+2f)^n\) is increasing and the optimum is the boundary limit \(f\to1^{-}\), giving \(\max g_n = n\ln 3\).
2. If \(f_*\le 0\), then the concave maximum lies to the left of the admissible interval, so the best admissible point is \(f=0\), with \(W_k(0)=1\) and therefore \(g_k(0)=0\).
3. If \(0<f_*<1\), then the optimum is achieved at that interior point and the code evaluates \(g_k(f_*)\) directly.
For a fixed admissible \(f\), replacing one loss by one win multiplies wealth by
$$\frac{1+2f}{1-f}>1 \qquad (0<f<1).$$
So for every fixed \(f\), the quantity \(W_k(f)\) is nondecreasing in \(k\), and strictly increasing when \(f>0\). Taking the maximum over all admissible \(f\) preserves this monotonicity, so \(\max_f g_k(f)\) also increases with \(k\).
That means there is a clean threshold \(k_{\min}\): the smallest number of wins for which the target becomes reachable, namely
$$k_{\min}=\min\{k:\max_f g_k(f)\ge \ln T\}.$$
Once this threshold is found, every outcome with at least \(k_{\min}\) wins is successful, and every outcome below it is impossible to rescue with any fixed fraction.
Because the tosses are fair, the number of wins \(K\) follows
$$K\sim\mathrm{Binomial}(n,1/2).$$
Therefore the answer is
$$P_{\mathrm{succ}}=\Pr[K\ge k_{\min}]=\sum_{k=k_{\min}}^{n}\binom{n}{k}2^{-n}.$$
The program does not compute factorials. Instead it starts with
$$P_0=2^{-n}$$
and uses the recurrence
$$P_{k+1}=P_k\frac{n-k}{k+1}.$$
This is the standard ratio between consecutive binomial masses and is much more stable numerically.
The code contains this test and expects the answer \(1/4\). Let us derive it exactly.
If \(k=1\), then
$$f_*=\frac{3\cdot1-2}{2\cdot2}=\frac14.$$
At this optimum,
$$W_1\!\left(\frac14\right)=\left(1+\frac12\right)\left(1-\frac14\right)=\frac32\cdot\frac34=\frac98<2.$$
So one win is not enough.
If \(k=2\), then every toss is a win and the optimum is the boundary \(f\to1^{-}\), where
$$W_2(f)\to 3^2=9>2.$$
Hence \(k_{\min}=2\). The success probability is just the probability of two wins in two fair tosses:
$$P_{\mathrm{succ}}=\binom22 2^{-2}=\frac14.$$
The second internal test expects \(5/16\). Again we can derive it by hand.
If \(k=2\), then
$$f_*=\frac{3\cdot2-4}{2\cdot4}=\frac14,$$
so
$$W_2\!\left(\frac14\right)=\left(\frac32\right)^2\left(\frac34\right)^2=\frac{81}{64}<4.$$
Thus two wins are still insufficient.
If \(k=3\), then
$$f_*=\frac{3\cdot3-4}{2\cdot4}=\frac58,$$
and
$$W_3\!\left(\frac58\right)=\left(1+\frac{10}{8}\right)^3\left(1-\frac58\right)=\left(\frac94\right)^3\frac38=\frac{2187}{512}>4.$$
Therefore \(k_{\min}=3\). The success probability is the binomial tail
$$\Pr[K\ge3]=\binom43 2^{-4}+\binom44 2^{-4}=\frac{4+1}{16}=\frac{5}{16}.$$
parse_arguments reads three command-line controls: --tosses=<n>, --target=<T>, and --skip-checkpoints.
minimum_wins_needed scans \(k=0,1,\dots,n\). For each \(k\), it computes the best possible log-wealth according to the three-case rule above. The first \(k\) whose best log-wealth reaches \(\ln T\) is returned.
binomial_tail_probability builds the probabilities \(P_k=\Pr[K=k]\) from \(P_0=2^{-n}\) using the binomial ratio recurrence, then sums from \(k_{\min}\) to \(n\).
solve_probability is just the composition of those two steps. The two checkpoints in run_checkpoints verify that both the threshold search and the tail summation are working correctly before the main Euler instance is evaluated.
The threshold search over \(k\) is \(O(n)\). Building and summing the binomial probabilities is also \(O(n)\). The implementation stores a probability vector of length \(n+1\), so the memory usage is \(O(n)\).
A streaming implementation could reduce the memory to \(O(1)\), because only the current probability is needed, but the vector version is simpler to read and perfectly adequate for \(n=1000\).
Der Spieler startet mit Kapital \(1\). In jedem der \(n\) fairen Würfe setzt er denselben festen Anteil \(f\) des aktuellen Kapitals. Ein Gewinn multipliziert das Gesamtvermögen mit \((1+2f)\), ein Verlust mit \((1-f)\).
Im ursprünglichen Euler-Problem gilt \(n=1000\) und das Ziel ist \(T=10^9\). Die C++-Lösung parametrisiert beide Größen, daher funktioniert dieselbe Herleitung für jedes \(n\ge1\) und \(T>1\).
Bei genau \(k\) Gewinnen spielt die Reihenfolge keine Rolle, weil nur Faktoren multipliziert werden. Das Endvermögen ist also
$$W_k(f)=(1+2f)^k(1-f)^{n-k}.$$
Für jedes feste \(k\) bleibt damit nur eine eindimensionale Optimierung über \(0\le f<1\).
Da \(\ln(x)\) für \(x>0\) streng monoton wächst, ist das Maximieren von \(W_k(f)\) äquivalent zum Maximieren von
$$g_k(f)=\ln W_k(f)=k\ln(1+2f)+(n-k)\ln(1-f).$$
So werden große Zwischenwerte vermieden, Produkte werden zu Summen, und die Ableitung wird sehr einfach.
Die Ableitung lautet
$$g_k'(f)=\frac{2k}{1+2f}-\frac{n-k}{1-f}.$$
Aus \(g_k'(f)=0\) folgt der kritische Punkt
$$f_*=\frac{3k-n}{2n}.$$
Die zweite Ableitung ist
$$g_k''(f)=-\frac{4k}{(1+2f)^2}-\frac{n-k}{(1-f)^2}<0,$$
also ist \(g_k\) konkav und jeder innere kritische Punkt automatisch das Globalmaximum.
Genau daraus entstehen die drei Zweige in minimum_wins_needed:
1. Ist \(k=n\), dann ist \(W_n(f)=(1+2f)^n\) streng wachsend; optimal ist der Rand \(f\to1^{-}\), also \(\max g_n=n\ln3\).
2. Ist \(f_*\le0\), dann liegt das konkave Maximum links vom zulässigen Intervall. Der beste zulässige Punkt ist also \(f=0\), mit \(W_k(0)=1\) und \(g_k(0)=0\).
3. Gilt \(0<f_*<1\), dann liegt das Optimum im Inneren und der Code wertet \(g_k(f_*)\) direkt aus.
Für festes zulässiges \(f\) ersetzt ein zusätzlicher Gewinn einen Verlust und multipliziert das Vermögen mit
$$\frac{1+2f}{1-f}>1 \qquad (0<f<1).$$
Also wächst \(W_k(f)\) für jedes feste \(f\) monoton mit \(k\). Nimmt man anschließend das Maximum über alle \(f\), bleibt diese Monotonie erhalten. Daher wächst auch \(\max_f g_k(f)\) mit \(k\).
Damit gibt es eine saubere Schwelle
$$k_{\min}=\min\{k:\max_f g_k(f)\ge\ln T\}.$$
Alle Ergebnisse mit mindestens \(k_{\min}\) Gewinnen sind erfolgreich; unterhalb davon kann kein konstantes \(f\) das Ziel retten.
Weil die Würfe fair sind, gilt
$$K\sim\mathrm{Binomial}(n,1/2).$$
Also ist die gesuchte Wahrscheinlichkeit
$$P_{\mathrm{succ}}=\Pr[K\ge k_{\min}]=\sum_{k=k_{\min}}^n\binom{n}{k}2^{-n}.$$
Das Programm arbeitet nicht mit Fakultäten, sondern startet bei
$$P_0=2^{-n}$$
und verwendet die Rekurrenz
$$P_{k+1}=P_k\frac{n-k}{k+1}.$$
Das ist das Standardverhältnis benachbarter Binomialwahrscheinlichkeiten und numerisch deutlich stabiler.
Der Code erwartet hier \(1/4\). Wir leiten das direkt her.
Für \(k=1\) ist
$$f_*=\frac{3\cdot1-2}{2\cdot2}=\frac14.$$
Damit ergibt sich
$$W_1\!\left(\frac14\right)=\left(1+\frac12\right)\left(1-\frac14\right)=\frac32\cdot\frac34=\frac98<2.$$
Ein Gewinn reicht also nicht.
Für \(k=2\) liegt das Optimum am Rand \(f\to1^{-}\), und dann gilt
$$W_2(f)\to3^2=9>2.$$
Somit ist \(k_{\min}=2\), und die Erfolgswahrscheinlichkeit ist die Wahrscheinlichkeit von zwei Gewinnen in zwei Würfen:
$$P_{\mathrm{succ}}=\binom22 2^{-2}=\frac14.$$
Der zweite interne Test liefert \(5/16\).
Für \(k=2\) erhält man
$$f_*=\frac{3\cdot2-4}{2\cdot4}=\frac14,$$
also
$$W_2\!\left(\frac14\right)=\left(\frac32\right)^2\left(\frac34\right)^2=\frac{81}{64}<4.$$
Zwei Gewinne genügen also noch nicht.
Für \(k=3\) gilt
$$f_*=\frac{3\cdot3-4}{2\cdot4}=\frac58,$$
und damit
$$W_3\!\left(\frac58\right)=\left(\frac94\right)^3\frac38=\frac{2187}{512}>4.$$
Daher ist \(k_{\min}=3\). Die Erfolgswahrscheinlichkeit ist der Binomialschwanz
$$\Pr[K\ge3]=\binom43 2^{-4}+\binom44 2^{-4}=\frac{4+1}{16}=\frac{5}{16}.$$
parse_arguments liest drei Kommandozeilenoptionen: --tosses=<n>, --target=<T> und --skip-checkpoints.
minimum_wins_needed durchläuft \(k=0,1,\dots,n\), berechnet jeweils den besten erreichbaren Log-Gewinn nach der obigen Dreifallregel und liefert das erste \(k\), das \(\ln T\) erreicht.
binomial_tail_probability erzeugt die Wahrscheinlichkeiten \(P_k=\Pr[K=k]\) ausgehend von \(P_0=2^{-n}\) mit der Rekurrenzformel und summiert dann den Schwanz ab \(k_{\min}\).
solve_probability verknüpft beide Schritte. run_checkpoints prüft die beiden kleinen Beispiele, bevor der eigentliche Euler-Fall berechnet wird.
Die Schwellenbestimmung über \(k\) kostet \(O(n)\). Das Erzeugen und Summieren der Binomialwahrscheinlichkeiten kostet ebenfalls \(O(n)\). Der Speicherverbrauch ist \(O(n)\), weil ein Vektor der Länge \(n+1\) gehalten wird.
Mit einer Streaming-Variante ließe sich der Speicher auf \(O(1)\) senken, aber für \(n=1000\) ist die aktuelle, besser lesbare Variante völlig ausreichend.
Oyuncu başlangıçta \(1\) birim sermayeye sahiptir. \(n\) adet adil atışın her birinde mevcut sermayesinin aynı sabit oranı \(f\) kadar bahis yapar. Kazanırsa toplam sermaye \((1+2f)\) ile, kaybederse \((1-f)\) ile çarpılır.
Orijinal Project Euler probleminde \(n=1000\) ve hedef \(T=10^9\) değeridir. C++ çözümü bu iki büyüklüğü parametre olarak tuttuğu için aynı türetim her \(n\ge1\) ve \(T>1\) için geçerlidir.
Toplam \(n\) atış içinde tam \(k\) tanesi kazanç ise, çarpma işlemi sıralamadan bağımsız olduğu için son servet
$$W_k(f)=(1+2f)^k(1-f)^{n-k}$$
olur. Böylece her sabit \(k\) için problem, \(0\le f<1\) aralığında tek değişkenli bir optimizasyona iner.
\(\ln(x)\) fonksiyonu \(x>0\) için sıkı artandır. Bu yüzden \(W_k(f)\) değerini büyütmek ile
$$g_k(f)=\ln W_k(f)=k\ln(1+2f)+(n-k)\ln(1-f)$$
değerini büyütmek tamamen eşdeğerdir. Kod bu biçimi kullanır; çünkü çok büyük ara sayılardan kaçınılır, çarpımlar toplama dönüşür ve türev hesabı sadeleşir.
Türev
$$g_k'(f)=\frac{2k}{1+2f}-\frac{n-k}{1-f}$$
şeklindedir. Bunu sıfıra eşitlersek kritik nokta
$$f_*=\frac{3k-n}{2n}$$
olarak bulunur. İkinci türev ise
$$g_k''(f)=-\frac{4k}{(1+2f)^2}-\frac{n-k}{(1-f)^2}<0$$
olduğu için \(g_k\) konkavdır; yani iç aralıktaki her kritik nokta doğrudan global maksimumdur.
minimum_wins_needed tam olarak şu üç durumu uygular:
1. \(k=n\) ise tüm atışlar kazançtır. \(W_n(f)=(1+2f)^n\) artandır; en iyi değer sınırda \(f\to1^{-}\) ile gelir ve \(\max g_n=n\ln3\) olur.
2. \(f_*\le0\) ise konkav maksimum izinli aralığın solunda kalır. Bu durumda izinli en iyi nokta \(f=0\) olup \(W_k(0)=1\), yani \(g_k(0)=0\) elde edilir.
3. \(0<f_*<1\) ise optimum doğrudan iç noktadadır ve kod \(g_k(f_*)\) değerini hesaplar.
Sabit bir \(f\) seçili olsun. Bir kaybı bir kazançla değiştirmek serveti
$$\frac{1+2f}{1-f}>1 \qquad (0<f<1)$$
katsayısıyla çarpar. Dolayısıyla her sabit \(f\) için \(W_k(f)\), \(k\) arttıkça azalmaz; \(f>0\) ise sıkı biçimde artar. Tüm izinli \(f\) değerleri üzerinde maksimum almak bu monotonluğu bozmaz. Bu yüzden \(\max_f g_k(f)\) de \(k\) ile artan bir dizidir.
Böylece temiz bir eşik tanımlanır:
$$k_{\min}=\min\{k:\max_f g_k(f)\ge\ln T\}.$$
Yani hedefe ulaşmak için gereken en küçük kazanç sayısı \(k_{\min}\)'dir. Bunun altındaki hiçbir \(k\) değeri, sabit bir oran seçerek kurtarılamaz.
Atışlar adil olduğundan kazanç sayısı
$$K\sim\mathrm{Binomial}(n,1/2)$$
dağılımına uyar. Aranan cevap
$$P_{\mathrm{succ}}=\Pr[K\ge k_{\min}]=\sum_{k=k_{\min}}^n \binom{n}{k}2^{-n}$$
şeklindedir. Program faktöriyellerle uğraşmaz; bunun yerine
$$P_0=2^{-n},\qquad P_{k+1}=P_k\frac{n-k}{k+1}$$
özyinelemesini kullanır. Bu, ardışık binom olasılıkları arasındaki standart oran bağıntısıdır ve sayısal olarak daha güvenlidir.
Kod burada sonucun \(1/4\) olmasını bekler. Bunu açıkça türetelim.
\(k=1\) için
$$f_*=\frac{3\cdot1-2}{2\cdot2}=\frac14$$
olur. Bu noktada
$$W_1\!\left(\frac14\right)=\left(1+\frac12\right)\left(1-\frac14\right)=\frac32\cdot\frac34=\frac98<2.$$
Demek ki tek kazanç yetmez.
\(k=2\) için tüm atışlar kazançtır ve optimum sınırda \(f\to1^{-}\) olur:
$$W_2(f)\to3^2=9>2.$$
Dolayısıyla \(k_{\min}=2\). Başarı olasılığı iki atışta iki kazanç olasılığıdır:
$$P_{\mathrm{succ}}=\binom22 2^{-2}=\frac14.$$
İkinci iç test \(5/16\) sonucunu bekler.
\(k=2\) için
$$f_*=\frac{3\cdot2-4}{2\cdot4}=\frac14,$$
dolayısıyla
$$W_2\!\left(\frac14\right)=\left(\frac32\right)^2\left(\frac34\right)^2=\frac{81}{64}<4.$$
İki kazanç yine yeterli değildir.
\(k=3\) için
$$f_*=\frac{3\cdot3-4}{2\cdot4}=\frac58,$$
ve
$$W_3\!\left(\frac58\right)=\left(\frac94\right)^3\frac38=\frac{2187}{512}>4.$$
Böylece \(k_{\min}=3\) olur. Gerekli olasılık binom kuyruğudur:
$$\Pr[K\ge3]=\binom43 2^{-4}+\binom44 2^{-4}=\frac{4+1}{16}=\frac{5}{16}.$$
parse_arguments üç komut satırı seçeneğini okur: --tosses=<n>, --target=<T> ve --skip-checkpoints.
minimum_wins_needed, \(k=0,1,\dots,n\) boyunca ilerler; her \(k\) için yukarıdaki üç-durum kuralıyla erişilebilen en iyi log-serveti hesaplar ve \(\ln T\)'yi ilk geçen \(k\)'yı döndürür.
binomial_tail_probability, \(P_0=2^{-n}\) değerinden başlayarak \(P_k=\Pr[K=k]\) olasılıklarını özyinelemeyle üretir ve \(k_{\min}\)'den \(n\)'ye kadar toplar.
solve_probability bu iki aşamayı birleştirir. run_checkpoints içindeki iki küçük test, hem eşik aramasının hem de kuyruk toplamının doğru çalıştığını doğrular.
\(k\) eşiğini bulma adımı \(O(n)\) zaman alır. Binom olasılıklarını üretip toplamak da \(O(n)\) zamandır. Program \(n+1\) uzunluklu bir olasılık dizisi tuttuğu için bellek kullanımı \(O(n)\)'dir.
İstenirse akış tipi bir uygulamayla bellek \(O(1)\)'e indirilebilir; ancak \(n=1000\) için mevcut vektör tabanlı sürüm hem yeterince hızlı hem de daha okunabilirdir.
El jugador empieza con capital \(1\). En cada uno de los \(n\) lanzamientos justos apuesta la misma fracción fija \(f\) del capital actual. Si gana, el capital total se multiplica por \((1+2f)\); si pierde, se multiplica por \((1-f)\).
En el problema original de Euler se toma \(n=1000\) y \(T=10^9\). La solución en C++ deja ambos valores como parámetros, así que la misma derivación sirve para cualquier \(n\ge1\) y \(T>1\).
Si al final hay exactamente \(k\) victorias, el orden no importa porque solo multiplicamos factores. Por tanto, la riqueza final es
$$W_k(f)=(1+2f)^k(1-f)^{n-k}.$$
Para cada \(k\) fijo, el problema se reduce a optimizar una sola variable en el intervalo \(0\le f<1\).
Como \(\ln(x)\) es estrictamente creciente para \(x>0\), maximizar \(W_k(f)\) es equivalente a maximizar
$$g_k(f)=\ln W_k(f)=k\ln(1+2f)+(n-k)\ln(1-f).$$
Esto evita números intermedios enormes, convierte productos en sumas y deja una derivada muy simple.
Derivando obtenemos
$$g_k'(f)=\frac{2k}{1+2f}-\frac{n-k}{1-f}.$$
Al anular la derivada aparece el punto crítico
$$f_*=\frac{3k-n}{2n}.$$
La segunda derivada es
$$g_k''(f)=-\frac{4k}{(1+2f)^2}-\frac{n-k}{(1-f)^2}<0,$$
de modo que \(g_k\) es cóncava y cualquier punto crítico interior es automáticamente el máximo global.
Eso produce exactamente las tres ramas usadas en minimum_wins_needed:
1. Si \(k=n\), entonces \(W_n(f)=(1+2f)^n\) crece con \(f\); el óptimo está en el borde \(f\to1^{-}\), dando \(\max g_n=n\ln3\).
2. Si \(f_*\le0\), el máximo cóncavo cae fuera del intervalo permitido por la izquierda; el mejor valor admisible es \(f=0\), con \(W_k(0)=1\) y \(g_k(0)=0\).
3. Si \(0<f_*<1\), el óptimo sí es interior y el código evalúa directamente \(g_k(f_*)\).
Para un \(f\) admisible fijo, sustituir una derrota por una victoria multiplica la riqueza por
$$\frac{1+2f}{1-f}>1 \qquad (0<f<1).$$
Así, para cada \(f\) fijo, \(W_k(f)\) es no decreciente en \(k\), y estrictamente creciente si \(f>0\). Al tomar el máximo sobre todos los \(f\), esa monotonía se conserva. Por eso \(\max_f g_k(f)\) también crece con \(k\).
Existe entonces un umbral limpio
$$k_{\min}=\min\{k:\max_f g_k(f)\ge\ln T\}.$$
Todo resultado con al menos \(k_{\min}\) victorias es exitoso; por debajo de ese valor no hay ninguna fracción fija que alcance el objetivo.
Como los lanzamientos son justos, el número de victorias satisface
$$K\sim\mathrm{Binomial}(n,1/2).$$
La respuesta es por tanto
$$P_{\mathrm{succ}}=\Pr[K\ge k_{\min}]=\sum_{k=k_{\min}}^{n}\binom{n}{k}2^{-n}.$$
El programa no usa factoriales. Empieza con
$$P_0=2^{-n}$$
y aplica la recurrencia
$$P_{k+1}=P_k\frac{n-k}{k+1}.$$
Esta es la razón estándar entre masas binomiales consecutivas y resulta mucho más estable numéricamente.
El código espera aquí \(1/4\). Lo derivamos exactamente.
Para \(k=1\),
$$f_*=\frac{3\cdot1-2}{2\cdot2}=\frac14.$$
En ese punto,
$$W_1\!\left(\frac14\right)=\left(1+\frac12\right)\left(1-\frac14\right)=\frac32\cdot\frac34=\frac98<2.$$
Una sola victoria no basta.
Para \(k=2\), el óptimo está en el borde \(f\to1^{-}\), donde
$$W_2(f)\to3^2=9>2.$$
Así, \(k_{\min}=2\). La probabilidad de éxito es simplemente la de dos victorias en dos lanzamientos justos:
$$P_{\mathrm{succ}}=\binom22 2^{-2}=\frac14.$$
La segunda comprobación interna espera \(5/16\).
Para \(k=2\),
$$f_*=\frac{3\cdot2-4}{2\cdot4}=\frac14,$$
y por tanto
$$W_2\!\left(\frac14\right)=\left(\frac32\right)^2\left(\frac34\right)^2=\frac{81}{64}<4.$$
Dos victorias todavía no alcanzan.
Para \(k=3\),
$$f_*=\frac{3\cdot3-4}{2\cdot4}=\frac58,$$
y entonces
$$W_3\!\left(\frac58\right)=\left(\frac94\right)^3\frac38=\frac{2187}{512}>4.$$
Por eso \(k_{\min}=3\). La probabilidad buscada es la cola binomial
$$\Pr[K\ge3]=\binom43 2^{-4}+\binom44 2^{-4}=\frac{4+1}{16}=\frac{5}{16}.$$
parse_arguments lee tres controles de línea de comandos: --tosses=<n>, --target=<T> y --skip-checkpoints.
minimum_wins_needed recorre \(k=0,1,\dots,n\), calcula para cada \(k\) la mejor ganancia logarítmica posible usando la regla de tres casos y devuelve el primer \(k\) que alcanza \(\ln T\).
binomial_tail_probability construye las probabilidades \(P_k=\Pr[K=k]\) a partir de \(P_0=2^{-n}\) con la recurrencia anterior y suma desde \(k_{\min}\) hasta \(n\).
solve_probability simplemente enlaza ambos pasos. run_checkpoints valida los dos ejemplos pequeños antes de calcular la instancia grande de Euler.
La búsqueda del umbral en \(k\) cuesta \(O(n)\). Construir y sumar las probabilidades binomiales también cuesta \(O(n)\). El programa usa \(O(n)\) memoria porque guarda un vector de longitud \(n+1\).
Se podría reducir la memoria a \(O(1)\) con una versión en flujo, pero para \(n=1000\) la implementación actual es suficientemente rápida y mucho más clara.
赌徒初始资本为 \(1\)。在 \(n\) 次公平抛掷中，每次都拿当前资本的固定比例 \(f\) 去下注。若赢，总代价乘以 \((1+2f)\)；若输，总代价乘以 \((1-f)\)。
原始 Project Euler 题目取 \(n=1000\)、\(T=10^9\)。C++ 程序把这两个量都写成参数，因此同一套推导对任意 \(n\ge1\) 与 \(T>1\) 都成立。
如果 \(n\) 次中恰好有 \(k\) 次胜利，那么胜负出现的顺序并不重要，因为最终只是若干乘法因子的乘积。因此最终财富为
$$W_k(f)=(1+2f)^k(1-f)^{n-k}.$$
对每个固定的 \(k\)，问题就变成在 \(0\le f<1\) 上优化一个单变量函数。
由于 \(\ln(x)\) 在 \(x>0\) 上严格递增，最大化 \(W_k(f)\) 与最大化
$$g_k(f)=\ln W_k(f)=k\ln(1+2f)+(n-k)\ln(1-f)$$
是完全等价的。这样做可以避免巨大的中间数，把乘积变成求和，也让求导更直接。
求导得到
$$g_k'(f)=\frac{2k}{1+2f}-\frac{n-k}{1-f}.$$
令导数为零，可得临界点
$$f_*=\frac{3k-n}{2n}.$$
二阶导数为
$$g_k''(f)=-\frac{4k}{(1+2f)^2}-\frac{n-k}{(1-f)^2}<0,$$
所以 \(g_k\) 是凹函数；只要临界点落在可行区间内部，它就自动是全局最大值。
minimum_wins_needed 正是按以下三种情况实现的：
1. 若 \(k=n\)，则 \(W_n(f)=(1+2f)^n\) 随 \(f\) 增长，最优点在边界 \(f\to1^{-}\)，于是 \(\max g_n=n\ln3\)。
2. 若 \(f_*\le0\)，说明凹函数的最大值落在可行区间左侧，最佳可行点只能是 \(f=0\)，此时 \(W_k(0)=1\)，即 \(g_k(0)=0\)。
3. 若 \(0<f_*<1\)，最优点就在内部，代码直接计算 \(g_k(f_*)\)。
对任意固定的可行 \(f\)，把一次失败换成一次胜利，会让财富乘上
$$\frac{1+2f}{1-f}>1 \qquad (0<f<1).$$
因此对每个固定 \(f\)，\(W_k(f)\) 都是关于 \(k\) 的不减函数；若 \(f>0\)，还是严格递增的。再对所有可行 \(f\) 取最大值，这个单调性不会消失，所以 \(\max_f g_k(f)\) 也随着 \(k\) 增大而增大。
于是存在清晰的阈值
$$k_{\min}=\min\{k:\max_f g_k(f)\ge\ln T\}.$$
也就是说，只要胜场数至少达到 \(k_{\min}\)，就能通过某个固定下注比例达到目标；低于这个值则无论怎样选固定 \(f\) 都不可能成功。
由于抛掷公平，胜场数 \(K\) 服从
$$K\sim\mathrm{Binomial}(n,1/2).$$
所以答案为
$$P_{\mathrm{succ}}=\Pr[K\ge k_{\min}]=\sum_{k=k_{\min}}^{n}\binom{n}{k}2^{-n}.$$
程序并不直接使用阶乘，而是从
$$P_0=2^{-n}$$
开始，并用递推
$$P_{k+1}=P_k\frac{n-k}{k+1}$$
生成相邻的二项概率。这正是连续二项质量之间的标准比例关系，数值上更稳定。
代码要求此时答案为 \(1/4\)。下面把它算出来。
当 \(k=1\) 时，
$$f_*=\frac{3\cdot1-2}{2\cdot2}=\frac14.$$
代回可得
$$W_1\!\left(\frac14\right)=\left(1+\frac12\right)\left(1-\frac14\right)=\frac32\cdot\frac34=\frac98<2.$$
所以一场胜利还不够。
当 \(k=2\) 时，所有抛掷都赢，最优值在边界 \(f\to1^{-}\)，此时
$$W_2(f)\to3^2=9>2.$$
因此 \(k_{\min}=2\)。成功概率就是两次抛掷全赢的概率：
$$P_{\mathrm{succ}}=\binom22 2^{-2}=\frac14.$$
第二个内部校验要求得到 \(5/16\)。
当 \(k=2\) 时，
$$f_*=\frac{3\cdot2-4}{2\cdot4}=\frac14,$$
于是
$$W_2\!\left(\frac14\right)=\left(\frac32\right)^2\left(\frac34\right)^2=\frac{81}{64}<4.$$
两场胜利仍然不够。
当 \(k=3\) 时，
$$f_*=\frac{3\cdot3-4}{2\cdot4}=\frac58,$$
并且
$$W_3\!\left(\frac58\right)=\left(\frac94\right)^3\frac38=\frac{2187}{512}>4.$$
因此 \(k_{\min}=3\)。最终概率是二项尾和
$$\Pr[K\ge3]=\binom43 2^{-4}+\binom44 2^{-4}=\frac{4+1}{16}=\frac{5}{16}.$$
parse_arguments 读取三个命令行参数：--tosses=<n>、--target=<T> 和 --skip-checkpoints。
minimum_wins_needed 按 \(k=0,1,\dots,n\) 顺序扫描，对每个 \(k\) 按上面的三分支规则计算可达到的最大对数财富，并返回第一个使其达到 \(\ln T\) 的 \(k\)。
binomial_tail_probability 从 \(P_0=2^{-n}\) 开始，利用递推式生成 \(P_k=\Pr[K=k]\)，再从 \(k_{\min}\) 累加到 \(n\)。
solve_probability 只是把这两步串起来。run_checkpoints 中的两个小例子用于先验证阈值搜索和尾和计算都正确。
寻找阈值 \(k_{\min}\) 的扫描是 \(O(n)\)。生成并求和二项概率同样是 \(O(n)\)。实现里保存了一个长度为 \(n+1\) 的概率数组，因此空间复杂度也是 \(O(n)\)。
如果只保留当前项，可以把空间压到 \(O(1)\)；但对 \(n=1000\) 而言，当前写法更容易阅读，也完全够快。
Игрок начинает с капитала \(1\). В каждом из \(n\) честных бросков он ставит одну и ту же фиксированную долю \(f\) текущего капитала. Победа умножает весь капитал на \((1+2f)\), поражение на \((1-f)\).
В исходной задаче Project Euler берутся \(n=1000\) и \(T=10^9\). В программе на C++ обе величины параметризованы, поэтому та же схема работает для любых \(n\ge1\) и \(T>1\).
Если среди \(n\) бросков ровно \(k\) побед, порядок уже не важен, потому что итог есть произведение множителей. Значит, конечное богатство равно
$$W_k(f)=(1+2f)^k(1-f)^{n-k}.$$
Для каждого фиксированного \(k\) остается одномерная оптимизация по \(f\) на интервале \(0\le f<1\).
Так как \(\ln(x)\) строго возрастает при \(x>0\), максимизация \(W_k(f)\) эквивалентна максимизации
$$g_k(f)=\ln W_k(f)=k\ln(1+2f)+(n-k)\ln(1-f).$$
Это убирает огромные промежуточные числа, превращает произведение в сумму и делает производную простой.
Производная равна
$$g_k'(f)=\frac{2k}{1+2f}-\frac{n-k}{1-f}.$$
Из условия \(g_k'(f)=0\) получаем критическую точку
$$f_*=\frac{3k-n}{2n}.$$
Вторая производная равна
$$g_k''(f)=-\frac{4k}{(1+2f)^2}-\frac{n-k}{(1-f)^2}<0,$$
поэтому \(g_k\) вогнута, и любая внутренняя критическая точка автоматически дает глобальный максимум.
Именно отсюда возникают три ветви в minimum_wins_needed:
1. Если \(k=n\), то \(W_n(f)=(1+2f)^n\) возрастает по \(f\), а оптимум находится на границе \(f\to1^{-}\), то есть \(\max g_n=n\ln3\).
2. Если \(f_*\le0\), то максимум вогнутой функции лежит левее допустимого интервала. Лучшая допустимая точка тогда \(f=0\), откуда \(W_k(0)=1\) и \(g_k(0)=0\).
3. Если \(0<f_*<1\), оптимум внутренний, и код просто вычисляет \(g_k(f_*)\).
Для фиксированного допустимого \(f\) замена одного поражения на одну победу умножает богатство на
$$\frac{1+2f}{1-f}>1 \qquad (0<f<1).$$
Следовательно, при каждом фиксированном \(f\) величина \(W_k(f)\) не убывает по \(k\), а при \(f>0\) даже строго возрастает. После взятия максимума по всем допустимым \(f\) эта монотонность сохраняется, значит, \(\max_f g_k(f)\) тоже возрастает по \(k\).
Отсюда появляется четкий порог
$$k_{\min}=\min\{k:\max_f g_k(f)\ge\ln T\}.$$
Все результаты с \(k\ge k_{\min}\) успешны; ниже этого уровня никакая фиксированная доля ставки цель не достигнет.
Поскольку броски честные, число побед \(K\) имеет распределение
$$K\sim\mathrm{Binomial}(n,1/2).$$
Следовательно, ответ равен
$$P_{\mathrm{succ}}=\Pr[K\ge k_{\min}]=\sum_{k=k_{\min}}^{n}\binom{n}{k}2^{-n}.$$
Программа не использует факториалы. Она начинает с
$$P_0=2^{-n}$$
и далее применяет рекурсию
$$P_{k+1}=P_k\frac{n-k}{k+1}.$$
Это стандартное отношение соседних биномиальных масс, численно гораздо устойчивее прямой формулы.
Код ожидает здесь ответ \(1/4\). Выведем его вручную.
Для \(k=1\)
$$f_*=\frac{3\cdot1-2}{2\cdot2}=\frac14.$$
Тогда
$$W_1\!\left(\frac14\right)=\left(1+\frac12\right)\left(1-\frac14\right)=\frac32\cdot\frac34=\frac98<2.$$
Одной победы недостаточно.
Для \(k=2\) оптимум лежит на границе \(f\to1^{-}\), и
$$W_2(f)\to3^2=9>2.$$
Значит, \(k_{\min}=2\). Вероятность успеха равна вероятности двух побед в двух бросках:
$$P_{\mathrm{succ}}=\binom22 2^{-2}=\frac14.$$
Вторая внутренняя проверка ожидает \(5/16\).
Для \(k=2\)
$$f_*=\frac{3\cdot2-4}{2\cdot4}=\frac14,$$
поэтому
$$W_2\!\left(\frac14\right)=\left(\frac32\right)^2\left(\frac34\right)^2=\frac{81}{64}<4.$$
Двух побед еще мало.
Для \(k=3\)
$$f_*=\frac{3\cdot3-4}{2\cdot4}=\frac58,$$
и тогда
$$W_3\!\left(\frac58\right)=\left(\frac94\right)^3\frac38=\frac{2187}{512}>4.$$
Следовательно, \(k_{\min}=3\). Искомая вероятность есть биномиальный хвост
$$\Pr[K\ge3]=\binom43 2^{-4}+\binom44 2^{-4}=\frac{4+1}{16}=\frac{5}{16}.$$
parse_arguments разбирает три параметра командной строки: --tosses=<n>, --target=<T> и --skip-checkpoints.
minimum_wins_needed перебирает \(k=0,1,\dots,n\), вычисляет для каждого \(k\) наилучший достижимый логарифм богатства по описанному трехветвевому правилу и возвращает первое \(k\), достигающее \(\ln T\).
binomial_tail_probability строит вероятности \(P_k=\Pr[K=k]\), начиная с \(P_0=2^{-n}\), затем по рекурсии и суммирует хвост от \(k_{\min}\) до \(n\).
solve_probability просто склеивает эти два шага. Функция run_checkpoints заранее проверяет оба маленьких примера, подтверждая корректность и поиска порога, и суммирования хвоста.
Поиск порога по \(k\) занимает \(O(n)\). Построение и суммирование биномиальных вероятностей тоже занимает \(O(n)\). Память равна \(O(n)\), поскольку хранится вектор длины \(n+1\).
Потоковая версия могла бы уменьшить память до \(O(1)\), но при \(n=1000\) текущий вариант гораздо проще читать и более чем достаточен по скорости.
يبدأ اللاعب برأس مال مقداره \(1\). في كل واحدة من \(n\) رميات عادلة يراهن على النسبة الثابتة نفسها \(f\) من رأس المال الحالي. إذا فاز ضُرب رأس المال كله في \((1+2f)\)، وإذا خسر ضُرب في \((1-f)\).
في مسألة Project Euler الأصلية نأخذ \(n=1000\) و\(T=10^9\). برنامج C++ يجعل القيمتين وسيطتين، لذلك يبقى الاشتقاق نفسه صحيحًا لأي \(n\ge1\) وأي \(T>1\).
إذا انتهت السلسلة بعدد انتصارات يساوي \(k\)، فإن الترتيب لا يهم لأننا نضرب عوامل فقط. لذلك تكون الثروة النهائية
$$W_k(f)=(1+2f)^k(1-f)^{n-k}.$$
ومن ثم فلكل \(k\) ثابت تتحول المسألة إلى تحسين دالة بمتغير واحد على المجال \(0\le f<1\).
بما أن \(\ln(x)\) دالة متزايدة تمامًا على \(x>0\)، فإن تعظيم \(W_k(f)\) مكافئ تمامًا لتعظيم
$$g_k(f)=\ln W_k(f)=k\ln(1+2f)+(n-k)\ln(1-f).$$
هذا يتجنب الأعداد الوسيطة الضخمة، ويحوّل الجداء إلى مجموع، ويجعل المشتقة أسهل بكثير.
المشتقة هي
$$g_k'(f)=\frac{2k}{1+2f}-\frac{n-k}{1-f}.$$
وبجعلها تساوي الصفر نحصل على النقطة الحرجة
$$f_*=\frac{3k-n}{2n}.$$
أما المشتقة الثانية فهي
$$g_k''(f)=-\frac{4k}{(1+2f)^2}-\frac{n-k}{(1-f)^2}<0,$$
ولذلك فالدالة \(g_k\) مقعرة، وأي نقطة حرجة داخلية تعطي مباشرة القيمة العظمى العالمية.
ومن هنا تأتي الحالات الثلاث المستعملة في minimum_wins_needed:
1. إذا كان \(k=n\)، فإن \(W_n(f)=(1+2f)^n\) تزداد مع \(f\)، وأفضل قيمة تقع على الحد \(f\to1^{-}\)، فنحصل على \(\max g_n=n\ln3\).
2. إذا كان \(f_*\le0\)، فمعنى ذلك أن أقصى الدالة المقعرة يقع يسار المجال المسموح. عندئذ تكون أفضل قيمة مسموحة هي \(f=0\)، ومن ثم \(W_k(0)=1\) و\(g_k(0)=0\).
3. إذا كان \(0<f_*<1\)، فال optimum داخلي، ويحسب الكود القيمة \(g_k(f_*)\) مباشرة.
لأي \(f\) ثابت مسموح، فإن استبدال خسارة واحدة بانتصار واحد يضرب الثروة في
$$\frac{1+2f}{1-f}>1 \qquad (0<f<1).$$
إذًا فلكل \(f\) ثابت تكون \(W_k(f)\) غير متناقصة مع \(k\)، وتصبح متزايدة تمامًا عندما \(f>0\). وأخذ القيمة العظمى على جميع القيم المسموح بها لـ \(f\) يحافظ على هذه الرتبية. لذلك فإن \(\max_f g_k(f)\) نفسها تزداد مع \(k\).
ومن ثم توجد عتبة واضحة
$$k_{\min}=\min\{k:\max_f g_k(f)\ge\ln T\}.$$
أي أن أقل عدد من الانتصارات الذي يسمح بالوصول إلى الهدف هو \(k_{\min}\). وأي نتيجة أقل من ذلك لا يمكن إنقاذها بأي نسبة رهان ثابتة.
بما أن الرميات عادلة، فإن عدد الانتصارات \(K\) يحقق
$$K\sim\mathrm{Binomial}(n,1/2).$$
وبالتالي يكون الجواب
$$P_{\mathrm{succ}}=\Pr[K\ge k_{\min}]=\sum_{k=k_{\min}}^{n}\binom{n}{k}2^{-n}.$$
البرنامج لا يستعمل المضروبات مباشرة. بل يبدأ من
$$P_0=2^{-n}$$
ثم يستخدم العلاقة التكرارية
$$P_{k+1}=P_k\frac{n-k}{k+1}.$$
وهذه هي النسبة القياسية بين كتلتي ثنائي الحدين المتتاليتين، وهي أكثر ثباتًا عدديًا.
يتوقع الكود هنا القيمة \(1/4\). لنشتقها مباشرة.
عند \(k=1\) نحصل على
$$f_*=\frac{3\cdot1-2}{2\cdot2}=\frac14.$$
وعند هذه القيمة
$$W_1\!\left(\frac14\right)=\left(1+\frac12\right)\left(1-\frac14\right)=\frac32\cdot\frac34=\frac98<2.$$
إذن انتصار واحد لا يكفي.
أما عند \(k=2\)، فكل الرميات انتصارات، والقيمة المثلى تكون على الحد \(f\to1^{-}\)، حيث
$$W_2(f)\to3^2=9>2.$$
إذًا \(k_{\min}=2\). واحتمال النجاح هو احتمال الفوز مرتين في رميتين عادلتين:
$$P_{\mathrm{succ}}=\binom22 2^{-2}=\frac14.$$
الاختبار الداخلي الثاني يتوقع \(5/16\).
عند \(k=2\)،
$$f_*=\frac{3\cdot2-4}{2\cdot4}=\frac14,$$
ومن ثم
$$W_2\!\left(\frac14\right)=\left(\frac32\right)^2\left(\frac34\right)^2=\frac{81}{64}<4.$$
إذًا انتصاران ما زالا غير كافيين.
عند \(k=3\)،
$$f_*=\frac{3\cdot3-4}{2\cdot4}=\frac58,$$
وعندها
$$W_3\!\left(\frac58\right)=\left(\frac94\right)^3\frac38=\frac{2187}{512}>4.$$
إذن \(k_{\min}=3\). ويكون الاحتمال المطلوب هو ذيل ثنائي الحدين
$$\Pr[K\ge3]=\binom43 2^{-4}+\binom44 2^{-4}=\frac{4+1}{16}=\frac{5}{16}.$$
parse_arguments يقرأ ثلاث وسيطات من سطر الأوامر: --tosses=<n> و--target=<T> و--skip-checkpoints.
minimum_wins_needed يمر على \(k=0,1,\dots,n\)، ويحسب لكل \(k\) أفضل ثروة لوغاريتمية ممكنة وفق قاعدة الحالات الثلاث أعلاه، ثم يعيد أول \(k\) يصل إلى \(\ln T\).
binomial_tail_probability يبني الاحتمالات \(P_k=\Pr[K=k]\) ابتداءً من \(P_0=2^{-n}\)، ثم بالعلاقة التكرارية السابقة، وبعد ذلك يجمع من \(k_{\min}\) حتى \(n\).
solve_probability يربط المرحلتين فقط. وتتحقق الدالة run_checkpoints من المثالين الصغيرين للتأكد من صحة كل من البحث عن العتبة وجمع الذيل.
البحث عن العتبة عبر \(k\) يكلف \(O(n)\). وبناء احتمالات ثنائي الحدين وجمعها يكلف أيضًا \(O(n)\). ويستعمل التنفيذ ذاكرة \(O(n)\) لأنه يخزن متجهًا بطول \(n+1\).
يمكن تنفيذ نسخة تدفقية تقلل الذاكرة إلى \(O(1)\)، لكن عند \(n=1000\) تبقى الصيغة الحالية أوضح وأكثر من كافية من حيث الأداء.