最烧脑概率问题，全网最详细解析！如何让不可能变为可能？

今天我们来讨论一道非常经典，同时也非常烧脑的概率问题——百囚徒挑战问题。

监狱决定给关押的100名囚徒一次特赦的机会，条件是这100名囚徒必须通过一项挑战。

1、所有囚徒从1—100编号；

2、将编号为1—100的100个号码牌，随机打乱放在编号为1—100的100个抽屉里，每个抽屉放一个号码牌；

3、每个囚徒可以打开最多50个抽屉，看了抽屉里面的号码后关上抽屉，并且不得拿走抽屉里的号码牌，也不能向其他囚徒透露任何信息或者对抽屉做记号。如果找到自己对应编号的号码牌，则该囚徒挑战成功，反之则挑战失败；

4、100个囚徒依次进行挑战，如果所有囚徒全部挑战成功，则该项挑战才算成功，任意一名囚徒挑战失败，则该项挑战失败。

5、100个囚徒有1天时间集中商量最佳方案。

请问：如何设计方案，使得挑战成功的概率最大，最大概率是多少？

表面看上去，这个挑战，囚徒毫无胜算。

对于每个囚徒而言，总共100个抽屉，只能打开其中50个，那么挑战成功的概率就是：

P=50/100=1/2

而规则要求这100名囚徒全部挑战成功才算成功，那么挑战成功的概率就是：

P=(1/2)^100=1/(2^100)

这个概率几乎就为0。

数学上将概率小于5%的事件称为小概率事件，通常认为，小概率事件在现实中几乎不可能发生。以上概率远远小于5%，显然囚徒们是不可能挑战成功的。

然而实际上，囚徒们只要采用合理的方案，就可以将挑战成功的概率提高到30%以上。

最佳方案如下：

每个囚徒首先打开自己编号的抽屉，接下来打开这个抽屉里面号码牌对应编号的抽屉，以此类推，直至找到自己对应编号的号码牌。

举个例子：

6号囚徒首先打开6号抽屉，假设抽屉里的号码牌是18号；接下来打开18号抽屉，假设抽屉里的号码牌是91号；接下来打开91号抽屉，假设抽屉里的号码牌是6号。

这样，6号囚徒只需要打开3个抽屉，就能够找到自己对应编号的号码牌。

如果将抽屉的编号和抽屉里面的号码牌编号对应成函数的话，就是：

f(6)=18，f(18)=91，f(91)=6

也就是说，这些编号会形成一条闭环的关系链。

6→18→91→6

以上这条闭环关系链的长度就为3，只要这条闭环的长度不超过50，那么囚徒就能挑战成功。

那么这样操作有什么优势呢？

对于同一条闭环关系链上的所有编号，其挑战成功的次数都是闭环的长度。

很显然，6号、18号和91号都只需要打开3个抽屉就能够挑战成功。

现在，我们的问题转化为，这100个编号的所有闭环的长度都不超过50，则囚徒们就一定能够挑战成功。反之，只要有一条闭环的长度超过50，则挑战失败。

接下来，我们来求出成功的概率。

这里采用反面思考，分析其对立事件的概率更为简单。

假设闭环的长度为m，首先需要从100个编号中选出m个，即C(100,m)；

接下来对这m个编号进行环形排列，形成闭环。

我们都知道m个元素的直线排列就是这m个元素的全排，即A(m,m)；

那么环形排列和直线排列的区别是什么呢？

直线排列有一个元素排在首位，而环形排列没有首位，我们可以任选一个元素排在首位，再去考虑剩余m-1个元素的排序。

也就是说，环形排列本质上相当于少一个元素的直线排列，m个元素的环形排列就相当于m-1个元素的直线排列，即A(m-1,m-1)；

最后，除了这m个元素以外，剩余100-m个元素再进行全排，即A(100-m,100-m)。

闭环长度为m的情况数为：

C(100,m)A(m-1,m-1)A(100-m,100-m)

根据公式

A(n,n)=n!

C(n,m)=n!/[m!(n-m)!]

C(100,m)A(m-1,m-1)A(100-m,100-m)

=[100!/m!(100-m)!](m-1)!(100-m)!

=100!/m

100个编号的全排为：

A(100,100)=100!

闭环长度为m的概率为：

P=(100!/m)/100!=1/m

挑战成功的对立事件为挑战失败

也就是出现闭环长度为51或52、53、…、100

注意到编号总数为100，所以出现闭环长度为51，就不可能出现闭环长度为52，其他闭环长度同理。也就是说，以上这些事件为两两互斥事件，任何两个事件都不可能同时发生。

对立事件的概率，就是这些事件的概率相加。

Σ(51≤m≤100)(1/m)

=1/51+1/52+…+1/100

≈0.688

挑战成功的概率为：

P=1-Σ(51≤m≤100)(1/m)

≈1-0.688=0.312=31.2%

至此，我们终于完美的解决了这个问题，挑战成功的最大概率约为0.312=31.2%。

我们再进一步探讨，如果囚徒的数量趋近于无穷大，其他规则不变，挑战成功的概率的极限为多少？

假设囚徒的数量为2N，如果出现闭环长度m＞N，则挑战失败。

根据刚才推出的结论，挑战成功的概率为：

P=1-Σ(N+1≤m≤2N)(1/m)

=1-[1/(N+1)+1/(N+2)+…+1/(2N)]

当N→∞时，概率P的极限为

lim(P)=lim[1-Σ(N+1≤m≤2N)(1/m)]

那么，这个极限值应该怎么求呢？

注意到

Σ(N+1≤m≤2N)(1/m)=

Σ(1≤m≤2N)(1/m)-Σ(1≤m≤N)(1/m)

我在前面的文章中讲到过著名的欧拉常数γ，有兴趣的朋友可以前往我的主页翻看学习。

n→∞

γ=lim[Σ(1≤k≤n)(1/k)-ln(n)]

=lim[(1/1+1/2+…+1/n)-ln(n)]

lim[Σ(1≤k≤n)(1/k)]=ln(n)+γ

N→∞

lim[Σ(N+1≤m≤2N)(1/m)]

=lim[Σ(1≤m≤2N)(1/m)-Σ(1≤m≤N)(1/m)]

=lim[Σ(1≤m≤2N)(1/m)]-lim[Σ(1≤m≤N)(1/m)]

=[ln(2N)+γ]-[ln(N)+γ]

=ln(2N)-ln(N)=ln(2N/N)

=ln(2)

N→∞

lim(P)=lim[1-Σ(N+1≤m≤2N)(1/m)]

=1-lim[Σ(N+1≤m≤2N)(1/m)]

=1-ln(2)

≈1-0.693=0.307=30.7%

当囚徒人数趋于无穷多时，挑战成功的最大概率约为30.7%。

本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。