Stone Game IV studies a one-heap take-away game controlled by a real parameter \(r\). On the opening turn, a player may remove any positive number of stones except the whole heap. After a move of size \(x\), the next player may remove at most \(r x\) stones. For each fixed \(r\), some starting heap sizes are losing positions, meaning the player to move has no winning strategy. These losing positions form an increasing sequence, and that sequence changes only when \(r\) crosses certain rational thresholds. The problem asks for the \(123456\)th value in the increasing threshold sequence obtained by starting from \(r_1=1\) and repeatedly jumping to the next larger transition.
The implementation does not search whole game trees. Instead it tracks how the losing-position sequence depends on \(r\), then extracts the next threshold where that sequence must change.
For a fixed \(r\), let \(w_r(n)\) be the smallest opening move that wins from a heap of size \(n\). If no winning opening move exists, define \(w_r(n)=n\). With this convention, \(n\) is a losing position exactly when
$$w_r(n)=n.$$
The recursion comes directly from the move rule. If the current player removes \(k\) stones, the opponent faces \(n-k\) stones and may remove at most \(r k\). That move is winning exactly when the opponent has no winning reply of size at most \(r k\). Since the opponent's smallest winning reply from \(n-k\) stones is \(w_r(n-k)\), we obtain
$$w_r(1)=1,\qquad w_r(n)=\min\left\{1\le k\le n:\; r k<w_r(n-k)\right\}\quad (n\ge 2).$$
The value \(k=n\) is a sentinel: it means every legal opening move \(1\le k\le n-1\) fails, so \(n\) is losing.
Let
$$L_1=1<L_2=2<L_3<L_4<\cdots$$
be the increasing sequence of losing starting heaps. If a move of size \(k\) leaves \(L_j\) stones, then that move is winning precisely when
$$r k<L_j,$$
because \(L_j\) itself has no winning reply smaller than \(L_j\). Therefore the profitable gaps after \(L_j\) are exactly the earlier losing positions whose size is still strictly below \(L_j/r\).
Suppose \(L_1,\dots,L_{i-1}\) are already known. Define \(d_i\) as the largest lag such that
$$\frac{L_{i-1}}{L_{i-d_i}}\le r.$$
Equivalently, \(L_{i-d_i}\) is the smallest earlier losing position that is at least \(L_{i-1}/r\). Then the next losing position is
$$L_i=L_{i-1}+L_{i-d_i}.$$
Why does this work? Every smaller earlier losing position \(L_t\) with \(L_t<L_{i-1}/r\) gives a winning move from \(L_{i-1}+L_t\): remove \(L_t\) stones and leave the losing heap \(L_{i-1}\), while the reply bound \(rL_t\) is still too small to unlock a winning response. The first earlier losing position that fails this inequality is exactly the gap where the winning block ends, so adding that gap produces the next losing heap.
For a fixed \(r\), the lag \(d_i\) stays unchanged until one more earlier losing position becomes admissible. The critical value for step \(i\) is therefore
$$c_i=\frac{L_{i-1}}{L_{i-(d_i+1)}},$$
whenever \(d_i<i-1\). Crossing \(c_i\) makes the next smaller denominator available, so the recurrence changes. Hence the next global transition above \(r\) is
$$T(r)=\min\left\{c_i:\; d_i<i-1,\ c_i>r\right\}.$$
This is the key observation behind the solver: build the losing sequence for the current threshold, record every candidate fraction just above \(r\), and keep the smallest one.
Start with \(L_1=1\) and \(L_2=2\).
For \(L_3\), the largest admissible lag is \(d_3=2\) because
$$\frac{L_2}{L_1}=\frac{2}{1}=2\le 2.$$
So
$$L_3=L_2+L_1=3.$$
For \(L_4\), we have
$$\frac{L_3}{L_2}=\frac{3}{2}\le 2,\qquad \frac{L_3}{L_1}=3>2,$$
so \(d_4=2\) and
$$L_4=L_3+L_2=5.$$
Next,
$$\frac{L_4}{L_3}=\frac{5}{3}\le 2,\qquad \frac{L_4}{L_2}=\frac{5}{2}>2,$$
which gives
$$L_5=L_4+L_3=8.$$
Continuing in the same way yields
$$1,2,3,5,8,13,\dots,$$
so the losing positions are the Fibonacci numbers. The transition candidates visible in these first steps are
$$c_4=3,\qquad c_5=\frac{5}{2},\qquad c_6=\frac{8}{3},\dots$$
The smallest candidate strictly above \(2\) is \(5/2\), therefore
$$T(2)=\frac{5}{2}.$$
Likewise, when \(r=1\), the recurrence doubles every term and the losing positions become \(1,2,4,8,\dots\), so the first transition is \(T(1)=2\).
The implementation stores the current threshold as an exact reduced fraction. For one transition evaluation, it generates the losing-position sequence only up to a finite horizon \(M\). A monotone lag pointer is advanced while the inequality \(L_{i-1}/L_{i-d}\le r\) remains true, so each new term is produced in amortized constant time. At the same moment, the implementation also forms the critical fraction \(L_{i-1}/L_{i-(d+1)}\) and keeps the smallest candidate that is strictly larger than the current threshold.
All fraction comparisons are done by exact cross-multiplication, avoiding floating-point error. Sequence growth is protected by overflow checks before every addition. Because the decisive transition might occur beyond the initial horizon, the implementation repeats the computation with larger and larger horizons until the same best candidate reappears far enough before the end of the computed region. That stabilization test makes the returned fraction reliable without pretending that a short finite prefix is automatically sufficient.
Finally, the transition map is iterated from
$$r_1=1,\qquad r_{m+1}=T(r_m),$$
until \(m=123456\). The C++, Python, and Java solutions all expose this same exact recurrence-based computation, and built-in checkpoints verify early values such as \(r_2=2\) and \(r_{22}=145/23\).
For a fixed horizon \(M\), one transition evaluation performs \(O(M)\) arithmetic operations and stores \(O(M)\) sequence values. The lag pointer only moves forward, so the inner search is amortized linear rather than quadratic. If \(M_{\mathrm{eff}}(r)\) is the final stabilized horizon needed for threshold \(r\), then a single transition costs \(O(M_{\mathrm{eff}}(r))\) time and \(O(M_{\mathrm{eff}}(r))\) memory. Reaching the target index therefore costs
$$O\left(\sum_{m=1}^{123455} M_{\mathrm{eff}}(r_m)\right)$$
time and
$$O\left(\max_m M_{\mathrm{eff}}(r_m)\right)$$
memory. In practice, the method is efficient because it follows only the recurrence of losing positions and the exact transition fractions, not the full game tree.
Stone Game IV behandelt ein Ein-Haufen-Spiel mit einem reellen Parameter \(r\). Im ersten Zug darf man eine positive Anzahl Steine wegnehmen, aber nicht den ganzen Haufen. Nach einem Zug der Größe \(x\) darf der nächste Spieler höchstens \(r x\) Steine entfernen. Für festes \(r\) gibt es Startgrößen, die Verlustpositionen sind, also Stellungen ohne Gewinnstrategie für den Spieler am Zug. Diese Verlustpositionen bilden eine wachsende Folge, und diese Folge ändert sich nur dann, wenn \(r\) bestimmte rationale Schwellen überschreitet. Gesucht ist der \(123456\)-te Wert der steigenden Schwellenfolge, wenn man bei \(r_1=1\) beginnt und immer zur nächsten größeren Übergangsschwelle springt.
Die Lösung durchsucht nicht den gesamten Spielbaum. Stattdessen beschreibt sie, wie die Folge der Verlustpositionen von \(r\) abhängt, und liest daraus die nächste Schwelle ab, an der sich diese Folge ändern muss.
Für festes \(r\) sei \(w_r(n)\) der kleinste Eröffnungszug, der bei einem Haufen der Größe \(n\) gewinnt. Falls kein gewinnender Eröffnungszug existiert, setzen wir \(w_r(n)=n\). Dann ist \(n\) genau dann eine Verlustposition, wenn
$$w_r(n)=n.$$
Die Rekursion folgt direkt aus der Zugregel. Nimmt der aktuelle Spieler \(k\) Steine, dann sieht der Gegner \(n-k\) Steine und darf höchstens \(r k\) Steine entfernen. Der Zug ist genau dann gewinnend, wenn der Gegner keinen gewinnenden Antwortzug mit Größe höchstens \(r k\) besitzt. Da der kleinste gewinnende Antwortzug bei \(n-k\) Steinen gleich \(w_r(n-k)\) ist, gilt
$$w_r(1)=1,\qquad w_r(n)=\min\left\{1\le k\le n:\; r k<w_r(n-k)\right\}\quad (n\ge 2).$$
Der Wert \(k=n\) dient nur als Markierung: Er bedeutet, dass jeder legale Eröffnungszug \(1\le k\le n-1\) scheitert und \(n\) daher verliert.
Sei
$$L_1=1<L_2=2<L_3<L_4<\cdots$$
die wachsende Folge der Verlustpositionen. Wenn ein Zug der Größe \(k\) genau \(L_j\) Steine übrig lässt, dann ist dieser Zug genau dann gewinnend, wenn
$$r k<L_j,$$
denn bei \(L_j\) gibt es keinen gewinnenden Antwortzug unterhalb von \(L_j\). Deshalb sind die gewinnenden Abstände hinter \(L_j\) genau die früheren Verlustpositionen, deren Größe noch strikt unter \(L_j/r\) liegt.
Angenommen, \(L_1,\dots,L_{i-1}\) sind bekannt. Definiere \(d_i\) als den größten Versatz mit
$$\frac{L_{i-1}}{L_{i-d_i}}\le r.$$
Äquivalent dazu ist \(L_{i-d_i}\) die kleinste frühere Verlustposition, die mindestens \(L_{i-1}/r\) groß ist. Dann lautet die Rekurrenz
$$L_i=L_{i-1}+L_{i-d_i}.$$
Der Grund ist einfach: Jede kleinere frühere Verlustposition \(L_t\) mit \(L_t<L_{i-1}/r\) liefert einen Gewinnzug aus \(L_{i-1}+L_t\), denn man entfernt \(L_t\) Steine, lässt \(L_{i-1}\) liegen und der Antwortspielraum \(rL_t\) reicht noch nicht für einen gewinnenden Gegenzug. Die erste frühere Verlustposition, bei der diese Ungleichung nicht mehr gilt, markiert also genau das Ende dieses Gewinnblocks und damit die nächste Verlustposition.
Für festes \(r\) bleibt der Versatz \(d_i\) so lange konstant, bis eine weitere frühere Verlustposition zugelassen wird. Der kritische Wert zu Schritt \(i\) ist deshalb
$$c_i=\frac{L_{i-1}}{L_{i-(d_i+1)}},$$
sofern \(d_i<i-1\) gilt. Beim Überschreiten von \(c_i\) wird der nächstkleinere Nenner zulässig, und die Rekurrenz ändert sich. Also ist der nächste globale Übergang oberhalb von \(r\)
$$T(r)=\min\left\{c_i:\; d_i<i-1,\ c_i>r\right\}.$$
Genau das nutzt der Algorithmus: Er baut die Verlustfolge für das aktuelle \(r\), sammelt alle Kandidaten knapp oberhalb von \(r\) und wählt den kleinsten.
Man startet mit \(L_1=1\) und \(L_2=2\).
Für \(L_3\) ist der größte zulässige Versatz \(d_3=2\), denn
$$\frac{L_2}{L_1}=\frac{2}{1}=2\le 2.$$
Daher
$$L_3=L_2+L_1=3.$$
Für \(L_4\) gilt
$$\frac{L_3}{L_2}=\frac{3}{2}\le 2,\qquad \frac{L_3}{L_1}=3>2,$$
also \(d_4=2\) und damit
$$L_4=L_3+L_2=5.$$
Danach folgt
$$\frac{L_4}{L_3}=\frac{5}{3}\le 2,\qquad \frac{L_4}{L_2}=\frac{5}{2}>2,$$
also
$$L_5=L_4+L_3=8.$$
So entsteht die Folge
$$1,2,3,5,8,13,\dots,$$
also genau die Fibonacci-Folge. Die zugehörigen Übergangskandidaten sind hier
$$c_4=3,\qquad c_5=\frac{5}{2},\qquad c_6=\frac{8}{3},\dots$$
Der kleinste Kandidat strikt oberhalb von \(2\) ist \(5/2\), also
$$T(2)=\frac{5}{2}.$$
Für \(r=1\) verdoppelt die Rekurrenz dagegen jeden Schritt, sodass \(1,2,4,8,\dots\) entsteht und \(T(1)=2\) gilt.
Die Implementierung hält die aktuelle Schwelle als exakt gekürzten Bruch. Für eine einzelne Übergangsberechnung wird die Folge der Verlustpositionen nur bis zu einem endlichen Horizont \(M\) erzeugt. Ein monoton wachsender Versatzzeiger wird so lange erhöht, wie \(L_{i-1}/L_{i-d}\le r\) bleibt; dadurch kostet jede neue Folgenglied-Erzeugung amortisiert nur konstante Zeit. Gleichzeitig wird auch der kritische Bruch \(L_{i-1}/L_{i-(d+1)}\) gebildet und der kleinste Kandidat strikt oberhalb der aktuellen Schwelle gespeichert.
Alle Bruchvergleiche laufen über exakte Kreuzmultiplikation, nicht über Gleitkommazahlen. Vor jeder Addition wird außerdem auf Überlauf geprüft. Weil der entscheidende Übergang auch jenseits des ersten Horizonts liegen kann, wird die Rechnung mit größeren und größeren Horizonten wiederholt, bis derselbe beste Kandidat erneut auftaucht und zugleich genügend Abstand zum Rand des berechneten Bereichs hat. Diese Stabilitätsprüfung verhindert, dass ein zu kurzer Präfix fälschlich als vollständig interpretiert wird.
Am Ende wird die Übergangsfunktion
$$r_1=1,\qquad r_{m+1}=T(r_m)$$
so oft iteriert, bis \(m=123456\) erreicht ist. Die C++-, Python- und Java-Lösungen geben alle dieselbe exakte Rekurrenzrechnung wieder; eingebaute Kontrollwerte prüfen unter anderem \(r_2=2\) und \(r_{22}=145/23\).
Für einen festen Horizont \(M\) benötigt eine Übergangsberechnung \(O(M)\) arithmetische Operationen und \(O(M)\) Speicher für die Folgenglieder. Da sich der Versatzzeiger nur vorwärts bewegt, bleibt die innere Suche amortisiert linear statt quadratisch. Bezeichnet \(M_{\mathrm{eff}}(r)\) den letztlich stabilen Horizont für die Schwelle \(r\), dann kostet ein einzelner Übergang \(O(M_{\mathrm{eff}}(r))\) Zeit und \(O(M_{\mathrm{eff}}(r))\) Speicher. Für das Ziel \(123456\) ergibt sich damit
$$O\left(\sum_{m=1}^{123455} M_{\mathrm{eff}}(r_m)\right)$$
Zeit und
$$O\left(\max_m M_{\mathrm{eff}}(r_m)\right)$$
Speicher. Praktisch ist das Verfahren schnell, weil nur die Verlustfolgen-Rekurrenz und die exakten Übergangsbrüche verfolgt werden, nicht der vollständige Spielbaum.
Stone Game IV, \(r\) adlı reel bir parametreye bağlı tek yığınlı bir taş alma oyununu inceler. İlk hamlede oyuncu pozitif sayıda taş alabilir ama tüm yığını alamaz. Bir oyuncu \(x\) taş aldıktan sonra sıradaki oyuncu en fazla \(r x\) taş alabilir. Sabit bir \(r\) için bazı başlangıç yığınları kayıp konumdur; yani sıra kendisinde olan oyuncunun kazanan bir stratejisi yoktur. Bu kayıp konumlar artan bir dizi oluşturur ve bu dizi yalnızca \(r\) bazı rasyonel eşiklerin üzerine çıktığında değişir. Soru, \(r_1=1\) ile başlayıp her adımda bir sonraki daha büyük geçiş değerine sıçrayınca elde edilen artan eşik dizisinin \(123456\). terimini istemektedir.
Çözüm tüm oyun ağacını taramaz. Bunun yerine kayıp konumlar dizisinin \(r\)'ye nasıl bağlı olduğunu çıkarır ve bu dizinin değişmek zorunda olduğu bir sonraki eşiği hesaplar.
Sabit bir \(r\) için \(w_r(n)\), \(n\) taşlık yığından kazanmayı sağlayan en küçük açılış hamlesi olsun. Eğer böyle bir açılış hamlesi yoksa \(w_r(n)=n\) tanımını yapalım. Bu durumda \(n\) tam ve ancak
$$w_r(n)=n$$
olduğunda kayıp konumdur.
Özyineleme doğrudan oyun kuralından gelir. Mevcut oyuncu \(k\) taş alırsa rakip \(n-k\) taş görür ve en fazla \(r k\) taş alabilir. Bu hamle, rakibin boyutu en fazla \(r k\) olan hiçbir kazandıran cevabı yoksa kazandırır. Rakibin \(n-k\) taş üzerindeki en küçük kazandıran cevabı \(w_r(n-k)\) olduğuna göre
$$w_r(1)=1,\qquad w_r(n)=\min\left\{1\le k\le n:\; r k<w_r(n-k)\right\}\quad (n\ge 2)$$
elde edilir. Buradaki \(k=n\) yalnızca işaret amaçlıdır: \(1\le k\le n-1\) aralığındaki tüm yasal açılış hamleleri başarısızsa sonuç \(w_r(n)=n\) olur ve bu da kayıp konumu gösterir.
Şimdi
$$L_1=1<L_2=2<L_3<L_4<\cdots$$
artan kayıp başlangıç yığınları olsun. Boyutu \(k\) olan bir hamle tam olarak \(L_j\) taş bırakıyorsa, bu hamle ancak
$$r k<L_j$$
ise kazandırır; çünkü \(L_j\) üzerinde \(L_j\)'den küçük hiçbir kazandıran karşılık yoktur. Dolayısıyla \(L_j\)'den sonraki kazandıran boşluklar, büyüklüğü hâlâ \(L_j/r\)'nin altında kalan daha eski kayıp konumlardır.
\(L_1,\dots,L_{i-1}\) biliniyor olsun. Şimdi
$$\frac{L_{i-1}}{L_{i-d_i}}\le r$$
koşulunu sağlayan en büyük gecikmeyi \(d_i\) olarak tanımlayalım. Eşdeğer biçimde, \(L_{i-d_i}\), \(L_{i-1}/r\)'den küçük olmayan en küçük önceki kayıp konumdur. O zaman bir sonraki kayıp konum
$$L_i=L_{i-1}+L_{i-d_i}$$
olur. Bunun nedeni şudur: \(L_t<L_{i-1}/r\) sağlayan her daha küçük eski kayıp konum \(L_t\), \(L_{i-1}+L_t\) değerinden kazandıran bir açılış hamlesi verir. Oyuncu \(L_t\) taş alıp \(L_{i-1}\) bırakır ve cevap sınırı \(rL_t\) hâlâ rakibe kazandıran bir cevap açacak kadar büyük değildir. Bu eşitsizliği ilk kez bozan önceki kayıp konum ise kazanç bloğunun bittiği noktayı, dolayısıyla bir sonraki kayıp konumu verir.
Sabit bir \(r\) için \(d_i\) değeri, bir başka eski kayıp konum daha uygun hâle gelene kadar değişmez. Bu yüzden \(i\). adımın kritik eşiği
$$c_i=\frac{L_{i-1}}{L_{i-(d_i+1)}}$$
olur; tabii \(d_i<i-1\) ise. \(r\) bu değeri aşınca bir önceki daha küçük payda da kullanılabilir hâle gelir ve rekürans değişir. O halde \(r\)'nin üstündeki bir sonraki genel geçiş
$$T(r)=\min\left\{c_i:\; d_i<i-1,\ c_i>r\right\}$$
şeklindedir. Çözümün özünde bu fikir vardır: geçerli eşik için kayıp konumlar dizisini üret, \(r\)'nin hemen üstündeki bütün aday kesirleri topla ve en küçüğünü seç.
\(L_1=1\) ve \(L_2=2\) ile başlayalım.
\(L_3\) için en büyük uygun gecikme \(d_3=2\)'dir, çünkü
$$\frac{L_2}{L_1}=\frac{2}{1}=2\le 2.$$
Bu yüzden
$$L_3=L_2+L_1=3.$$
\(L_4\) için
$$\frac{L_3}{L_2}=\frac{3}{2}\le 2,\qquad \frac{L_3}{L_1}=3>2$$
olduğundan \(d_4=2\) ve
$$L_4=L_3+L_2=5$$
elde edilir. Sonra
$$\frac{L_4}{L_3}=\frac{5}{3}\le 2,\qquad \frac{L_4}{L_2}=\frac{5}{2}>2$$
olur ve
$$L_5=L_4+L_3=8$$
bulunur. Böylece dizi
$$1,2,3,5,8,13,\dots$$
şeklinde başlar; yani kayıp konumlar Fibonacci sayılarıdır. Bu ilk adımlardaki geçiş adayları
$$c_4=3,\qquad c_5=\frac{5}{2},\qquad c_6=\frac{8}{3},\dots$$
olur. \(2\)'den büyük en küçük aday \(5/2\) olduğundan
$$T(2)=\frac{5}{2}.$$
Aynı şekilde \(r=1\) iken rekürans her adımı iki katına çıkarır; kayıp konumlar \(1,2,4,8,\dots\) olur ve ilk geçiş \(T(1)=2\) çıkar.
Uygulama mevcut eşiği sadeleştirilmiş tam bir kesir olarak tutar. Tek bir geçiş hesabı için kayıp konumlar dizisi yalnızca sonlu bir \(M\) ufkuna kadar üretilir. Tek yönlü ilerleyen bir gecikme işaretçisi, \(L_{i-1}/L_{i-d}\le r\) eşitsizliği sürdükçe artırılır; bu nedenle her yeni terim amortize sabit zamanda gelir. Aynı anda kritik kesir \(L_{i-1}/L_{i-(d+1)}\) de hesaplanır ve mevcut eşikten kesin olarak büyük en küçük aday saklanır.
Bütün kesir karşılaştırmaları kayan nokta yerine tam sayı çapraz çarpımıyla yapılır. Her toplama öncesinde taşma riski de kontrol edilir. Belirleyici geçiş ilk ufkun ötesinde olabilir; bu yüzden uygulama ufku tekrar tekrar büyütür ve aynı en iyi aday hesaplanan aralığın sonundan yeterince uzakta yeniden görülene kadar devam eder. Bu kararlılık denetimi, kısa bir ön ekin sonsuz davranışı temsil ettiği varsayımından kaçınır.
Son aşamada
$$r_1=1,\qquad r_{m+1}=T(r_m)$$
dönüşümü \(m=123456\) olana kadar yinelenir. C++, Python ve Java çözümleri aynı tam rekürans hesabını sunar; yerleşik doğrulamalar arasında \(r_2=2\) ve \(r_{22}=145/23\) gibi erken kontrol değerleri de vardır.
Sabit \(M\) ufku için tek bir geçiş hesabı \(O(M)\) aritmetik işlem yapar ve \(O(M)\) tane dizi değeri saklar. Gecikme işaretçisi sadece ileri gittiği için iç arama karesel değil, amortize lineerdir. Eğer \(M_{\mathrm{eff}}(r)\), \(r\) eşiği için gereken son kararlı ufuk ise, tek bir geçişin maliyeti \(O(M_{\mathrm{eff}}(r))\) zaman ve \(O(M_{\mathrm{eff}}(r))\) bellektir. Hedef değere ulaşmanın toplam maliyeti
$$O\left(\sum_{m=1}^{123455} M_{\mathrm{eff}}(r_m)\right)$$
zaman ve
$$O\left(\max_m M_{\mathrm{eff}}(r_m)\right)$$
bellektir. Pratikte yöntem hızlıdır; çünkü tüm oyun ağacını değil, sadece kayıp konum reküransını ve tam geçiş kesirlerini izler.
Stone Game IV estudia un juego de una sola pila controlado por un parámetro real \(r\). En la jugada inicial se puede retirar cualquier cantidad positiva de piedras salvo toda la pila. Después de una jugada de tamaño \(x\), el siguiente jugador puede retirar como máximo \(r x\) piedras. Para cada \(r\) fijo existen tamaños iniciales que son posiciones perdedoras, es decir, estados en los que el jugador al turno no tiene estrategia ganadora. Esas posiciones perdedoras forman una sucesión creciente, y la sucesión solo cambia cuando \(r\) cruza ciertos umbrales racionales. El problema pide el término \(123456\) de la sucesión creciente de umbrales obtenida al empezar con \(r_1=1\) y saltar repetidamente al siguiente valor de transición.
La idea no es explorar árboles completos de juego. En cambio, se describe cómo depende de \(r\) la sucesión de posiciones perdedoras y, a partir de ella, se identifica el siguiente umbral en el que esa sucesión debe cambiar.
Para un \(r\) fijo, sea \(w_r(n)\) la menor jugada inicial que gana desde una pila de tamaño \(n\). Si no existe una apertura ganadora, definimos \(w_r(n)=n\). Con esta convención, \(n\) es una posición perdedora exactamente cuando
$$w_r(n)=n.$$
La recurrencia sale directamente de la regla del juego. Si el jugador actual retira \(k\) piedras, el rival ve \(n-k\) piedras y puede quitar como máximo \(r k\). Esa jugada es ganadora exactamente cuando el rival no dispone de respuesta ganadora de tamaño a lo sumo \(r k\). Como la menor respuesta ganadora del rival desde \(n-k\) piedras es \(w_r(n-k)\), resulta
$$w_r(1)=1,\qquad w_r(n)=\min\left\{1\le k\le n:\; r k<w_r(n-k)\right\}\quad (n\ge 2).$$
El caso \(k=n\) es solo una marca técnica: significa que todas las aperturas legales \(1\le k\le n-1\) fallan y, por tanto, \(n\) es perdedora.
Sea
$$L_1=1<L_2=2<L_3<L_4<\cdots$$
la sucesión creciente de tamaños iniciales perdedores. Si una jugada de tamaño \(k\) deja exactamente \(L_j\) piedras, entonces esa jugada es ganadora si y solo si
$$r k<L_j,$$
porque en \(L_j\) no existe respuesta ganadora menor que \(L_j\). Por eso, los huecos ganadores que aparecen después de \(L_j\) son precisamente las posiciones perdedoras anteriores cuyo tamaño todavía es estrictamente menor que \(L_j/r\).
Supongamos conocidos \(L_1,\dots,L_{i-1}\). Definimos \(d_i\) como el mayor desfase que cumple
$$\frac{L_{i-1}}{L_{i-d_i}}\le r.$$
Equivale a decir que \(L_{i-d_i}\) es la menor posición perdedora previa que ya alcanza \(L_{i-1}/r\). Entonces la siguiente posición perdedora es
$$L_i=L_{i-1}+L_{i-d_i}.$$
La razón es la siguiente: toda posición perdedora anterior más pequeña \(L_t\) con \(L_t<L_{i-1}/r\) da una jugada ganadora desde \(L_{i-1}+L_t\). Basta retirar \(L_t\) piedras para dejar la pila perdedora \(L_{i-1}\), y el límite de respuesta \(rL_t\) todavía es demasiado pequeño para abrir una réplica ganadora. La primera posición perdedora previa que ya no satisface esa desigualdad marca, exactamente, el final de ese bloque ganador y por ello produce la siguiente posición perdedora.
Para un \(r\) fijo, el desfase \(d_i\) permanece igual hasta que una posición perdedora anterior adicional pasa a ser admisible. El valor crítico del paso \(i\) es, por tanto,
$$c_i=\frac{L_{i-1}}{L_{i-(d_i+1)}},$$
siempre que \(d_i<i-1\). Al cruzar \(c_i\), el denominador inmediatamente menor también entra en juego y la recurrencia cambia. Así, la siguiente transición global por encima de \(r\) es
$$T(r)=\min\left\{c_i:\; d_i<i-1,\ c_i>r\right\}.$$
Ese es el núcleo del método: construir la sucesión de posiciones perdedoras para el umbral actual, registrar todas las fracciones candidatas estrictamente mayores que \(r\) y conservar la menor.
Se empieza con \(L_1=1\) y \(L_2=2\).
Para \(L_3\), el mayor desfase admisible es \(d_3=2\), porque
$$\frac{L_2}{L_1}=\frac{2}{1}=2\le 2.$$
Entonces
$$L_3=L_2+L_1=3.$$
Para \(L_4\) se tiene
$$\frac{L_3}{L_2}=\frac{3}{2}\le 2,\qquad \frac{L_3}{L_1}=3>2,$$
de modo que \(d_4=2\) y
$$L_4=L_3+L_2=5.$$
Después,
$$\frac{L_4}{L_3}=\frac{5}{3}\le 2,\qquad \frac{L_4}{L_2}=\frac{5}{2}>2,$$
por lo que
$$L_5=L_4+L_3=8.$$
La sucesión comienza entonces como
$$1,2,3,5,8,13,\dots,$$
es decir, aparecen los números de Fibonacci. Las primeras fracciones críticas son
$$c_4=3,\qquad c_5=\frac{5}{2},\qquad c_6=\frac{8}{3},\dots$$
La menor fracción estrictamente mayor que \(2\) es \(5/2\), así que
$$T(2)=\frac{5}{2}.$$
De manera análoga, cuando \(r=1\) la recurrencia duplica cada término, las posiciones perdedoras son \(1,2,4,8,\dots\) y la primera transición es \(T(1)=2\).
La implementación guarda el umbral actual como una fracción exacta ya reducida. Para evaluar una sola transición, genera la sucesión de posiciones perdedoras solo hasta un horizonte finito \(M\). Un puntero de desfase monótono se va moviendo mientras siga cumpliéndose \(L_{i-1}/L_{i-d}\le r\), lo que permite producir cada nuevo término en tiempo amortizado constante. Al mismo tiempo, la implementación forma la fracción crítica \(L_{i-1}/L_{i-(d+1)}\) y conserva la menor candidata que sea estrictamente mayor que el umbral actual.
Todas las comparaciones de fracciones se hacen mediante productos cruzados exactos, sin recurrir a coma flotante. Además, antes de cada suma se comprueba el posible desbordamiento. Como la transición decisiva puede aparecer más allá del horizonte inicial, el cálculo se repite con horizontes cada vez mayores hasta que el mismo mejor candidato vuelve a aparecer suficientemente lejos del final de la zona calculada. Esa comprobación de estabilización evita suponer, sin justificación, que un prefijo corto ya representa el comportamiento infinito.
Por último, se itera el mapa
$$r_1=1,\qquad r_{m+1}=T(r_m)$$
hasta llegar a \(m=123456\). Las soluciones en C++, Python y Java exponen la misma computación exacta basada en recurrencias, y las verificaciones incluidas confirman valores tempranos como \(r_2=2\) y \(r_{22}=145/23\).
Para un horizonte fijo \(M\), una evaluación de transición realiza \(O(M)\) operaciones aritméticas y almacena \(O(M)\) valores de la sucesión. El puntero de desfase solo avanza, así que la búsqueda interna es lineal amortizada y no cuadrática. Si \(M_{\mathrm{eff}}(r)\) es el horizonte final estabilizado necesario para el umbral \(r\), entonces una transición cuesta \(O(M_{\mathrm{eff}}(r))\) tiempo y \(O(M_{\mathrm{eff}}(r))\) memoria. Alcanzar el índice objetivo requiere
$$O\left(\sum_{m=1}^{123455} M_{\mathrm{eff}}(r_m)\right)$$
de tiempo y
$$O\left(\max_m M_{\mathrm{eff}}(r_m)\right)$$
de memoria. En la práctica, el método es eficiente porque sigue solo la recurrencia de posiciones perdedoras y las fracciones de transición exactas, no el árbol completo del juego.
Stone Game IV 研究的是一个由实参数 \(r\) 控制的单堆取石游戏。首回合可以取走任意正数颗石子，但不能一次取完整堆。某一回合若玩家取走 \(x\) 颗，那么下一位玩家至多只能取 \(r x\) 颗。对固定的 \(r\) 而言，存在一些起始堆大小是必败态，也就是轮到当前玩家时不存在必胜策略。这些必败态组成一个严格递增序列，而且只有当 \(r\) 穿过某些有理数阈值时，这个序列才会发生变化。题目要求从 \(r_1=1\) 出发，每次跳到下一个更大的转折阈值，求出这条递增阈值序列的第 \(123456\) 项。
实现并不枚举完整博弈树，而是直接研究“必败态序列如何随 \(r\) 变化”，再从中提取出下一个必须发生变化的阈值。
对固定的 \(r\)，记 \(w_r(n)\) 为从 \(n\) 颗石子的起始局面出发时，能够保证获胜的最小首步。如果不存在必胜首步，就约定
$$w_r(n)=n.$$
于是，\(n\) 是必败态当且仅当
$$w_r(n)=n.$$
这个递推关系直接来自游戏规则。当前玩家若先取 \(k\) 颗，则对手面对 \(n-k\) 颗石子，并且最多只能取 \(r k\) 颗。这个首步是必胜的，当且仅当对手没有任何大小不超过 \(r k\) 的必胜回应。而从 \(n-k\) 出发，对手的最小必胜回应恰好是 \(w_r(n-k)\)，因此有
$$w_r(1)=1,\qquad w_r(n)=\min\left\{1\le k\le n:\; r k<w_r(n-k)\right\}\quad (n\ge 2).$$
这里的 \(k=n\) 只是一个哨兵值，含义是所有合法首步 \(1\le k\le n-1\) 都失败了，因此 \(n\) 必败。
记
$$L_1=1<L_2=2<L_3<L_4<\cdots$$
为递增的必败起始堆大小。若某个首步大小为 \(k\)，并且恰好留下 \(L_j\) 颗石子，那么这个首步必胜当且仅当
$$r k<L_j,$$
因为在 \(L_j\) 这个必败态上，不存在任何比 \(L_j\) 更小的必胜回应。所以，在 \(L_j\) 之后能够形成必胜局面的“间隔”正好对应那些仍然严格小于 \(L_j/r\) 的更早必败态。
假设 \(L_1,\dots,L_{i-1}\) 已知。定义 \(d_i\) 为满足
$$\frac{L_{i-1}}{L_{i-d_i}}\le r$$
的最大滞后量。等价地说，\(L_{i-d_i}\) 是第一个不小于 \(L_{i-1}/r\) 的更早必败态。于是下一项满足
$$L_i=L_{i-1}+L_{i-d_i}.$$
原因如下：任何更小的必败态 \(L_t\)，只要满足 \(L_t<L_{i-1}/r\)，就会给出从 \(L_{i-1}+L_t\) 出发的一个必胜首步。当前玩家只需取走 \(L_t\) 颗，把局面留成必败态 \(L_{i-1}\)；同时，对手的上限 \(rL_t\) 还不够大，无法解锁任何获胜回应。第一个不再满足这条不等式的更早必败态，恰好标记了这段必胜区间的终点，因此把它加上去就得到下一项必败态。
当 \(r\) 固定时，滞后量 \(d_i\) 会一直保持不变，直到又有一个更早的必败态变得“可用”。因此第 \(i\) 步对应的临界值是
$$c_i=\frac{L_{i-1}}{L_{i-(d_i+1)}},$$
前提是 \(d_i<i-1\)。一旦 \(r\) 越过 \(c_i\)，更小的那个分母也会进入可选范围，递推式随之改变。因此，高于当前 \(r\) 的下一个全局转移就是
$$T(r)=\min\left\{c_i:\; d_i<i-1,\ c_i>r\right\}.$$
这就是求解器的核心思想：先按当前阈值生成必败态序列，再记录所有严格大于 \(r\) 的临界分数，最后选出其中最小者。
从 \(L_1=1\)、\(L_2=2\) 开始。
计算 \(L_3\) 时，最大的可行滞后量是 \(d_3=2\)，因为
$$\frac{L_2}{L_1}=\frac{2}{1}=2\le 2.$$
所以
$$L_3=L_2+L_1=3.$$
接着计算 \(L_4\)。此时
$$\frac{L_3}{L_2}=\frac{3}{2}\le 2,\qquad \frac{L_3}{L_1}=3>2,$$
因此 \(d_4=2\)，从而
$$L_4=L_3+L_2=5.$$
再往后，
$$\frac{L_4}{L_3}=\frac{5}{3}\le 2,\qquad \frac{L_4}{L_2}=\frac{5}{2}>2,$$
于是
$$L_5=L_4+L_3=8.$$
继续下去可得
$$1,2,3,5,8,13,\dots,$$
也就是说，当 \(r=2\) 时，必败态正好是斐波那契数。前几步产生的临界转移分数为
$$c_4=3,\qquad c_5=\frac{5}{2},\qquad c_6=\frac{8}{3},\dots$$
其中严格大于 \(2\) 的最小值是 \(5/2\)，所以
$$T(2)=\frac{5}{2}.$$
同理，当 \(r=1\) 时，递推会在每一步直接翻倍，必败态变成 \(1,2,4,8,\dots\)，因此第一道转移阈值就是 \(T(1)=2\)。
实现把当前阈值保存为约分后的精确分数。为了求一次转移，它只把必败态序列生成到某个有限视野 \(M\)。一个单调前进的滞后指针会在 \(L_{i-1}/L_{i-d}\le r\) 继续成立时不断右移，因此每生成一个新项的均摊代价都是常数级。同时，程序还会形成临界分数 \(L_{i-1}/L_{i-(d+1)}\)，并保留所有严格大于当前阈值的候选值中最小的一个。
所有分数比较都通过整数交叉相乘完成，不依赖浮点数，因此不会引入舍入误差。每次新项相加之前，也会先做溢出保护。由于真正决定结果的转移分数可能出现在初始视野之后，程序会不断扩大视野，直到同一个最佳候选再次出现，并且它离当前已计算区间的末端已经足够远。这个“稳定化”判据的作用，是避免把一个过短的有限前缀误当成整个无限过程的真实答案。
最后再反复迭代
$$r_1=1,\qquad r_{m+1}=T(r_m),$$
直到 \(m=123456\)。C++、Python 和 Java 三种实现对外呈现的是同一套精确递推计算，内置校验也验证了早期值，例如 \(r_2=2\) 与 \(r_{22}=145/23\)。
在固定视野 \(M\) 下，单次转移评估需要 \(O(M)\) 次算术操作，并保存 \(O(M)\) 个序列值。由于滞后指针只会单向前移，内部搜索是均摊线性的，而不是平方级。若把某个阈值 \(r\) 所需的最终稳定视野记为 \(M_{\mathrm{eff}}(r)\)，那么一次转移的代价就是 \(O(M_{\mathrm{eff}}(r))\) 时间和 \(O(M_{\mathrm{eff}}(r))\) 空间。到达目标下标的总时间复杂度为
$$O\left(\sum_{m=1}^{123455} M_{\mathrm{eff}}(r_m)\right),$$
空间复杂度为
$$O\left(\max_m M_{\mathrm{eff}}(r_m)\right).$$
在实际计算中，这个方法之所以可行，是因为它只跟踪必败态递推和精确转移分数，而不是展开完整的博弈树。
Stone Game IV рассматривает игру с одной кучей камней, зависящую от вещественного параметра \(r\). На первом ходу можно взять любое положительное число камней, кроме всей кучи целиком. Если игрок взял \(x\) камней, то следующий игрок может взять не более \(r x\) камней. Для фиксированного \(r\) некоторые стартовые размеры кучи являются проигрышными позициями, то есть у игрока на ходу нет выигрышной стратегии. Эти проигрышные размеры образуют возрастающую последовательность, и она меняется только тогда, когда \(r\) пересекает специальные рациональные пороги. Требуется найти \(123456\)-й элемент возрастающей последовательности порогов, если начать с \(r_1=1\) и каждый раз переходить к следующему большему значению перехода.
Решение не перебирает полный игровой граф. Вместо этого оно описывает, как последовательность проигрышных позиций зависит от \(r\), и из этого извлекает следующий порог, при котором такая последовательность обязана измениться.
Для фиксированного \(r\) обозначим через \(w_r(n)\) минимальный первый ход, который выигрывает из кучи размера \(n\). Если выигрышного первого хода нет, по соглашению положим \(w_r(n)=n\). Тогда \(n\) является проигрышной позицией тогда и только тогда, когда
$$w_r(n)=n.$$
Рекурсия следует прямо из правила игры. Если текущий игрок снимает \(k\) камней, то соперник получает кучу из \(n-k\) камней и может снять не более \(r k\). Такой ход выигрышен тогда и только тогда, когда у соперника нет выигрышного ответа размера не больше \(r k\). Поскольку минимальный выигрышный ответ из состояния \(n-k\) равен \(w_r(n-k)\), имеем
$$w_r(1)=1,\qquad w_r(n)=\min\left\{1\le k\le n:\; r k<w_r(n-k)\right\}\quad (n\ge 2).$$
Значение \(k=n\) играет роль технического маркера: оно означает, что все легальные первые ходы \(1\le k\le n-1\) проигрывают, а значит, \(n\) само является проигрышной позицией.
Пусть
$$L_1=1<L_2=2<L_3<L_4<\cdots$$
это возрастающая последовательность проигрышных стартовых куч. Если ход размера \(k\) оставляет ровно \(L_j\) камней, то он выигрышен в точности при условии
$$r k<L_j,$$
потому что у позиции \(L_j\) нет выигрышного ответа меньшего размера. Следовательно, выигрышные промежутки после \(L_j\) соответствуют именно тем более ранним проигрышным позициям, чья величина всё ещё строго меньше \(L_j/r\).
Предположим, что \(L_1,\dots,L_{i-1}\) уже известны. Определим \(d_i\) как наибольший сдвиг, удовлетворяющий
$$\frac{L_{i-1}}{L_{i-d_i}}\le r.$$
Эквивалентно, \(L_{i-d_i}\) есть самая маленькая из более ранних проигрышных позиций, которая не меньше \(L_{i-1}/r\). Тогда следующая проигрышная позиция задаётся формулой
$$L_i=L_{i-1}+L_{i-d_i}.$$
Смысл формулы таков: любая меньшая более ранняя проигрышная позиция \(L_t\), для которой \(L_t<L_{i-1}/r\), даёт выигрышный ход из состояния \(L_{i-1}+L_t\). Достаточно снять \(L_t\) камней, оставить сопернику проигрышную кучу \(L_{i-1}\), и предел ответа \(rL_t\) всё ещё слишком мал, чтобы открыть выигрышный ответ. Первая предыдущая проигрышная позиция, на которой это неравенство перестаёт выполняться, как раз и отмечает конец такого выигрышного блока, а значит, даёт следующую проигрышную позицию.
Для фиксированного \(r\) сдвиг \(d_i\) остаётся неизменным, пока не станет допустимой ещё одна более ранняя проигрышная позиция. Поэтому критическое значение на шаге \(i\) равно
$$c_i=\frac{L_{i-1}}{L_{i-(d_i+1)}},$$
если \(d_i<i-1\). При переходе через \(c_i\) становится доступен следующий меньший знаменатель, и рекурсия меняется. Следовательно, ближайший глобальный переход выше \(r\) равен
$$T(r)=\min\left\{c_i:\; d_i<i-1,\ c_i>r\right\}.$$
Именно это и делает алгоритм: строит проигрышную последовательность для текущего порога, собирает все дроби-кандидаты строго выше \(r\) и выбирает наименьшую.
Начинаем с \(L_1=1\) и \(L_2=2\).
Для \(L_3\) наибольший допустимый сдвиг равен \(d_3=2\), поскольку
$$\frac{L_2}{L_1}=\frac{2}{1}=2\le 2.$$
Поэтому
$$L_3=L_2+L_1=3.$$
Для \(L_4\) имеем
$$\frac{L_3}{L_2}=\frac{3}{2}\le 2,\qquad \frac{L_3}{L_1}=3>2,$$
значит, \(d_4=2\) и
$$L_4=L_3+L_2=5.$$
Далее
$$\frac{L_4}{L_3}=\frac{5}{3}\le 2,\qquad \frac{L_4}{L_2}=\frac{5}{2}>2,$$
откуда
$$L_5=L_4+L_3=8.$$
Продолжение даёт
$$1,2,3,5,8,13,\dots,$$
то есть проигрышные позиции совпадают с числами Фибоначчи. Соответствующие критические дроби начинаются так:
$$c_4=3,\qquad c_5=\frac{5}{2},\qquad c_6=\frac{8}{3},\dots$$
Наименьшая дробь, строго большая \(2\), равна \(5/2\), следовательно,
$$T(2)=\frac{5}{2}.$$
Аналогично, при \(r=1\) каждый шаг просто удваивает предыдущий, проигрышные позиции становятся \(1,2,4,8,\dots\), и первый переход равен \(T(1)=2\).
Реализация хранит текущий порог как точную сокращённую дробь. Для вычисления одного перехода последовательность проигрышных позиций строится только до конечного горизонта \(M\). Монотонный указатель сдвига двигается вперёд, пока выполняется неравенство \(L_{i-1}/L_{i-d}\le r\), поэтому каждая новая позиция вычисляется за амортизированное постоянное время. Одновременно формируется критическая дробь \(L_{i-1}/L_{i-(d+1)}\), и среди всех кандидатов строго больше текущего порога сохраняется наименьший.
Все сравнения дробей выполняются точным перекрёстным умножением, без плавающей точки. Перед каждым сложением также проверяется возможность переполнения. Поскольку решающий переход может возникнуть позже начального горизонта, вычисление повторяется с всё большими горизонтами до тех пор, пока один и тот же лучший кандидат не начнёт повторяться достаточно далеко от края вычисленного диапазона. Такая проверка стабилизации нужна затем, чтобы не принимать слишком короткий префикс за полную картину бесконечной последовательности.
После этого итеративно применяется отображение
$$r_1=1,\qquad r_{m+1}=T(r_m),$$
пока не будет достигнуто \(m=123456\). Решения на C++, Python и Java воспроизводят одну и ту же точную рекуррентную схему, а встроенные проверки подтверждают ранние значения, например \(r_2=2\) и \(r_{22}=145/23\).
При фиксированном горизонте \(M\) одно вычисление перехода требует \(O(M)\) арифметических операций и \(O(M)\) памяти для значений последовательности. Поскольку указатель сдвига движется только вперёд, внутренняя часть работает амортизированно линейно, а не квадратично. Если \(M_{\mathrm{eff}}(r)\) обозначает окончательный стабилизированный горизонт, нужный для порога \(r\), то одна итерация перехода стоит \(O(M_{\mathrm{eff}}(r))\) по времени и \(O(M_{\mathrm{eff}}(r))\) по памяти. Для достижения целевого индекса требуется
$$O\left(\sum_{m=1}^{123455} M_{\mathrm{eff}}(r_m)\right)$$
времени и
$$O\left(\max_m M_{\mathrm{eff}}(r_m)\right)$$
памяти. На практике метод эффективен, потому что отслеживает только рекурсию проигрышных позиций и точные переходные дроби, а не весь игровой граф.
Stone Game IV يدرس لعبة كومة واحدة تتحكم فيها قيمة حقيقية \(r\). في الحركة الأولى يمكن للاعب أن يزيل أي عدد موجب من الحجارة ما عدا إزالة الكومة كلها. وإذا أزال لاعب \(x\) حجرًا، فإن اللاعب التالي لا يجوز له أن يزيل أكثر من \(r x\) حجرًا. لكل قيمة ثابتة من \(r\) توجد أحجام ابتدائية للكومة تكون أوضاع خسارة، أي أوضاع لا يملك فيها اللاعب الذي عليه الدور استراتيجية فوز. هذه الأوضاع الخاسرة تشكل متتالية متزايدة، ولا تتغير إلا عندما تتجاوز \(r\) عتبات كسرية معينة. المطلوب هو إيجاد الحد رقم \(123456\) في متتالية العتبات المتزايدة الناتجة من البدء عند \(r_1=1\) ثم القفز في كل مرة إلى العتبة الانتقالية التالية الأكبر.
الحل لا يستعرض شجرة اللعب كاملة. بدلًا من ذلك يصف كيف تعتمد متتالية الأوضاع الخاسرة على \(r\)، ثم يستخرج من هذا الوصف العتبة التالية التي لا بد أن تغيّر تلك المتتالية.
لـ \(r\) ثابتة، نرمز بـ \(w_r(n)\) إلى أصغر حركة افتتاحية تؤدي إلى الفوز من كومة حجمها \(n\). وإذا لم توجد حركة افتتاحية رابحة فإننا نعرّف
$$w_r(n)=n.$$
وعندئذ تكون \(n\) وضعية خاسرة إذا وفقط إذا
$$w_r(n)=n.$$
العلاقة العودية تأتي مباشرة من قاعدة اللعبة. إذا أزال اللاعب الحالي \(k\) حجرًا، فإن الخصم يرى \(n-k\) حجرًا ويستطيع أن يزيل في أقصى حد \(r k\) حجرًا. وتكون هذه الحركة رابحة إذا وفقط إذا لم يكن لدى الخصم أي رد رابح حجمه لا يتجاوز \(r k\). وبما أن أصغر رد رابح من الحالة \(n-k\) هو \(w_r(n-k)\)، نحصل على
$$w_r(1)=1,\qquad w_r(n)=\min\left\{1\le k\le n:\; r k<w_r(n-k)\right\}\quad (n\ge 2).$$
أما القيمة \(k=n\) فهي مجرد قيمة حارسة: معناها أن جميع الحركات الافتتاحية القانونية \(1\le k\le n-1\) تفشل، وبالتالي تكون \(n\) نفسها وضعية خاسرة.
لتكن
$$L_1=1<L_2=2<L_3<L_4<\cdots$$
هي المتتالية المتزايدة لأحجام البداية الخاسرة. إذا كانت حركة بحجم \(k\) تترك بالضبط \(L_j\) حجرًا، فإن هذه الحركة تكون رابحة إذا وفقط إذا
$$r k<L_j,$$
لأن الوضعية \(L_j\) لا تملك أي رد رابح أصغر من \(L_j\). لذلك فإن الفجوات الرابحة التي تظهر بعد \(L_j\) هي تحديدًا الأوضاع الخاسرة الأقدم التي يبقى حجمها أصغر تمامًا من \(L_j/r\).
افترض أن \(L_1,\dots,L_{i-1}\) معروفة. نعرّف \(d_i\) بأنه أكبر تأخر يحقق
$$\frac{L_{i-1}}{L_{i-d_i}}\le r.$$
وبصورة مكافئة، تكون \(L_{i-d_i}\) أصغر وضعية خاسرة سابقة لا تقل عن \(L_{i-1}/r\). عندها تكون الوضعية الخاسرة التالية
$$L_i=L_{i-1}+L_{i-d_i}.$$
والفكرة هي أن كل وضعية خاسرة أقدم وأصغر \(L_t\) تحقق \(L_t<L_{i-1}/r\) تعطي حركة رابحة من \(L_{i-1}+L_t\): يزيل اللاعب \(L_t\) حجرًا فيترك الكومة الخاسرة \(L_{i-1}\)، بينما يبقى الحد الأقصى لرد الخصم \(rL_t\) أصغر من أن يفتح له ردًا رابحًا. وأول وضعية خاسرة سابقة تتوقف عندها هذه المتباينة عن الصدق تحدد نهاية هذا المقطع الرابح، ولذلك فإن إضافتها تعطي مباشرة الوضعية الخاسرة التالية.
عند تثبيت \(r\)، يبقى التأخر \(d_i\) كما هو إلى أن تصبح وضعية خاسرة سابقة إضافية صالحة للاستعمال. لذلك تكون القيمة الحرجة في الخطوة \(i\) هي
$$c_i=\frac{L_{i-1}}{L_{i-(d_i+1)}},$$
وذلك عندما يكون \(d_i<i-1\). وعند تجاوز \(c_i\) يصبح المقام الأصغر التالي متاحًا، فتتغير العلاقة العودية. ومن ثم فإن الانتقال العالمي التالي فوق \(r\) يساوي
$$T(r)=\min\left\{c_i:\; d_i<i-1,\ c_i>r\right\}.$$
وهذه هي الفكرة المحورية في الحل: نبني متتالية الأوضاع الخاسرة للعتبة الحالية، ونسجل كل الكسور المرشحة الواقعة فوق \(r\)، ثم نأخذ أصغرها.
نبدأ بـ \(L_1=1\) و\(L_2=2\).
لحساب \(L_3\)، يكون أكبر تأخر ممكن هو \(d_3=2\) لأن
$$\frac{L_2}{L_1}=\frac{2}{1}=2\le 2.$$
إذًا
$$L_3=L_2+L_1=3.$$
أما في \(L_4\) فنجد
$$\frac{L_3}{L_2}=\frac{3}{2}\le 2,\qquad \frac{L_3}{L_1}=3>2,$$
ومن ثم \(d_4=2\) و
$$L_4=L_3+L_2=5.$$
وبعد ذلك
$$\frac{L_4}{L_3}=\frac{5}{3}\le 2,\qquad \frac{L_4}{L_2}=\frac{5}{2}>2,$$
فنحصل على
$$L_5=L_4+L_3=8.$$
وبالاستمرار تظهر المتتالية
$$1,2,3,5,8,13,\dots,$$
أي أن الأوضاع الخاسرة تصبح أعداد فيبوناتشي. أما الكسور الحرجة الأولى فهي
$$c_4=3,\qquad c_5=\frac{5}{2},\qquad c_6=\frac{8}{3},\dots$$
وأصغر كسر أكبر من \(2\) هو \(5/2\)، لذلك
$$T(2)=\frac{5}{2}.$$
وبالمثل، عندما تكون \(r=1\) فإن العلاقة العودية تضاعف كل حد، فتصير الأوضاع الخاسرة \(1,2,4,8,\dots\)، ومن ثم يكون أول انتقال هو \(T(1)=2\).
تحتفظ الشيفرة بالعتبة الحالية على صورة كسر مختزل تمامًا. ولحساب انتقال واحد، فإنها تبني متتالية الأوضاع الخاسرة حتى أفق محدود \(M\) فقط. يوجد مؤشر تأخر أحادي الاتجاه يتقدم طالما بقيت المتباينة \(L_{i-1}/L_{i-d}\le r\) صحيحة، ولهذا فإن توليد كل حد جديد يتم بزمن ثابت وسطي. وفي الوقت نفسه تُحسب الكسرة الحرجة \(L_{i-1}/L_{i-(d+1)}\) ويُحتفظ بأصغر مرشح أكبر من العتبة الحالية.
جميع مقارنات الكسور تُنفذ بضرب تبادلي دقيق، من دون استخدام الأعداد العائمة. كما توجد حماية من الفيض قبل كل عملية جمع. ولأن الكسر الانتقالي الحاسم قد يظهر بعد الأفق الابتدائي، تعيد الشيفرة الحساب مع آفاق أكبر فأكبر حتى يظهر أفضل مرشح نفسه مرة أخرى على مسافة آمنة من نهاية الجزء المحسوب. هذا فحص استقرار مهم، لأنه يمنع افتراض أن مقدمة قصيرة من المتتالية تكفي لوصف السلوك اللانهائي كله.
بعد ذلك تُكرر الدالة
$$r_1=1,\qquad r_{m+1}=T(r_m),$$
إلى أن نصل إلى \(m=123456\). حلول C++ وPython وJava تعرض الحساب الدقيق نفسه القائم على العلاقة العودية، كما أن نقاط التحقق المضمنة تؤكد قيمًا مبكرة مثل \(r_2=2\) و\(r_{22}=145/23\).
عند أفق ثابت \(M\)، يكلف تقييم انتقال واحد \(O(M)\) عملية حسابية و\(O(M)\) من الذاكرة لتخزين حدود المتتالية. وبما أن مؤشر التأخر لا يتحرك إلا إلى الأمام، فإن البحث الداخلي خطي وسطي وليس تربيعيًا. وإذا رمزنا بالأفق المستقر النهائي اللازم للعتبة \(r\) بالرمز \(M_{\mathrm{eff}}(r)\)، فإن كلفة انتقال واحد هي \(O(M_{\mathrm{eff}}(r))\) زمنًا و\(O(M_{\mathrm{eff}}(r))\) ذاكرة. ومن ثم تكون الكلفة الكلية للوصول إلى الفهرس الهدف
$$O\left(\sum_{m=1}^{123455} M_{\mathrm{eff}}(r_m)\right)$$
زمنًا و
$$O\left(\max_m M_{\mathrm{eff}}(r_m)\right)$$
ذاكرة. وعمليًا تبقى الطريقة فعالة لأنها تتعقب فقط علاقة الأوضاع الخاسرة والكسور الانتقالية الدقيقة، لا شجرة اللعب الكاملة.