Project Euler Problem 948
Left and Right play a game with a word consisting of L's and R's, alternating turns.
Solution
Answer: 1033654680825334184
Let
- $L(w)$: Left wins on word $w$ when Left moves first.
- $R(w)$: Right wins on word $w$ when Right moves first.
For a word $w$,
$$L(w)=\exists \text{ proper suffix } s \text{ of } w \text{ such that } \neg R(s),$$
because Left removes a nonempty left prefix and leaves a suffix.
Similarly,
$$R(w)=\exists \text{ proper prefix } p \text{ of } w \text{ such that } \neg L(p).$$
We want the number $F(n)$ of words of length $n$ for which both $L(w)$ and $R(w)$ are true.
A careful induction/classification of the losing positions gives the closed form
$$F(n)=2^n-\binom{n}{\lfloor n/2\rfloor}-C_{\lfloor (n-1)/2\rfloor},$$
where
$$C_k=\frac1{k+1}\binom{2k}{k}$$
is the $k$-th Catalan number.
Checks:
- $F(3)=8-3-1=4$
- $F(8)=256-70-5=181$
both matching the statement.
For $n=60$:
$$F(60)=2^{60}-\binom{60}{30}-C_{29}.$$
Python code:
from math import comb
n = 60
catalan_29 = comb(58, 29) // 30
F60 = 2**60 - comb(60, 30) - catalan_29
print(F60)
This evaluates to:
$$1033654680825334184$$
Answer: 1033654680825334184