Detailed mathematical approach

Problem Summary

Let \(P(N)\) denote the number of winning opening moves in the \(N\times N\) Flipping Game. The implementations validate the method with

$P(1)=1,\qquad P(2)=0,\qquad P(5)=8,\qquad P(100)=31395,$

and the real target is \(P(10^6)\). The key observation is that a legal rectangle is determined by a triangular height and a square width, so the board can be analyzed through two coupled one-dimensional impartial games.

Mathematical Approach

For a board of size \(N\), define the legal height and width families by

$\mathcal T_N=\left\{\frac{k(k+1)}{2}:k\ge 1,\ \frac{k(k+1)}{2}\le N\right\},\qquad \mathcal S_N=\left\{k^2:k\ge 1,\ k^2\le N\right\}.$

A move is therefore a pair consisting of one allowed vertical interval and one allowed horizontal interval. The solution first analyzes each axis separately and then combines them with nimber multiplication.

Step 1: Build the One-Dimensional Grundy Recurrence

Fix one length family \(\mathcal L\), either \(\mathcal T_N\) or \(\mathcal S_N\). Let \(g_i\) be the Grundy number of the size-\(i\) component on that axis, and let

$x_0=0,\qquad x_i=g_1\oplus g_2\oplus\cdots\oplus g_i.$

The recursive structure used by the implementations implies that a legal choice of length \(\ell\in\mathcal L\) with \(\ell\le i\) leads to a child position whose nimber is

$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}.$

Therefore

$g_i=\operatorname{mex}\left\{y_{i,\ell}:\ell\in\mathcal L,\ \ell\le i\right\}.$

This recurrence is the core of the whole solution.

Step 2: Use Prefix XORs to Evaluate Every Move in \(O(1)\)

Without the prefix values \(x_i\), each child nimber would require xoring a whole interval of earlier Grundy values. The identity

$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}$

compresses that interval into two array accesses and one xor. Since every legal pair \((i,\ell)\) is visited exactly once, the one-dimensional pass is efficient enough even when \(N=10^6\).

Step 3: Convert Child Nimbers into Move Nimbers

Once \(g_i\) is known, a move from the size-\(i\) component to a child nimber \(y_{i,\ell}\) changes that component by

$m_{i,\ell}=g_i\oplus y_{i,\ell}.$

This is the move nimber contributed by that axis. If we count how often each value appears, we obtain a histogram

$c_{\mathcal L}(a)=\#\left\{(i,\ell):\ell\in\mathcal L,\ \ell\le i,\ m_{i,\ell}=a\right\}.$

The total nimber of the whole axis is simply

$X_{\mathcal L}=x_N.$

Step 4: Combine Height and Width by Nimber Multiplication

Let \(X_{\mathcal T}\) be the total nimber of the triangular-height axis and \(X_{\mathcal S}\) the total nimber of the square-width axis. The full board nimber is

$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S},$

where \(\otimes\) denotes nimber multiplication. Likewise, if a row move has nimber \(a\) and a column move has nimber \(b\), the corresponding rectangle move has nimber

$a\otimes b.$

Under normal play, an opening move is winning exactly when it moves to nimber \(0\), which here is equivalent to

$a\otimes b=\Gamma.$

Step 5: Count the Winning Pairs

If \(\Gamma=0\), nimber multiplication has no zero divisors, so

$a\otimes b=0 \iff a=0 \text{ or } b=0.$

Hence the number of winning openings is

$c_{\mathcal T}(0)\sum_b c_{\mathcal S}(b)+c_{\mathcal S}(0)\sum_a c_{\mathcal T}(a)-c_{\mathcal T}(0)c_{\mathcal S}(0).$

If \(\Gamma\neq 0\), every nonzero \(a\) determines a unique partner

$b=a^{-1}\otimes \Gamma,$

so the answer becomes

$P(N)=\sum_{a\ne 0} c_{\mathcal T}(a)\,c_{\mathcal S}\!\left(a^{-1}\otimes \Gamma\right).$

The implementations compute inverses inside a sufficiently large finite nimber field, using \(a^{-1}=a^{q-2}\) for a field size \(q\) larger than every nimber that occurs.

Worked Example: \(N=5\)

For \(N=5\), the legal lengths are

$\mathcal T_5=\{1,3\},\qquad \mathcal S_5=\{1,4\}.$

On the triangular side, the recurrence gives

$g_1=g_2=g_3=g_4=g_5=1,$

so the total axis nimber is \(X_{\mathcal T}=1\). There are \(5+3=8\) legal row intervals, and each one has move nimber \(1\), hence

$c_{\mathcal T}(1)=8.$

On the square side, the recurrence yields

$g_1=1,\qquad g_2=1,\qquad g_3=1,\qquad g_4=2,\qquad g_5=1,$

so

$X_{\mathcal S}=1\oplus 1\oplus 1\oplus 2\oplus 1=2.$

The column histogram is

$c_{\mathcal S}(1)=4,\qquad c_{\mathcal S}(2)=1,\qquad c_{\mathcal S}(3)=2.$

Therefore the board nimber is

$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S}=1\otimes 2=2.$

Because the only row move nimber is \(a=1\), the winning condition forces

$b=1^{-1}\otimes 2=2.$

There are \(8\) such row moves and exactly \(1\) matching column move, so

$P(5)=8\cdot 1=8,$

which matches the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations generate all triangular heights and square widths up to \(N\). For each family they sweep from \(1\) to \(N\), maintain the prefix-xor table \(x_i\), evaluate every reachable child nimber \(y_{i,\ell}\), take the mex to obtain the next Grundy number, and update a histogram of move nimbers \(m_{i,\ell}\).

To keep the mex step fast, the implementation uses temporary frequency storage for the child nimbers that occur at the current size \(i\), then clears only the touched entries. It also starts with a moderate nimber-table size and doubles that size if a larger nimber appears, recomputing only when necessary.

After both axis histograms are known, the implementation computes the total board nimber \(\Gamma\) with memoized recursive nimber multiplication based on Fermat 2-power decomposition. It then applies the counting formulas above: inclusion-exclusion when \(\Gamma=0\), and multiplicative inversion when \(\Gamma\neq 0\). The Python implementation uses the same underlying computation, so the mathematical method is identical across languages.

Complexity Analysis

Let \(t=|\mathcal T_N|\) and \(s=|\mathcal S_N|\). Since \(t=\Theta(\sqrt N)\) and \(s=\Theta(\sqrt N)\), the two one-dimensional passes cost

$O(Nt)+O(Ns)=O(N^{3/2}).$

The final histogram pairing is linear in the nimber-table size actually needed, which is small compared with the \(O(N^{3/2})\) sweep. Memory usage is \(O(N)\) for the prefix data plus the move histograms and temporary frequency tables, so the overall space complexity is linear in \(N\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=459
2. Sprague-Grundy theorem: Wikipedia — Sprague-Grundy theorem
3. Nimber: Wikipedia — Nimber
4. Nim: Wikipedia — Nim