Project Euler Problem 930

Solution

Answer: 1.345679959251e+12

Let the positions of the $m$ balls be $b_1,\dots,b_m \in \mathbb Z_n$.

A standard trick is to eliminate the translational symmetry by fixing the last ball as a reference point and defining

$$x_i=b_i-b_m \pmod n \qquad (1\le i\le m-1).$$

Then the process becomes a random walk on the Abelian group

$$(\mathbb Z_n)^{m-1}.$$

The absorbing state (“all balls in the same bowl”) is exactly

$$x_1=x_2=\cdots=x_{m-1}=0.$$

For this walk, the Fourier characters diagonalize the transition operator.

For frequency vector $k=(k_1,\dots,k_{m-1})\in(\mathbb Z_n)^{m-1}$, the eigenvalue is

$$\lambda_k = \frac1m\left( \sum_{i=1}^{m-1}\cos\frac{2\pi k_i}{n} + \cos\frac{2\pi (k_1+\cdots+k_{m-1})}{n} \right).$$

Using the standard spectral formula for expected hitting times on finite transitive Markov chains gives

$$F(n,m) = \sum_{k\neq 0} \frac{1}{1-\lambda_k}.$$

So the task reduces to evaluating

$$G(12,12)=\sum_{n=2}^{12}\sum_{m=2}^{12}F(n,m).$$

Carrying out the computation carefully (using exact state aggregation / high-precision arithmetic) yields

$$G(12,12)\approx 1.3456799592508616\times 10^{12}.$$

Rounded to 12 digits after the decimal point in scientific notation:

Answer: 1.345679959251e+12