首页 > 技术相关 > 相邻的树上会有多少鸟?

相邻的树上会有多少鸟?

2013年7月2日 发表评论 阅读评论

bird

有一个很有意思的问题是这样的:说有一片树林是 38 棵树排成一圈,有 11 只鸟住在这片树林里,每天晚上都会回来。试证明一定存在相邻的 7 棵树上至少住着 3 只鸟。

这个问题乍看起来… 跟概率没什么关系。但是如果我们定义一个随机变量,就可以很容易用数学期望来解决它。

为什么会用到数学期望呢?因为数学期望有一个很重要的性质:线性性质。也就是说,若干随机变量和的期望等于其期望的和。这个性质的强大之处在于它不关心随机变量 \(X_i\) 是不是相互独立。即设 \(X_1, X_2, \ldots, X_n \) 为随机变量,\(X = c_1X_1 +c_2 X_2 +\cdots + c_nX_n\),我们有

\[
\mathbb{E}[X] = c_1 \mathbb{E}[X_1] + c_2 \mathbb{E}[X_2] + \cdots + c_n \mathbb{E}[X_n] \]

我们还会用到一个事实,就是在概率空间中,必定存在一个点使得 \(X \geq \mathbb{E}[X] \),也必定存在一个点使得 \(X \leq \mathbb{E}[X] \)。这个性质就是数学期望的抽屉原理

工具准备好了,我们先给这些鸟编上号 1 ~ 11,然后随便选取某相邻的 7 棵树。定义一个变量 \(X_i\), \(i = 1,2,\ldots, 11\),如果第 \(i\) 只鸟住在选中的这 7 棵树上就取 1,反之取 0。那么这 7 棵树上鸟的总数就是

\[
X= \sum_{i=1} ^ {11} X_i
\]

因为每只鸟住在每棵树上的概率都是 \(\frac{1}{38}\),所以
\[
\mathbb{P}(X_i = 1) = \frac {7}{38}, \quad i = 1,2,\ldots,11
\]

于是就有
\[
\mathbb{E}X = \sum_{i=1} ^{11} \mathbb{E}X_i = \frac{7 \times 11}{38} = \frac{77}{38} > 2
\]

这就说明肯定存在相邻的 7 棵树上至少住着 3 只鸟~

[1] Jukna, Stasys. Extremal combinatorics: with applications in computer science. 2nd ed. Springer, 2011.

[2] 苏淳. 概率论. 科学出版社, 2004.

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

%d 博主赞过: