Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 306: Paper-strip Game

Project Euler Problem 306 Solution

EulerSolve provides an optimized solution for Project Euler Problem 306, Paper-strip Game, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We play on a strip of length $n$. A move removes two adjacent cells, so the strip breaks into a left part and a right part. Under normal play, the player who makes the last legal move wins. The Project Euler question asks for how many lengths $1 \le n \le 10^6$ the starting player has a winning strategy. Mathematical Approach 1) This is an impartial splitting game If we remove the domino covering positions $\ell+1$ and $\ell+2$, the remaining cells split into two independent strips of lengths $\ell \quad \text{and} \quad n-2-\ell.$ Because the two sides no longer interact, the position after one move is the disjoint sum of two smaller games. That is exactly the setting where Sprague-Grundy theory applies. 2) Grundy recurrence Let $g(n)$ be the Grundy number of a strip of length $n$. The empty strip and the length-1 strip have no legal move, so $g(0)=0,\qquad g(1)=0.$ For $n \ge 2$, every legal move produces the xor of two smaller Grundy numbers, hence $g(n)=\operatorname{mex}\{g(\ell)\oplus g(n-2-\ell): 0\le \ell \le n-2\}.$ The mex operator returns the smallest nonnegative integer that does not appear among the reachable xor-values....

Detailed mathematical approach

Problem Summary

We play on a strip of length $n$. A move removes two adjacent cells, so the strip breaks into a left part and a right part. Under normal play, the player who makes the last legal move wins. The Project Euler question asks for how many lengths $1 \le n \le 10^6$ the starting player has a winning strategy.

Mathematical Approach

1) This is an impartial splitting game

If we remove the domino covering positions $\ell+1$ and $\ell+2$, the remaining cells split into two independent strips of lengths

$\ell \quad \text{and} \quad n-2-\ell.$

Because the two sides no longer interact, the position after one move is the disjoint sum of two smaller games. That is exactly the setting where Sprague-Grundy theory applies.

2) Grundy recurrence

Let $g(n)$ be the Grundy number of a strip of length $n$. The empty strip and the length-1 strip have no legal move, so

$g(0)=0,\qquad g(1)=0.$

For $n \ge 2$, every legal move produces the xor of two smaller Grundy numbers, hence

$g(n)=\operatorname{mex}\{g(\ell)\oplus g(n-2-\ell): 0\le \ell \le n-2\}.$

The mex operator returns the smallest nonnegative integer that does not appear among the reachable xor-values.

3) Why the code only scans half the split positions

The move with split $(\ell,n-2-\ell)$ gives the same xor-value as the mirrored move $(n-2-\ell,\ell)$, because xor is commutative:

$g(\ell)\oplus g(n-2-\ell)=g(n-2-\ell)\oplus g(\ell).$

So the implementation only iterates while $\ell \le n-2-\ell$. This does not change the reachable set; it only avoids duplicate work.

4) Small worked table

The first few values already show the mechanism clearly.

For $n=2$, the only move leaves $(0,0)$, so the reachable set is $\{0\}$, hence

$g(2)=\operatorname{mex}\{0\}=1.$

For $n=4$, the legal splits are $(0,2)$ and $(1,1)$, so the reachable set is

$\{g(0)\oplus g(2),\ g(1)\oplus g(1)\}=\{1,0\},$

therefore

$g(4)=\operatorname{mex}\{0,1\}=2.$

For $n=5$, the only distinct splits are $(0,3)$ and $(1,2)$, and both give xor-value $1$. Thus

$g(5)=\operatorname{mex}\{1\}=0.$

So length $5$ is a losing position: every legal move hands a winning position to the opponent.

5) Winning and losing lengths

A position is losing exactly when its Grundy number is zero. Therefore a strip length $n$ is winning iff

$g(n)\neq 0.$

The computed prefix begins

$g(1..10)=(0,1,1,2,0,3,1,1,0,3).$

So the first losing lengths are

$1,5,9,15,\dots$

and among $1 \le n \le 5$ the winners are $2,3,4$. This matches the checkpoint

$\texttt{solve(5)}=3.$

The source also checks

$\texttt{solve(50)}=40.$

6) Eventual periodicity

For many finite splitting games, the Grundy sequence eventually becomes periodic, and this game shows that behavior too. The implementation does not prove periodicity from first principles; instead it computes a long prefix and verifies the pattern

$g(n)=g(100+((n-100)\bmod 34))$

for every

$100 \le n \le 1200.$

After that validation step, the solver safely reuses the same period-$34$ block to count winning lengths up to $10^6$. So the program relies on a checked empirical periodicity, not on an unproved guess.

How the Code Works

1) Prefix computation. compute_grundy(n) builds the table $g(0),g(1),\dots,g(n)$ in increasing order, so when it needs $g(\ell)$ and $g(n-2-\ell)$, those values already exist.

2) Fast mex with timestamps. Instead of clearing a boolean array for every length, the code stores seen[value] = length. Then a value is known to belong to the current reachable set exactly when seen[value] == length. This is a classic timestamp trick.

3) Periodic lookup. solve() precomputes Grundy values up to $1200$. For $n \le 100$ it reads the exact value; for $n > 100$ it maps $n$ back into the verified period window.

4) Counting winners. The final loop tests whether the selected Grundy value is nonzero and increments the answer. Because the code still scans all lengths $1$ through $N$, the final counting phase is linear in $N$, even though each lookup itself is constant time.

Complexity Analysis

If $P$ is the precomputed prefix length, the Grundy table costs about $O(P^2)$, because each $g(n)$ scans $O(n)$ split points. In the actual program $P=1200$, so this stage is tiny. The final counting pass is $O(N)$ for the requested limit $N=10^6$. Memory usage is $O(P)$.