Project Euler

The Chase

One hundred players sit around a circular table. Two opposite players start with one die each. On every turn, the two players who currently hold dice roll them: on a 1, the die is passed to the nei...

Source sync May 21, 2026

Problem #0227

Level Level 09

Solved By 2,460

Languages C++, Python

Answer 3780.618622

Length 278 words

geometryprobabilitylinear_algebra

The Chase is a game played with two dice and an even number of players.

The players sit around a table and the game begins with two opposite players having one die each. On each turn, the two players with a die roll it.

If the player rolls 1, then the die passes to the neighbour on the left.

If the player rolls 6, then the die passes to the neighbour on the right.

Otherwise, the player keeps the die for the next turn.

The game ends when one player has both dice after they have been rolled and passed; that player has then lost.

In a game with 100 players, what is the expected number of turns the game lasts?

Give your answer rounded to ten significant digits.

Problem 227: The Chase

Mathematical Development

The rotational symmetry means that the full state is determined by the shorter circular distance $d$ between the two dice:

d \in \{0,1,\dots,50\}.

State $d=0$ is absorbing.

For one die, the move distribution is

-1 \text{ with probability } \frac16, \qquad 0 \text{ with probability } \frac46, \qquad 1 \text{ with probability } \frac16.

Therefore the distance change for the pair is

\Delta \in \{-2,-1,0,1,2\}

with probabilities

\frac1{36},\ \frac8{36},\ \frac{18}{36},\ \frac8{36},\ \frac1{36}.

If the current state is $d$ , let

r=(d+\Delta)\bmod 100.

Then the actual next state is the shorter of the two arcs:

d'=\min(r,100-r).

Let $E(d)$ be the expected remaining number of turns from state $d$ . Then

E(0)=0

and for $1 \le d \le 50$ ,

E(d)=1+\sum_{d'=1}^{50} T(d,d')\,E(d'),

where $T(d,d')$ is the transition probability. This is a $50\times 50$ linear system:

(I-T)\,E=\mathbf 1.

Editorial

Once the distance between the dice is chosen as the state, nothing else matters. The labels of the players disappear completely, and the stochastic process becomes a small absorbing Markov chain.

The transition law is also tiny. Each die only has three possible effects on the gap, so the combined move has five possibilities, from $-2$ to $+2$ . That means the whole problem is just linear algebra: build the $50\times 50$ transition matrix on the transient states, write down the first-step equations

E(d)=1+\sum T(d,d')E(d'),

and solve them with Gaussian elimination. The wanted value is the expectation from the initial opposite state $d=50$ .

Pseudocode

Build the five probabilities for the net distance change:
    -2, -1, 0, 1, 2.

For each transient state d from 1 to 50:
    For each possible net change:
        update the probability of the resulting shorter-arc distance d'

Form the linear system
    (I - T) * E = 1
on the 50 transient states.

Solve the system by Gaussian elimination.
Output E(50) with 6 digits after the decimal point.

Complexity Analysis

Time: $O(50^3)$ for Gaussian elimination.
Space: $O(50^2)$ for the matrix.

Answer

\boxed{3780.618622}

C++ project_euler/problem_227/solution.cpp

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    const int board = 100;
    const int states = board / 2;
    const vector<pair<int, double>> deltas = {
        {-2, 1.0 / 36.0},
        {-1, 8.0 / 36.0},
        {0, 18.0 / 36.0},
        {1, 8.0 / 36.0},
        {2, 1.0 / 36.0},
    };

    vector<vector<double>> transition(states, vector<double>(states, 0.0));
    for (int distance = 1; distance <= states; distance++) {
        for (const auto& entry : deltas) {
            int delta = entry.first;
            double probability = entry.second;
            int raw = (distance + delta) % board;
            if (raw < 0) raw += board;
            int next = min(raw, board - raw);
            if (1 <= next && next <= states) {
                transition[distance - 1][next - 1] += probability;
            }
        }
    }

    vector<vector<double>> augmented(states, vector<double>(states + 1, 0.0));
    for (int row = 0; row < states; row++) {
        for (int col = 0; col < states; col++) {
            augmented[row][col] = (row == col ? 1.0 : 0.0) - transition[row][col];
        }
        augmented[row][states] = 1.0;
    }

    for (int col = 0; col < states; col++) {
        int pivot = col;
        for (int row = col + 1; row < states; row++) {
            if (fabs(augmented[row][col]) > fabs(augmented[pivot][col])) {
                pivot = row;
            }
        }
        swap(augmented[col], augmented[pivot]);

        for (int row = col + 1; row < states; row++) {
            double factor = augmented[row][col] / augmented[col][col];
            if (factor == 0.0) continue;
            for (int index = col; index <= states; index++) {
                augmented[row][index] -= factor * augmented[col][index];
            }
        }
    }

    vector<double> expectation(states, 0.0);
    for (int row = states - 1; row >= 0; row--) {
        double value = augmented[row][states];
        for (int col = row + 1; col < states; col++) {
            value -= augmented[row][col] * expectation[col];
        }
        expectation[row] = value / augmented[row][row];
    }

    cout << fixed << setprecision(6) << expectation.back() << '\n';
    return 0;
}

Python project_euler/problem_227/solution.py

"""
Problem 227: The Chase

State d is the shorter circular distance between the two dice, so d ranges
from 0 to 50. The expected time satisfies

    E(d) = 1 + sum P(d -> d') * E(d')

for d >= 1. We solve the resulting 50 x 50 linear system.
"""


def gaussian_elimination(matrix):
    n = len(matrix)

    for col in range(n):
        pivot = max(range(col, n), key=lambda row: abs(matrix[row][col]))
        matrix[col], matrix[pivot] = matrix[pivot], matrix[col]

        pivot_value = matrix[col][col]
        for row in range(col + 1, n):
            factor = matrix[row][col] / pivot_value
            if factor == 0.0:
                continue
            for index in range(col, n + 1):
                matrix[row][index] -= factor * matrix[col][index]

    solution = [0.0] * n
    for row in range(n - 1, -1, -1):
        value = matrix[row][n]
        for col in range(row + 1, n):
            value -= matrix[row][col] * solution[col]
        solution[row] = value / matrix[row][row]

    return solution


def solve():
    board = 100
    states = board // 2
    delta_probabilities = {
        -2: 1.0 / 36.0,
        -1: 8.0 / 36.0,
        0: 18.0 / 36.0,
        1: 8.0 / 36.0,
        2: 1.0 / 36.0,
    }

    transition = [[0.0] * states for _ in range(states)]
    for distance in range(1, states + 1):
        for delta, probability in delta_probabilities.items():
            raw = (distance + delta) % board
            new_distance = min(raw, board - raw)
            if 1 <= new_distance <= states:
                transition[distance - 1][new_distance - 1] += probability

    augmented = []
    for row in range(states):
        equation = [0.0] * (states + 1)
        for col in range(states):
            equation[col] = (1.0 if row == col else 0.0) - transition[row][col]
        equation[states] = 1.0
        augmented.append(equation)

    expectations = gaussian_elimination(augmented)
    print(f"{expectations[states - 1]:.6f}")


if __name__ == "__main__":
    solve()