n个人坐n个位置的问题

2020-03-08 本文已影响0人 Azur_wxj

问题

设 $n$ 个人（ $n\geqslant 2$ ）准备依次坐 $n$ 个位置，假定第 $i$ 个人原本的位置是第 $i$ 个位置。现在，第一个人等可能地从 $n$ 个位置中随机挑选一个坐，此后的所有人将：

如果他原本的位置是空的，那么他将做到他原本的位置
如果他原本的位置已经被之前的占据了，则他将在剩下的空位中等可能随机挑选一个

问题是，最后一个人，即第 $n$ 个人，恰好坐在第 $n$ 个位置的概率有多大。

解决

方法一

我们将位置编号，并设第 $i$ 个位置为 $S_i$ 。对于第 $1$ 个人而言，他的选择有三种情况：

坐在 $S_1$
坐在 $S_n$
坐在 $S_2\sim S_{n-1}$

如果是第一种情况，那么此后所有人都将按照原本的位置坐下；
如果是第二种情况，那么无论如何最后一个人都无法坐在原本的位置上。
现在考虑第三种情况，我们假定他坐在了 $S_i$ ，那么对于第 $2,3,\cdots,(i-1)$ 这 $(i-2)$ 个人实际上是没有影响的（因为他们都可以坐在属于自己的位置上）。现在，对于第 $i$ 个人，因为 $S_i$ 已经被第一个人占据，他可以选择的位置只有 $S_1,S_{i+1},S_{i+2},\dotsc,S_n$ 这 $(n+1-i)$ 个位置，此时依然有三种情况：

如果他坐在 $S_1$ ，那么此后所有人都将按照原本的位置坐下
如果他坐在 $S_n$ ，那么无论如何最后一个人都无法坐在原本的位置上
如果他坐在 $S_{i+1}\sim S_{n-1}$

我们会发现此时，对于第 $i$ 个人，他的选择所造成的结果与第一个人是完全相同的。只不过这次问题的规模由 $n$ 变为了 $n+1-i$ 。那么我们实际上可以等价的认为：当第 $i$ 个人发现第1个人占据了他的位置后，他将第1个人赶走了，自己坐在 $S_i$ ，然后让第1个人自己重新挑选。也就是说，我们将第 $i$ 个人看成了新的第1个人。

这种等价思想所直接导致的后果是，可以认为第1个人就总在 $S_1,S_n$ 这两个座位上随机挑选，与其他人无关，因为其他人都一定能坐在自己的位置上。因此，最终的结果是 $0.5$ 。

方法二

设事件 $A_k$ ：当第 $k$ 个人要入座时发现座位 $S_k$ 已经被占据。此时只可能是被第 $1,2,\dotsc,k-1$ 个人所占据。于是该事件的一个划分是 $A_k=\bigcup_{i=1}^{k-1}B_{i,k}$ ，其中 $B_{i,k}$ 表示第 $i$ 个人占据了第 $k$ 个位置。于是令 $P_k=P(A_k)$ ，则有 $P_k=\sum_{i=1}^{k-1}P(B_{i,k})$ 我们现在来考虑 $P(B_{i,k})$ 。注意到 $i<k$ ，因此如果第 $i$ 个人要占据 $S_k$ ，则有：

他入座时发现 $S_i$ 已经被占据，这对应着事件 $A_i$
在 $A_i$ 发生的条件下，他会在剩下的 $n-i+1$ 个座位中等可能随机挑选一个，而他挑选到了 $S_k$ 。

设事件 $C_{i,k}$ 表示第 $i$ 个人在剩下的位置中随机挑选到了 $S_k$ ，显然有 $P(C_{i,k}|A_i)=\frac{1}{n-i+1}$ 故而事件 $B_{i,k}$ 的概率是一个条件概率： $P(B_{i,k})=P(A_iC_{i,k})=P(A_i)P(C_{i,k}|A_i)=P_i\cdot\frac{1}{n-i+1}$ 此外还需单独考虑到 $P(B_{1,k})$ ，因为按照定义， $P_1=0$ （第1个人要入座时都是空座位，因此不可能有人占据 $S_1$ ），按照条件概率公式就会求出 $P(B_{i,k})=0$ ，但是这显然是不合理的，因为第一个人与其他人不同，他是可以任意挑选的，所以应该有 $P(B_{1,k})=\frac{1}{n}$ 于是，对于 $k\geqslant2$ ，有 $P_k=\frac{1}{n}+\sum_{i=2}^{k-1}P_i\cdot\frac{1}{n-i+1}$ 我们接下来证明 $P_k=\frac{1}{n+2-k}\;(k\geqslant2)$ ，采用数学归纳法：

当 $k=2$ 时，显然成立（注意如果求和符号的上标小于下标则认为没有求和）
假设 $k=t$ 时成立，即 $P_t=\frac{1}{n}+\sum_{i=2}^{t-1}P_i\cdot\frac{1}{n-i+1}=\frac{1}{n+2-t}$
则对于 $k=t+1$ ，有 $\begin{split} P_{t+1}&=\frac{1}{n}+\sum_{i=2}^{t}P_i\cdot\frac{1}{n-i+1}\\ &=\left(\frac{1}{n}+\sum_{i=2}^{t-1}P_i\cdot\frac{1}{n-i+1}\right)+P_{t}\cdot\frac{1}{ n+1-t }\\ &=P_t+P_{t}\cdot\frac{1}{ n+1-t }=P_t\cdot\frac{ n+2-t }{ n+1-t }\\ &=\frac{1}{n+2-t}\cdot\frac{ n+2-t }{ n+1-t }\\ &=\frac{1}{n+1-t}=\frac{1}{n+2-(t+1)} \end{split}$ 于是也成立

现在，我们已知第 $n$ 个人入座时，他的原本的座位被人占据的概率是 $P_n=\frac{1}{n}+\sum_{i=2}^{n-1}P_i\cdot\frac{1}{n-i+1}=\frac{1}{n+2-n}=\frac{1}{2}$ 从而他能够坐在原本的位置的概率 $\bar{P_n}$ 是 $\bar{ P_ n }=1-P_n=1-\frac{1}{2}=\frac{1}{2}$

n个人坐n个位置的问题

问题

解决

方法一

方法二

猜你喜欢

热点阅读