Project Euler 398

题目

Cutting rope

Inside a rope of length \(n\), \(n-1\) points are placed with distance \(1\) from each other and from the endpoints. Among these points, we choose \(m-1\) points at random and cut the rope at these points to create \(m\) segments.

Let \(E(n, m)\) be the expected length of the second-shortest segment.

For example, \(E(3, 2) = 2\) and \(E(8, 3) = 16/7\).

Note that if multiple segments have the same shortest length the length of the second-shortest segment is defined as the same as the shortest length.

Find \(E(10^7, 100)\).

Give your answer rounded to \(5\) decimal places behind the decimal point.

解决方案

选择 \(m-1\) 个切点等价于把整数 \(n\) 表示为 \(m\) 个正整数的有序和：\(x_1+x_2+\cdots+x_m=n, x_i\ge 1.\)每一种切法与每一个 \((x_1,\dots,x_m)\) 一一对应，且等概率出现。总方案数为经典插板法：\(T(n,m)=\dbinom{n-1}{m-1}.\)

令排序后的段长为\(V_{(1)}\le V_{(2)}\le \cdots \le V_{(m)}.\)题目中的若最短有并列，则第二短等于最短正是统计学意义下的第二顺序统计量 \(V_{(2)}\)。

对整数 \(s\ge 1\)，考虑事件 \(V_{(2)}\ge s\)。它的含义是：至多只有 \(1\) 段长度小于 \(s\)；换言之，至少有 \(m-1\) 段长度 \(\ge s\)。

设\(B(s)=\#{(x_1,\dots,x_m):x_1+\cdots+x_m=n,x_i\ge 1,V_{(2)}\ge s}.\)则\(\mathbb{P}(V_{(2)}\ge s)=\dfrac{B(s)}{T(n,m)}.\)接下来对 \(B(s)\) 分类计数。

第一种情况是所有 \(m\) 段都满足 \(\ge s\)。令\(x_i=y_i+(s-1), y_i\ge 1,\)则\(y_1+\cdots+y_m=n-m(s-1).\)方案数为\(B_0(s)=\dbinom{n-m(s-1)-1}{m-1}=\dbinom{n-1-(s-1)m}{m-1}.\)

第二种情况则是恰有 1 段小于 \(s\)。先选出这一段的位置，有 \(m\) 种。

设该段长度为 \(r\)，其中\(1\le r\le s-1.\)其余 \(m-1\) 段都满足 \(\ge s\)，同样令它们减去 \((s-1)\)，得到 \(m-1\) 个正整数之和：\(y_1+\cdots+y_{m-1}=n-r-(m-1)(s-1), y_i\ge 1,\) 方案数为\(\dbinom{n-1-(s-1)(m-1)-r}{m-2}.\)因此该情况总数为

\[ B_1(s) =m\sum_{r=1}^{s-1}\binom{n-1-(s-1)(m-1)-r}{m-2}. \]

对上式使用Hockey Stick Identity：\(\displaystyle{\sum_{t=L}^{U}\binom{t}{k}=\binom{U+1}{k+1}-\binom{L}{k+1},}\)可化简为\(\displaystyle{\sum_{r=1}^{s-1}\binom{A-r}{m-2}=\binom{A}{m-1}-\binom{A-(s-1)}{m-1},}\) 其中 \(A=n-1-(s-1)(m-1)\)。于是

\[ B_1(s) =m\left[ \binom{n-1-(s-1)(m-1)}{m-1} -\binom{n-1-(s-1)m}{m-1} \right]. \]

于是合并得到 \(B(s)\)：

\[ \begin{aligned} B(s) &=B_0(s)+B_1(s)\\ &=\binom{n-1-(s-1)m}{m-1}+m\left[\binom{n-1-(s-1)(m-1)}{m-1}-\binom{n-1-(s-1)m}{m-1}\right]\\ &=m\binom{n-1-(s-1)(m-1)}{m-1}-(m-1)\binom{n-1-(s-1)m}{m-1}. \end{aligned} \]

令\(N(s)=\#\{V_{(2)}=s\}.\)显然\(N(s)=B(s)-B(s+1).\)代入上式并展开可得一个非常整洁的四项形式：

\[ N(s)= m\binom{n-1-(s-1)(m-1)}{m-1} -m\binom{n-1-s(m-1)}{m-1} -(m-1)\binom{n-1-(s-1)m}{m-1} +(m-1)\binom{n-1-sm}{m-1}. \]

第二短段长的最大可能值为\(s_{\max}=\left\lfloor\dfrac{n-1}{m-1}\right\rfloor,\)因为至少有 \(m-1\) 段不短于 \(V_{(2)}\)，它们的总长不超过 \(n-1\)（还需留出至少 \(1\) 给最短那段）。

最终，由定义得到： \[ E(n,m)=\sum_{s=1}^{s_{\max}} s\cdot \mathbb{P}(V_{(2)}=s)=\frac{\sum_{s=1}^{s_{\max}} sN(s)}{\binom{n-1}{m-1}}. \]

直接计算 \(\binom{\cdot}{m-1}\) 会产生天文大整数。注意所有项的下标都是同一个 \(m-1\)，因此可用比值计算：令 \(r=m-1\)，\(N=n-1\)，则对任意 \(T\ge r\)，有\(\displaystyle{\frac{\binom{T}{r}}{\binom{N}{r}}=\prod_{i=0}^{r-1}\frac{T-i}{N-i}.}\)

通过次式可间接计算出\(E(n,m)\)。

代码

import numpy as np

N = 10_000_000
M = 100

def E(n: int, m: int) -> float:
    r = m - 1
    N = n - 1
    smax = (n - 1) // (m - 1)

    s = np.arange(1, smax + 1, dtype=np.int64)
    s_ld = s.astype(np.longdouble)

    den = (N - np.arange(r, dtype=np.longdouble))

    def ratio_choose(T):
        T = T.astype(np.longdouble)
        out = np.ones_like(T, dtype=np.longdouble)
        for i in range(r):
            out *= (T - i) / den[i]
        out = np.where(T >= r, out, np.longdouble(0))
        return out

    T1 = N - (s - 1) * (m - 1)
    T2 = N - s * (m - 1)
    T3 = N - (s - 1) * m
    T4 = N - s * m

    R1 = ratio_choose(T1)
    R2 = ratio_choose(T2)
    R3 = ratio_choose(T3)
    R4 = ratio_choose(T4)

    P = m * (R1 - R2) - (m - 1) * (R3 - R4)
    ans = np.sum(s_ld * P)

    return float(ans)



val = E(N, M)
print(f"{val:.5f}")