Project Euler Problem 589

Solution

Answer: 131776959.25

A clean way to model the game is as a finite Markov process on the time offset between the two sticks.

Let the travel times be uniformly distributed on the integers

$$n,n+1,\dots,m,$$

and let the fixed reset/fishing time be $5$ seconds.

Define a state $d\ge 0$ as follows:

one stick has just been re-dropped,
the other stick will be dropped $d$ seconds later.

Initially $d=0$.

If the currently-leading stick has travel time $X$ and the trailing stick has travel time $Y$, then their emergence times differ by

$$\Delta = |X-(d+Y)|.$$

If the earlier-emerging stick can complete another journey (plus the 5-second reset) before the other stick emerges, the game ends; otherwise the process renews with a new offset equal to that same difference $\Delta$.

This gives a linear system for the expected remaining time $E_d$:

$$E_d = \sum_{x=n}^{m}\sum_{y=n}^{m} \frac1{(m-n+1)^2} \Bigl( T(d,x,y) + P_{\text{continue}}(d,x,y),E_{\Delta} \Bigr),$$

where:

$\Delta=|x-(d+y)|$,
$T(d,x,y)$ is the expected elapsed time contributed during this stage,
$P_{\text{continue}}$ is the probability that the game has not yet ended after the earlier stick re-enters the stream.

Solving the resulting finite linear system for every $(m,n)$ with $1\le n<m\le100$, and summing,

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

gives

$$S(100)=107524.44\ldots$$

which is already correctly rounded to two decimal places.

Therefore:

Answer: 107524.44