Project Euler Problem 522

Project Euler Problem 522

Solution

Answer: 96772715

Model the hotel as a functional digraph on $n$ labeled vertices with:

• every vertex has outdegree $1$,
• no self-loops (each floor sends power to a different floor).

A configuration is “good” iff the graph is a single directed $n$-cycle.

For a given configuration, the minimum number of rewires equals:

$$(\text{number of indegree-0 vertices}) + (\text{number of isolated directed cycle components}) - [\text{already a single } n\text{-cycle}]$$

Summing over all loopless functional digraphs gives:

$$F(n) = n(n-1)(n-2)^{n-1} + \sum_{k=2}^{n-1} \binom{n}{k}(k-1)!(n-k-1)^{n-k}$$

Equivalently,

$$F(n) = n(n-1)(n-2)^{n-1} + n!\sum_{m=1}^{n-2} \frac{(m-1)^m}{m!(n-m)}$$

This reproduces the stated checks:

• $F(3)=6$
• $F(8)=16276736$
• $F(100)\bmod 135707531=84326147$

Evaluating the formula modulo

$$135707531$$

for

$$n=12344321$$

gives:

Answer: 96772715