Detailed mathematical approach

Problem Summary

Two sticks are dropped into a river. Each first passage under the bridge takes an integer number of seconds chosen uniformly from \([n,m]\). Whenever a stick emerges, it is picked up and re-dropped 5 seconds later, so every later cycle time is uniform on \([n+5,m+5]\). The race ends when one stick emerges while the other stick is still somewhere inside its previous passage, meaning that the leader is now exactly one whole passage ahead. For each pair \((m,n)\) we need the expected finishing time \(E(m,n)\), and the overall quantity is

$S(k)=\sum_{m=2}^{k}\sum_{n=1}^{m-1}E(m,n).$

The key observation is that after the first emergence, the full history is irrelevant: only the current time gap and the current race phase matter.

Mathematical Approach

Fix one pair \((n,m)\). Write

$u=n+5,\qquad v=m+5,\qquad q=v-u+1=m-n+1.$

After the first bridge passage, every new cycle time is an independent uniform draw from \(\{u,u+1,\dots,v\}\).

Step 1: Separate the Initial Passage from Later Cycles

The first trip of each stick does not include the 5-second re-drop delay, so the initial draw is uniform on \(\{n,\dots,m\}\). After the first emergence, every future trip does include that delay, which is why the later process uses \(\{u,\dots,v\}\). This separation explains why the implementation treats the opening move differently from the recursive part.

Once the first stick has emerged, the only information that matters is how many seconds remain until the other stick emerges, together with whether the race is in a balanced situation or in a one-pass lead situation.

Step 2: Compress the Race to Gap-and-Phase States

For each integer gap \(r\in\{1,\dots,v\}\), define two expectations:

Let \(X_r\) denote the expected remaining time in the balanced phase with gap \(r\).

Let \(Y_r\) denote the expected remaining time in the one-pass lead phase with gap \(r\).

The balanced phase means that the next emergence will create a one-pass lead but cannot end the race immediately. The one-pass lead phase means that the stick that has just been re-dropped will win immediately if it emerges again before the other stick finishes its current passage.

Simultaneous emergence creates a fresh cycle with a new remaining time distributed uniformly over \(\{u,\dots,v\}\). Therefore we also need the averages

$\bar X=\frac{1}{q}\sum_{r=u}^{v}X_r,\qquad \bar Y=\frac{1}{q}\sum_{r=u}^{v}Y_r.$

Step 3: First-Step Equation for the Balanced Phase

Suppose we are in the balanced phase with gap \(r\), and let \(T\) be the next full cycle time of the stick that was just re-dropped. There are three cases.

If \(T<r\), that stick emerges first after \(T\) seconds. The race is still alive, but now one stick has a one-pass lead and the new gap is \(r-T\), so the continuation is \(Y_{r-T}\).

If \(T=r\), both sticks emerge together after \(r\) seconds. The process restarts in the balanced phase, and the continuation is the averaged quantity \(\bar X\).

If \(T>r\), the other stick emerges first after \(r\) seconds. The race moves to the one-pass lead phase with new gap \(T-r\), so the continuation is \(Y_{T-r}\).

Because \(T\) is uniform on \(\{u,\dots,v\}\), we obtain

$X_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}\left(t+Y_{r-t}\right)+\mathbf{1}_{u\le r\le v}\left(r+\bar X\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+Y_{t-r}\right)\right).$

Step 4: First-Step Equation for the One-Pass Lead Phase

Now suppose we are in the one-pass lead phase with gap \(r\). Again let \(T\) be the next full cycle time of the stick that has just been re-dropped.

If \(T<r\), that leading stick emerges again before the other one finishes its current passage. At that exact moment the race ends, so the additional time is simply \(T\).

If \(T=r\), both sticks emerge together after \(r\) seconds. The lead phase survives, but the exact gap is reset by a fresh uniform draw, so the continuation is \(\bar Y\).

If \(T>r\), the lagging stick emerges first after \(r\) seconds and catches up to the balanced phase. The new gap is \(T-r\), so the continuation is \(X_{T-r}\).

This gives

