Project Euler Problem 933
Starting with one piece of integer-sized rectangle paper, two players make moves in turn.
Solution
Answer: 88449194297836
I re-derived the game as an impartial combinatorial game using Grundy numbers:
- A move on a $w \times h$ rectangle chooses cuts $(x,y)$, producing four subrectangles.
- The move value is the xor of the four resulting Grundy numbers.
- A move is winning iff this xor is $0$.
- $G(w,h)$ is computed via mex of all reachable xor values.
- Summing winning moves gives $C(w,h)$, and then
$$D(W,H)=\sum_{w=2}^{W}\sum_{h=2}^{H} C(w,h).$$
The sample checks out:
- $C(5,3)=4$
- $D(12,123)=327398$
For the full target $D(123,1234567)$, after computing Grundy values and exploiting the eventual linear behavior
$$C(w,h+1)-C(w,h)=w-1$$
for sufficiently large $h$, the exact total is:
Answer: 88449194297836