Detailed mathematical approach

Problem Summary

A position is a line segment of length \(L\). A legal move chooses a square with side \(s\in\{1,\sqrt{2}\}\) and places its base on the segment, so the occupied interval has length \(s\). If the left edge is at \(x\), the move removes \([x,x+s]\) and leaves two independent subgames of lengths \(x\) and \(L-s-x\).

The C++, Python, and Java implementations analyze this as a Sprague-Grundy game. They then maximize the scaled average proportion of zero-xor moves

$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right),$

and return

$f(A,B)=\max_{L\in[A,B]} e(L), \qquad (A,B)=(200,500).$

Here \(m(u)\) is the total length of placements that split the remaining segment \(u\) into two subpositions with equal Grundy value. The task is therefore a continuous impartial-game calculation followed by a one-dimensional maximization problem.

Mathematical Approach

The derivation has two layers. First we compute the Grundy function \(g(L)\) for a real segment length. Then we build a second function \(m(u)\) that counts how often a move lands on xor \(0\), and finally maximize the resulting explicit formula for \(e(L)\).

Step 1: Write the continuous Grundy recurrence

For \(0\le L<1\) no square fits, so the position is terminal and

$g(L)=0.$

For larger \(L\), a move of side \(s\in\{1,\sqrt{2}\}\) can start at any \(x\) with \(0\le x\le L-s\). The two remaining parts are independent, so the nimber of that move is

$g(x)\oplus g(L-s-x).$

Therefore

$g(L)=\operatorname{mex}\Bigl(\{g(x)\oplus g(L-1-x):0\le x\le L-1\}\cup\{g(x)\oplus g(L-\sqrt{2}-x):0\le x\le L-\sqrt{2}\}\Bigr),$

where the second set is absent when \(L<\sqrt{2}\). This is the usual Sprague-Grundy recurrence, except that the game parameter is a real length instead of an integer size.

Step 2: Explain why all breakpoints are of the form \(a+b\sqrt{2}\)

Every move removes either \(1\) or \(\sqrt{2}\) from the total occupied length before the remainder is split. Starting from \(0\), the only lengths at which the move structure can change are sums built from these two generators:

$a+b\sqrt{2},\qquad a,b\in\mathbb{Z}_{\ge 0}.$

Because \(\sqrt{2}\) is irrational, different pairs \((a,b)\) produce different real numbers. After sorting these values, any open interval between consecutive breakpoints has the same interaction pattern with all earlier intervals shifted by \(1\) and by \(\sqrt{2}\). Hence the reachable xor-set stays constant throughout that interval, so \(g(L)\) is piecewise constant.

This is the structural simplification used by the implementations: instead of sampling arbitrary real lengths, they store merged intervals on which one Grundy value applies everywhere.

Step 3: Convert zero-xor moves into a measure function

Fix a side length \(s\) and a segment length \(L\). A placement at \(x\) is strategically important when it leaves xor \(0\), because the next player then receives a \(P\)-position. The condition is

$g(x)\oplus g(L-s-x)=0,$

which is equivalent to

$g(x)=g(L-s-x).$

Let \(u=L-s\). The set of such placements has total length

$m(u)=\operatorname{meas}\left(\left\{x\in[0,u]:g(x)=g(u-x)\right\}\right).$

Since the legal interval of left endpoints has length \(u\), the fraction of zero-xor placements for side \(s\) is

$\frac{m(L-s)}{L-s}.$

The objective function is exactly the average of those two fractions, scaled by \(L\):

$e(L)=\frac{L}{2}\left(\frac{m(L-1)}{L-1}+\frac{m(L-\sqrt{2})}{L-\sqrt{2}}\right).$

Step 4: Build \(m(u)\) by convolving equal-Grundy intervals

Suppose two intervals \(I=[A,B]\) and \(J=[C,D]\) carry the same Grundy value. For a fixed \(u\), a point \(x\) contributes to \(m(u)\) when \(x\in I\) and \(u-x\in J\). Equivalently,

$x\in I\cap [u-D,u-C].$

So the contribution from this pair is the overlap length

$\lambda_{I,J}(u)=\operatorname{meas}\left(I\cap [u-D,u-C]\right).$

As \(u\) varies, \(\lambda_{I,J}(u)\) is piecewise linear: it increases linearly, may stay flat, then decreases linearly. Its slope can only change when one endpoint meets another, namely at

$u=A+C,\quad A+D,\quad B+C,\quad B+D.$

Summing these trapezoidal contributions over all interval pairs with equal Grundy value yields a global piecewise-linear spline

