Project Euler Problem 960 Solution

Project Euler Problem 960 Statement

There are $n$ distinct piles of stones, each of size $n-1$. Starting with an initial score of $0$, the following procedure is repeated:

Choose any two piles and remove exactly $n$ stones in total from the two piles.
If the number of stones removed from the two piles were $a$ and $b$, add $\min(a,b)$ to the score.

If all piles are eventually emptied, the current score is confirmed as final. However, if one gets "stuck" and cannot empty all piles, the current score is discarded, resulting in a final score of $0$.

Three example sequences of turns are illustrated below for $n=4$, with each tuple representing pile sizes as one proceeds, and with additions to the score indicated above the arrows. $$ \begin{align} &(3,3,3,3)\xrightarrow{+1}(0,3,2,3)\xrightarrow{+1}(0,3,1,0)\xrightarrow{+1}(0,0,0,0)&:\quad\text{final score }=3\\ &(3,3,3,3)\xrightarrow{+1}(3,0,3,2)\xrightarrow{+2}(1,0,3,0)\xrightarrow{+1}(0,0,0,0)&:\quad\text{final score }=4\\ &(3,3,3,3)\xrightarrow{+2}(1,3,1,3)\xrightarrow{+1}(1,2,1,0)\rightarrow\text{stuck!}&:\quad\text{final score }=0 \end{align} $$

Define $F(n)$ to be the sum of the final scores achieved for every sequence of turns which successfully empty all piles.

You are given $F(3)=12$, $F(4)=360$, and $F(8)=16785941760$.

Find $F(100)$. Give your answer modulo $10^9+7$.

Solution

Project Euler Problem 960 overview:

Solution Summary

Core idea: Every valid sequence of moves corresponds to a tree.

Each pile is a vertex

Each move (choosing two piles and removing stones) is an edge between those two vertices

There are exactly $n - 1$ moves (since each move removes $n$ stones and there are $n(n - 1)$ stones total)

The graph has $n$ vertices and $n - 1$ edges

You cannot use the same pair of piles twice: two moves on the same pair would remove $2n$ stones from them, but they only have $2(n - 1)$ stones total.

The graph must be connected; otherwise, one connected component would have both:

Total stones = (number of vertices in component) × $(n - 1)$

Total removed via moves = (number of edges in component) × $n$

This is only possible for the whole set of piles, not a proper subset.

So the move-graph is a simple connected graph with $n$ vertices and $n - 1$ edges, i.e. a tree.

Solution Detail

Score Calculation

The score of a sequence depends only on the tree, not on the order or the exact $a, b$ removals.

For a given tree, any valid way of assigning move amounts that empties all piles leads to the same total score.

Remove an edge $e$: the tree splits into two components with sizes $k$ and $n - k$.

The total contribution of that edge to the score is exactly:

\[ \min(k, n - k) \]

So for a fixed tree $T$:

\[ \text{score}(T) = \sum_{\text{edges } e \in T} \min(|A_e|, n - |A_e|) \]

where $A_e$ is one of the two components when you remove $e$.

Counting Sequences

Each tree corresponds to $(n - 1)!$ different sequences.

Once you fix the tree (which edges are used), the valid move amounts are forced.

The only remaining freedom is the order in which you apply the $n - 1$ moves (edges).

Any permutation of the edges gives a valid sequence that empties all piles with the same score for that tree.

Therefore, if we let:

\[ S(n) = \sum_{\text{all labeled trees } T} \text{score}(T) \]

then:

\[ F(n) = (n - 1)! \cdot S(n) \]

Computing $S(n)$

Compute $S(n)$ by counting edges by split sizes.

For each $k = 1, \ldots, \lfloor n/2 \rfloor$, consider edges whose removal splits the tree into parts of sizes $k$ and $n - k$, with $k$ being the smaller side.

Each such edge contributes $k$ to the score.

Combinatorial construction:

Choose the set $S$ of $k$ vertices: $\binom{n}{k}$ ways
Choose a labeled tree on $S$: $k^{k-2}$ ways (Cayley)
Choose a labeled tree on the complement: $(n - k)^{n - k - 2}$ ways
Choose which vertex in $S$ and which in the complement are joined by the bridging edge: $k(n - k)$ ways

So the number of triples (tree, edge, "smaller side" of size $k$) is:

\[ \binom{n}{k} \cdot k^{k-2} \cdot (n - k)^{n - k - 2} \cdot k(n - k) \]

Special case: When $n$ is even and $k = n/2$, both sides have size $k$, so each such edge is counted twice. Divide by 2 for this case.

Thus:

\[ S(n) = \sum_{k=1}^{\lfloor n/2 \rfloor} k \cdot \binom{n}{k} \cdot k^{k-2} \cdot (n - k)^{n - k - 2} \cdot k(n - k) \cdot \begin{cases} 1, & 2k < n, \\ \frac{1}{2}, & 2k = n \end{cases} \]

Final Formula

\[ F(n) = (n - 1)! \cdot S(n) \pmod{10^9 + 7} \]

Python Source Code

from math import comb, factorial

n, MOD = 1000, 10**9 + 7
ans = 0

for k in range(1, n//2 + 1):
    ck = 1 if k == 1 else pow(k, k-2, MOD)
    term = k*ck*pow(n-k, n-k-2, MOD) * comb(n, k)*k*(n-k) % MOD
    if 2 * k == n:
        term *= (MOD+1) // 2 % MOD
    ans = (ans + term) % MOD

print(ans * factorial(n - 1) % MOD)