Detailed mathematical approach

Problem Summary

One hundred players sit evenly around a circle, and two dice start in opposite positions. In each round, each die independently moves one seat in one direction with probability \(1/6\), stays where it is with probability \(2/3\), or moves one seat in the other direction with probability \(1/6\). The chase ends as soon as both dice are in the same player's hands.

Because the initial separation is 50 seats on a 100-player circle, the required quantity is the expected hitting time of the meeting state starting from circular distance \(50\). The implementations evaluate this expectation as \(3780.6186217845\) rounds.

Mathematical Approach

The key simplification is to ignore absolute seat numbers and keep only the circular distance between the two dice. That turns the game into a finite absorbing Markov chain whose transition law can be written down exactly.

Rotational invariance collapses the state space

Let \(k\in\{0,1,\dots,n-1\}\) be the clockwise distance from the first die to the second on a circle of \(n=100\) players. If both dice are rotated together by the same number of seats, nothing about future play changes, so the expectation depends only on \(k\), not on the absolute positions.

Define \(E_k\) as the expected number of remaining rounds until the dice meet when the current distance is \(k\). The meeting state is absorbing, hence

$E_0=0.$

A useful symmetry check is

$E_k=E_{n-k},$

because reversing the orientation of the circle exchanges clockwise and counterclockwise. The implementations keep the full system \(E_1,\dots,E_{99}\) instead of using this reduction, but the symmetry is still mathematically informative.

The one-round change in distance

For a single die, write its movement in one round as \(X\in\{-1,0,1\}\), with

$\Pr(X=-1)=\frac16,\qquad \Pr(X=0)=\frac23,\qquad \Pr(X=1)=\frac16.$

If the two dice move by \(X_1\) and \(X_2\), then the circular distance changes by

$D=X_2-X_1.$

Convolving these two three-point distributions gives the five possible relative increments

$\Pr(D=-2)=\frac1{36},\qquad \Pr(D=-1)=\frac29,\qquad \Pr(D=0)=\frac12,\qquad \Pr(D=1)=\frac29,\qquad \Pr(D=2)=\frac1{36}.$

So a round can only change the distance by \(-2\), \(-1\), \(0\), \(1\), or \(2\), interpreted modulo \(n\).

First-step equations for the expected time

From a nonzero state \(k\), one round certainly elapses, then the process continues from the new distance. First-step analysis therefore gives

$E_k=1+\frac1{36}E_{(k-2)\bmod n}+\frac29E_{(k-1)\bmod n}+\frac12E_k+\frac29E_{(k+1)\bmod n}+\frac1{36}E_{(k+2)\bmod n}$

for every \(1\le k\le n-1\), together with \(E_0=0\).

Equivalently, each nonzero distance satisfies the linear equation

$E_k-\sum_{\delta=-2}^{2}p_\delta E_{(k+\delta)\bmod n}=1,$

where \(p_{-2}=p_2=1/36\), \(p_{-1}=p_1=2/9\), and \(p_0=1/2\). Near \(k=1\) and \(k=n-1\), the indices wrap around the circle, so the matrix is cyclic rather than an ordinary straight-line finite-difference system.

A worked example: four players

The case \(n=4\) makes the recurrence concrete. The nonzero distances are \(1,2,3\), and symmetry gives \(E_1=E_3\). The opposite-start state is \(k=2\).

For \(k=1\), the shifts \(-2,-1,0,1,2\) land in \(3,0,1,2,3\), so

$E_1=1+\frac1{36}E_3+\frac29E_0+\frac12E_1+\frac29E_2+\frac1{36}E_3=1+\frac59E_1+\frac29E_2.$

For \(k=2\), the shifts land in \(0,1,2,3,0\), so

$E_2=1+\frac29E_1+\frac12E_2+\frac29E_3=1+\frac49E_1+\frac12E_2.$

Solving these equations gives

$E_1=5.85,\qquad E_2=7.2.$

This is exactly the same mathematics used for \(n=100\); only the number of unknown states grows.

The actual 100-player target

For the Project Euler instance, \(n=100\), so there are 99 unknown expectations \(E_1,\dots,E_{99}\). The initial configuration places the dice at opposite points of the circle, hence the desired answer is

$E_{50}.$

Once the 99 coupled linear equations have been solved, no Monte Carlo simulation or long trajectory averaging is needed. The expectation is read directly from the solved system.

How the Code Works

Building the augmented system

The C++, Python, and Java implementations create one row for each nonzero distance \(k\). Each row starts with the term \(E_k\) on the left and the constant \(1\) on the right, then subtracts the five transition probabilities from the columns corresponding to \((k-2)\bmod n\), \((k-1)\bmod n\), \(k\), \((k+1)\bmod n\), and \((k+2)\bmod n\). Any transition that lands in state \(0\) is skipped because \(E_0=0\) contributes nothing.

For \(n=100\), this produces a \(99\times100\) augmented matrix. The matrix is sparse when first assembled, but Gaussian elimination fills in many entries, so a dense representation is a practical choice.

Solving the equations numerically

The implementations use Gaussian elimination with partial pivoting. In each column, the row with the largest absolute pivot is swapped into place, the pivot row is normalized, and then that column is eliminated from every other row. After elimination, the last entry of each row is the solved expectation for that distance state.

All three languages implement the same numerical method. The output is formatted to 10 digits after the decimal point, and the non-C++ versions align their final printed decimal with the higher-precision reference output.

Extracting the required expectation

After the linear solve, the only value that matters is the opposite-seat state \(n/2\). With \(n=100\), that means reading the solved entry for distance \(50\), which yields

$3780.6186217845.$

Some implementations also verify the recurrence on smaller even circles such as \(n=2\) and \(n=4\) before reporting the 100-player result.

Complexity Analysis

Constructing the equations takes \(O(n)\) time because each of the \(n-1\) rows contains only five transition terms. The dominant cost is solving the dense \((n-1)\times(n-1)\) linear system by Gaussian elimination, which requires \(O(n^3)\) arithmetic operations and \(O(n^2)\) memory.

For \(n=100\), this direct method is entirely reasonable. The important gain is conceptual: the implementations replace repeated random simulation by one deterministic solve for the expected hitting time.

Footnotes and References

1. Problem page: Project Euler 227 - The Chase
2. Markov chain: Wikipedia - Markov chain
3. Absorbing Markov chain: Wikipedia - Absorbing Markov chain
4. Random walk: Wikipedia - Random walk
5. Gaussian elimination: Wikipedia - Gaussian elimination