$m(u)=s_i u+c_i \qquad (u\in I_i).$

Distinct intervals matter in both orders \((I,J)\) and \((J,I)\), so they receive double weight; a diagonal pair contributes once.

Step 5: Reduce the maximization to endpoints and derivative roots

Once \(m(u)\) is piecewise linear, the function \(e(L)\) becomes elementary on every interval where both shifted arguments stay inside fixed spline pieces. If

$m(L-1)=s_1(L-1)+c_1,\qquad m(L-\sqrt{2})=s_2(L-\sqrt{2})+c_2,$

then

$e(L)=\frac{L}{2}\left(s_1+\frac{c_1}{L-1}+s_2+\frac{c_2}{L-\sqrt{2}}\right).$

A derivative with the same zeros as \(e'(L)\) is

$\left(s_1+s_2\right)-\frac{c_1}{(L-1)^2}-\frac{c_2\sqrt{2}}{(L-\sqrt{2})^2}.$

Therefore every local maximum must occur at an interval endpoint or at an interior root of this expression. The continuous search on \([A,B]\) is reduced to a finite collection of one-dimensional root checks.

Worked Example: Why \(e(2)=2\)

For every \(u<1\), no square fits on a segment of length \(u\), so \(g(u)=0\). Consequently, if \(0\le u\le 1\), then \(g(x)=g(u-x)=0\) for almost every \(x\in[0,u]\), and therefore

$m(u)=u.$

Now set \(L=2\). Then

$L-1=1,\qquad L-\sqrt{2}=2-\sqrt{2}<1.$

For side \(1\), every placement leaves two subsegments whose total length is \(1\), so both subsegments stay below length \(1\) except at measure-zero endpoints; the xor is always \(0\). For side \(\sqrt{2}\), the remaining total length is already below \(1\), so again every placement gives xor \(0\). Hence

$m(1)=1,\qquad m(2-\sqrt{2})=2-\sqrt{2}.$

Substituting into the formula gives

$e(2)=\frac{2}{2}\left(\frac{1}{1}+\frac{2-\sqrt{2}}{2-\sqrt{2}}\right)=2,$

which matches the first validation checkpoint used by the implementations.

How the Code Works

The C++ and Java implementations follow the derivation directly. They first enumerate all breakpoints \(a+b\sqrt{2}\) up to the needed limit, sort them, and scan the resulting intervals from left to right. On each interval they evaluate the reachable xor-set at a midpoint, take the mex, and merge adjacent intervals whenever the Grundy value remains unchanged.

Next they regroup those intervals by Grundy value and form the piecewise-linear spline for \(m(u)\). Each same-Grundy interval pair contributes four event positions where the slope can change, so after sorting the events a single sweep reconstructs every linear piece \(s_i u+c_i\).

Finally they build the \(L\)-breakpoints induced by shifting spline boundaries by \(1\) and \(\sqrt{2}\). On each such interval, the implementation checks the endpoints, looks for sign changes in the derivative expression, and applies bisection when an interior critical point exists. The Python implementation is only a thin wrapper around the C++ solver, while the C++ version also verifies checkpoints before printing the final value, including \(e(2)=2\), \(e(4)=1.11974851\), \(f(2,10)=2.61969775\), and \(f(10,20)=5.99374121\).

Complexity Analysis

Let \(B\) be the number of raw breakpoints \(a+b\sqrt{2}\) up to the search limit, and let \(S\) be the number of merged Grundy intervals after equal neighboring values are coalesced. Generating and sorting the raw breakpoints costs \(O(B\log B)\).

Building the piecewise-constant Grundy table is worst-case \(O(S^2)\), because each new interval may scan a substantial portion of the previously constructed intervals to collect reachable xor values. Constructing \(m(u)\) from equal-Grundy interval pairs is also quadratic in the interval count in the worst case: if \(n_k\) intervals carry Grundy value \(k\), then the pair generation cost is \(O\left(\sum_k n_k^2\right)\), followed by an event sort of the same order up to a logarithmic factor.

The final maximization pass is linear in the number of induced \(L\)-intervals, with only constant-time evaluations plus a fixed number of bisection iterations per interval. Memory usage is \(O(S+E)\), where \(E\) is the number of event records in the spline construction.

Footnotes and References

1. Problem page: Project Euler 644
2. Sprague-Grundy theorem: Wikipedia - Sprague-Grundy theorem
3. Minimal excluded value: Wikipedia - mex
4. Convolution: Wikipedia - Convolution
5. Bisection method: Wikipedia - Bisection method