Consider a row of \(n\) cells, each marked \(L\) or \(R\). If only one cell remains, the player named on that cell wins. On a longer interval, the Left player may delete one or more cells from the left end, leaving a non-empty suffix, and the Right player may delete one or more cells from the right end, leaving a non-empty prefix. The quantity of interest is \(F(n)\), the number of length-\(n\) words for which both opening players can force a win on the full row.
The implementations do not search the full game tree for \(n=60\). Instead, they reduce the game to an interval recurrence, discover a prefix-balance invariant, and then count the exceptional path classes with ballot numbers and Catalan numbers.
Write the word as \(a_1a_2\dots a_n\) with each \(a_m\in\{L,R\}\). For any interval \(a_i\dots a_j\), let \(\mathcal{L}(i,j)\) mean that Left to move can force a win, and let \(\mathcal{R}(i,j)\) mean that Right to move can force a win. These interval states are the mathematical core of the solver.
On a single cell, the label decides the winner immediately:
$$\mathcal{L}(i,i)=1 \iff a_i=L,\qquad \mathcal{R}(i,i)=1 \iff a_i=R.$$
On a longer interval, Left wins exactly when she can cut to a suffix on which Right loses, and Right wins exactly when he can cut to a prefix on which Left loses:
$$\mathcal{L}(i,j)=1 \iff \exists\, t\in\{i+1,\dots,j\}\text{ such that }\mathcal{R}(t,j)=0,$$
$$\mathcal{R}(i,j)=1 \iff \exists\, t\in\{i,\dots,j-1\}\text{ such that }\mathcal{L}(i,t)=0.$$
This recurrence is what the small-\(n\) verifier fills by dynamic programming. The closed form comes from understanding which words make an interval lose for one side.
Assign \(+1\) to each \(L\) and \(-1\) to each \(R\), and define the prefix balance
$$s_m=\#\{q\le m:a_q=L\}-\#\{q\le m:a_q=R\},\qquad s_0=0.$$
An induction on interval length shows that the non-both-winning words fall into three very specific classes.
Left wins and Right loses exactly when every prefix is left-heavy:
$$s_m \gt 0\qquad (1\le m\le n).$$
Right wins and Left loses by the mirror condition: the final balance is the unique minimum, so
$$s_m \gt s_n\qquad (0\le m \lt n),\qquad s_n \lt 0.$$
There is also a balanced class in which neither player can force a win:
$$s_m \gt 0\qquad (1\le m \lt n),\qquad s_n=0.$$
The recurrence explains these conditions. If every prefix stays strictly above zero, Right can never cut to a prefix where Left is already dead, so Right loses. If the walk returns to zero only at the very end, Left also fails, because every suffix begins below its own starting level somewhere along the way. If the walk finishes above zero instead, Left can cut to the suffix that starts just after the last time the balance was \(1\), and that suffix again traps Right.
Call \(A_n\) the number of words for which Left wins and Right loses. These are exactly the walks with strictly positive partial sums. Deleting the first \(L\) turns such a walk into a walk of length \(n-1\) that never goes below zero. By the classical ballot/reflection count,
$$A_{2k+1}=\binom{2k}{k},\qquad A_{2k}=\binom{2k-1}{k-1}.$$
By symmetry, the same numbers count the words for which Right wins and Left loses.
The balanced class can only occur when \(n=2k\). In that case the walk stays strictly positive until the final step and then returns to zero. Removing the first \(L\) and the last \(R\) produces a Dyck path of semilength \(k-1\), so the number of such words is
$$B_{2k}=\operatorname{Cat}_{k-1}=\frac{1}{k}\binom{2k-2}{k-1}.$$
Therefore the desired count is obtained by subtracting the two one-sided classes and, for even length, the balanced neither-winning class:
$$F(2k+1)=2^{2k+1}-2\binom{2k}{k},$$
$$F(2k)=2^{2k}-2\binom{2k-1}{k-1}-\operatorname{Cat}_{k-1}.$$
For \(n=8\) we have \(k=4\). The Left-only words are counted by
$$A_8=\binom{7}{3}=35,$$
and the Right-only words contribute the same amount. The neither-winning words are the balanced positive-prefix walks, so
$$B_8=\operatorname{Cat}_3=5.$$
Since there are \(2^8=256\) total \(L/R\) words, the final count is
$$F(8)=256-35-35-5=181,$$
which is exactly the check used in the implementations. As a concrete path example, the word \(LLRLRR\) has balances \(1,2,1,2,1,0\); all proper prefixes are positive and the total balance is \(0\), so it belongs to the balanced neither-winning class.
The C++, Python, and Java implementations compute binomial coefficients multiplicatively, so no factorial tables or floating-point arithmetic are needed. The Catalan term is obtained from a binomial coefficient by exact division, and the power \(2^n\) is produced directly with integer shifts. After a parity test on \(n\), the program evaluates the appropriate closed formula.
The implementations also contain an exhaustive verifier for small \(n\). It enumerates all \(2^n\) words, initializes the singleton interval states from the cell labels, and then fills all longer intervals in increasing length order using the same two recurrence relations written above. The brute-force counts are compared with the closed form for \(n=1\) through \(12\), and the sample values \(F(3)=4\) and \(F(8)=181\) are checked explicitly before the final evaluation at \(n=60\).
The production path is the closed-form computation. With multiplicative binomial evaluation, it uses \(O(n)\) arithmetic steps and \(O(1)\) auxiliary storage apart from the integer object itself. For the Project Euler input \(n=60\), this is tiny.
The verifier is intentionally much more expensive. It enumerates \(2^n\) words, fills \(O(n^2)\) interval states for each word, and each state scans up to \(O(n)\) cut positions. That gives \(O(2^n n^3)\) time and \(O(n^2)\) memory, which is why the verifier is only used for very small \(n\).
Betrachte eine Reihe aus \(n\) Feldern, von denen jedes mit \(L\) oder \(R\) markiert ist. Bleibt nur ein Feld uebrig, gewinnt der dort genannte Spieler. Auf einem laengeren Intervall darf Left einen nichtleeren linken Praefix abschneiden und einen nichtleeren Suffix uebrig lassen; Right darf symmetrisch einen nichtleeren rechten Suffix abschneiden und einen nichtleeren Praefix uebrig lassen. Gesucht ist \(F(n)\), die Anzahl der Woerter der Laenge \(n\), fuer die beide Spieler als Startspieler auf dem vollen Intervall eine Gewinnstrategie besitzen.
Die Implementierungen loesen das Problem fuer \(n=60\) nicht durch brute force. Stattdessen wird das Spiel zuerst als Intervallrekurrenz beschrieben und dann ueber einen Praefixsaldo in ein Ballot- beziehungsweise Dyck-Pfad-Problem uebersetzt. Daraus folgt direkt eine geschlossene Formel.
Schreibe das Wort als \(a_1a_2\dots a_n\) mit \(a_m\in\{L,R\}\). Fuer ein Intervall \(a_i\dots a_j\) bezeichne \(\mathcal{L}(i,j)\), dass Left am Zug sicher gewinnt, und \(\mathcal{R}(i,j)\), dass Right am Zug sicher gewinnt. Genau diese mathematischen Objekte werden in den drei Implementierungen ausgewertet.
Bei einem einzelnen Feld entscheidet das Label sofort:
$$\mathcal{L}(i,i)=1 \iff a_i=L,\qquad \mathcal{R}(i,i)=1 \iff a_i=R.$$
Auf einem laengeren Intervall gilt:
$$\mathcal{L}(i,j)=1 \iff \exists\, t\in\{i+1,\dots,j\}\text{ mit }\mathcal{R}(t,j)=0,$$
$$\mathcal{R}(i,j)=1 \iff \exists\, t\in\{i,\dots,j-1\}\text{ mit }\mathcal{L}(i,t)=0.$$
Left gewinnt also genau dann, wenn sie auf einen Suffix schneiden kann, auf dem Right verliert; Right gewinnt genau dann, wenn er auf einen Praefix schneiden kann, auf dem Left verliert. Die kleine Test-DP folgt genau dieser Rekurrenz.
Wir geben jedem \(L\) den Wert \(+1\) und jedem \(R\) den Wert \(-1\). Der Praefixsaldo lautet
$$s_m=\#\{q\le m:a_q=L\}-\#\{q\le m:a_q=R\},\qquad s_0=0.$$
Eine Induktion ueber die Intervalllaenge zeigt, dass die Woerter, bei denen nicht beide Spieler gewinnen koennen, genau in drei Klassen zerfallen.
Left gewinnt, Right verliert genau dann, wenn jeder Praefix links-lastig ist:
$$s_m \gt 0\qquad (1\le m\le n).$$
Symmetrisch gewinnt Right allein genau dann, wenn der Endsaldo das eindeutige Minimum ist:
$$s_m \gt s_n\qquad (0\le m \lt n),\qquad s_n \lt 0.$$
Ausserdem gibt es eine balancierte Klasse, in der keiner eine Gewinnstrategie hat:
$$s_m \gt 0\qquad (1\le m \lt n),\qquad s_n=0.$$
Diese Bedingungen erklaeren die Rekurrenz sehr direkt. Wenn jeder Praefix strikt positiv bleibt, kann Right nie auf einen verlorenen Praefix fuer Left schneiden. Kehrt der Pfad erst im letzten Schritt nach \(0\) zurueck, dann verliert auch Left, weil jeder echte Suffix irgendwo unter sein Startniveau faellt. Endet der Pfad dagegen oberhalb von \(0\), kann Left zum Suffix hinter dem letzten Auftreten des Saldos \(1\) schneiden und Right erneut in dieselbe Falle schicken.
Sei \(A_n\) die Anzahl der Woerter, in denen Left gewinnt und Right verliert. Das sind genau die Wege mit strikt positiven Partialsummen. Entfernt man das erste \(L\), erhaelt man einen Weg der Laenge \(n-1\), der nie unter \(0\) faellt. Mit Ballot-Theorem oder Spiegelungsprinzip folgt
$$A_{2k+1}=\binom{2k}{k},\qquad A_{2k}=\binom{2k-1}{k-1}.$$
Wegen der Links-Rechts-Symmetrie zaehlen dieselben Zahlen auch die Woerter, in denen nur Right gewinnt.
Die balancierte Klasse existiert nur fuer \(n=2k\). Dann bleibt der Weg bis zum Schluss strikt positiv und endet erst im letzten Schritt bei \(0\). Entfernt man das erste \(L\) und das letzte \(R\), bleibt ein Dyck-Pfad der Halblaenge \(k-1\). Daher ist die Anzahl
$$B_{2k}=\operatorname{Cat}_{k-1}=\frac{1}{k}\binom{2k-2}{k-1}.$$
Damit ergibt sich sofort
$$F(2k+1)=2^{2k+1}-2\binom{2k}{k},$$
$$F(2k)=2^{2k}-2\binom{2k-1}{k-1}-\operatorname{Cat}_{k-1}.$$
Fuer \(n=8\) ist \(k=4\). Die Left-only-Klasse hat
$$A_8=\binom{7}{3}=35$$
Elemente, und genauso viele gibt es in der spiegelbildlichen Right-only-Klasse. Die balancierte Klasse hat
$$B_8=\operatorname{Cat}_3=5.$$
Bei insgesamt \(2^8=256\) Woertern folgt also
$$F(8)=256-35-35-5=181.$$
Ein konkretes Beispiel aus der balancierten Klasse ist \(LLRLRR\) mit Praefixsalden \(1,2,1,2,1,0\). Alle echten Praefixe sind positiv, aber der Gesamtwert ist \(0\); deshalb hat in diesem Fall keiner der beiden Spieler eine Gewinnstrategie.
Die C++-, Python- und Java-Implementierungen berechnen Binomialkoeffizienten multiplikativ und bleiben dadurch jederzeit in exakter Ganzzahlarithmetik. Der Catalan-Term wird aus einem Binomialkoeffizienten per exakter Division gewonnen, und \(2^n\) entsteht direkt per Bitverschiebung. Nach dem Paritaetstest fuer \(n\) wird die passende Formel ausgewertet.
Zusaetzlich enthalten die Implementierungen einen Volltest fuer kleine \(n\). Dabei werden alle \(2^n\) Woerter erzeugt, die Einzelintervalle aus den Labels initialisiert und danach alle laengeren Intervalle in wachsender Laenge mit derselben Rekurrenz gefuellt. Die brute-force-Werte werden fuer \(n=1\) bis \(12\) mit der geschlossenen Formel verglichen; ausserdem werden die Stichproben \(F(3)=4\) und \(F(8)=181\) explizit geprueft, bevor am Ende \(F(60)\) berechnet wird.
Der eigentliche Produktionspfad ist die geschlossene Formel. Die multiplikative Auswertung der Binomialkoeffizienten braucht \(O(n)\) arithmetische Schritte und \(O(1)\) zusaetzlichen Speicher abgesehen vom Integer-Objekt selbst. Fuer \(n=60\) ist dieser Aufwand vernachlaessigbar klein.
Die Verifikation ist absichtlich viel teurer. Fuer jedes der \(2^n\) Woerter werden \(O(n^2)\) Intervallzustaende berechnet, und jeder Zustand prueft bis zu \(O(n)\) moegliche Schnitte. Insgesamt ergibt das \(O(2^n n^3)\) Zeit und \(O(n^2)\) Speicher. Genau deshalb wird dieser Teil nur fuer kleine Testwerte verwendet.
\(n\) hucreden olusan bir dizi dusunun; her hucre ya \(L\) ya da \(R\) ile etiketlidir. Yalnizca tek hucre kalirsa, o hucrede adi yazan oyuncu kazanir. Aralik daha uzunsa Left soldan bir veya daha fazla hucre silip bos olmayan bir son ek birakabilir; Right da simetrik bicimde sagdan bir veya daha fazla hucre silip bos olmayan bir on ek birakabilir. Aranan nicelik \(F(n)\), uzunlugu \(n\) olan ve tam dizide her iki oyuncunun da ilk oynayan olarak kazanabildigi sozcuklerin sayisidir.
Uygulamalar \(n=60\) icin tum oyun agacini aramaz. Bunun yerine once aralik tabanli bir kazanc rekurrensi yazilir, sonra bu rekurrensin aslinda bir on ek denge yurusune donustugu fark edilir. Son adimda sayim, ballot sayilari ve Catalan sayilariyla kapali formulle biter.
Sozcugu \(a_1a_2\dots a_n\) olarak yazalim; burada her \(a_m\in\{L,R\}\). Herhangi bir \(a_i\dots a_j\) araligi icin \(\mathcal{L}(i,j)\), Left sira kendisindeyken zorunlu kazanabiliyor demek olsun; \(\mathcal{R}(i,j)\) de Right icin ayni anlama gelsin. Cozumun kalbi bu aralik durumlaridir.
Tek hucrelik durumda etiketi okumak yeterlidir:
$$\mathcal{L}(i,i)=1 \iff a_i=L,\qquad \mathcal{R}(i,i)=1 \iff a_i=R.$$
Daha uzun aralikta Left ancak Right'i kaybettiren bir son eke kesebiliyorsa kazanir; Right da ancak Left'i kaybettiren bir on eke kesebiliyorsa kazanir:
$$\mathcal{L}(i,j)=1 \iff \exists\, t\in\{i+1,\dots,j\}\text{ oyle ki }\mathcal{R}(t,j)=0,$$
$$\mathcal{R}(i,j)=1 \iff \exists\, t\in\{i,\dots,j-1\}\text{ oyle ki }\mathcal{L}(i,t)=0.$$
Kucuk \(n\) icin yazilan dogrulama kodu tam olarak bu rekurrensi dinamik programlama ile doldurur. Kapali formule gecis ise hangi sozcuklerin bir tarafi zorunlu kaybettirdigini anlamaktan gelir.
Her \(L\) icin \(+1\), her \(R\) icin \(-1\) verelim ve
$$s_m=\#\{q\le m:a_q=L\}-\#\{q\le m:a_q=R\},\qquad s_0=0$$
olsun. Aralik uzunlugu uzerinden yapilan bir induksiyon, iki oyuncunun birden kazanamadigi sozcuklerin yalnizca uc sinifa ayrildigini gosterir.
Left kazanip Right kaybediyorsa her on ek soldan agir olmak zorundadir:
$$s_m \gt 0\qquad (1\le m\le n).$$
Right'in tek basina kazandigi durum bunun ayna goruntusudur; son denge tek minimum olur:
$$s_m \gt s_n\qquad (0\le m \lt n),\qquad s_n \lt 0.$$
Bir de hic kimsenin kazanamadigi dengeli sinif vardir:
$$s_m \gt 0\qquad (1\le m \lt n),\qquad s_n=0.$$
Bu kosullar rekurrensle uyumludur. Tum on ekler sifirin ustunde kalirsa Right, Left'i olduren bir on eke hic kesemez. Yuruyus ancak son adimda sifira donuyorsa Left de kazanamaz; cunku her gercek son ek kendi baslangic seviyesinin altina bir yerde iner. Buna karsilik toplam denge pozitif biterse Left, dengenin son kez \(1\) oldugu yerin hemen sonrasina keserek Right'i yine kayip bir son eke iter.
\(A_n\), Left'in kazandigi ve Right'in kaybettigi sozcuklerin sayisi olsun. Bunlar tam olarak tum kismi toplamlarin pozitif kaldigi yollardir. Ilk \(L\)'yi kaldirinca uzunlugu \(n-1\) olan ve hic negatif olmayan bir yuruyus kalir. Klasik ballot / yansitma prensibi sayimi
$$A_{2k+1}=\binom{2k}{k},\qquad A_{2k}=\binom{2k-1}{k-1}$$
sonucunu verir. Sol-sag simetrisi nedeniyle ayni sayilar Right-only sinifi icin de gecerlidir.
Dengeli ve hic kimsenin kazanamadigi sinif yalnizca \(n=2k\) iken gorulur. Bu durumda yuruyus son ana kadar pozitif kalir ve son adimda sifira doner. Ilk \(L\) ile son \(R\)'yi atinca yari uzunlugu \(k-1\) olan bir Dyck yolu elde edilir. Bu nedenle sayi
$$B_{2k}=\operatorname{Cat}_{k-1}=\frac{1}{k}\binom{2k-2}{k-1}$$
olur. Dolayisiyla aranan formuller
$$F(2k+1)=2^{2k+1}-2\binom{2k}{k},$$
$$F(2k)=2^{2k}-2\binom{2k-1}{k-1}-\operatorname{Cat}_{k-1}$$
seklindedir.
\(n=8\) icin \(k=4\) olur. Left-only sinifi
$$A_8=\binom{7}{3}=35$$
elemanlidir; Right-only sinifi de ayni buyukluktedir. Hic kimsenin kazanamadigi dengeli sinif ise
$$B_8=\operatorname{Cat}_3=5$$
adet sozcuk icerir. Toplam \(2^8=256\) sozcuk bulundugu icin
$$F(8)=256-35-35-5=181$$
elde edilir; bu deger dogrudan uygulamalarda da test edilir. Somut bir dengeli ornek olarak \(LLRLRR\) sozcugunun denge dizisi \(1,2,1,2,1,0\) olur. Tum gercek on ekler pozitiftir ama toplam denge \(0\)'a doner; bu yuzden her iki oyuncu da ilk oyuncu olarak kazanamaz.
C++, Python ve Java uygulamalari binom katsayilarini carpimli bicimde hesaplar; boylece faktoriyel tablosu ya da kayan nokta kullanmadan tam sayi aritmetigi korunur. Catalan terimi bir binom katsayisindan tam bolme ile elde edilir, \(2^n\) ise dogrudan bit kaydirma ile uretilir. Ardindan \(n\)'in tek ya da cift olmasina gore uygun kapali formul degerlendirilir.
Uygulamalarda ayrica kucuk \(n\) icin tam dogrulama da vardir. Tum \(2^n\) sozcukler gezilir, tek hucreli araliklar etiketlerden kurulur ve daha uzun araliklar yukaridaki iki rekurrens kullanilarak artan uzunluk sirasiyla doldurulur. Elde edilen brute-force sayilari \(n=1\) ile \(12\) arasinda kapali formulle karsilastirilir; ayrica \(F(3)=4\) ve \(F(8)=181\) ornekleri acikca kontrol edilir. Son uretim adimi ise \(n=60\) icin kapali formulun tek seferde hesaplanmasidir.
Asil uretim yolu kapali formuldur. Binom katsayilarinin carpimli hesaplanmasi \(O(n)\) aritmetik adim ve tamsayi nesnesi disinda \(O(1)\) ek bellek kullanir. Project Euler girdisi olan \(n=60\) icin bu maliyet cok kucuktur.
Dogrulama yolu ise bilerek pahali tutulmustur. Her bir \(2^n\) sozcuk icin \(O(n^2)\) aralik durumu doldurulur ve her durumda \(O(n)\) olasi kesim denenir. Toplam zaman \(O(2^n n^3)\), bellek ise \(O(n^2)\) olur. Bu nedenle bu kisim yalnizca kucuk test degerleri icin kullanilir.
Considere una fila de \(n\) casillas, cada una marcada con \(L\) o con \(R\). Si solo queda una casilla, gana el jugador indicado por esa letra. En un intervalo mas largo, Left puede borrar una o mas casillas desde el extremo izquierdo y dejar un sufijo no vacio; Right puede borrar una o mas casillas desde el extremo derecho y dejar un prefijo no vacio. La cantidad buscada es \(F(n)\), el numero de palabras de longitud \(n\) para las cuales ambos jugadores, si empiezan sobre la fila completa, tienen estrategia ganadora.
Las implementaciones no exploran el arbol completo del juego cuando \(n=60\). Primero escriben una recurrencia sobre intervalos, luego identifican un invariante de balances de prefijo y finalmente cuentan las clases excepcionales con numeros ballot y numeros de Catalan.
Escribamos la palabra como \(a_1a_2\dots a_n\), con \(a_m\in\{L,R\}\). Para un intervalo \(a_i\dots a_j\), sea \(\mathcal{L}(i,j)\) la afirmacion "Left, moviendo ahora, puede forzar la victoria", y sea \(\mathcal{R}(i,j)\) la afirmacion analoga para Right. Estos estados de intervalo son el objeto matematico central de la solucion.
En una sola casilla, la letra decide el ganador:
$$\mathcal{L}(i,i)=1 \iff a_i=L,\qquad \mathcal{R}(i,i)=1 \iff a_i=R.$$
En un intervalo mas largo, Left gana exactamente si puede cortar hasta un sufijo donde Right pierda, y Right gana exactamente si puede cortar hasta un prefijo donde Left pierda:
$$\mathcal{L}(i,j)=1 \iff \exists\, t\in\{i+1,\dots,j\}\text{ tal que }\mathcal{R}(t,j)=0,$$
$$\mathcal{R}(i,j)=1 \iff \exists\, t\in\{i,\dots,j-1\}\text{ tal que }\mathcal{L}(i,t)=0.$$
La verificacion exhaustiva para \(n\) pequenos rellena exactamente esta recurrencia. La formula cerrada aparece cuando se entiende que palabras hacen perder forzosamente a un lado.
Asignemos \(+1\) a cada \(L\) y \(-1\) a cada \(R\), y definamos
$$s_m=\#\{q\le m:a_q=L\}-\#\{q\le m:a_q=R\},\qquad s_0=0.$$
Una induccion sobre la longitud del intervalo muestra que las palabras donde no ganan ambos jugadores se separan en tres clases precisas.
Left gana y Right pierde exactamente cuando todos los prefijos son favorables a la izquierda:
$$s_m \gt 0\qquad (1\le m\le n).$$
Right gana en solitario por la condicion espejo: el balance final es el minimo estricto, de modo que
$$s_m \gt s_n\qquad (0\le m \lt n),\qquad s_n \lt 0.$$
Ademas existe una clase balanceada donde ninguno puede forzar la victoria:
$$s_m \gt 0\qquad (1\le m \lt n),\qquad s_n=0.$$
La recurrencia explica estas condiciones. Si todos los prefijos permanecen estrictamente por encima de cero, Right nunca puede cortar hacia un prefijo donde Left ya este perdida. Si el paseo solo regresa a cero en el paso final, Left tambien fracasa, porque cualquier sufijo propio cae por debajo de su nivel inicial en algun momento. En cambio, si el balance total termina positivo, Left puede cortar justo despues de la ultima vez que el balance fue \(1\), y el sufijo restante vuelve a ser una trampa para Right.
Sea \(A_n\) el numero de palabras donde Left gana y Right pierde. Son exactamente los paseos con sumas parciales estrictamente positivas. Al borrar la primera \(L\), queda un paseo de longitud \(n-1\) que nunca baja de cero. Por el teorema ballot o el principio de reflexion,
$$A_{2k+1}=\binom{2k}{k},\qquad A_{2k}=\binom{2k-1}{k-1}.$$
Por simetria, las mismas cantidades cuentan las palabras donde Right gana y Left pierde.
La clase balanceada solo puede aparecer cuando \(n=2k\). Entonces el paseo permanece positivo hasta el final y vuelve a cero en el ultimo paso. Si se eliminan la primera \(L\) y la ultima \(R\), queda un camino de Dyck de semilongitud \(k-1\). Por tanto, el numero de tales palabras es
$$B_{2k}=\operatorname{Cat}_{k-1}=\frac{1}{k}\binom{2k-2}{k-1}.$$
La formula final es entonces
$$F(2k+1)=2^{2k+1}-2\binom{2k}{k},$$
$$F(2k)=2^{2k}-2\binom{2k-1}{k-1}-\operatorname{Cat}_{k-1}.$$
Para \(n=8\) tenemos \(k=4\). Las palabras Left-only se cuentan con
$$A_8=\binom{7}{3}=35,$$
y la clase simetrica Right-only aporta otras \(35\). La clase balanceada aporta
$$B_8=\operatorname{Cat}_3=5.$$
Como el total de palabras es \(2^8=256\), resulta
$$F(8)=256-35-35-5=181,$$
que coincide con la comprobacion incluida en las implementaciones. Un ejemplo concreto de la clase balanceada es \(LLRLRR\), cuyos balances de prefijo son \(1,2,1,2,1,0\); todos los prefijos propios son positivos, pero el balance total vale \(0\), asi que ninguno de los dos jugadores puede forzar la victoria.
Las implementaciones en C++, Python y Java calculan los coeficientes binomiales de manera multiplicativa, evitando factoriales gigantes y cualquier aproximacion en punto flotante. El termino de Catalan se obtiene por una division exacta de un binomial, y \(2^n\) se construye directamente con desplazamientos enteros. Despues de comprobar la paridad de \(n\), se evalua la formula correspondiente.
Tambien hay un verificador completo para valores pequenos de \(n\). Recorre las \(2^n\) palabras posibles, inicializa los estados de longitud \(1\) con la letra de cada casilla y rellena todos los intervalos mayores en orden creciente de longitud usando las mismas dos recurrencias de arriba. Los conteos exhaustivos se comparan con la formula cerrada para \(n=1,\dots,12\), y ademas se comprueban explicitamente los casos \(F(3)=4\) y \(F(8)=181\) antes de evaluar el caso final \(n=60\).
La ruta principal es la formula cerrada. Con el calculo multiplicativo de binomiales, requiere \(O(n)\) operaciones aritmeticas y \(O(1)\) memoria auxiliar aparte del entero que almacena el resultado. Para \(n=60\), el coste es muy pequeno.
La verificacion es mucho mas cara a proposito. Enumera \(2^n\) palabras, rellena \(O(n^2)\) estados de intervalo para cada una y cada estado prueba hasta \(O(n)\) posiciones de corte. El coste total es \(O(2^n n^3)\) en tiempo y \(O(n^2)\) en memoria, razon por la cual esta parte solo se usa en casos muy pequenos.
设有一排长度为 \(n\) 的格子，每个格子都标着 \(L\) 或 \(R\)。如果最后只剩一个格子，那么写在这个格子上的那一方获胜。区间长度大于 \(1\) 时，Left 可以从左端删去一个或多个格子，留下一个非空后缀；Right 可以从右端删去一个或多个格子，留下一个非空前缀。题目要求的 \(F(n)\)，就是长度为 \(n\) 的所有 \(L/R\) 串中，有多少个串满足：无论由 Left 先手还是由 Right 先手，在完整区间上都能强制取胜。
实现并没有在 \(n=60\) 时暴力搜索整个博弈树。它先把游戏写成区间递推，再把递推压缩成一个前缀平衡量不变量，最后把剩下的计数问题化成 ballot 路径与 Catalan 数的经典计数。
把字符串写成 \(a_1a_2\dots a_n\)，其中每个 \(a_m\in\{L,R\}\)。对任意区间 \(a_i\dots a_j\)，记 \(\mathcal{L}(i,j)\) 为“轮到 Left 行动时她能否必胜”，记 \(\mathcal{R}(i,j)\) 为“轮到 Right 行动时他能否必胜”。这两个区间状态就是整套推导的数学核心。
当区间只剩一个格子时，结论立刻由字母决定：
$$\mathcal{L}(i,i)=1 \iff a_i=L,\qquad \mathcal{R}(i,i)=1 \iff a_i=R.$$
当区间更长时，Left 只有在能切到某个让 Right 失败的后缀时才会赢；Right 也只有在能切到某个让 Left 失败的前缀时才会赢：
$$\mathcal{L}(i,j)=1 \iff \exists\, t\in\{i+1,\dots,j\}\text{ 使得 }\mathcal{R}(t,j)=0,$$
$$\mathcal{R}(i,j)=1 \iff \exists\, t\in\{i,\dots,j-1\}\text{ 使得 }\mathcal{L}(i,t)=0.$$
小规模验证程序正是按这个区间递推表来填值的。真正高效的闭式解，则来自于理解哪些字符串会把某一方逼成必败。
把每个 \(L\) 记作 \(+1\)，每个 \(R\) 记作 \(-1\)，并定义前缀平衡量
$$s_m=\#\{q\le m:a_q=L\}-\#\{q\le m:a_q=R\},\qquad s_0=0.$$
对区间长度做归纳之后，可以得到一个很干净的分类：那些“不是双方都能赢”的字符串，恰好分成三类。
第一类是 Left-only，即 Left 能赢而 Right 不能赢。它的特征是每一个前缀都偏向左边：
$$s_m \gt 0\qquad (1\le m\le n).$$
第二类是 Right-only，完全由镜像对称得到：最终平衡量是唯一的严格最小值，因此
$$s_m \gt s_n\qquad (0\le m \lt n),\qquad s_n \lt 0.$$
第三类是一个只在偶数长度里出现的平衡类，其中双方都无法强制取胜：
$$s_m \gt 0\qquad (1\le m \lt n),\qquad s_n=0.$$
为什么这三个条件和递推完全一致？如果所有前缀都严格大于零，Right 永远找不到一个“切完以后 Left 已经死掉”的前缀，所以 Right 必败。如果路径直到最后一步才回到零，那么 Left 也没有可行的必胜切法，因为任何真后缀在自己的起点之后都会先跌破自身起始高度。相反，如果整条路径最后停在正高度，那么 Left 可以切到“最后一次平衡量等于 \(1\)”之后的那个后缀，而那个后缀又会重复同样的结构，从而把 Right 送进必败位置。
记 \(A_n\) 为 Left-only 字符串的数量。它们正好对应于所有部分和始终严格为正的步行。删去最前面的那个 \(L\) 以后，剩下的是一个长度为 \(n-1\) 且从不跌破零的步行。由经典的 ballot 计数或反射原理可得
$$A_{2k+1}=\binom{2k}{k},\qquad A_{2k}=\binom{2k-1}{k-1}.$$
左右对称意味着 Right-only 的数量完全相同。
“双方都不能赢”的平衡类只会出现在 \(n=2k\) 时。此时路径在最后一步之前一直严格为正，并且最后一步回到零。把最前面的 \(L\) 和最后面的 \(R\) 去掉，就得到一个半长度为 \(k-1\) 的 Dyck 路。因此这一类的数量是
$$B_{2k}=\operatorname{Cat}_{k-1}=\frac{1}{k}\binom{2k-2}{k-1}.$$
于是最终公式为
$$F(2k+1)=2^{2k+1}-2\binom{2k}{k},$$
$$F(2k)=2^{2k}-2\binom{2k-1}{k-1}-\operatorname{Cat}_{k-1}.$$
当 \(n=8\) 时，\(k=4\)。Left-only 的数量为
$$A_8=\binom{7}{3}=35,$$
Right-only 由于对称性也有 \(35\) 个。平衡的 neither 类数量为
$$B_8=\operatorname{Cat}_3=5.$$
总共有 \(2^8=256\) 个 \(L/R\) 串，所以
$$F(8)=256-35-35-5=181,$$
这正是实现中明确验证的数值。再看一个路径例子：字符串 \(LLRLRR\) 的前缀平衡量依次是 \(1,2,1,2,1,0\)。所有真前缀都严格为正，但最后总平衡量回到 \(0\)，因此它属于“双方都不能强制取胜”的平衡类。
C++、Python 和 Java 实现都用乘法方式计算二项式系数，因此不需要巨大的阶乘表，也不需要浮点近似。Catalan 项由一个二项式系数做整除得到，而 \(2^n\) 直接用整数移位构造。随后程序只需判断 \(n\) 的奇偶性，并代入对应的闭式公式即可。
实现中还保留了一个只用于小 \(n\) 的完整验证器。它枚举全部 \(2^n\) 个字符串，先用单格标签初始化长度为 \(1\) 的区间状态，再按区间长度递增的顺序，用上面的两条递推关系填完所有更长区间。之后把穷举得到的计数与闭式结果在 \(n=1\) 到 \(12\) 上逐一比较，并额外显式检查 \(F(3)=4\) 与 \(F(8)=181\)，最后才计算目标值 \(F(60)\)。
真正用于求解的路径是闭式计算。用乘法方式求二项式系数时，总共只需要 \(O(n)\) 次整数运算，除结果对象本身外额外空间为 \(O(1)\)。对 Project Euler 的输入 \(n=60\) 来说，这几乎可以看作常数时间。
验证器则刻意保留为昂贵但可靠的形式。它枚举 \(2^n\) 个字符串，对每个字符串填 \(O(n^2)\) 个区间状态，而每个状态又要扫描最多 \(O(n)\) 个切割位置，因此总时间复杂度为 \(O(2^n n^3)\)，空间复杂度为 \(O(n^2)\)。这也是为什么它只用于很小的 \(n\)。
Рассматривается строка длины \(n\), где каждая позиция помечена буквой \(L\) или \(R\). Если остается единственная клетка, побеждает тот игрок, чья буква в ней записана. На более длинном отрезке Left может удалить один или несколько символов слева, оставив непустой суффикс, а Right может удалить один или несколько символов справа, оставив непустой префикс. Нужно найти \(F(n)\): число строк длины \(n\), для которых и Left, и Right, начиная первыми на полном отрезке, имеют выигрышную стратегию.
Реализации не перебирают все дерево игры для \(n=60\). Сначала игра записывается как рекурсия по интервалам, затем эта рекурсия сводится к инварианту префиксного баланса, после чего подсчет исключительных классов выполняется через ballot-числа и числа Каталана.
Запишем слово как \(a_1a_2\dots a_n\), где каждый \(a_m\in\{L,R\}\). Для интервала \(a_i\dots a_j\) обозначим через \(\mathcal{L}(i,j)\) утверждение, что Left, ходя на этом интервале, может гарантированно выиграть, а через \(\mathcal{R}(i,j)\) аналогичное утверждение для Right. Именно эти интервальные состояния лежат в основе решения.
Для одного символа победитель определяется сразу:
$$\mathcal{L}(i,i)=1 \iff a_i=L,\qquad \mathcal{R}(i,i)=1 \iff a_i=R.$$
Для более длинного интервала Left выигрывает тогда и только тогда, когда может отрезать префикс и оставить суффикс, на котором Right проигрывает. Для Right действует полностью симметричное правило:
$$\mathcal{L}(i,j)=1 \iff \exists\, t\in\{i+1,\dots,j\}\text{ такое, что }\mathcal{R}(t,j)=0,$$
$$\mathcal{R}(i,j)=1 \iff \exists\, t\in\{i,\dots,j-1\}\text{ такое, что }\mathcal{L}(i,t)=0.$$
Проверочный перебор для малых \(n\) буквально заполняет эту таблицу динамикой по длине интервала. Закрытая формула появляется после того, как становится ясно, какие строки делают одно из направлений безнадежным.
Положим, что \(L\) дает вклад \(+1\), а \(R\) дает вклад \(-1\). Тогда
$$s_m=\#\{q\le m:a_q=L\}-\#\{q\le m:a_q=R\},\qquad s_0=0$$
есть префиксный баланс. Индукция по длине интервала показывает, что все строки, в которых не выигрывают оба стартовых игрока, распадаются ровно на три класса.
Класс Left-only, где Left выигрывает, а Right нет, задается условием
$$s_m \gt 0\qquad (1\le m\le n).$$
Класс Right-only получается зеркально: конечный баланс является строгим минимумом, то есть
$$s_m \gt s_n\qquad (0\le m \lt n),\qquad s_n \lt 0.$$
Кроме того, существует сбалансированный класс, в котором не может выиграть никто:
$$s_m \gt 0\qquad (1\le m \lt n),\qquad s_n=0.$$
Именно так и работает рекурсия. Если каждый префикс строго положителен, Right не может отрезать такой префикс, после которого Left уже проиграла. Если путь возвращается к нулю только в самом конце, Left тоже не находит выигрышного среза: любой собственный суффикс где-то опускается ниже своего стартового уровня. Если же итоговый баланс положителен, Left режет сразу после последнего места, где баланс был равен \(1\), и снова оставляет Right в проигрышной позиции.
Обозначим через \(A_n\) число строк Left-only. Это в точности пути со строго положительными частичными суммами. Если удалить первый символ \(L\), получится путь длины \(n-1\), который никогда не опускается ниже нуля. По теореме Бертрана о голосовании или по принципу отражения получаем
$$A_{2k+1}=\binom{2k}{k},\qquad A_{2k}=\binom{2k-1}{k-1}.$$
По симметрии те же числа дают количество строк Right-only.
Сбалансированный класс существует только при \(n=2k\). Тогда путь остается строго положительным до последнего шага и возвращается к нулю только в конце. Если убрать первый \(L\) и последний \(R\), останется путь Дика полудлины \(k-1\). Следовательно, число таких строк равно
$$B_{2k}=\operatorname{Cat}_{k-1}=\frac{1}{k}\binom{2k-2}{k-1}.$$
Отсюда сразу следуют формулы
$$F(2k+1)=2^{2k+1}-2\binom{2k}{k},$$
$$F(2k)=2^{2k}-2\binom{2k-1}{k-1}-\operatorname{Cat}_{k-1}.$$
При \(n=8\) имеем \(k=4\). Количество строк класса Left-only равно
$$A_8=\binom{7}{3}=35,$$
столько же дает симметричный класс Right-only. Сбалансированный класс neither имеет мощность
$$B_8=\operatorname{Cat}_3=5.$$
Так как всего строк \(2^8=256\), получаем
$$F(8)=256-35-35-5=181,$$
и именно это значение проверяется в реализациях. Конкретный пример сбалансированного класса: строка \(LLRLRR\) с префиксными балансами \(1,2,1,2,1,0\). Все собственные префиксы положительны, но полный баланс равен нулю, поэтому выигрышной стратегии нет ни у одного стартующего игрока.
Реализации на C++, Python и Java вычисляют биномиальные коэффициенты мультипликативно, без факториалов и без вещественной арифметики. Число Каталана получается точным делением биномиального коэффициента, а \(2^n\) строится непосредственно сдвигом целого числа. После проверки четности \(n\) программа подставляет данные в соответствующую формулу.
Кроме основной формулы, в коде есть полный проверяющий модуль для малых размеров. Он перебирает все \(2^n\) строк, инициализирует интервалы длины \(1\) по их буквам, а затем заполняет все более длинные интервалы в порядке возрастания длины с помощью двух рекуррентных соотношений выше. Полученные значения сравниваются с закрытой формулой для \(n=1,\dots,12\); отдельно проверяются \(F(3)=4\) и \(F(8)=181\), после чего вычисляется целевой случай \(n=60\).
Основной рабочий путь - это закрытая формула. При мультипликативном вычислении биномиальных коэффициентов она требует \(O(n)\) арифметических операций и \(O(1)\) дополнительной памяти, если не считать самого большого целого числа. Для входа \(n=60\) это очень мало.
Проверяющий перебор существенно дороже. Он перечисляет \(2^n\) строк, для каждой строки заполняет \(O(n^2)\) интервальных состояний, и каждое состояние перебирает до \(O(n)\) возможных разрезов. В итоге получаем \(O(2^n n^3)\) времени и \(O(n^2)\) памяти. Поэтому этот режим используется только на очень малых \(n\).
لدينا صف من \(n\) خانات، وكل خانة تحمل الرمز \(L\) أو \(R\). إذا بقيت خانة واحدة فقط فالفائز هو اللاعب المكتوب اسمه على تلك الخانة. وعندما يكون المقطع أطول من ذلك، يستطيع Left أن يحذف خانة واحدة أو أكثر من الطرف الأيسر ويترك لاحقة غير فارغة، بينما يستطيع Right أن يحذف خانة واحدة أو أكثر من الطرف الأيمن ويترك بادئة غير فارغة. المطلوب هو \(F(n)\): عدد الكلمات بطول \(n\) التي يملك فيها كل من اللاعبَين، إذا بدأ اللعب من المقطع الكامل، استراتيجية فوز مؤكدة.
التنفيذ لا يستعرض شجرة اللعب كاملة عند \(n=60\). بدلا من ذلك، يحول اللعبة إلى علاقة رجعية على المقاطع، ثم يستخرج منها ثابتًا مبنيًا على توازن البوادئ، وبعد ذلك يحسب الفئات الاستثنائية باستخدام عدات ballot وأعداد Catalan.
لنكتب الكلمة على صورة \(a_1a_2\dots a_n\)، حيث \(a_m\in\{L,R\}\). ولأي مقطع \(a_i\dots a_j\)، نرمز بـ \(\mathcal{L}(i,j)\) إلى العبارة "Left إذا كان دوره الآن يستطيع أن يفرض الفوز"، وبـ \(\mathcal{R}(i,j)\) إلى العبارة المناظرة لـ Right. هاتان الحالتان على المقاطع هما لب الحل كله.
إذا كان لدينا موضع واحد فقط، فالرمز نفسه يحدد الفائز:
$$\mathcal{L}(i,i)=1 \iff a_i=L,\qquad \mathcal{R}(i,i)=1 \iff a_i=R.$$
أما إذا كان المقطع أطول، فإن Left يفوز بالضبط إذا استطاع أن يقطع إلى لاحقة يخسر فيها Right، ويفوز Right بالضبط إذا استطاع أن يقطع إلى بادئة يخسر فيها Left:
$$\mathcal{L}(i,j)=1 \iff \exists\, t\in\{i+1,\dots,j\},\ \mathcal{R}(t,j)=0,$$
$$\mathcal{R}(i,j)=1 \iff \exists\, t\in\{i,\dots,j-1\},\ \mathcal{L}(i,t)=0.$$
ولهذا السبب يملأ برنامج التحقق الصغير جدول الحالات على المقاطع بالديناميكية. أما الصيغة المغلقة فتظهر عندما نفهم أي الكلمات تجعل أحد الجانبين في وضع خاسر حتمي.
نعطي كل \(L\) القيمة \(+1\)، وكل \(R\) القيمة \(-1\)، ثم نعرف
$$s_m=\#\{q\le m:a_q=L\}-\#\{q\le m:a_q=R\},\qquad s_0=0.$$
وبالاستقراء على طول المقطع يتبين أن الكلمات التي لا يفوز فيها اللاعبان معًا تنقسم إلى ثلاث فئات فقط.
الفئة الأولى هي التي يفوز فيها Left وحده ويخسر Right، وتمتاز بأن كل بادئة ترجح كفة اليسار:
$$s_m \gt 0\qquad (1\le m\le n).$$
والفئة الثانية هي الصورة المرآتية حيث يفوز Right وحده، وفيها يكون التوازن النهائي هو الأصغر بشكل صارم:
$$s_m \gt s_n\qquad (0\le m \lt n),\qquad s_n \lt 0.$$
وهناك أيضًا فئة متوازنة لا يملك فيها أي من الطرفين استراتيجية فوز:
$$s_m \gt 0\qquad (1\le m \lt n),\qquad s_n=0.$$
هذه الشروط نابعة مباشرة من العلاقة الرجعية. فإذا بقي كل توازن بادئة فوق الصفر، فلن يستطيع Right أن يقطع إلى بادئة تكون فيها Left ميتة مسبقًا. وإذا لم يعد المسار إلى الصفر إلا في الخطوة الأخيرة، فإن Left يخسر أيضًا لأن كل لاحقة حقيقية تنخفض في مكان ما تحت مستواها الابتدائي. أما إذا انتهى التوازن الكلي بقيمة موجبة، فيمكن لـ Left أن يقطع مباشرة بعد آخر مرة كان فيها التوازن مساويًا لـ \(1\)، وعندئذ يترك لاحقة جديدة تجعل Right في وضع خاسر مرة أخرى.
لنرمز بـ \(A_n\) إلى عدد الكلمات التي يفوز فيها Left ويخسر Right. هذه هي بالضبط المسارات التي تبقى جميع مجاميعها الجزئية موجبة. إذا حذفنا أول \(L\)، نحصل على مسار طوله \(n-1\) لا ينزل أبدًا تحت الصفر. ومن نظرية ballot الكلاسيكية أو مبدأ الانعكاس نحصل على
$$A_{2k+1}=\binom{2k}{k},\qquad A_{2k}=\binom{2k-1}{k-1}.$$
وبالتماثل نفسه، تعطي هذه الأعداد أيضًا عدد الكلمات التي يفوز فيها Right ويخسر Left.
الفئة المتوازنة لا تظهر إلا عندما \(n=2k\). في هذه الحالة يبقى المسار موجبًا حتى اللحظة الأخيرة ثم يعود إلى الصفر في الخطوة النهائية. وإذا حذفنا أول \(L\) وآخر \(R\)، نحصل على مسار Dyck بنصف طول يساوي \(k-1\). لذلك يكون عدد هذه الكلمات
$$B_{2k}=\operatorname{Cat}_{k-1}=\frac{1}{k}\binom{2k-2}{k-1}.$$
ومن ثم تكون الصيغ النهائية
$$F(2k+1)=2^{2k+1}-2\binom{2k}{k},$$
$$F(2k)=2^{2k}-2\binom{2k-1}{k-1}-\operatorname{Cat}_{k-1}.$$
عندما \(n=8\)، يكون \(k=4\). عدد كلمات الفئة Left-only هو
$$A_8=\binom{7}{3}=35,$$
والفئة المناظرة Right-only تعطي \(35\) أخرى. أما الفئة المتوازنة neither فعددها
$$B_8=\operatorname{Cat}_3=5.$$
وبما أن العدد الكلي للكلمات هو \(2^8=256\)، نحصل على
$$F(8)=256-35-35-5=181,$$
وهو نفس العدد الذي تتحقق منه التطبيقات. ومثال ملموس على الفئة المتوازنة هو الكلمة \(LLRLRR\) ذات توازنات البوادئ \(1,2,1,2,1,0\). جميع البوادئ الحقيقية موجبة، لكن التوازن الكلي يعود إلى الصفر، ولذلك لا يستطيع أي من اللاعبَين أن يفرض الفوز إذا بدأ من المقطع الكامل.
تقوم تطبيقات C++ وPython وJava بحساب معاملات ذي الحدين بطريقة ضرب متدرج، من دون جداول عامليات ضخمة ومن دون أي تقريب عشري. ويُستخرج حد Catalan من معامل ذي حدين بقسمة صحيحة، بينما يُنتج \(2^n\) مباشرة بإزاحة عدد صحيح. وبعد معرفة زوجية \(n\)، يطبق البرنامج الصيغة المناسبة مباشرة.
يتضمن التنفيذ أيضًا متحققًا كاملا للقيم الصغيرة من \(n\). فهو يعدد جميع الكلمات الممكنة وعددها \(2^n\)، ثم يهيئ حالات المقاطع ذات الطول \(1\) من الحروف نفسها، وبعد ذلك يملأ كل المقاطع الأطول بترتيب تصاعدي في الطول باستخدام العلاقتين الرجوعيتين السابقتين. ثم يقارن النتائج الشاملة مع الصيغة المغلقة للقيم \(n=1\) حتى \(12\)، ويفحص أيضًا على نحو صريح العيّنتين \(F(3)=4\) و\(F(8)=181\)، ثم يحسب في النهاية القيمة المطلوبة عند \(n=60\).
المسار الأساسي للحل هو الصيغة المغلقة. مع الحساب الضربي لمعاملات ذي الحدين، يحتاج هذا المسار إلى \(O(n)\) عملية حسابية وإلى \(O(1)\) ذاكرة إضافية إذا استثنينا الكائن العددي نفسه. وبالنسبة إلى \(n=60\)، فإن هذه الكلفة صغيرة جدًا.
أما مسار التحقق فهو أغلى بكثير عمدًا. إذ يعدد \(2^n\) كلمة، ويملأ لكل كلمة \(O(n^2)\) حالة على المقاطع، وكل حالة قد تفحص حتى \(O(n)\) موضع قطع. لذلك يكون الزمن \(O(2^n n^3)\) والذاكرة \(O(n^2)\)، ولهذا السبب يقتصر هذا الجزء على القيم الصغيرة فقط.