Project Euler 469
Project Euler 469
题目
Empty chairs
In a room \(N\) chairs are placed around a round table.
Knights enter the room one by one and choose at random an available empty chair.
To have enough elbow room the knights always leave at least one empty chair between each other.
When there aren’t any suitable chairs left, the fraction \(C\) of empty chairs is determined.
We also define \(E(N)\) as the expected value of \(C\).
We can verify that \(E(4) = 1/2\) and \(E(6) = 5/9\).
Find \(E(10^{18})\). Give your answer rounded to fourteen decimal places in the form \(0.abcdefghijklmn\).
解决方案
令 \(G(N)\) 表示圆桌上最终坐下的骑士数的期望，则\(E(N)=1-\dfrac{G(N)}{N}.\)圆桌过程的第一位骑士必定会坐下，并且其左右相邻两把椅子之后都不可能再被占用。于是圆桌被“切开”为一段长度为 \(N-3\) 的直线座位区间（两侧端点的外侧邻居恒为空，不造成额外约束），而后续过程仅在这段直线上独立进行。
因此存在一个直线版本的期望函数 \(f(n)\)：在一排 \(n\) 把椅子（直线排列）上进行同样的随机入座规则（禁止相邻），最终坐下的骑士数的期望。
那么圆桌的期望占用数满足\(G(N)=1+f(N-3),\)从而\(E(N)=1-\dfrac{1+f(N-3)}{N}.\)因此只需研究直线问题的 \(f(n)\)。
2. 直线问题的递推
考虑直线的 \(n\) 把椅子编号为 \(1,2,\dots,n\)。第一位骑士等概率随机选择某个位置 \(i\) 坐下。
坐下后，位置 \(i-1,i,i+1\) 都无法再被占用（其中 \(i\) 已占用，\(i\pm1\) 被邻接禁止）。剩余可供继续随机过程的椅子分裂为两段互不影响的子问题：
- 左段长度为 \(i-2\)（椅子 \(1,\dots,i-2\)）
- 右段长度为 \(n-i-1\)（椅子 \(i+2,\dots,n\)）
于是条件期望为\(\displaystyle{f(n)=1+\frac1n\sum_{i=1}^{n}\bigl(f(i-2)+f(n-i-1)\bigr).}\)注意到对称性使两项求和相等，因此\(\displaystyle{f(n)=1+\frac{2}{n}\sum_{i=1}^{n} f(i-2).}\)
将指标平移 \(k=i-2\)（并约定 \(f(m)=0\) 对于 \(m\le 0\)），得到一个更常用的形式：
\[ f(n)=1+\frac{2}{n}\sum_{k=0}^{n-2} f(k),n\ge 1, \]
并且初值为\(f(0)=0, f(1)=1.\)
把上式两边乘以 \(n\)：
\[ n f(n)=n+2\sum_{k=0}^{n-2} f(k). \]
同理，对 \(n-1\) 写一遍：
\[ (n-1)f(n-1)=(n-1)+2\sum_{k=0}^{n-3} f(k). \]
两式相减：\(n f(n)-(n-1)f(n-1)=1+2f(n-2).\)于是得到关键递推：\(n f(n)=(n-1)f(n-1)+2f(n-2)+1,n\ge 2,\)配合\(f(0)=0, f(1)=1.\)这已经是一个“几乎线性常系数”的递推，下一步用生成函数求闭式。
定义普通生成函数\(\displaystyle{F(t)=\sum_{n=0}^{\infty} f(n)t^n.}\)从递推式
\[n f(n)-(n-1)f(n-1)=2f(n-2)+1(n\ge 2)\]
两边乘 \(t^n\) 后对 \(n\ge 2\) 求和。接下来考虑两边进行化简。
对于左边，利用恒等式\(\displaystyle{\sum_{n\ge 0} n f(n)t^n=tF'(t),}\)得到\(\displaystyle{\sum_{n\ge 2} n f(n)t^n=tF'(t)-t,}\)
因为 \(n=1\) 项为 \(1\cdot f(1)t=t\)。另令 \(m=n-1\)，则
\[ \sum_{n\ge 2}(n-1)f(n-1)t^n =\sum_{m\ge 1} m f(m)t^{m+1} =t\sum_{m\ge 1} m f(m)t^m =t\cdot tF'(t) =t^2F'(t). \]
因此左边总和为\((tF'(t)-t)-t^2F'(t)=t(1-t)F'(t)-t.\)
对于右边，可见
\(\displaystyle{\sum_{n\ge 2}2f(n-2)t^n=2t^2\sum_{n\ge 2} f(n-2)t^{n-2}=2t^2F(t).}\)以及\(\displaystyle{\sum_{n\ge 2} t^n=\frac{t^2}{1-t}.}\)因此右边两块的结果为\(2t^2F(t)+\dfrac{t^2}{1-t}\)。
于是得到\(t(1-t)F'(t)-t=2t^2F(t)+\dfrac{t^2}{1-t}.\)两边除以 \(t\) 并移项，那么有：\((1-t)F'(t)-2tF(t)=\dfrac{1}{1-t}.\)再除以 \((1-t)\)，得到：
\[ F'(t)-\frac{2t}{1-t}F(t)=\frac{1}{(1-t)^2}. \]
这是标准一阶线性微分方程。其积分因子为
\[ \mu(t)=\exp\left(\int -\frac{2t}{1-t}dt\right) =\exp\left(2t+2\ln(1-t)\right) =e^{2t}(1-t)^2. \]
因此\((\mu(t)F(t))'=\mu(t)\cdot \dfrac{1}{(1-t)^2}=e^{2t}.\)积分得到\(\mu(t)F(t)=\dfrac12 e^{2t}+C,\)从而\(F(t)=\dfrac{1}{2(1-t)^2}+\dfrac{C e^{-2t}}{(1-t)^2}.\)由初值 \(F(0)=f(0)=0\) 得\(0=\dfrac12 +C \Longrightarrow C=-\dfrac12,\)最终有
\[ F(t)=\frac{1}{2}\cdot \frac{1-e^{-2t}}{(1-t)^2}. \]
现在我们展开\(\displaystyle{\dfrac{1}{(1-t)^2}=\sum_{i=0}^{\infty}(i+1)t^i,}\)以及\(\displaystyle{1-e^{-2t}=1-\sum_{j=0}^{\infty}\frac{(-2t)^j}{j!}=-\sum_{j=1}^{\infty}\frac{(-2)^j}{j!}t^j.}\)于是
\[ F(t) =\frac12\left(\sum_{i\ge 0}(i+1)t^i\right)\left(-\sum_{j\ge 1}\frac{(-2)^j}{j!}t^j\right). \]
取 \(t^n\) 系数，令 \(j=k\ge 1\)，则 \(i=n-k\ge 0\)，得到
\[ f(n)=\sum_{k=1}^{n}\frac{(-2)^{k-1}}{k!}(n-k+1). \]
这给出了直线问题的完全显式解。
由之前的关系\(E(N)=1-\dfrac{1+f(N-3)}{N}.\)
当 \(N\) 很大时，使用显式公式可把 \(f(n)\) 拆成两部分：
\[ f(n)=(n+1)\sum_{k=1}^{n}\frac{(-2)^{k-1}}{k!} -\sum_{k=1}^{n}\frac{(-2)^{k-1}}{(k-1)!}. \]
当 \(n\to\infty\) 时，级数收敛到
\[ \sum_{k=1}^{\infty}\frac{(-2)^{k-1}}{k!} = -\frac12\sum_{k=1}^{\infty}\frac{(-2)^k}{k!} =-\frac12\left(e^{-2}-1\right) =\frac{1-e^{-2}}{2}, \]
以及
\[ \sum_{k=1}^{\infty}\frac{(-2)^{k-1}}{(k-1)!} =\sum_{j=0}^{\infty}\frac{(-2)^j}{j!}=e^{-2}. \]
因此
\[ f(n)=\frac{n+1}{2}(1-e^{-2})-e^{-2}+o(1), \]
从而直线的占用比例满足\(\displaystyle{\frac{f(n)}{n}\to \frac{1-e^{-2}}{2}.}\)圆桌占用数为 \(1+f(N-3)\)，于是圆桌的空椅比例期望为\(E(N)=1-\dfrac{1+f(N-3)}{N}\to 1-\dfrac{1-e^{-2}}{2}=\dfrac{1+e^{-2}}{2}.\)
由于题目要求 \(N=10^{18}\) 极大，对 \(14\) 位小数完全可以忽略。因此
\[ E(N)\approx E(\infty)=\frac{1+e^{-2}}{2} \]
代码
1 | from math import exp |