Project Euler 826
Project Euler 826
题目
Birds on a Wire
Consider a wire of length \(1\) unit between two posts. Every morning \(n\) birds land on it randomly with every point on the wire equally likely to host a bird. The interval from each bird to its closest neighbour is then painted.
Define \(F(n)\) to be the expected length of the wire that is painted. You are given \(F(3) = 0.5\).
Find the average of \(F(n)\) where \(n\) ranges through all odd prime less than a million. Give your answer rounded to \(10\) places after the decimal point.
解决方案
设落点排序后为\(0 < X_1 < X_2 < \cdots < X_n < 1 .\)相邻两鸟之间的距离定义为\(g_i = X_{i+1}-X_i (i=1,2,\dots,n-1).\)此外还有两端空隙\(g_0 = X_1-0, g_n = 1-X_n.\)这样整条线被分割为 \(n+1\) 段：\(\displaystyle{g_0,g_1,\dots,g_{n-1},g_n, \sum_{i=0}^{n} g_i = 1.}\)
考虑某个内部相邻距离 \(g_i\)（\(1<i<n-1\)），它夹在 \(X_i\) 与 \(X_{i+1}\) 之间。
- 鸟 \(X_i\) 会选择右邻居 \(X_{i+1}\) 当且仅当 \(g_i < g_{i-1}\)。
- 鸟 \(X_{i+1}\) 会选择左邻居 \(X_i\) 当且仅当 \(g_i < g_{i+1}\)。
因此 \(g_i\) 会被涂色 当且仅当：\(g_i \le g_{i-1} \lor g_i \le g_{i+1}.\)也就是说，\(g_i\) 不被涂色 的唯一情形是它比左右相邻两段都长：\(g_i > g_{i-1}\land g_i > g_{i+1}.\)
而边界的 \(g_1, g_{n-1}\) 永远会被涂色：\(X_1\) 只有 \(X_2\) 可选，\(X_n\) 只有 \(X_{n-1}\) 可选。
于是
\[ F(n)=\mathbb{E}(g_1)+\mathbb{E}(g_{n-1})+\sum_{i=2}^{n-2}\mathbb{E}(g_i\cdot\mathbf{1}\{g_i\le g_{i-1}\lor g_i\le g_{i+1}\}). \]
由对称性可得：
\[ F(n)=2\cdot \mathbb{E}(g_1) + (n-3)\cdot E_{\text{mid}}, \]
其中\(E_{\text{mid}}=\mathbb{E}(g_i\cdot\mathbf{1}\{g_i\le g_{i-1}\lor g_i\le g_{i+1}\}), (1<i<n-1).\)
将 \([0,1]\) 上的 \(n\) 个独立均匀点排序后，\(n+1\) 段长度\((g_0,g_1,\dots,g_n)\)
在单纯形 \(\sum g_i=1, g_i\ge 0\) 上服从 Dirichlet 分布：\(\text{Dirichlet}(1,1,\dots,1)\)，即在该单纯形上均匀。
因此每一段的期望长度相同：\(\mathbb{E}(g_k)=\dfrac{1}{n+1}.\)所以边界两段贡献：\(2\cdot\mathbb{E}(g_1)=\dfrac{2}{n+1}.\)
接下来只需求 \(E_{\text{mid}}\)。固定某个 \(1<i<n-1\)，令\(x=g_{i-1}, y=g_i, z=g_{i+1}, s=x+y+z.\)
把其余 \(n-2\) 段合并为总长度 \(w=1-s\)。由于 Dirichlet 分布的边缘仍是 Dirichlet 分布：\((x,y,z,w)\sim\text{Dirichlet}(1,1,1,n-2).\)
故 \((x,y,z)\) 的非归一化密度正比于\((1-x-y-z)^{,n-3} = (1-s)^{n-3}, x,y,z\ge 0,s\le 1.\)于是
\[ E_{\text{mid}} = \frac{\int_{x,y,z\ge 0,s\le 1} y\cdot \mathbf{1}\{(y\le x\lor y\le z)\}(1-s)^{n-3}dxdydz} {\int_{x,y,z\ge 0,s\le 1} (1-s)^{n-3}dxdydz}. \]
对分母，记\(\displaystyle{D=\int_{x,y,z\ge 0,s\le 1} (1-s)^{n-3}dxdydz.}\)那么有
\[\begin{aligned} D &= \int_{x,y,z\ge 0,s\le 1} (1-s)^{n-3}dxdydz\\ &=\int_0^1 (1-s)^{n-3}\cdot\frac{s^2}{2}ds\\ &=\frac12B(3,n-2)\\ &=\frac{(n-3)!}{n!}. \end{aligned}\]
对于第二行，这时因为对固定 \(s\)，满足 \(x+y+z\le s\) 的体积为 \(s^3/6\)，因此层密度为 \(\frac{d}{ds}(s^3/6)=s^2/2\)。于是
指示条件 \(y\le x\lor y\le z\) 的补集就是 局部极大：\(y>x \land y>z.\)因此\(E_{\text{mid}}=\mathbb{E}(y)-\mathbb{E}(y\cdot\mathbf{1}\{y>x,y>z\}).\)
在 \(\text{Dirichlet}(1,1,1,n-2)\) 下，\(\mathbb{E}(y)=\dfrac{1}{n+1}\)。所以关键是求\(\displaystyle{M=\mathbb{E}(y\cdot\mathbf{1}\{y>x,y>z\})= \frac{1}{D}\int y\mathbf{1}\{y>x,y>z\}(1-s)^{n-3}dxdydz.}\)
对固定 \(s=x+y+z\)，令 \((u,v,w)=(x/s,y/s,z/s)\)，则 \(u+v+w=1\)，且缩放带来\(\displaystyle{\int_{x+y+z=s} y\mathbf{1}_{y>x,y>z}dxdy= s^3 \cdot C,}\)其中\(\displaystyle{C=\int_{\substack{u,v\ge 0,u+v\le 1\\v\ge u,v\ge 1-u-v}} vdudv.}\)
条件 \(v\ge 1-u-v\) 等价于 \(2v+u\ge 1\)。于是区域为：\(u\ge 0,v\ge 0,u+v\le 1,v\ge u,v\ge \dfrac{1-u}{2}.\)
对 \(u\) 分段：
- 若 \(0\le u\le 1/3\)，下界为 \(v=(1-u)/2\)，上界为 \(v=1-u\)；
- 若 \(1/3\le u\le 1/2\)，下界为 \(v=u\)，上界为 \(v=1-u\)。
因此\(\displaystyle{C=\int_0^{1/3}\int_{(1-u)/2}^{1-u} vdvdu+\int_{1/3}^{1/2}\int_u^{1-u} vdvdu=\frac{11}{108}.}\)
于是局部极大项的非归一化积分为：\(\displaystyle{\int y\mathbf{1}\{y>x,y>z\}(1-s)^{n-3}dxdydz= \int_0^1 (1-s)^{n-3}\cdot (s^3 C)ds.}\)
代入 \(C=11/108\)，得\(\displaystyle{\int_0^1 s^3(1-s)^{n-3}ds = B(4,n-2)=\frac{6(n-3)!}{(n+1)!},}\)
所以局部极大非归一化的结果为\(\dfrac{11}{108}\cdot\dfrac{6(n-3)!}{(n+1)!}=\dfrac{11}{18}\cdot\dfrac{(n-3)!}{(n+1)!}.\)再除以 \(D=(n-3)!/n!\) 得
\[ M=\frac{11}{18}\cdot\frac{1}{n+1}. \]
因此得到：
\[ E_{\text{mid}}=\frac{1}{n+1}-\frac{11}{18}\cdot\frac{1}{n+1} =\frac{7}{18(n+1)}. \]
最终有：
\[ F(n)=2\cdot\frac{1}{n+1}+(n-3)\cdot\frac{7}{18(n+1)} =\frac{7n+15}{18(n+1)}. \]
代码
1 | from tools import get_prime |