Project Euler Problem 306
The following game is a classic example of Combinatorial Game Theory: Two players start with a strip of n white squares
Solution
Answer: 852938
Let $G(n)$ be the Grundy number of a strip of length $n$. A move paints two adjacent squares black, splitting the strip into two independent subgames of lengths $i$ and $n-i-2$. Therefore:
$$G(n)=\operatorname{mex}{G(i)\oplus G(n-i-2)\mid 0\le i\le n-2}$$
The first player has a winning strategy iff $G(n)\neq 0$.
Checking the small cases:
- $n=1$: $G(1)=0$ (loss)
- $n=2,3,4$: winning
- $n=5$: losing
This gives exactly 3 winning values for $1\le n\le 5$, matching the statement.
Computing the sequence further reproduces the given fact that there are 40 winning values for $1\le n\le 50$.
The key observation is that the Grundy sequence becomes periodic:
- From $n=53$ onward,
- Period $=34$.
Using this periodicity, we count all $n\le 1{,}000{,}000$ with $G(n)\neq 0$, obtaining:
Answer: 852938