Detailed mathematical approach

Problem Summary

There are \(n\) boats in front-to-back order, initially separated by \(40\) metres. Boat \(j\) rows at a constant random speed

$v_j=-\log X_j,\qquad X_j\sim U(0,1),$

with the \(X_j\) independent. A boat stops as soon as it bumps the boat directly ahead or reaches the finish line. Each bump is an adjacent swap, so the race ends with a final permutation \(\pi\) of the starting order. The goal is to compute the probability that this final permutation is even. For the actual problem we need the case \(n=13\) and \(L=1800\).

Mathematical Approach

The implementations do not track even and odd outcomes separately. Instead, they work with the expected sign of the final permutation, because the sign of a concatenation of independent permutation blocks multiplies cleanly.

Step 1: Remove the 40-metre scale

Because every starting gap equals \(40\), we divide all distances by \(40\) and set

$m=\frac{L}{40}.$

So the target instance becomes \((n,m)=(13,45)\).

If the boats are indexed from front to back, then boat \(k\) has

$r_k=m-k+1$

scaled units of unobstructed water available before its first decisive event. Summing these distances gives

$R(n,m)=\sum_{k=1}^{n} r_k = nm-\frac{n(n-1)}{2}.$

Step 2: Replace parity probabilities by an expected sign

Let \(\operatorname{sgn}(\pi)=+1\) for an even permutation and \(-1\) for an odd permutation. Define

$\Sigma(n,m)=\mathbb{E}[\operatorname{sgn}(\pi)].$

Then

$\Sigma(n,m)=P_{\mathrm{even}}(n,m)-P_{\mathrm{odd}}(n,m)=2p(n,m)-1,$

so the required probability is recovered by

$p(n,m)=\frac{1+\Sigma(n,m)}{2}.$

This single quantity is exactly what the dynamic program stores.

Step 3: Identify the first decisive event

Boat \(k\) needs to cover distance \(r_k\) before its first decisive event occurs, so its associated time scale is

$T_k=\frac{r_k}{v_k}=-\frac{r_k}{\log X_k}.$

Now define the transformed variable

$Y_k=X_k^{1/r_k}=e^{-v_k/r_k}.$

The map between \(T_k\) and \(Y_k\) is monotone decreasing, so the first decisive event is determined by the largest \(Y_k\).

For \(0\le y\le 1\),

$\Pr(Y_k\le y)=\Pr(X_k\le y^{r_k})=y^{r_k},$

hence \(Y_k\) has density \(r_k y^{r_k-1}\). Therefore

$\Pr\!\bigl(Y_k=\max(Y_1,\dots,Y_n)\bigr)=\int_0^1 r_k y^{r_k-1}\prod_{j\ne k} y^{r_j}\,dy=\frac{r_k}{R(n,m)}.$

So the first decisive event chooses index \(k\) with weight

$\frac{m-k+1}{nm-\frac{n(n-1)}{2}}.$

Step 4: Split the race after that first event

Condition on the first decisive event being attached to boat \(k\). Then the leading block of \(k\) boats becomes a closed Torpids subrace on the critical course \(k-1\): once that first event is fixed, there is no spare scaled water left inside that block. The boats behind it never interact with that resolved block again.

After deleting the resolved leading block, the remaining boats form a fresh instance of the same process with \(n-k\) boats and course parameter \(m-k\).

Because permutation signs multiply under concatenation, the conditional contribution to the expected sign is

$\Sigma(k,k-1)\,\Sigma(n-k,m-k).$

Step 5: Recurrence and boundary values

Averaging over all possible values of \(k\) yields the main recurrence, valid for \(m\ge n\):

$\Sigma(n,m)=\sum_{k=1}^{n}\frac{m-k+1}{nm-\frac{n(n-1)}{2}}\;\Sigma(k,k-1)\,\Sigma(n-k,m-k).$

The trivial base cases are

$\Sigma(0,m)=\Sigma(1,m)=1,$

because with zero or one boat the final permutation is always even.

At the critical boundary \(m=n-1\), the newly added last boat contributes a fixed parity factor of \((-1)^{n-1}\), while the remaining uncertainty is exactly the \((n-1,n-1)\) instance. Thus

$\Sigma(n,n-1)=(-1)^{n-1}\Sigma(n-1,n-1).$

These formulas completely determine every state needed by the dynamic program.

Step 6: Worked Example: \(n=3\), \(L=160\)

Here \(m=160/40=4\). Start with the small boundary values

$\Sigma(1,0)=1,\qquad \Sigma(2,1)=-1.$

For \((n,m)=(2,2)\), the recurrence gives

$\Sigma(2,2)=\frac{2}{3}\Sigma(1,0)\Sigma(1,1)+\frac{1}{3}\Sigma(2,1)\Sigma(0,0)=\frac{2}{3}-\frac{1}{3}=\frac{1}{3}.$

Therefore the critical value for three boats is

$\Sigma(3,2)=(-1)^2\Sigma(2,2)=\frac{1}{3}.$

Now apply the main recurrence at \((3,4)\). Since

$R(3,4)=3\cdot 4-\frac{3\cdot 2}{2}=9,$

the weights are \(4/9\), \(3/9\), and \(2/9\). Also \(\Sigma(2,3)=1/5\). Hence

$\Sigma(3,4)=\frac{4}{9}\cdot 1\cdot \frac{1}{5}+\frac{3}{9}\cdot (-1)\cdot 1+\frac{2}{9}\cdot \frac{1}{3}\cdot 1=\frac{4}{45}-\frac{1}{3}+\frac{2}{27}=-\frac{23}{135}.$

So the even-permutation probability is

$p(3,4)=\frac{1+\Sigma(3,4)}{2}=\frac{1-23/135}{2}=\frac{56}{135}.$

This is the exact small checkpoint reproduced by the implementations.

How the Code Works

The C++, Python, and Java implementations build a two-dimensional table of expected signs for every state up to \((13,45)\). They first fill the trivial rows for \(0\) and \(1\) boat, then assign the boundary values at \(m=n-1\), and finally sweep all larger \(m\) bottom-up with the recurrence above.

Every entry only depends on states that have already been computed, so the iteration order is straightforward and stable. After the table is complete, the implementation converts the stored expected sign into the desired probability with

$p=\frac{1+\Sigma}{2}.$

The arithmetic is done in high-precision decimal form so that repeated weighted sums do not introduce visible rounding drift before the final answer is rounded to \(10\) decimal places. The same table also reproduces the exact smaller values \(56/135\) for \((3,4)\) and \(521/1020\) for \((4,10)\).

Complexity Analysis

Let \(m=L/40\). The table contains \(O(nm)\) states. Each nontrivial state performs a sum over \(k=1,\dots,n\), so the total running time is

$O(n^2m).$

The memory usage is dominated by the table itself, which stores one high-precision number per state:

$O(nm).$

For the target instance \((13,45)\), both bounds are very small.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=597
2. Exponential distribution: Wikipedia — Exponential distribution
3. Parity of a permutation: Wikipedia — Parity of a permutation
4. Order statistic: Wikipedia — Order statistic
5. Continuous uniform distribution: Wikipedia — Continuous uniform distribution