Project Euler Problem 398

Solution

Answer: 2010.59096

Let the segment lengths be

$$X_1,\dots,X_m \in \mathbb Z_{>0}, \qquad X_1+\cdots+X_m=n.$$

Choosing $m-1$ cut points uniformly among the $n-1$ interior lattice points is equivalent to choosing a composition of $n$ into $m$ positive parts uniformly at random.

The total number of such compositions is

$$\binom{n-1}{m-1}.$$

Let $Y$ be the second-smallest segment length.

We use the standard tail-sum identity for positive integer random variables:

$$\mathbb E[Y] = \sum_{k\ge1}\Pr(Y\ge k).$$

So the whole problem reduces to counting compositions for which the second-smallest part is at least $k$.

---

1. Counting $\Pr(Y\ge k)$

The condition $Y\ge k$ means:

• either all segments are at least $k$,
• or exactly one segment is $<k$, while all others are at least $k$.

---

Case A: all segments $\ge k$

Write

$$X_i = k + Z_i, \qquad Z_i\ge0.$$

Then

$$Z_1+\cdots+Z_m = n-mk.$$

Number of solutions:

$$A_k = \binom{n-mk+m-1}{m-1}.$$

---

Case B: exactly one segment $<k$

Choose which segment is small: $m$ choices.

Suppose that small segment has value $t\in{1,\dots,k-1}$.

For the remaining $m-1$ segments write

$$X_i = k + Z_i,\qquad Z_i\ge0.$$

Then

$$\sum Z_i = n-t-(m-1)k.$$

Hence the number of possibilities is

$$\binom{n-t-(m-1)k+m-2}{m-2}.$$

Summing over $t=1,\dots,k-1$ and using the hockey-stick identity gives

$$B_k = \binom{n-(m-1)(k-1)-1}{m-1} - \binom{n-m(k-1)-1}{m-1}.$$

Thus the number of favorable compositions is

$$N_k = A_k + mB_k.$$

After simplification:

$$N_k = m\binom{n-(m-1)(k-1)-1}{m-1} - (m-1)\binom{n-m(k-1)-1}{m-1}.$$

Therefore

$$\Pr(Y\ge k) = \frac{ m\binom{n-(m-1)(k-1)-1}{m-1} - (m-1)\binom{n-m(k-1)-1}{m-1} }{ \binom{n-1}{m-1} }.$$

Finally,

$$E(n,m) = \sum_{k\ge1}\Pr(Y\ge k).$$

---

2. Python implementation

from math import comb

def E(n, m):
    total = comb(n - 1, m - 1)

    ans = 0.0
    k = 1

    while True:
        a_top = n - m * (k - 1) - 1
        b_top = n - (m - 1) * (k - 1) - 1

        if a_top < m - 1 and b_top < m - 1:
            break

        A = comb(a_top, m - 1) if a_top >= m - 1 else 0
        B = comb(b_top, m - 1) if b_top >= m - 1 else 0

        favorable = m * B - (m - 1) * A

        ans += favorable / total
        k += 1

    return ans

# sanity checks
print(E(3, 2))   # 2.0
print(E(8, 3))   # 16/7 = 2.285714285714...

# target
value = E(10**7, 100)
print(f"{value:.5f}")

---

3. Code walkthrough

• total is the total number of compositions:

$$\binom{n-1}{m-1}.$$

• For each $k$, we compute:

• A = number of compositions where all parts are at least $k$,

• B = auxiliary hockey-stick term,

• favorable = m*B - (m-1)*A.

• Dividing by total gives $\Pr(Y\ge k)$.

• Summing over all $k$ yields the expectation.

The checks:

$$E(3,2)=2$$

and

$$E(8,3)=\frac{16}{7}$$

match the statement exactly.

---

4. Final verification

For $n=10^7$ and $m=100$:

• average segment length is $10^5$,
• the minimum and second minimum should be much smaller,
• a value around $2000$ is entirely reasonable for the second-smallest order statistic.

The computation gives

$$E(10^7,100)=2010.590959579\ldots$$

Rounded to 5 decimal places:

Answer: 2010.59096