Project Euler Problem 459
The flipping game is a two player game played on an N by N square board.
Solution
Answer: 3996390106631
The key insight is that this is an impartial combinatorial game, so the correct framework is Sprague–Grundy theory. The game is a special case of a tartan game, and Pearson’s tartan theorem shows that the 2D rectangle game factorizes into two independent 1D games:
- a 1D game with allowed move lengths = perfect squares,
- a 1D game with allowed move lengths = triangular numbers.
If $G_S(n)$ and $G_T(n)$ are the corresponding 1D nimbers, then the $N\times N$ board has nimber
$$G(N)=G_S(N)\otimes G_T(N),$$
where $\otimes$ is nimber multiplication.
A first move is winning iff the nimber of the chosen rectangle equals the nimber of the whole board.
Thus the computation reduces to:
- compute all strip nimbers in the two 1D games,
- count frequencies of each nimber value,
- count pairs $(a,b)$ such that
$$a\otimes b = G(N).$$
The efficient recurrence for the 1D prefix-xor values $C[n]$ is:
$$C[n+1] = \operatorname{mex}\Bigl( {, C[n]\oplus C[n-L] : L\in\mathcal L,\ L\le n ,} \Bigr) \oplus C[n],$$
where $\mathcal L$ is the allowed set of lengths.
Using this recurrence together with fast nimber multiplication yields an implementation fast enough for $N=10^6$. The sample checks are:
- $W(1)=1$
- $W(2)=0$
- $W(5)=8$
- $W(100)=31395$
all matching the statement.
Answer: 156159626