Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Interval Recurrence for the Game

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.

The Prefix-Balance Invariant

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.

Counting the One-Sided Words

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 Even-Length Catalan Correction

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}.$

Worked Example: Why \(F(8)=181\)

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.

How the Code Works

Closed-Form Evaluation

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.

Small-\(n\) Verifier

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\).

Complexity Analysis

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\).

Footnotes and References

1. Problem page: Project Euler 948
2. Bertrand's ballot theorem: Wikipedia - Bertrand's ballot theorem
3. Catalan number: Wikipedia - Catalan number
4. Dyck path: Wikipedia - Dyck path
5. Reflection principle: Wikipedia - Reflection principle