Project Euler Problem 649

Solution

Answer: 924668016

Let the board coordinates be $0,\dots,n-1$ in each direction, with a coin at $(x,y)$. A move reduces exactly one coordinate by one of ${2,3,5,7}$, so the game is an impartial normal-play game and decomposes into independent subgames.

1. Mathematical analysis

Step 1: Grundy values in one dimension

Define $g(k)$ as the Grundy number for a token on a line at coordinate $k$.

The recurrence is

$$g(k)=\operatorname{mex}{g(k-2),g(k-3),g(k-5),g(k-7)},$$

where only valid predecessors are included.

Computing the first terms:

$$0,0,1,1,2,2,3,3,4,0,0,1,1,2,2,3,3,4,\dots$$

This is periodic with period $9$:

$$(0,0,1,1,2,2,3,3,4).$$

Thus each coordinate contributes one of ${0,1,2,3,4}$.

For

$$n=10{,}000{,}019,$$

we have

$$10{,}000{,}019 = 9\cdot 1{,}111{,}113 + 2.$$

So the coordinate Grundy counts are:

$$#(0)=2q+2,\quad #(1)=2q,\quad #(2)=2q,\quad #(3)=2q,\quad #(4)=q,$$

with $q=1{,}111{,}113$, i.e.

$$(2222228,\ 2222226,\ 2222226,\ 2222226,\ 1111113).$$

Step 2: Grundy value of a square

Since horizontal and vertical moves are independent,

$$G(x,y)=g(x)\oplus g(y).$$

Counting all board squares by xor value gives:

$$v = \bigl( 20987734567981,, 19753162469208,, 19753162469208,, 19753162469208,, 4938292839528,, 4938288395076,, 4938288395076,, 4938288395076 \bigr),$$

for Grundy values $0,\dots,7$.

Step 3: $100$ distinguishable coins

The total position Grundy is the xor of all coin Grundies.

Alice wins iff the xor is nonzero.

Because coins are distinguishable and may overlap, the number of configurations with xor $0$ is the $100$-fold xor convolution coefficient at $0$.

Using the Walsh–Hadamard transform:

$$L = \frac{1}{8} \sum_{k=0}^{7} \widehat v(k)^{100},$$

where

$$\widehat v = ( 100000380000361,, 1234576543225,, 1234576543225,, 1234576543225,, 60494063950849,, 1234567654321,, 1234567654321,, 1234567654321 ).$$

The total number of arrangements is

$$T=(n^2)^{100}.$$

Hence

$$M(n,100)=T-L.$$

Taking the last $9$ digits yields:

$$M(10{,}000{,}019,100)\equiv 924668016 \pmod{10^9}.$$

2. Python implementation

from collections import Counter

MOD = 10**9
n = 10_000_019
c = 100

# 1D Grundy pattern (period 9)
pattern = [0, 0, 1, 1, 2, 2, 3, 3, 4]

# Count coordinate Grundy frequencies
q, r = divmod(n, 9)

coord_count = [0] * 5
for g in pattern:
    coord_count[g] += q
for g in pattern[:r]:
    coord_count[g] += 1

# Count board-square Grundy values G(x,y)=gx xor gy
board_count = [0] * 8
for gx, cx in enumerate(coord_count):
    for gy, cy in enumerate(coord_count):
        board_count[gx ^ gy] += cx * cy

# Walsh-Hadamard transform values
transform = []
for mask in range(8):
    s = 0
    for x, v in enumerate(board_count):
        if bin(mask & x).count("1") % 2:
            s -= v
        else:
            s += v
    transform.append(s)

# Number of losing positions (xor = 0)
losing = sum(pow(x, c) for x in transform) // 8

# Total arrangements
total = pow(sum(board_count), c)

answer = (total - losing) % MOD
print(answer)

3. Verification on examples

The same method gives:

$M(3,1)=4$
$M(3,2)=40$
$M(9,3)=450304$

matching the problem statement exactly.

4. Final verification

Total arrangements are enormous: $(10{,}000{,}019^2)^{100}$, so only modular arithmetic is practical.
The transform method is exact and exploits xor-independence.
Small cases match perfectly, confirming the recurrence and periodicity.

Answer: 924668016