首页 > 技术相关 > 随机打结可以系成几个环?

随机打结可以系成几个环?

2012年8月5日 发表评论 阅读评论

假设口袋里有 100 根绳子,随机从里面抽出两个头打个结再放回去,直到没有空闲的绳头为止。最后得到的圈数的期望值是多少?

这个问题乍看起来就和这一口袋绳子一样毫无头绪。随机打结可能会恰好把一根绳子打成结,也可能把两根绳子连在了一起,但是在若干步之后又恰好把这两根绳子的另一头扎起来了……

还是一步一步来分析一下吧。比方说一开始有 \(n\) 根绳子,那就有 \(2n\) 个绳头。如果随便拿出两个绳头来打结,那就有如下几种可能:

  • 恰好抽到了一根绳子的两个头,打结之后这根绳子就再也不用考虑了。这时我们还剩下 \(n-1\) 根绳子,和 \(2(n-1)\) 个绳头。这时就多了一个圈。
  • 抽到的两个头不是一根绳子的,打结之后,两根绳子就变成了一根,绳头也少了两个。于是我们还是剩下 \(n-1\) 根绳子,和 \(2(n-1)\) 个绳头。这时没有多出圈来。

从 \(2n\) 个绳头里面挑出两个头,共有 \(\binom{2n}{2}\) 种挑法,其中 \(n\) 种情况会挑到一根绳子的两个头。于是多出来一个圈的概率就是

\[
\displaystyle \frac{n}{\binom{2n}{2}} = \frac{n}{\frac{2n(2n-1)}{2}}=\frac{1}{2n-1}.)
\]

这时候还剩下 \(n-1\) 根绳子。以此类推,一直到剩下一根绳子,所以最后得到的圈数的期望就是

\[
\displaystyle \frac{1}{2n-1} + \frac{1}{2n-3} + \frac{1}{2n-5} + \cdots + \frac{1}{3} + 1.)
\]

这问题似乎就算解决了……似乎。可这个数算出来是多少呢?

编个程序算一下,这个结果是 3.2843。想想 100 根绳子忙到最后,平均才只能得到 3 个圈,这个机会真是不大。

再来观察一下这个级数,我们知道调和数

\[
\displaystyle H_n= 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} =\sum_{k=1}^n \frac{1}{k}.)
\]

那么
\[
\begin{aligned}
&\displaystyle \frac{1}{2n-1} + \frac{1}{2n-3} + \frac{1}{2n-5} + \cdots + \frac{1}{3} + 1\\
=&\displaystyle \left( \frac{1}{2n} + \frac{1}{2n-1} + \frac{1}{2n-2} + \cdots + \frac{1}{2} + 1 \right) – \left( \frac{1}{2n} + \frac{1}{2n-2} + \frac{1}{2n-4} + \cdots + \frac{1}{2} \right)\\
=&H_{2n} – \frac{1}{2}H_n\end{aligned}
\]

我们可以用 Mathematica 来算这个HarmonicNumber[200]- HarmonicNumber[100]/2,得到了精确解……@_@

\[
\displaystyle \frac{8654590343632330736271597329038616601268156410349231938070835683330531233950965153947472}{2635106162757236442495826303084698495565581115509040892412867358728390766099042109898375}.)
\]

调和数有一个渐进形式:

\[
\displaystyle H_n \sim \ln n+ \gamma + \frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120 n^4}-\frac{1}{252n^6}+\cdots,)
\]

其中 \(\gamma= 0.5772156649\cdots\) 是欧拉常数。于是

\[
H_{2n} – \frac{1}{2}H_n \sim \ln 2 + \frac{1}{2}\ln n + \frac{1}{2} \gamma + O(n^{-2}) \approx \frac{1}{2}\ln n + 0.9818).
\]

所以,圈数的期望的增长正比于绳数的对数。那么这样算下来,10000 根绳子得到的圈数的期望也不不过是 5.587……这个活动是有多么悲催…… -_-|||

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.

%d 博主赞过: