囚徒与红豆

还记得上一个故事里的5名大盗吗？就在他们正要瓜分那条价值连城的珍珠项链的时候，国王的士兵趁他们不备，包围了他们。负隅顽抗只有死路一条，举手投降说不定还有活下来的机会，于是，这5名绝顶聪明、理智过人却也极度自私、互相猜忌的大盗，就这么变成了5名阶下囚。

国王对这5名为非作歹的大盗早有耳闻，他决定用一种特别的方式来让他们自己决定对自己的惩罚。国王让典狱官拿来一口布袋，并在布袋里放进100颗红豆。5名囚徒通过抽签决定从1号到5号的顺序，并按顺序在口袋中抓出一定数量的红豆。当5个人都抓过红豆之后，典狱官会来确认他们手中的红豆数量，并将抓得最多的人和抓得最少的人处死，剩下的人则将被判处苦役。

他们不必将所有红豆全部抓完，但他们每个人至少要抓1颗红豆；这就意味着，前面的人在抓红豆时，至少要留下数量与尚未抓取红豆的人数相同的红豆。如果抓得最多或抓得最少的不止一人，比如有两名囚犯都只抓了1颗红豆，其他人抓取的红豆则不止1颗，那么按照规则，这两名囚犯都会作为抓得最少的人被处死。5名囚徒抓取红豆的过程都是在典狱官的监督下单独进行的，也就是说他们之间无法交流，但每个人都可以摸出布袋中剩余的红豆数量。

别忘了，这5个人极度自私且互相猜忌，所以他们行动的最大前提是保住自己的小命，而且会尽可能地使事态对其他人不利，同时他们也不可能互相合作；并且他们都是同样理智、同样聪明的人，所以5个人中无论是谁想出的办法，其他人也一样想得到。

请问，在这5名囚徒之中，谁的存活概率最低？如果国王允许这五个人在抓取红豆之前先进行交流，情况将会发生什么样的变化呢？

 

答案：

首先，让我们确认这一点：这5个人的行动原则都是先求保命，再尽可能地置其他囚犯于死地，也即每个人都会考虑排在自己后面的人可能采取的最佳方案，并选择剩下的人采取最佳方案时使自己存活概率最大的方案；如果存在多种方案使自己的存活概率最大化，那么他们会选择可以杀死最多人的方案。

其次，由于抓得最多和抓得最少的人都将被处死，所以对于后手来说，安全的做法是“平均值法”，即先摸出已有多少颗红豆被取走，然后用已被取走的红豆数除以排在自己前面的人数，得到一个平均值。当平均值为整数时，抓取颗数等于平均值的红豆；当平均值不为整数时，则先四舍五入取整，再抓取相应颗数的红豆。

接下来，让我们使用完全归纳法来推理一下可能出现的情况：

由于规定每人至少要抓1颗红豆，所以不妨先分给五名囚徒每人1颗红豆，然后再让他们在剩下的95颗红豆中抓取X颗红豆，即0≤X≤95，且X为整数。假设1号囚徒所抓取的红豆数量为整数Y,2号囚徒所抓取的红豆数量为整数Z。

（1）当Y=95时，1号囚徒为抓得最多的人，剩下的四名囚徒都是抓得最少的人。结果为无人生存。

（2）当48≤Y≤94时，2号囚徒必然会抓走剩下的所有红豆，使1号抓得最多，3号、4号、5号抓得最少。结果为2号独活。

（3）当33≤Y≤47时，2号囚徒出于自保必然会抓取Y-1颗红豆。3号摸出了剩下的红豆数量，并推理出了自己不可能成为抓得最多的人这一点，于是他选择抓走剩下的所有红豆，使1号抓得最多，4号、5号抓得最少。结果为2号、3号存活。

（4）当20≤Y≤32时，2号、3号、4号囚徒出于自保都会选择抓取Y-1颗。因为对于2号和3号来说，要杀死三人（1号、4号、5号）需要抓走剩下的所有红豆，但如果这么做的话便无法保证自己存活（自己有可能成为抓得最多的人），所以在自保（只比1号少抓1颗）的同时杀死两人已经是最优策略了。身为后手的4号采取了前面提到的“平均值法”，同样拿走了Y-1颗。如此一来，5号别无选择，只能成为抓得最少的人；1号则成为抓得最多的人。结果是2号、3号、4号存活。

（5）当1≤Y≤18时，必有Y-1≤Z≤Y+1，因为如若不然，3号、4号、5号就会根据“平均值法”行动，抓取数量等于Y和Z的平均值的红豆，使得1号和2号分别成为抓得最多和抓的最少的人，而剩下的三人存活。然而，当Y-1≤Z≤Y+1时，根据“平均值法”,3号、4号、5号所抓取的红豆数量也不会大于Y，结果为无人生存。

（6）当Y=0时，结果是1号囚徒成为抓得最少的人，必然无法存活。

（7）当Y=19时，就相当于将问题的主角换成了2号囚徒。对于2号来说，当Z≥20时，情况同（3）、（4）；当Z≤20时，情况同（5）。但在（3）、（4）、（5）三种情况中，2号都无法存活，所以对于2号来说，最佳策略是使Z=19。接下来问题的主角换成了3号囚徒……出于同样的原因，最终五个人全部各自抓取了19颗红豆，结果是五名囚徒同时成为抓得最多也是抓得最少的人，即无人生存。

综上所述，无论选择抓取多少颗红豆，1号囚徒都必然死亡；即对1号囚徒来说，不存在能使自己存活的最佳策略。在这种情况下，1号囚徒会退而求其次，并选择尽可能地置其他囚犯于死地的策略，即使Y=95或Y=19，使得无人生存。也就是说，五名囚徒的存活概率都是相同的——他们的存活概率都是0。

如果国王允许这五个人在抓取红豆之前先进行交流，情况会不会有所改善呢？让我们设想一下：五名同样绝顶聪明又同样自私的囚徒经过一番推理，都得出了自己必死无疑的事实……

这时，1号囚徒开口说道：“根据国王规定的规则，我们5个人中至少有两个是必死无疑的。相信你们也推理出来了，在这种情况下后手的决策取决于先手，而最先抓取红豆的我掌握着你们的生杀大权，我无法保证你们存活，但却一定可以置你们于死地。不如这样吧，你们4个人商量一个方案出来，谁死谁活都无所谓，只要保证我百分之百存活，我就会配合你们行动；如果做不到这一点，你们就给我陪葬吧。”

2号囚徒也对着排在自己后面的3个人说：“我同意1号的办法。你们3个商量一个方案出来吧，谁死谁活都无所谓，只要能保证1号和我百分之百存活，我就会和1号一起配合你们行动；如果做不到的话，我就让你们3个给我陪葬。”

3号囚徒听了，便对4号和5号说：“我同意1号和2号的办法，你们两个商量一个方案出来吧，谁死谁活都无所谓，只要能保证1号、2号和我百分之百存活……”

4号和5号异口同声地打断了3号的话：“你的意思就是叫我们两个去死喽？凭什么啊，大不了大家同归于尽呗！”

可以想见，即便5名囚徒可以先交流再行动，他们的存活概率也依然为0——因为他们5个人的行动准则都是利己第一、损人第二。