The three implementations reduce the chess match to a one-dimensional lead process. If the current lead of player A is \(i\), then after one round it becomes \(i+1\) with probability \(a\), \(i-1\) with probability \(b\), and stays at \(i\) with probability \(1-a-b\). Independently, the process survives to the next round with probability \(q=1-t\), where \(t\) is the stopping probability.
For each integer \(k\in\{3,4,\dots,50\}\), the parameters are
$$a_k=\frac{1}{\sqrt{k+3}},\qquad b_k=a_k+\frac{1}{k^2},\qquad t_k=\frac{1}{k^3},\qquad q_k=1-t_k.$$
The task is to evaluate the expected lead-counting quantity attached to this stopped walk for every \(k\), and then sum those \(48\) values. The implementations do not simulate long matches; instead they solve one closed-form recurrence and reuse it for every parameter set.
The cleanest derivation introduces an auxiliary state value \(U_i\), where \(i\in\mathbb Z\) is the current lead of player A. After solving for \(U_0\), the quantity printed by the implementations is obtained by dividing by \(q\).
Let \(U_i\) satisfy
$$U_i=\mathbf{1}_{i>0}+q\left(a\,U_{i+1}+b\,U_{i-1}+(1-a-b)U_i\right).$$
The indicator term contributes one unit exactly when the current lead is positive. This auxiliary normalization is convenient because the same linear operator appears on both sides of zero, and the final quantity of interest will simply be
$$H(a,b,t)=\frac{U_0}{q}.$$
Write
$$s=1-a-b,\qquad c=1-q s=t+q(a+b).$$
Then the recurrence becomes
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=-\mathbf{1}_{i>0}.$$
The right-hand side is \(0\) for \(i\le 0\) and \(-1\) for \(i\ge 1\), so the problem naturally splits into a non-positive side and a positive side.
The homogeneous recurrence is
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=0.$$
Substituting \(U_i=r^i\) gives the characteristic polynomial
$$q a r^2-c r+q b=0.$$
Its two roots are
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa}.$$
The discriminant is always positive in this problem family, because
$$c^2-4q^2ab=\left(t+q(a+b)\right)^2-4q^2ab=t^2+2tq(a+b)+q^2(a-b)^2>0.$$
So the roots are real and distinct. Moreover, evaluating the polynomial at \(r=1\) gives
$$q a-c+q b=-t<0,$$
while at \(r=0\) it equals \(q b>0\). Hence one root lies in \((0,1)\). Since
$$\rho_-\rho_+=\frac{b}{a}>1$$
for the actual parameters \(b=a+1/k^2\), the other root must be larger than \(1\). Therefore
$$0<\rho_-<1<\rho_+.$$
For \(i\le 0\), the recurrence is homogeneous, so boundedness as \(i\to-\infty\) forces the solution to use only the root larger than \(1\):
$$U_i=A\,\rho_+^i\qquad (i\le 0).$$
For \(i\ge 1\), the forcing term is constant. A constant particular solution \(U_i\equiv K\) must satisfy
$$K=1+qK,$$
so
$$K=\frac{1}{t}.$$
To keep the positive side bounded as \(i\to+\infty\), we keep only the decaying root \(\rho_-\):
$$U_i=\frac{1}{t}+B\,\rho_-^i\qquad (i\ge 1).$$
This is the core structural simplification: one exponential branch on the left, one constant-plus-exponential branch on the right.
We now impose the recurrence at the two interface points. At \(i=0\), substituting \(U_0=A\), \(U_{-1}=A/\rho_+\), and \(U_1=1/t+B\rho_-\) gives
$$A=q\left(a\left(\frac{1}{t}+B\rho_-\right)+b\frac{A}{\rho_+}+sA\right).$$
Using the characteristic equation to simplify the coefficients yields
$$A\rho_+=\frac{1}{t}+B\rho_-.$$
At \(i=1\), substituting \(U_1=1/t+B\rho_-\), \(U_2=1/t+B\rho_-^2\), and \(U_0=A\) gives
$$\frac{1}{t}+B\rho_-=1+q\left(a\left(\frac{1}{t}+B\rho_-^2\right)+bA+s\left(\frac{1}{t}+B\rho_-\right)\right).$$
After subtracting the constant particular solution and simplifying again with the characteristic equation, this reduces to
$$B=A-\frac{1}{t}.$$
Substituting that relation back into the previous equation gives
$$A(\rho_+-\rho_-)=\frac{1-\rho_-}{t},$$
so
$$A=\frac{1-\rho_-}{t(\rho_+-\rho_-)}.$$
Since the required value is \(H(a,b,t)=U_0/q=A/q\), we obtain the exact expression used by all three implementations:
$$\boxed{H(a,b,t)=\frac{1-\rho_-}{tq(\rho_+-\rho_-)}}$$
with
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa},\qquad c=t+q(a+b),\qquad q=1-t.$$
The final answer for the problem is therefore
$$\sum_{k=3}^{50} H\left(\frac{1}{\sqrt{k+3}},\ \frac{1}{\sqrt{k+3}}+\frac{1}{k^2},\ \frac{1}{k^3}\right).$$
That turns a potentially enormous stochastic process into a short deterministic computation: one square root and a few arithmetic operations per value of \(k\).
This exact checkpoint is especially useful because the algebra collapses nicely. Here
$$q=\frac12,\qquad c=t+q(a+b)=\frac12+\frac12\cdot\frac12=\frac34.$$
The discriminant is
$$c^2-4q^2ab=\frac{9}{16}-4\cdot\frac14\cdot\frac1{16}=\frac12,$$
so the two roots are
$$\rho_-=\frac{\frac34-\sqrt{\frac12}}{\frac14}=3-2\sqrt2,\qquad \rho_+=3+2\sqrt2.$$
Then
$$\rho_+-\rho_-=4\sqrt2,\qquad 1-\rho_-=2(\sqrt2-1).$$
Plugging these into the closed form gives
$$H\left(\frac14,\frac14,\frac12\right)=\frac{2(\sqrt2-1)}{\frac12\cdot\frac12\cdot 4\sqrt2}=2-\sqrt2\approx 0.585786.$$
This matches the numerical checkpoint embedded in the implementations. For the actual parameter family, the first term of the final sum, corresponding to \(k=3\), is approximately \(6.8345\).
The C++, Python, and Java implementations all follow exactly the same mathematical pipeline. For each \(k\) from \(3\) to \(50\), they construct \(a_k\), \(b_k\), and \(t_k\); compute \(q_k\), \(c_k\), the discriminant, and the square root; form the smaller and larger characteristic roots; and then evaluate the closed form above.
No dynamic programming table, recursion tree, or Monte Carlo sampling is needed. The entire match model has already been collapsed into the algebraic expression for \(H(a,b,t)\), so each loop iteration is independent and constant size.
The language-specific difference is numerical precision rather than algorithm design. The C++ version uses extended floating-point arithmetic, the Python version uses decimal arithmetic with high precision, and the Java version uses decimal arithmetic with a high-precision math context. All three then accumulate the \(48\) terms and format the final total to four decimal places.
The loop runs for exactly \(48\) values of \(k\). Each iteration performs a fixed number of arithmetic operations and one square root, so for fixed precision the running time is \(O(1)\) overall and the memory usage is \(O(1)\).
If one wants to count the cost of arbitrary-precision arithmetic explicitly, then the dominant operation is still the square root in each iteration, but the precision level is fixed by the required decimal output. In practice the computation is tiny.
Die drei Implementierungen reduzieren das Schachmatch auf einen eindimensionalen Führungsprozess. Wenn der aktuelle Vorsprung von Spieler A gleich \(i\) ist, wird er nach einer Runde mit Wahrscheinlichkeit \(a\) zu \(i+1\), mit Wahrscheinlichkeit \(b\) zu \(i-1\) und bleibt mit Wahrscheinlichkeit \(1-a-b\) unverändert. Unabhängig davon wird der Prozess mit Wahrscheinlichkeit \(q=1-t\) fortgesetzt, wobei \(t\) die Stoppwahrscheinlichkeit pro Runde ist.
Für jedes \(k\in\{3,4,\dots,50\}\) werden die Parameter durch
$$a_k=\frac{1}{\sqrt{k+3}},\qquad b_k=a_k+\frac{1}{k^2},\qquad t_k=\frac{1}{k^3},\qquad q_k=1-t_k$$
festgelegt. Gesucht ist die zugehörige Erwartungsgröße dieses gestoppten Prozesses für jedes \(k\) und danach die Summe aller \(48\) Beiträge. Statt eine lange Zufallsdynamik zu simulieren, lösen die Implementierungen eine geschlossene Rekurrenzformel.
Für die Herleitung führt man eine Hilfsgröße \(U_i\) ein, wobei \(i\in\mathbb Z\) den aktuellen Vorsprung von Spieler A bezeichnet. Nach der Bestimmung von \(U_0\) erhält man den tatsächlich ausgegebenen Wert einfach durch Division durch \(q\).
Die Folge \(U_i\) erfülle
$$U_i=\mathbf{1}_{i>0}+q\left(a\,U_{i+1}+b\,U_{i-1}+(1-a-b)U_i\right).$$
Der Indikatorterm liefert genau dann einen Beitrag von \(1\), wenn der aktuelle Vorsprung positiv ist. Diese Normalisierung ist algebraisch nützlich, weil auf beiden Seiten von \(0\) derselbe lineare Operator erscheint. Die endgültige Zielgröße ist dann
$$H(a,b,t)=\frac{U_0}{q}.$$
Setze
$$s=1-a-b,\qquad c=1-q s=t+q(a+b).$$
Dann lässt sich die Rekurrenz als
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=-\mathbf{1}_{i>0}$$
schreiben. Die rechte Seite ist für \(i\le 0\) gleich \(0\) und für \(i\ge 1\) gleich \(-1\), daher behandelt man die nichtpositive und die positive Seite getrennt.
Zum homogenen Teil gehört die Gleichung
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=0.$$
Mit dem Ansatz \(U_i=r^i\) erhält man das charakteristische Polynom
$$q a r^2-c r+q b=0.$$
Die beiden Wurzeln sind
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa}.$$
Die Diskriminante ist in dieser Aufgabenfamilie stets positiv, denn
$$c^2-4q^2ab=\left(t+q(a+b)\right)^2-4q^2ab=t^2+2tq(a+b)+q^2(a-b)^2>0.$$
Somit sind die Wurzeln reell und verschieden. Außerdem gilt beim Einsetzen von \(r=1\)
$$q a-c+q b=-t<0,$$
während für \(r=0\) der Wert \(q b>0\) ist. Also liegt eine Wurzel in \((0,1)\). Wegen
$$\rho_-\rho_+=\frac{b}{a}>1$$
und \(b=a+1/k^2\) für die echten Parameter folgt, dass die andere Wurzel größer als \(1\) sein muss. Daher gilt
$$0<\rho_-<1<\rho_+.$$
Für \(i\le 0\) ist die Rekurrenz homogen. Beschränktheit für \(i\to-\infty\) erzwingt daher
$$U_i=A\,\rho_+^i\qquad (i\le 0).$$
Für \(i\ge 1\) ist die Störgröße konstant. Eine konstante partikuläre Lösung \(U_i\equiv K\) muss
$$K=1+qK$$
erfüllen, also
$$K=\frac{1}{t}.$$
Damit die positive Seite für \(i\to+\infty\) beschränkt bleibt, darf dort nur die fallende Wurzel auftreten:
$$U_i=\frac{1}{t}+B\,\rho_-^i\qquad (i\ge 1).$$
Genau hierin steckt die wesentliche Vereinfachung: links eine reine Exponentiallösung, rechts eine Konstante plus abklingende Exponentialkorrektur.
Nun werden die beiden Teilstücke an der Schnittstelle zusammengefügt. Für \(i=0\) setzt man \(U_0=A\), \(U_{-1}=A/\rho_+\) und \(U_1=1/t+B\rho_-\) ein und erhält
$$A=q\left(a\left(\frac{1}{t}+B\rho_-\right)+b\frac{A}{\rho_+}+sA\right).$$
Mit Hilfe der charakteristischen Gleichung vereinfacht sich das zu
$$A\rho_+=\frac{1}{t}+B\rho_-.$$
Für \(i=1\) folgt aus \(U_1=1/t+B\rho_-\), \(U_2=1/t+B\rho_-^2\) und \(U_0=A\)
$$\frac{1}{t}+B\rho_-=1+q\left(a\left(\frac{1}{t}+B\rho_-^2\right)+bA+s\left(\frac{1}{t}+B\rho_-\right)\right).$$
Nach Abzug der konstanten partikulären Lösung und erneuter Verwendung der charakteristischen Gleichung bleibt
$$B=A-\frac{1}{t}.$$
Einsetzen in die vorige Beziehung liefert
$$A(\rho_+-\rho_-)=\frac{1-\rho_-}{t},$$
also
$$A=\frac{1-\rho_-}{t(\rho_+-\rho_-)}.$$
Da die gesuchte Größe \(H(a,b,t)=U_0/q=A/q\) ist, ergibt sich genau die Formel, die in allen drei Implementierungen verwendet wird:
$$\boxed{H(a,b,t)=\frac{1-\rho_-}{tq(\rho_+-\rho_-)}}$$
mit
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa},\qquad c=t+q(a+b),\qquad q=1-t.$$
Damit lautet die endgültige Antwort
$$\sum_{k=3}^{50} H\left(\frac{1}{\sqrt{k+3}},\ \frac{1}{\sqrt{k+3}}+\frac{1}{k^2},\ \frac{1}{k^3}\right).$$
Ein riesiger stochastischer Prozess wird also auf eine kurze deterministische Rechnung reduziert: pro \(k\) nur eine Quadratwurzel und einige arithmetische Operationen.
Dieser exakte Kontrollfall ist besonders angenehm, weil sich die Terme schön vereinfachen. Hier gilt
$$q=\frac12,\qquad c=t+q(a+b)=\frac12+\frac12\cdot\frac12=\frac34.$$
Die Diskriminante ist
$$c^2-4q^2ab=\frac{9}{16}-4\cdot\frac14\cdot\frac1{16}=\frac12,$$
und daher
$$\rho_-=3-2\sqrt2,\qquad \rho_+=3+2\sqrt2.$$
Somit
$$\rho_+-\rho_-=4\sqrt2,\qquad 1-\rho_-=2(\sqrt2-1).$$
Die geschlossene Formel liefert
$$H\left(\frac14,\frac14,\frac12\right)=\frac{2(\sqrt2-1)}{\frac12\cdot\frac12\cdot4\sqrt2}=2-\sqrt2\approx 0.585786.$$
Genau dieser Wert erscheint als numerischer Kontrollpunkt in den Implementierungen. Für die echte Aufgabenfamilie ist der erste Summand bei \(k=3\) ungefähr \(6.8345\).
Die C++-, Python- und Java-Implementierungen verwenden exakt denselben mathematischen Ablauf. Für jedes \(k\) von \(3\) bis \(50\) werden \(a_k\), \(b_k\) und \(t_k\) aufgebaut, dann \(q_k\), \(c_k\), die Diskriminante und ihre Quadratwurzel berechnet, daraus die kleinere und die größere charakteristische Wurzel bestimmt und schließlich die obige geschlossene Formel ausgewertet.
Es wird weder eine dynamische Programmierung über viele Zustände noch eine Monte-Carlo-Simulation benötigt. Das gesamte Modell ist bereits in die algebraische Formel für \(H(a,b,t)\) kondensiert, daher ist jede Schleifeniteration unabhängig und von konstanter Größe.
Der Unterschied zwischen den drei Sprachen liegt nur in der Zahlendarstellung. C++ verwendet erweiterte Gleitkommaarithmetik, Python arbeitet mit hochpräziser Dezimalarithmetik, und Java nutzt Dezimalarithmetik mit einem hochpräzisen Rechenkontext. Danach werden die \(48\) Beiträge aufsummiert und auf vier Nachkommastellen formatiert.
Die Schleife läuft über genau \(48\) Werte von \(k\). Pro Iteration fallen nur konstant viele Rechenoperationen und eine Quadratwurzel an. Bei fester Präzision ist die Gesamtlaufzeit also \(O(1)\) und der Speicherbedarf \(O(1)\).
Wenn man die Kosten beliebig genauer Arithmetik separat modellieren möchte, bleibt die Quadratwurzel die teuerste Einzeloperation pro Iteration. Für die verlangte Ausgabepräzision ist das in der Praxis jedoch vernachlässigbar klein.
Üç uygulama da satranç maçını tek boyutlu bir liderlik sürecine indirger. Oyuncu A'nın mevcut farkı \(i\) ise, bir turun ardından bu fark \(a\) olasılığıyla \(i+1\), \(b\) olasılığıyla \(i-1\) olur ve \(1-a-b\) olasılığıyla değişmeden kalır. Bundan bağımsız olarak süreç, turdan sonra \(q=1-t\) olasılığıyla devam eder; burada \(t\) durma olasılığıdır.
Her \(k\in\{3,4,\dots,50\}\) için parametreler
$$a_k=\frac{1}{\sqrt{k+3}},\qquad b_k=a_k+\frac{1}{k^2},\qquad t_k=\frac{1}{k^3},\qquad q_k=1-t_k$$
şeklindedir. Amaç, bu durdurulmuş yürüyüşe bağlı beklenen liderlik büyüklüğünü her \(k\) için hesaplayıp toplamaktır. Uygulamalar uzun maçları simüle etmez; bunun yerine kapalı formda çözülen tek bir reküransı her parametre setine uygular.
Türetmeyi temizleştirmek için \(i\in\mathbb Z\) anlık liderlik farkını gösterirken bir yardımcı durum değeri \(U_i\) tanımlanır. \(U_0\) bulunduktan sonra uygulamaların bastığı gerçek değer, yalnızca \(q\)'ya bölünerek elde edilir.
\(U_i\) şu eşitliği sağlasın:
$$U_i=\mathbf{1}_{i>0}+q\left(a\,U_{i+1}+b\,U_{i-1}+(1-a-b)U_i\right).$$
Gösterge terimi, mevcut fark pozitif olduğunda bir birim katkı yapar. Bu normalizasyon kullanışlıdır; çünkü sıfırın her iki tarafında da aynı doğrusal operatör kalır. Sonunda ihtiyaç duyulan büyüklük
$$H(a,b,t)=\frac{U_0}{q}$$
olacaktır.
Şimdi
$$s=1-a-b,\qquad c=1-q s=t+q(a+b)$$
tanımlarını yapalım. Rekürans böylece
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=-\mathbf{1}_{i>0}$$
biçimine dönüşür. Sağ taraf \(i\le 0\) için \(0\), \(i\ge 1\) için \(-1\) olduğundan problem doğal olarak iki bölgeye ayrılır.
Homojen denklem
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=0$$
olur. \(U_i=r^i\) denenirse karakteristik polinom
$$q a r^2-c r+q b=0$$
elde edilir. Kökler
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa}$$
şeklindedir. Diskriminant bu problem ailesinde daima pozitiftir, çünkü
$$c^2-4q^2ab=\left(t+q(a+b)\right)^2-4q^2ab=t^2+2tq(a+b)+q^2(a-b)^2>0.$$
Yani iki farklı reel kök vardır. Ayrıca polinom \(r=1\) için
$$q a-c+q b=-t<0$$
değerini, \(r=0\) için ise \(q b>0\) değerini alır; dolayısıyla bir kök \((0,1)\) aralığındadır. Üstelik
$$\rho_-\rho_+=\frac{b}{a}>1$$
olduğundan ve gerçek parametrelerde \(b=a+1/k^2\) olduğundan, diğer kök zorunlu olarak \(1\)'den büyüktür. Sonuç:
$$0<\rho_-<1<\rho_+.$$
\(i\le 0\) için denklem homojendir. \(i\to-\infty\) giderken sınırlı kalmak için yalnızca \(1\)'den büyük kökü kullanmak gerekir:
$$U_i=A\,\rho_+^i\qquad (i\le 0).$$
\(i\ge 1\) için sağ tarafta sabit bir zorlayıcı terim vardır. Sabit bir özel çözüm \(U_i\equiv K\) alırsak
$$K=1+qK$$
olmalı, dolayısıyla
$$K=\frac{1}{t}.$$
Pozitif tarafta \(i\to+\infty\) iken büyümemesi için yalnızca sönümlenen kök tutulur:
$$U_i=\frac{1}{t}+B\,\rho_-^i\qquad (i\ge 1).$$
Temel sadeleşme tam olarak budur: solda tek bir üstel kol, sağda ise sabit artı sönümlenen üstel düzeltme.
Şimdi iki parçayı arayüzde birleştiririz. \(i=0\) için \(U_0=A\), \(U_{-1}=A/\rho_+\), \(U_1=1/t+B\rho_-\) yazılırsa
$$A=q\left(a\left(\frac{1}{t}+B\rho_-\right)+b\frac{A}{\rho_+}+sA\right)$$
elde edilir. Karakteristik denklemle sadeleştirildiğinde bu
$$A\rho_+=\frac{1}{t}+B\rho_-$$
halini alır. \(i=1\) için ise
$$\frac{1}{t}+B\rho_-=1+q\left(a\left(\frac{1}{t}+B\rho_-^2\right)+bA+s\left(\frac{1}{t}+B\rho_-\right)\right)$$
yazılır. Sabit özel çözüm çıkarılıp yine karakteristik denklem kullanıldığında
$$B=A-\frac{1}{t}$$
kalır. Bunu önceki bağıntıya koyunca
$$A(\rho_+-\rho_-)=\frac{1-\rho_-}{t}$$
ve dolayısıyla
$$A=\frac{1-\rho_-}{t(\rho_+-\rho_-)}$$
bulunur.
İstenen büyüklük \(H(a,b,t)=U_0/q=A/q\) olduğundan, üç uygulamanın da kullandığı tam ifade
$$\boxed{H(a,b,t)=\frac{1-\rho_-}{tq(\rho_+-\rho_-)}}$$
olur. Burada
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa},\qquad c=t+q(a+b),\qquad q=1-t.$$
Problemin nihai cevabı da
$$\sum_{k=3}^{50} H\left(\frac{1}{\sqrt{k+3}},\ \frac{1}{\sqrt{k+3}}+\frac{1}{k^2},\ \frac{1}{k^3}\right)$$
şeklindedir. Böylece çok uzun sürebilecek stokastik süreç, her \(k\) için yalnızca bir karekök ve birkaç aritmetik işlemle biten kısa bir deterministik hesaba dönüşür.
Bu tam kontrol örneği özellikle faydalıdır; çünkü cebir güzelce sadeleşir. Burada
$$q=\frac12,\qquad c=t+q(a+b)=\frac12+\frac12\cdot\frac12=\frac34.$$
Diskriminant
$$c^2-4q^2ab=\frac{9}{16}-4\cdot\frac14\cdot\frac1{16}=\frac12$$
olur ve kökler
$$\rho_-=3-2\sqrt2,\qquad \rho_+=3+2\sqrt2$$
çıkar. O halde
$$\rho_+-\rho_-=4\sqrt2,\qquad 1-\rho_-=2(\sqrt2-1).$$
Kapalı forma yerleştirince
$$H\left(\frac14,\frac14,\frac12\right)=\frac{2(\sqrt2-1)}{\frac12\cdot\frac12\cdot4\sqrt2}=2-\sqrt2\approx 0.585786$$
elde edilir. Bu değer uygulamalardaki sayısal kontrol noktasıyla aynıdır. Gerçek problem ailesinde ise son toplamın ilk terimi, yani \(k=3\) için katkı, yaklaşık \(6.8345\)'tir.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. \(k=3\) ile \(50\) arasındaki her değer için önce \(a_k\), \(b_k\), \(t_k\) hesaplanır; sonra \(q_k\), \(c_k\), diskriminant ve onun karekökü bulunur; küçük ve büyük karakteristik kökler çıkarılır; son olarak yukarıdaki kapalı form değerlendirilir.
Burada ne büyük bir dinamik programlama tablosu vardır ne de Monte Carlo benzetimi. Tüm maç modeli önceden \(H(a,b,t)\) ifadesine sıkıştırıldığı için her döngü adımı bağımsız ve sabit boyutludur.
Diller arasındaki fark algoritmada değil, sayısal hassasiyettedir. C++ genişletilmiş kayan nokta türü kullanır, Python yüksek hassasiyetli ondalık aritmetik kullanır, Java ise yüksek hassasiyetli bir ondalık bağlam kullanır. Üçü de \(48\) terimi toplar ve sonucu dört ondalık basamakla biçimlendirir.
Döngü tam olarak \(48\) adet \(k\) değeri için çalışır. Her adımda sabit sayıda aritmetik işlem ve bir karekök vardır. Sabit hassasiyet altında toplam çalışma süresi \(O(1)\), bellek kullanımı da \(O(1)\)'dir.
İstenirse keyfi hassasiyetli aritmetiğin maliyeti ayrıca modellenebilir; o durumda da baskın işlem her iterasyondaki karekök olur. Fakat gerekli çıktı hassasiyetinde bu maliyet pratikte çok küçüktür.
Las tres implementaciones reducen la partida a un proceso unidimensional de ventaja. Si la ventaja actual del jugador A es \(i\), entonces tras una ronda pasa a \(i+1\) con probabilidad \(a\), a \(i-1\) con probabilidad \(b\), y permanece en \(i\) con probabilidad \(1-a-b\). De manera independiente, el proceso continúa con probabilidad \(q=1-t\), donde \(t\) es la probabilidad de detenerse.
Para cada \(k\in\{3,4,\dots,50\}\), los parámetros son
$$a_k=\frac{1}{\sqrt{k+3}},\qquad b_k=a_k+\frac{1}{k^2},\qquad t_k=\frac{1}{k^3},\qquad q_k=1-t_k.$$
La tarea consiste en evaluar la cantidad esperada asociada a este paseo detenido para cada \(k\) y después sumar los \(48\) valores. No hace falta simular partidas largas: las implementaciones resuelven una recurrencia cerrada y la reutilizan para todos los parámetros.
La derivación más limpia introduce un valor auxiliar \(U_i\), donde \(i\in\mathbb Z\) representa la ventaja actual de A. Una vez calculado \(U_0\), el valor que imprimen las implementaciones se obtiene simplemente dividiendo por \(q\).
Definimos \(U_i\) por
$$U_i=\mathbf{1}_{i>0}+q\left(a\,U_{i+1}+b\,U_{i-1}+(1-a-b)U_i\right).$$
El indicador aporta una unidad exactamente cuando la ventaja actual es positiva. Esta normalización es útil porque deja el mismo operador lineal a ambos lados de \(0\). La cantidad final será
$$H(a,b,t)=\frac{U_0}{q}.$$
Introducimos
$$s=1-a-b,\qquad c=1-q s=t+q(a+b).$$
Entonces la ecuación puede escribirse como
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=-\mathbf{1}_{i>0}.$$
El lado derecho vale \(0\) cuando \(i\le 0\) y \(-1\) cuando \(i\ge 1\), de modo que el problema se separa naturalmente en dos regiones.
La recurrencia homogénea es
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=0.$$
Si probamos con \(U_i=r^i\), obtenemos el polinomio característico
$$q a r^2-c r+q b=0.$$
Sus dos raíces son
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa}.$$
El discriminante siempre es positivo en esta familia, porque
$$c^2-4q^2ab=\left(t+q(a+b)\right)^2-4q^2ab=t^2+2tq(a+b)+q^2(a-b)^2>0.$$
Por tanto, las raíces son reales y distintas. Además, al evaluar el polinomio en \(r=1\) obtenemos
$$q a-c+q b=-t<0,$$
mientras que en \(r=0\) vale \(q b>0\). Así, una raíz está en \((0,1)\). Como
$$\rho_-\rho_+=\frac{b}{a}>1$$
y en el problema real \(b=a+1/k^2\), la otra raíz debe ser mayor que \(1\). En resumen,
$$0<\rho_-<1<\rho_+.$$
Para \(i\le 0\), la recurrencia es homogénea. La condición de acotación cuando \(i\to-\infty\) obliga a usar solo la raíz mayor que \(1\):
$$U_i=A\,\rho_+^i\qquad (i\le 0).$$
Para \(i\ge 1\), el término de fuerza es constante. Si buscamos una solución particular constante \(U_i\equiv K\), debe cumplir
$$K=1+qK,$$
de donde
$$K=\frac{1}{t}.$$
Para que la solución siga acotada cuando \(i\to+\infty\), solo se conserva la raíz decreciente:
$$U_i=\frac{1}{t}+B\,\rho_-^i\qquad (i\ge 1).$$
Esta es la simplificación clave: una rama exponencial pura a la izquierda y una constante más una corrección exponencial decreciente a la derecha.
Ahora imponemos la ecuación en los puntos de interfaz. En \(i=0\), al sustituir \(U_0=A\), \(U_{-1}=A/\rho_+\) y \(U_1=1/t+B\rho_-\), resulta
$$A=q\left(a\left(\frac{1}{t}+B\rho_-\right)+b\frac{A}{\rho_+}+sA\right).$$
Usando la ecuación característica para simplificar coeficientes, esto se reduce a
$$A\rho_+=\frac{1}{t}+B\rho_-.$$
En \(i=1\), con \(U_1=1/t+B\rho_-\), \(U_2=1/t+B\rho_-^2\) y \(U_0=A\), obtenemos
$$\frac{1}{t}+B\rho_-=1+q\left(a\left(\frac{1}{t}+B\rho_-^2\right)+bA+s\left(\frac{1}{t}+B\rho_-\right)\right).$$
Tras restar la solución particular constante y simplificar otra vez con la ecuación característica, queda
$$B=A-\frac{1}{t}.$$
Al sustituirlo en la relación anterior se obtiene
$$A(\rho_+-\rho_-)=\frac{1-\rho_-}{t},$$
y por tanto
$$A=\frac{1-\rho_-}{t(\rho_+-\rho_-)}.$$
Como la cantidad buscada es \(H(a,b,t)=U_0/q=A/q\), llegamos exactamente a la expresión usada por las tres implementaciones:
$$\boxed{H(a,b,t)=\frac{1-\rho_-}{tq(\rho_+-\rho_-)}}$$
con
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa},\qquad c=t+q(a+b),\qquad q=1-t.$$
La respuesta final del problema es entonces
$$\sum_{k=3}^{50} H\left(\frac{1}{\sqrt{k+3}},\ \frac{1}{\sqrt{k+3}}+\frac{1}{k^2},\ \frac{1}{k^3}\right).$$
Así, un proceso estocástico potencialmente enorme se convierte en un cálculo determinista muy corto: una raíz cuadrada y unas pocas operaciones aritméticas por cada \(k\).
Este punto de control exacto es muy útil porque la cuenta se simplifica de forma elegante. Aquí
$$q=\frac12,\qquad c=t+q(a+b)=\frac12+\frac12\cdot\frac12=\frac34.$$
El discriminante vale
$$c^2-4q^2ab=\frac{9}{16}-4\cdot\frac14\cdot\frac1{16}=\frac12,$$
y por tanto
$$\rho_-=3-2\sqrt2,\qquad \rho_+=3+2\sqrt2.$$
Luego
$$\rho_+-\rho_-=4\sqrt2,\qquad 1-\rho_-=2(\sqrt2-1).$$
Al sustituir en la forma cerrada, obtenemos
$$H\left(\frac14,\frac14,\frac12\right)=\frac{2(\sqrt2-1)}{\frac12\cdot\frac12\cdot4\sqrt2}=2-\sqrt2\approx 0.585786.$$
Ese valor coincide con el control numérico incluido en las implementaciones. Para la familia real del problema, el primer término de la suma final, correspondiente a \(k=3\), es aproximadamente \(6.8345\).
Las implementaciones en C++, Python y Java siguen exactamente la misma secuencia matemática. Para cada \(k\) entre \(3\) y \(50\), construyen \(a_k\), \(b_k\) y \(t_k\); calculan \(q_k\), \(c_k\), el discriminante y su raíz cuadrada; forman la raíz característica pequeña y la grande; y evalúan la forma cerrada anterior.
No se usa ni programación dinámica sobre un gran espacio de estados ni simulación Monte Carlo. Todo el comportamiento del modelo ya quedó comprimido en la expresión algebraica \(H(a,b,t)\), así que cada iteración del bucle es independiente y de tamaño constante.
La diferencia entre lenguajes está en la precisión numérica, no en el algoritmo. La versión en C++ utiliza coma flotante extendida, la versión en Python usa aritmética decimal de alta precisión y la versión en Java emplea aritmética decimal con un contexto de precisión alta. Las tres acumulan los \(48\) términos y formatean el total con cuatro decimales.
El bucle recorre exactamente \(48\) valores de \(k\). Cada iteración realiza un número fijo de operaciones aritméticas y una raíz cuadrada, así que con precisión fija el tiempo total es \(O(1)\) y la memoria usada es \(O(1)\).
Si se desea modelar explícitamente el coste de la aritmética de precisión arbitraria, la operación dominante sigue siendo la raíz cuadrada en cada iteración. Para la precisión decimal exigida por la respuesta final, el coste práctico es mínimo.
这三份实现都把这场“长棋赛”抽象成一个一维领先差过程。若当前 A 的领先差为 \(i\)，那么下一轮之后它会以概率 \(a\) 变成 \(i+1\)，以概率 \(b\) 变成 \(i-1\)，以概率 \(1-a-b\) 保持不变。与此同时，过程还会以概率 \(q=1-t\) 继续到下一轮，其中 \(t\) 是每轮的停止概率。
对每个 \(k\in\{3,4,\dots,50\}\)，参数取为
$$a_k=\frac{1}{\sqrt{k+3}},\qquad b_k=a_k+\frac{1}{k^2},\qquad t_k=\frac{1}{k^3},\qquad q_k=1-t_k.$$
题目要我们对每个 \(k\) 计算这个被截断随机过程对应的期望领先量，然后把全部 \(48\) 项加起来。实现的关键点不是模拟漫长比赛，而是把问题压缩成一个可以直接求闭式的线性递推。
最顺手的推导方式，是先引入一个辅助状态值 \(U_i\)，其中 \(i\in\mathbb Z\) 表示当前 A 的领先差。求出 \(U_0\) 之后，程序真正输出的量只需要再除以 \(q\) 即可。
定义 \(U_i\) 满足
$$U_i=\mathbf{1}_{i>0}+q\left(a\,U_{i+1}+b\,U_{i-1}+(1-a-b)U_i\right).$$
这里的指示项表示：只有当当前领先差是正数时，才贡献 \(1\) 个单位。这样的归一化有一个直接好处，就是零点两侧都由同一个线性算子控制。最后要求的值是
$$H(a,b,t)=\frac{U_0}{q}.$$
记
$$s=1-a-b,\qquad c=1-q s=t+q(a+b).$$
则递推式可以改写成
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=-\mathbf{1}_{i>0}.$$
这说明右端在 \(i\le 0\) 时为 \(0\)，在 \(i\ge 1\) 时为 \(-1\)。因此，自然要把零左侧和零右侧分开求解，再在边界处拼接。
先看齐次递推
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=0.$$
设 \(U_i=r^i\)，得到特征多项式
$$q a r^2-c r+q b=0.$$
因此两个特征根为
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa}.$$
在本题的参数族中，判别式总是正的，因为
$$c^2-4q^2ab=\left(t+q(a+b)\right)^2-4q^2ab=t^2+2tq(a+b)+q^2(a-b)^2>0.$$
所以这两个根不仅是实数，而且彼此不同。再看多项式在 \(r=1\) 时的值：
$$q a-c+q b=-t<0,$$
而在 \(r=0\) 时它等于 \(q b>0\)。这说明必有一个根落在 \((0,1)\) 内。另一方面，根的乘积满足
$$\rho_-\rho_+=\frac{b}{a}>1,$$
而题目中的参数又有 \(b=a+1/k^2\)，故另一根必然大于 \(1\)。于是可以明确地写成
$$0<\rho_-<1<\rho_+.$$
当 \(i\le 0\) 时，递推右端为 \(0\)，因此只需要解齐次方程。为了让解在 \(i\to-\infty\) 时保持有界，只能保留大于 \(1\) 的那个根：
$$U_i=A\,\rho_+^i\qquad (i\le 0).$$
当 \(i\ge 1\) 时，右端恒为 \(-1\)，因此需要一个常数特解。若取 \(U_i\equiv K\)，代入原式可得
$$K=1+qK,$$
于是
$$K=\frac{1}{t}.$$
为了让正半轴上的解在 \(i\to+\infty\) 时不发散，只保留衰减的那个根：
$$U_i=\frac{1}{t}+B\,\rho_-^i\qquad (i\ge 1).$$
这就是整个推导的结构核心：左边是一条纯指数解，右边是一条“常数 + 衰减指数”的解。
接下来要把两边的解拼接起来。对 \(i=0\)，代入 \(U_0=A\)、\(U_{-1}=A/\rho_+\)、\(U_1=1/t+B\rho_-\)，得到
$$A=q\left(a\left(\frac{1}{t}+B\rho_-\right)+b\frac{A}{\rho_+}+sA\right).$$
利用特征方程化简系数后，可整理成
$$A\rho_+=\frac{1}{t}+B\rho_-.$$
再对 \(i=1\) 代入 \(U_1=1/t+B\rho_-\)、\(U_2=1/t+B\rho_-^2\)、\(U_0=A\)，可得
$$\frac{1}{t}+B\rho_-=1+q\left(a\left(\frac{1}{t}+B\rho_-^2\right)+bA+s\left(\frac{1}{t}+B\rho_-\right)\right).$$
把常数特解部分减掉，再利用一次特征方程，最终会化成非常简单的关系
$$B=A-\frac{1}{t}.$$
把它代回上一式，就有
$$A(\rho_+-\rho_-)=\frac{1-\rho_-}{t},$$
因此
$$A=\frac{1-\rho_-}{t(\rho_+-\rho_-)}.$$
因为真正需要的量是 \(H(a,b,t)=U_0/q=A/q\)，于是直接得到三份实现共同使用的闭式：
$$\boxed{H(a,b,t)=\frac{1-\rho_-}{tq(\rho_+-\rho_-)}}$$
其中
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa},\qquad c=t+q(a+b),\qquad q=1-t.$$
这样一来，题目的最终答案就是
$$\sum_{k=3}^{50} H\left(\frac{1}{\sqrt{k+3}},\ \frac{1}{\sqrt{k+3}}+\frac{1}{k^2},\ \frac{1}{k^3}\right).$$
原本可能非常长的随机过程，被压缩成了 \(48\) 次短小的确定性计算。每个 \(k\) 只需要一次平方根和少量四则运算。
这个检验例非常适合作为人工核对，因为公式会明显简化。此时
$$q=\frac12,\qquad c=t+q(a+b)=\frac12+\frac12\cdot\frac12=\frac34.$$
判别式为
$$c^2-4q^2ab=\frac{9}{16}-4\cdot\frac14\cdot\frac1{16}=\frac12,$$
因此两根是
$$\rho_-=3-2\sqrt2,\qquad \rho_+=3+2\sqrt2.$$
于是
$$\rho_+-\rho_-=4\sqrt2,\qquad 1-\rho_-=2(\sqrt2-1).$$
代回闭式得到
$$H\left(\frac14,\frac14,\frac12\right)=\frac{2(\sqrt2-1)}{\frac12\cdot\frac12\cdot4\sqrt2}=2-\sqrt2\approx 0.585786.$$
这与实现中的数值校验完全一致。对题目真正的参数族来说，最终总和的第一项，也就是 \(k=3\) 对应的项，约为 \(6.8345\)。
C++、Python 和 Java 三份实现遵循完全相同的数学流程。对每个 \(k=3,4,\dots,50\)，它们先生成 \(a_k\)、\(b_k\)、\(t_k\)；再计算 \(q_k\)、\(c_k\)、判别式及其平方根；随后构造较小和较大的两个特征根；最后把这些量代入上面的闭式并累加到总答案中。
整个过程中没有建立大型动态规划表，也没有进行随机模拟。因为所有随机行为已经在推导中被压缩进 \(H(a,b,t)\) 这个公式，所以每一轮循环都只是固定规模的代数计算。
三种语言之间真正的差别只是数值精度策略。C++ 使用扩展浮点精度，Python 使用高精度十进制运算，Java 使用高精度十进制上下文。三者最后都把 \(48\) 项求和，并按四位小数输出结果。
循环只处理固定的 \(48\) 个 \(k\) 值。每次迭代只做常数次算术运算和一次平方根，因此在固定精度下，总时间复杂度是 \(O(1)\)，空间复杂度也是 \(O(1)\)。
如果要把高精度十进制运算的代价单独计入，那么每轮最重的操作依旧是平方根。不过本题只需要最终输出四位小数，因此实际计算量极小。
Все три реализации сводят длинный матч к одномерному процессу лидерства. Если текущий перевес игрока A равен \(i\), то после одного раунда он становится \(i+1\) с вероятностью \(a\), \(i-1\) с вероятностью \(b\), а с вероятностью \(1-a-b\) не меняется. Независимо от этого процесс продолжается в следующий раунд с вероятностью \(q=1-t\), где \(t\) — вероятность остановки.
Для каждого \(k\in\{3,4,\dots,50\}\) параметры задаются формулами
$$a_k=\frac{1}{\sqrt{k+3}},\qquad b_k=a_k+\frac{1}{k^2},\qquad t_k=\frac{1}{k^3},\qquad q_k=1-t_k.$$
Нужно вычислить соответствующую ожидаемую величину для этого остановленного процесса при каждом \(k\), а затем сложить все \(48\) значений. Реализации не моделируют длинные партии напрямую; вместо этого они выводят замкнутую формулу из линейной рекуррентности.
Для удобства вывода вводится вспомогательная величина \(U_i\), где \(i\in\mathbb Z\) обозначает текущий перевес игрока A. После нахождения \(U_0\) искомое значение, которое печатают реализации, получается простым делением на \(q\).
Пусть \(U_i\) удовлетворяет соотношению
$$U_i=\mathbf{1}_{i>0}+q\left(a\,U_{i+1}+b\,U_{i-1}+(1-a-b)U_i\right).$$
Индикатор даёт вклад \(1\) ровно тогда, когда текущий перевес положителен. Такая нормировка удобна тем, что по обе стороны от нуля остаётся один и тот же линейный оператор. В конце понадобится величина
$$H(a,b,t)=\frac{U_0}{q}.$$
Обозначим
$$s=1-a-b,\qquad c=1-q s=t+q(a+b).$$
Тогда рекуррентность переписывается как
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=-\mathbf{1}_{i>0}.$$
Правая часть равна \(0\) при \(i\le 0\) и \(-1\) при \(i\ge 1\), поэтому задачу естественно решать отдельно на неположительной и положительной полуосях.
Однородная часть имеет вид
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=0.$$
Если подставить \(U_i=r^i\), получится характеристический многочлен
$$q a r^2-c r+q b=0.$$
Его корни равны
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa}.$$
Дискриминант в этой задаче всегда положителен, поскольку
$$c^2-4q^2ab=\left(t+q(a+b)\right)^2-4q^2ab=t^2+2tq(a+b)+q^2(a-b)^2>0.$$
Значит, корни вещественные и различны. Кроме того, в точке \(r=1\) многочлен равен
$$q a-c+q b=-t<0,$$
а в точке \(r=0\) он равен \(q b>0\). Следовательно, один корень лежит в интервале \((0,1)\). Поскольку
$$\rho_-\rho_+=\frac{b}{a}>1$$
и в реальных параметрах \(b=a+1/k^2\), второй корень обязан быть больше \(1\). Поэтому
$$0<\rho_-<1<\rho_+.$$
При \(i\le 0\) правая часть равна нулю, то есть нужно решать однородное уравнение. Чтобы решение оставалось ограниченным при \(i\to-\infty\), надо оставить только корень, больший \(1\):
$$U_i=A\,\rho_+^i\qquad (i\le 0).$$
При \(i\ge 1\) правая часть постоянна, поэтому сначала ищется постоянное частное решение \(U_i\equiv K\). Подстановка даёт
$$K=1+qK,$$
откуда
$$K=\frac{1}{t}.$$
Чтобы на положительной полуоси решение не росло при \(i\to+\infty\), сохраняется только затухающая ветвь:
$$U_i=\frac{1}{t}+B\,\rho_-^i\qquad (i\ge 1).$$
Это и есть ключевое структурное упрощение: слева чистая экспонента, справа постоянная плюс затухающая экспоненциальная поправка.
Теперь нужно сшить оба куска. Для \(i=0\) подставляем \(U_0=A\), \(U_{-1}=A/\rho_+\), \(U_1=1/t+B\rho_-\) и получаем
$$A=q\left(a\left(\frac{1}{t}+B\rho_-\right)+b\frac{A}{\rho_+}+sA\right).$$
После упрощения с помощью характеристического уравнения это превращается в
$$A\rho_+=\frac{1}{t}+B\rho_-.$$
Для \(i=1\) используем \(U_1=1/t+B\rho_-\), \(U_2=1/t+B\rho_-^2\), \(U_0=A\) и получаем
$$\frac{1}{t}+B\rho_-=1+q\left(a\left(\frac{1}{t}+B\rho_-^2\right)+bA+s\left(\frac{1}{t}+B\rho_-\right)\right).$$
Если вычесть постоянное частное решение и ещё раз воспользоваться характеристическим уравнением, останется простая связь
$$B=A-\frac{1}{t}.$$
Подставляя её обратно, получаем
$$A(\rho_+-\rho_-)=\frac{1-\rho_-}{t},$$
а значит
$$A=\frac{1-\rho_-}{t(\rho_+-\rho_-)}.$$
Так как искомая величина равна \(H(a,b,t)=U_0/q=A/q\), получаем точную формулу, которую используют все три реализации:
$$\boxed{H(a,b,t)=\frac{1-\rho_-}{tq(\rho_+-\rho_-)}}$$
где
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa},\qquad c=t+q(a+b),\qquad q=1-t.$$
Следовательно, окончательный ответ задачи равен
$$\sum_{k=3}^{50} H\left(\frac{1}{\sqrt{k+3}},\ \frac{1}{\sqrt{k+3}}+\frac{1}{k^2},\ \frac{1}{k^3}\right).$$
Тем самым очень длинный случайный процесс заменяется коротким детерминированным вычислением: одна квадратная корень и несколько арифметических операций на каждое \(k\).
Этот контрольный пример особенно удобен, потому что выражения красиво упрощаются. Здесь
$$q=\frac12,\qquad c=t+q(a+b)=\frac12+\frac12\cdot\frac12=\frac34.$$
Дискриминант равен
$$c^2-4q^2ab=\frac{9}{16}-4\cdot\frac14\cdot\frac1{16}=\frac12,$$
поэтому
$$\rho_-=3-2\sqrt2,\qquad \rho_+=3+2\sqrt2.$$
Отсюда
$$\rho_+-\rho_-=4\sqrt2,\qquad 1-\rho_-=2(\sqrt2-1).$$
Подстановка в закрытую формулу даёт
$$H\left(\frac14,\frac14,\frac12\right)=\frac{2(\sqrt2-1)}{\frac12\cdot\frac12\cdot4\sqrt2}=2-\sqrt2\approx 0.585786.$$
Это совпадает с численной проверкой, присутствующей в реализациях. Для реальной параметрической семьи первая добавка в итоговую сумму, соответствующая \(k=3\), примерно равна \(6.8345\).
Реализации на C++, Python и Java используют один и тот же математический конвейер. Для каждого \(k\) от \(3\) до \(50\) они вычисляют \(a_k\), \(b_k\), \(t_k\), затем находят \(q_k\), \(c_k\), дискриминант и его квадратный корень, строят меньший и больший характеристические корни и подставляют их в приведённую выше замкнутую формулу.
Никакого большого динамического программирования и никакого Монте-Карло здесь нет. Всё вероятностное поведение уже сжато в алгебраическое выражение \(H(a,b,t)\), поэтому каждая итерация цикла независима и имеет постоянный размер.
Различие между языками касается только численной точности, а не самого алгоритма. Версия на C++ использует расширенную плавающую точку, версия на Python — высокоточную десятичную арифметику, а версия на Java — десятичную арифметику с высокоточным контекстом. После этого все три реализации суммируют \(48\) вкладов и форматируют результат до четырёх знаков после запятой.
Цикл проходит ровно по \(48\) значениям \(k\). В каждой итерации выполняется фиксированное число арифметических операций и одна квадратная корень, поэтому при фиксированной точности общее время работы равно \(O(1)\), а память — \(O(1)\).
Если отдельно учитывать стоимость арифметики произвольной точности, то самой дорогой операцией всё равно остаётся квадратный корень в каждой итерации. Для требуемой точности итогового вывода эта стоимость на практике очень мала.
تختزل التطبيقات الثلاثة المباراة الطويلة إلى عملية أحادية البعد تمثل فارق التقدم. إذا كان تقدم اللاعب A يساوي حاليًا \(i\)، فإنه بعد جولة واحدة يصبح \(i+1\) باحتمال \(a\)، ويصبح \(i-1\) باحتمال \(b\)، ويبقى كما هو باحتمال \(1-a-b\). وبصورة مستقلة، تستمر العملية إلى الجولة التالية باحتمال \(q=1-t\)، حيث تمثل \(t\) احتمال التوقف في كل جولة.
لكل \(k\in\{3,4,\dots,50\}\) تكون المعلمات
$$a_k=\frac{1}{\sqrt{k+3}},\qquad b_k=a_k+\frac{1}{k^2},\qquad t_k=\frac{1}{k^3},\qquad q_k=1-t_k.$$
المطلوب هو حساب كمية التوقع المرتبطة بهذه المسيرة المتوقفة لكل قيمة من \(k\)، ثم جمع القيم الثماني والأربعين كلها. لا تعتمد التطبيقات على محاكاة مباريات طويلة، بل تحل علاقة رجوعية مغلقة ثم تعيد استخدامها لكل مجموعة معلمات.
لجعل الاشتقاق أوضح، نعرّف قيمة مساعدة \(U_i\)، حيث إن \(i\in\mathbb Z\) يمثل فارق التقدم الحالي لصالح A. وبعد إيجاد \(U_0\)، نحصل على القيمة التي تطبعها التطبيقات بقسمة بسيطة على \(q\).
نعرّف \(U_i\) بحيث تحقق
$$U_i=\mathbf{1}_{i>0}+q\left(a\,U_{i+1}+b\,U_{i-1}+(1-a-b)U_i\right).$$
يعطي حد المؤشر مساهمة مقدارها \(1\) فقط عندما يكون فارق التقدم الحالي موجبًا. هذه الموازنة مفيدة جبريًا لأنها تُبقي المؤثر الخطي نفسه على جانبي الصفر. أما الكمية النهائية فهي
$$H(a,b,t)=\frac{U_0}{q}.$$
لنكتب
$$s=1-a-b,\qquad c=1-q s=t+q(a+b).$$
عندها تصبح العلاقة
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=-\mathbf{1}_{i>0}.$$
الطرف الأيمن يساوي \(0\) عندما \(i\le 0\)، ويساوي \(-1\) عندما \(i\ge 1\)، ولذلك تنقسم المسألة طبيعيًا إلى جانب غير موجب وجانب موجب.
الجزء المتجانس هو
$$q a\,U_{i+1}-c\,U_i+q b\,U_{i-1}=0.$$
وباستخدام الفرض \(U_i=r^i\) نحصل على كثير الحدود المميز
$$q a r^2-c r+q b=0.$$
وجذراه هما
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa}.$$
المميز موجب دائمًا في هذه العائلة من المعلمات، لأن
$$c^2-4q^2ab=\left(t+q(a+b)\right)^2-4q^2ab=t^2+2tq(a+b)+q^2(a-b)^2>0.$$
إذًا الجذور حقيقية ومتميزة. كما أن قيمة كثير الحدود عند \(r=1\) هي
$$q a-c+q b=-t<0,$$
بينما قيمته عند \(r=0\) هي \(q b>0\). ومن ثم يوجد أحد الجذرين داخل الفترة \((0,1)\). ولأن
$$\rho_-\rho_+=\frac{b}{a}>1$$
ومعلمات المسألة الفعلية تحقق \(b=a+1/k^2\)، فلا بد أن يكون الجذر الآخر أكبر من \(1\). وبالتالي
$$0<\rho_-<1<\rho_+.$$
عندما \(i\le 0\)، يكون الطرف الأيمن صفرًا، أي إننا نحل معادلة متجانسة. ولكي يبقى الحل محدودًا عند \(i\to-\infty\)، يجب الاحتفاظ فقط بالجذر الأكبر من \(1\):
$$U_i=A\,\rho_+^i\qquad (i\le 0).$$
أما عندما \(i\ge 1\)، فهناك حد قسري ثابت. إذا بحثنا عن حل خاص ثابت \(U_i\equiv K\)، فيجب أن يحقق
$$K=1+qK,$$
ومنها
$$K=\frac{1}{t}.$$
ولكي يبقى الحل على الجهة الموجبة محدودًا عندما \(i\to+\infty\)، نحتفظ فقط بالجذر المتناقص:
$$U_i=\frac{1}{t}+B\,\rho_-^i\qquad (i\ge 1).$$
هذه هي البنية الأساسية للحل: فرع أسي صرف على اليسار، وثابت مضاف إليه تصحيح أسي متناقص على اليمين.
الآن نربط الجزأين عند نقطتي الواجهة. عند \(i=0\)، وبالتعويض \(U_0=A\)، و\(U_{-1}=A/\rho_+\)، و\(U_1=1/t+B\rho_-\)، نحصل على
$$A=q\left(a\left(\frac{1}{t}+B\rho_-\right)+b\frac{A}{\rho_+}+sA\right).$$
وباستخدام المعادلة المميزة لتبسيط المعاملات، تتحول هذه العلاقة إلى
$$A\rho_+=\frac{1}{t}+B\rho_-.$$
وعند \(i=1\)، نعوض \(U_1=1/t+B\rho_-\)، و\(U_2=1/t+B\rho_-^2\)، و\(U_0=A\)، فنجد
$$\frac{1}{t}+B\rho_-=1+q\left(a\left(\frac{1}{t}+B\rho_-^2\right)+bA+s\left(\frac{1}{t}+B\rho_-\right)\right).$$
بعد طرح الحل الخاص الثابت ثم استخدام المعادلة المميزة مرة أخرى، نحصل على العلاقة البسيطة
$$B=A-\frac{1}{t}.$$
وبالتعويض في العلاقة السابقة يصبح لدينا
$$A(\rho_+-\rho_-)=\frac{1-\rho_-}{t},$$
ومن ثم
$$A=\frac{1-\rho_-}{t(\rho_+-\rho_-)}.$$
بما أن الكمية المطلوبة هي \(H(a,b,t)=U_0/q=A/q\)، نحصل بالضبط على الصيغة التي تعتمدها التطبيقات الثلاثة:
$$\boxed{H(a,b,t)=\frac{1-\rho_-}{tq(\rho_+-\rho_-)}}$$
حيث
$$\rho_{\pm}=\frac{c\pm\sqrt{c^2-4q^2ab}}{2qa},\qquad c=t+q(a+b),\qquad q=1-t.$$
وعليه فإن جواب المسألة النهائي هو
$$\sum_{k=3}^{50} H\left(\frac{1}{\sqrt{k+3}},\ \frac{1}{\sqrt{k+3}}+\frac{1}{k^2},\ \frac{1}{k^3}\right).$$
وهكذا تتحول عملية عشوائية طويلة جدًا إلى حساب حتمي قصير: جذر تربيعي واحد وعدة عمليات حسابية لكل قيمة من \(k\).
هذه الحالة الاختبارية مفيدة جدًا لأن الجبر فيها يتبسط بصورة جميلة. لدينا هنا
$$q=\frac12,\qquad c=t+q(a+b)=\frac12+\frac12\cdot\frac12=\frac34.$$
ومن ثم يكون المميز
$$c^2-4q^2ab=\frac{9}{16}-4\cdot\frac14\cdot\frac1{16}=\frac12,$$
فتكون الجذور
$$\rho_-=3-2\sqrt2,\qquad \rho_+=3+2\sqrt2.$$
وبالتالي
$$\rho_+-\rho_-=4\sqrt2,\qquad 1-\rho_-=2(\sqrt2-1).$$
بالتعويض في الصيغة المغلقة نحصل على
$$H\left(\frac14,\frac14,\frac12\right)=\frac{2(\sqrt2-1)}{\frac12\cdot\frac12\cdot4\sqrt2}=2-\sqrt2\approx 0.585786.$$
وهذه القيمة تطابق نقطة التحقق العددية الموجودة داخل التطبيقات. أما في عائلة المعلمات الفعلية للمسألة، فإن الحد الأول في المجموع النهائي، أي عند \(k=3\)، يساوي تقريبًا \(6.8345\).
تتبع تطبيقات C++ وPython وJava خط الأنابيب الرياضي نفسه تمامًا. فلكل \(k\) من \(3\) إلى \(50\)، تبني القيم \(a_k\) و\(b_k\) و\(t_k\)، ثم تحسب \(q_k\) و\(c_k\) والمميز وجذره التربيعي، وبعد ذلك تستخرج الجذر الأصغر والجذر الأكبر للمعادلة المميزة، وأخيرًا تعوضها كلها في الصيغة المغلقة السابقة.
لا حاجة هنا إلى برمجة ديناميكية على فضاء حالات كبير، ولا إلى محاكاة مونت كارلو. فكل السلوك الاحتمالي للنموذج قد اختُزل مسبقًا في التعبير الجبري \(H(a,b,t)\)، ولذلك تكون كل دورة من الحلقة مستقلة وثابتة الحجم.
الاختلاف بين اللغات الثلاث ليس في الخوارزمية بل في أسلوب التعامل مع الدقة العددية. نسخة C++ تستخدم دقة فاصلة عائمة موسعة، ونسخة Python تستخدم حسابًا عشريًا عالي الدقة، ونسخة Java تستخدم حسابًا عشريًا بسياق دقة مرتفع. ثم تجمع النسخ الثلاث الحدود الثمانية والأربعين وتطبع الناتج بأربع منازل عشرية.
تعمل الحلقة على \(48\) قيمة ثابتة فقط من \(k\). وفي كل دورة توجد مجموعة ثابتة من العمليات الحسابية بالإضافة إلى جذر تربيعي واحد. لذلك، عند ثبات الدقة، يكون الزمن الكلي \(O(1)\) ويكون استهلاك الذاكرة \(O(1)\).
وإذا أردنا احتساب كلفة الحساب العشري عالي الدقة صراحة، فستبقى العملية الأغلى في كل دورة هي استخراج الجذر التربيعي. لكن عند مستوى الدقة المطلوب في الناتج النهائي، تبقى الكلفة العملية صغيرة جدًا.