一道看似简单却没头绪的概率题?50条煮熟的面条共100个端点,将这些端点两两随机系在一起,得到面条圈数的期望值是多少?

Question

一道看似简单却没头绪的概率题?
50条煮熟的面条共100个端点,将这些端点两两随机系在一起,得到面条圈数的期望值是多少?

Answer 1

这个问题可以这么来考虑：
假设n条煮熟的面条,进行相应的操作后,得到面条圈数的期望值是f(n),本题就是要求f(50).
我们来计算f(n),取出其中1条面条,选中1个端点,这个端点有2n-1种连法,其中1种就是连上自己另一个端点,2n-2种就是连上另外一条线段的某个端点.
对于前者,剩下n-1条没有连接的面条,加上1条自己形成的圈,期望值是f(n-1)+1；
对于后者,那两条面条形成了一条长一点的面条,此时,共有n-2条短面条和1条长面条,期望值是f(n-1)；
因此,我们得到f(n)=(1/(2n-1))(f(n-1)+1)+((2n-2)/(2n-1))f(n-1)=f(n-1)+1/(2n-1)；
而f(1)=1/1,所以f(50)=1/1+1/3+1/5+1/7+...+1/99=Σ(i=1to50)1/(2i-1)≈2.94条.