Project Euler Problem 960

Solution

Answer: 243559751

Let a move between piles $i,j$ remove $a$ and $b$ stones respectively, with

$$a+b=n,\qquad 1\le a,b\le n-1.$$

The score gained is $\min(a,b)$.

Since the total number of stones is $n(n-1)$, and each move removes exactly $n$ stones, every successful game has exactly

$$\frac{n(n-1)}{n}=n-1$$

moves.

1. Tree interpretation

Associate one edge to each move, connecting the two piles used in that move.

There are $n$ vertices (piles).
A successful game has $n-1$ edges.

A standard invariant argument shows:

a successful sequence is possible iff the move graph is a tree;
for an edge whose removal splits the tree into components of sizes

$k$ and $n-k$, the move must remove exactly

$k$ stones from one endpoint and $n-k$ from the other.

Hence the contribution of that edge to the score is

$$\min(k,n-k).$$

Therefore every labeled tree $T$ has a fixed score

$$S(T)=\sum_{e\in T}\min(s_e,n-s_e),$$

where $s_e$ is one side of the cut produced by deleting edge $e$.

2. Counting move orders

For a fixed tree, every permutation of its $n-1$ edges gives a valid successful sequence.

So each tree contributes

$$(n-1)! \cdot S(T)$$

to $F(n)$.

Thus

$$F(n)=(n-1)!\sum_T S(T).$$

3. Counting edges by component size

Fix $k\le n/2$.

How many labeled trees contain an edge whose removal splits the vertices into sets of sizes $k$ and $n-k$?

Choose:

the $k$-set:

$$\binom nk$$ 2. a tree on each side:

$$k^{k-2},\qquad (n-k)^{n-k-2}$$

(Cayley) 3. the connecting edge:

$$k(n-k)$$

Hence the number of such edges is

$$\binom nk k^{k-2}(n-k)^{n-k-2}k(n-k).$$

If $k=n/2$, this is double-counted, so divide by $2$.

Each such edge contributes score $k$.

Therefore

$$\sum_T S(T) = \sum_{k=1}^{\lfloor n/2\rfloor} k\cdot \binom nk k^{k-2}(n-k)^{n-k-2}k(n-k),$$

with an extra factor $1/2$ when $2k=n$.

This reproduces:

$F(3)=12$
$F(4)=360$
$F(8)=16785941760$

exactly.

4. Compute $F(100)\pmod{10^9+7}$

Evaluating the formula modulo

$$M=10^9+7$$

gives

$$F(100)\equiv 243559751 \pmod{10^9+7}.$$

Answer: 243559751