Solution

Answer: 0.5001817828

Let the boats be indexed $1,2,\dots,n$ from lowest to highest in the starting order.

Boat $i$ starts $40(i-1)$ metres upstream from the lowest boat, so its remaining distance to the finish is

$$d_i=L-40(i-1).$$

The speeds are i.i.d.

$$v_i=-\log X_i \sim \text{Exp}(1).$$

We want the probability that the final permutation is even.

1. Key mathematical insight

Suppose boat $i$ is chasing boat $i+1$.

They begin $40$ metres apart, so a bump occurs iff

$$\frac{40}{v_i-v_{i+1}} \le \frac{d_i}{v_i}.$$

After rearranging,

$$d_{i+1}v_i \ge d_i v_{i+1}.$$

Define

$$w_i=\frac{v_i}{d_i}.$$

Then the bump condition becomes simply

$$w_i \ge w_{i+1}.$$

Now observe:

since $v_i\sim \text{Exp}(1)$,
scaling gives

$$w_i \sim \text{Exp}(d_i).$$

Thus the $w_i$ are independent exponentials with rates $d_i$.

Recursive structure

Introduce the “target coordinate”

$$t=\frac{L}{40}+1.$$

Then

$$d_i=40(t-i).$$

Ignoring the common factor $40$, we may regard

$$w_i \sim \text{Exp}(t-i).$$

A crucial fact about exponentials:

If independent exponentials have rates $\lambda_i$, then the probability that variable $m$ is the minimum is

$$\frac{\lambda_m}{\sum \lambda_j}.$$

The boat with minimum $w_i$:

can never bump another boat,
therefore remains the lowest boat in the final order.

Suppose that minimum occurs at position $m$.

Then:

boats $l,\dots,m-1$ form an independent subproblem whose new target becomes $m$,
boats $m+1,\dots,r$ form another independent subproblem with the original target unchanged.

Moving boat $m$ to the front changes permutation parity by

$$(-1)^{m-l}.$$

So if $E(l,r,t)$ denotes the expected permutation sign

($+1$ for even, $-1$ for odd),

we get the recursion

$$E(l,r,t) = \sum_{m=l}^r \Pr(m\text{ minimum}) (-1)^{m-l} E(l,m-1,m) E(m+1,r,t).$$

The minimum probability is

$$\Pr(m\text{ minimum}) = \frac{t-m} {\sum_{j=l}^r (t-j)}.$$

Finally,

$$p(n,L)=\frac{1+E(1,n,L/40+1)}{2}.$$

2. Python implementation

from fractions import Fraction
from functools import lru_cache

def probability_even(n, L, spacing=40):
    # target coordinate
    t0 = Fraction(L, spacing) + 1

    @lru_cache(None)
    def expected_sign(l, r, t):
        """
        Expected permutation sign (+1 even, -1 odd)
        for boats l..r with target coordinate t.
        """

        # empty or single boat => identity permutation
        if l >= r:
            return Fraction(1, 1)

        count = r - l + 1

        # S = sum_{j=l}^r (t - j)
        S = Fraction(count, 1) * t - (l + r) * count // 2

        total = Fraction(0, 1)

        for m in range(l, r + 1):

            # probability that m is the minimum
            pm = (t - m) / S

            # parity change caused by moving m to front
            sign_flip = -1 if ((m - l) & 1) else 1

            # left and right independent subproblems
            left = expected_sign(l, m - 1, Fraction(m, 1))
            right = expected_sign(m + 1, r, t)

            total += pm * sign_flip * left * right

        return total

    e = expected_sign(1, n, t0)

    # convert expected sign to probability of even permutation
    return (Fraction(1, 1) + e) / 2

def rounded_decimal(frac, digits=10):
    scale = 10 ** digits
    x = frac * scale

    q = x.numerator // x.denominator
    r = x.numerator % x.denominator

    # round half up
    if 2 * r >= x.denominator:
        q += 1

    integer = q // scale
    decimal = q % scale

    return f"{integer}.{decimal:0{digits}d}"

# verification
print(probability_even(3, 160))          # 56/135
print(rounded_decimal(probability_even(4, 400), 10))
print(rounded_decimal(probability_even(13, 1800), 10))

3. Code walkthrough

`expected_sign(l, r, t)`

This recursively computes the expected sign of the permutation produced by boats $l$ through $r$.

Base case

if l >= r:
    return Fraction(1, 1)

A single boat (or empty interval) contributes an even permutation.

Total exponential rate

S = sum(t - j)

This is the total rate of all exponentials in the interval.

Choosing the minimum

pm = (t - m) / S

Independent exponentials choose the minimum proportionally to their rates.

Parity contribution

sign_flip = (-1)^(m-l)

Moving the minimum boat to the front requires $m-l$ swaps.

Recursive decomposition

left = expected_sign(...)
right = expected_sign(...)

The left and right parts become independent subproblems.

4. Verification

The program reproduces the values given in the problem:

$$p(3,160)=\frac{56}{135}$$

and

$$p(4,400)=0.5107843137.$$

For the target value:

$$p(13,1800) = 0.5001817828233158\ldots$$

which rounds to:

$$0.5001817828.$$

This is very plausible: with many boats, parity becomes extremely close to equally likely.

Answer: 0.5001817828

Project Euler Problem 597