经典概率题，著名的反直觉问题——百囚徒挑战

很多时候，我们都会靠直觉去评价一件事情，但很多时候，我们的直觉是错的，哪怕感觉有多么准确，而最著名的反直觉问题，就是百囚徒挑战。

案例和问题

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

1、所有囚徒被一一编号，编号为1-100。

2、将编号1-100的100个号码牌，随机放在100个抽屉。

3、每个囚徒可以打开最多50个抽屉，如果找到对应自己编号的号码牌，则该囚徒挑战成功，反之挑战失败。

4、所有囚徒全部挑战成功，该项挑战才算成功，任意一名囚徒挑战失败，则该项挑战失败！

囚徒们有一个月的时间去讨论策略，那么，这100个囚徒有多大的概率能够得到释放？

直觉

前三点看起来并不难，但第四条直接将难度直线升级。从直觉来看，每个囚徒完成挑战的概率就是1/2，而且每个囚徒的挑战都是独立事件，所以100个囚徒同时成功的概率就是（1/2）的100次方，这个数，几乎接近于零！

做个简单的对比，好比100个人一起掷硬币，要求100人全部都是正面……难度之大，可想而知。

一线生机

但实际上，百囚徒挑战这并不是一个单纯的概率事件，只要协商好策略，可以大幅度提高概率，在看似不可能的环境下，寻得一线生机。

举个例子，假设只有2个囚徒，按照直觉，他们一起完成挑战的概率就是1/4，但实际上，如果他们选择不同的抽屉，那么一起完成挑战的概率就是1/2，而如果他们选择相同的抽屉，那么一起完成挑战的概率就是0。

这就是一个月谋划时间的意义！

策略

有一个策略就是顶针，每个囚徒进去，首先打开与自己编号相同的抽屉，从中取出号码牌，然后打开号码牌所对应的抽屉。之后，重复此过程，直到找到自己的号码牌，或者50个抽屉的机会用完。

比如，3号囚徒进去，打开3号抽屉，得到24号号码牌，再打开24号抽屉，得到15号号码牌，再打开15号抽屉……直到找到自己的号码牌（3号），或者打开了50个抽屉。

那么这个策略下，所有囚徒一起完成挑战的可能性是多大呢？

问题解析

首先，我们用映射来表示这个策略，上面那个例子，就是f(3)=24,f(24)=15,从任意一个数出发，通过不停地叠加，最终一定会回到这个数，形成一个环。

通过这个办法，1-100的数字就被分割成了若干个环，而这些环的总长度加起来刚好就是100。

比如上面2个环，长度分别为4和5。

当且仅当所有环的长度都不超过50，所有囚徒的挑战才算成功。只要有任意一个环的长度大于50，那么所有囚徒的挑战就是失败，因为所有环的长度加起来不超过100，所以，最多肯定也只可能有一个环的长度大于50，但这个环的长度可能是51，52……100，而且这些出现的可能性是相互独立的。

所以，相对于计算“所有环的长度都不超过50”的概率，计算“有一个环的长度超过50”的概率会更好算一些。

概率求解

假设最长环的长度为m，这样的排列种类有

而总排列种类为100！

所以，最长环的长度为m的概率为1/m

有一个环的长度超过50的概率就是1/51+1/52+1/53+……1/100

所以通过挑战的概率就是1-（1/51+1/52+1/53+……1/100）≈30%。

结论

直觉告诉我们，那是一个趋近于零的概率，但通过这个策略，变成了30%的概率，这就是百囚徒挑战的大概情况，有时候不要靠直觉，静下来抓住可能的漏洞，就有机会实现逆转。