囚徒与红豆
还记得上一个故事里的五名大盗吗?就在他们正要瓜分那条价值连城的珍珠项链时,国王的士兵趁机包围了他们。负隅顽抗只有死路一条,举手投降说不定还有活下来的机会。于是,这五名绝顶聪明、理智过人却也极度自私、互相猜忌的大盗就这么变成阶下囚。
国王对这五名为非作歹的大盗早有耳闻,他决定用一种特别的方式来让他们自己决定对自己的惩罚。国王让典狱官拿来一个布袋,并在布袋里放进100颗红豆。五名囚徒通过抽签决定从1号到5号的顺序,并按顺序在布袋中抓出一定数量的红豆。当五个人都抓过红豆之后,典狱官会确认他们手中的红豆数量,并将抓得最多的人和抓得最少的人处死,剩下的人则将被判处苦役。
他们不必将所有红豆全部抓完,但每个人至少要抓1颗红豆。这就意味着前面的人在抓红豆时,至少要留下数量与尚未抓取红豆的人数相同的红豆。如果抓得最多或抓得最少的不止一人,比如,有两名囚犯都只抓出1颗红豆,其他人抓取的红豆则不止1颗,那么按照规则,这两名囚犯都会作为抓得最少的人被处死。五名囚徒抓取红豆的过程都是在典狱官的监督下单独进行的,也就是说他们之间无法交流,但每个人都可以摸出布袋中剩余的红豆数量。
别忘了,这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号囚徒开口说道:“根据国王规定的规则,我们五个人中至少有两个必死无疑。相信你们也推理出,在这种情况下后手的决策取决于先手,而最先抓取红豆的我掌握着你们的生杀大权,我无法保证你们存活,但一定可以置你们于死地。不如这样,你们四个人商量一个方案出来,谁死谁活都无所谓,只要能保证我百分之百存活,我就会配合你们行动;如果做不到这一点,你们就都给我陪葬吧。”
2号囚徒也对着排在自己后面的三个人说:“我同意1号的办法。你们三个商量一个方案出来,谁死谁活都无所谓,只要能保证1号和我百分之百存活,我就会和1号一起配合你们行动;如果做不到的话,我就让你们给我陪葬。”
3号囚徒听了便对4号和5号说:“我同意1号和2号的办法,你们两个商量一个方案出来,谁死谁活都无所谓,只要能保证1号、2号和我百分之百存活……”
4号和5号异口同声地打断3号的话:“你的意思就是叫我们两个去死喽?凭什么啊,大不了大家同归于尽!”
可以想见,即便五名囚徒可以先交流再行动,他们的存活概率也依然为0——因为他们五个人的行动准则都是利己第一、损人第二。