$Y_r=\frac{1}{q}\left(\sum_{t=u}^{\min(v,r-1)}t+\mathbf{1}_{u\le r\le v}\left(r+\bar Y\right)+\sum_{t=\max(u,r+1)}^{v}\left(r+X_{t-r}\right)\right).$

Step 5: Recover \(E(m,n)\) from the Opening Move

The opening passage times of the two sticks are independent uniform draws \(T_1,T_2\in\{n,\dots,m\}\).

If \(T_1<T_2\), the first stick emerges after \(T_1\) seconds and the race enters the one-pass lead phase with gap \(T_2-T_1\), contributing \(T_1+Y_{T_2-T_1}\).

If \(T_2<T_1\), the contribution is \(T_2+Y_{T_1-T_2}\).

If \(T_1=T_2\), both sticks emerge together and the continuation is the balanced average \(\bar X\), contributing \(T_1+\bar X\).

Therefore

$E(m,n)=\frac{1}{q^2}\left(\sum_{n\le t_1<t_2\le m}\left(t_1+Y_{t_2-t_1}\right)+\sum_{n\le t_2<t_1\le m}\left(t_2+Y_{t_1-t_2}\right)+\sum_{t=n}^{m}\left(t+\bar X\right)\right).$

Worked Example: \(n=1,\ m=2\)

Here the later cycle times are \(u=6\), \(v=7\), and \(q=2\). The averaged states become

$\bar X=\frac{X_6+X_7}{2},\qquad \bar Y=\frac{Y_6+Y_7}{2}.$

Consider the one-pass lead phase with gap \(r=1\). Since every later cycle time is either 6 or 7, the leader cannot win immediately. After 1 second the trailing stick must emerge first, so

$Y_1=1+\frac{X_5+X_6}{2}.$

Now consider the balanced phase with gap \(r=6\). If the new cycle time is 6, both sticks emerge together and the continuation is \(\bar X\). If the new cycle time is 7, the other stick emerges first after 6 seconds and the process moves to \(Y_1\). Hence

$X_6=6+\frac{\bar X+Y_1}{2}.$

At the very start, the ordered opening pairs \((1,2)\) and \((2,1)\) each contribute \(1+Y_1\), while the ties \((1,1)\) and \((2,2)\) contribute \(1+\bar X\) and \(2+\bar X\). This small example shows exactly how the state equations mirror the race rules.

How the Code Works

The C++, Python, and Java implementations solve one pair \((n,m)\) at a time. For each possible gap \(r\), they precompute which cycle times are smaller than \(r\), equal to \(r\), or larger than \(r\), together with the corresponding counts and time sums. That turns the first-step formulas above into a linear system whose unknowns are

$X_1,\dots,X_v,\qquad Y_1,\dots,Y_v,\qquad \bar X,\qquad \bar Y.$

The system therefore has size

$2v+2.$

The implementation fills the coefficient matrix directly from the transition ranges and solves it by Gaussian elimination with partial pivoting. After that, it averages over all opening pairs \((T_1,T_2)\) to obtain \(E(m,n)\). Finally it sums those expectations over every \(1\le n<m\le k\) to obtain \(S(k)\). The Python version delegates to the compiled solver, while the C++ and Java versions implement the same linear-algebra model explicitly; the C++ version also parallelizes the outer summation.

Complexity Analysis

For a fixed pair \((n,m)\), the matrix dimension is \(2v+2=2m+12\). Filling the dense matrix from the interval transitions costs \(O(v^2)\) time, Gaussian elimination costs \(O(v^3)\) time, and the memory usage is \(O(v^2)\). The final opening-pair average contributes only \(O((m-n+1)^2)\), which is smaller than the elimination step for the actual parameter range.

Summing over all pairs for \(S(k)\) gives

$\sum_{m=2}^{k}\sum_{n=1}^{m-1}O((m+5)^3)=O(k^5),$

with peak memory determined by the largest single system, namely \(O(k^2)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=589
2. Markov chain: Wikipedia - Markov chain
3. Absorbing Markov chain: Wikipedia - Absorbing Markov chain
4. Expected value: Wikipedia - Expected value
5. Gaussian elimination: Wikipedia - Gaussian elimination