囚徒與紅豆

還記得上一個(gè)故事里的五名大盜嗎？就在他們正要瓜分那條價(jià)值連城的珍珠項(xiàng)鏈時(shí)，國(guó)王的士兵趁機(jī)包圍了他們。負(fù)隅頑抗只有死路一條，舉手投降說(shuō)不定還有活下來(lái)的機(jī)會(huì)。于是，這五名絕頂聰明、理智過(guò)人卻也極度自私、互相猜忌的大盜就這么變成階下囚。

國(guó)王對(duì)這五名為非作歹的大盜早有耳聞，他決定用一種特別的方式來(lái)讓他們自己決定對(duì)自己的懲罰。國(guó)王讓典獄官拿來(lái)一個(gè)布袋，并在布袋里放進(jìn)100顆紅豆。五名囚徒通過(guò)抽簽決定從1號(hào)到5號(hào)的順序，并按順序在布袋中抓出一定數(shù)量的紅豆。當(dāng)五個(gè)人都抓過(guò)紅豆之后，典獄官會(huì)確認(rèn)他們手中的紅豆數(shù)量，并將抓得最多的人和抓得最少的人處死，剩下的人則將被判處苦役。

他們不必將所有紅豆全部抓完，但每個(gè)人至少要抓1顆紅豆。這就意味著前面的人在抓紅豆時(shí)，至少要留下數(shù)量與尚未抓取紅豆的人數(shù)相同的紅豆。如果抓得最多或抓得最少的不止一人，比如，有兩名囚犯都只抓出1顆紅豆，其他人抓取的紅豆則不止1顆，那么按照規(guī)則，這兩名囚犯都會(huì)作為抓得最少的人被處死。五名囚徒抓取紅豆的過(guò)程都是在典獄官的監(jiān)督下單獨(dú)進(jìn)行的，也就是說(shuō)他們之間無(wú)法交流，但每個(gè)人都可以摸出布袋中剩余的紅豆數(shù)量。

別忘了，這5個(gè)人極度自私且互相猜忌，所以他們行動(dòng)的最大前提是保住自己的命，而且會(huì)盡可能地使事態(tài)對(duì)其他人不利，同時(shí)他們也不可能合作；并且他們都是同樣理智、同樣聰明的人，所以五個(gè)人中無(wú)論是誰(shuí)想出的辦法，其他人也一樣想得到。

請(qǐng)問(wèn)，在這五名囚徒之中，誰(shuí)的存活概率最低？如果國(guó)王允許這五個(gè)人在抓取紅豆之前先進(jìn)行交流，情況將會(huì)發(fā)生什么樣的變化呢？

答案：

首先，讓我們確認(rèn)這一點(diǎn)：這五個(gè)人的行動(dòng)原則都是先求保命，再盡可能地置其他人于死地，即每個(gè)人都會(huì)考慮排在自己后面的人可能采取的最佳方案，并選擇剩下的人所采取的最佳方案中使自己存活概率最大的方案；如果存在多種方案使自己的存活概率最大化，那么他們會(huì)選擇可以殺死最多人的方案。

其次，由于抓得最多和抓得最少的人都將被處死，所以對(duì)于后手來(lái)說(shuō)，安全的做法是“平均值法”，即先摸出已有多少顆紅豆被取走，然后用已被取走的紅豆數(shù)量除以排在自己前面的人數(shù)，得到一個(gè)平均值。當(dāng)平均值為整數(shù)時(shí)，抓取顆數(shù)等于平均值的紅豆；當(dāng)平均值不為整數(shù)時(shí)，則先四舍五入取整，再抓取相應(yīng)顆數(shù)的紅豆。

接下來(lái)，讓我們使用完全歸納法來(lái)推理一下可能出現(xiàn)的情況：

由于規(guī)定每人至少要抓出1顆紅豆，所以不妨先分給五名囚徒每人1顆紅豆，然后再讓他們?cè)谑Ｏ碌?5顆紅豆中抓取x顆紅豆，即0≤x≤95，且x為整數(shù)。假設(shè)1號(hào)囚徒所抓取的紅豆數(shù)量為整數(shù)y，2號(hào)囚徒所抓取的紅豆數(shù)量為整數(shù)z。

（1）當(dāng)y=95時(shí)，1號(hào)囚徒為抓得最多的人，剩下的四名囚徒都是抓得最少的人。結(jié)果為無(wú)人生存。

（2）當(dāng)48≤y≤94時(shí)，2號(hào)囚徒必然會(huì)抓走剩下的所有紅豆，使1號(hào)抓得最多，3號(hào)、4號(hào)、5號(hào)抓得最少。結(jié)果為2號(hào)獨(dú)活。

（3）當(dāng)33≤y≤47時(shí)，2號(hào)囚徒出于自保必然會(huì)抓取y-1顆紅豆。3號(hào)摸出剩下的紅豆數(shù)量，并推理出自己不可能成為抓得最多的人這一點(diǎn)，于是選擇抓走剩下的所有紅豆，使1號(hào)抓得最多，4號(hào)、5號(hào)抓得最少。結(jié)果為2號(hào)、3號(hào)存活。

（4）當(dāng)20≤y≤32時(shí)，2號(hào)、3號(hào)、4號(hào)囚徒出于自保都會(huì)選擇抓取Y-1顆紅豆。因?yàn)閷?duì)于2號(hào)和3號(hào)來(lái)說(shuō)，要?dú)⑺廊耍?號(hào)、4號(hào)、5號(hào)）需要抓走剩下的所有紅豆，但如果這么做的話便無(wú)法保證自己存活（自己有可能成為抓得最多的人），所以在自保（只比1號(hào)少抓1顆）的同時(shí)殺死兩人是最優(yōu)策略。身為后手的4號(hào)采取“平均值法”，同樣拿走y-1顆。如此一來(lái)，5號(hào)別無(wú)選擇，只能成為抓得最少的人；1號(hào)則成為抓得最多的人。結(jié)果為2號(hào)、3號(hào)、4號(hào)存活。

（5）當(dāng)1≤y≤18時(shí)，必有y-1≤z≤y+1。因?yàn)槿缛舨蝗唬?號(hào)、4號(hào)、5號(hào)囚徒就會(huì)根據(jù)“平均值法”抓取數(shù)量等于y和z的平均值的紅豆，使得1號(hào)和2號(hào)分別成為抓得最多和抓得最少的人，而剩下的三人存活。然而，當(dāng)y-1≤z≤y+1時(shí)，根據(jù)“平均值法”，3號(hào)、4號(hào)、5號(hào)所抓取的紅豆數(shù)量也不會(huì)大于y，結(jié)果為無(wú)人生存。

（6）當(dāng)y=0時(shí)，1號(hào)囚徒為抓得最少的人，必然無(wú)法存活。

（7）當(dāng)y=19時(shí)，就相當(dāng)于將問(wèn)題的主角換成2號(hào)囚徒。對(duì)于2號(hào)來(lái)說(shuō)，當(dāng)z≥20時(shí)，情況同（3）、（4）；當(dāng)z≤20時(shí)，情況同（5）。但在（3）、（4）、（5）三種情況中，2號(hào)都無(wú)法存活，所以對(duì)于2號(hào)來(lái)說(shuō)，最佳策略是使z=19。接下來(lái)問(wèn)題的主角換成3號(hào)囚徒……出于同樣的原因，最終五個(gè)人全部各自抓取19顆紅豆，結(jié)果是五名囚徒同時(shí)成為抓得最多也是抓得最少的人，即無(wú)人生存。

綜上所述，無(wú)論選擇抓取多少顆紅豆，1號(hào)囚徒都必然死亡，即對(duì)1號(hào)來(lái)說(shuō)，不存在使自己存活的最佳策略。在這種情況下，1號(hào)會(huì)退而求其次，并選擇盡可能地置其他囚犯于死地的策略，即使y=95或y=19，使得無(wú)人生存。也就是說(shuō)，五名囚徒的存活概率是相同的——他們的存活概率都是0。

如果國(guó)王允許這五個(gè)人在抓取紅豆之前先進(jìn)行交流，情況會(huì)不會(huì)有所改善呢？讓我們?cè)O(shè)想一下：五名同樣絕頂聰明又同樣自私的囚徒經(jīng)過(guò)一番推理，都得出自己必死無(wú)疑的事實(shí)……

這時(shí)，1號(hào)囚徒開口說(shuō)道：“根據(jù)國(guó)王規(guī)定的規(guī)則，我們五個(gè)人中至少有兩個(gè)必死無(wú)疑。相信你們也推理出，在這種情況下后手的決策取決于先手，而最先抓取紅豆的我掌握著你們的生殺大權(quán)，我無(wú)法保證你們存活，但一定可以置你們于死地。不如這樣，你們四個(gè)人商量一個(gè)方案出來(lái)，誰(shuí)死誰(shuí)活都無(wú)所謂，只要能保證我百分之百存活，我就會(huì)配合你們行動(dòng)；如果做不到這一點(diǎn)，你們就都給我陪葬吧。”

2號(hào)囚徒也對(duì)著排在自己后面的三個(gè)人說(shuō)：“我同意1號(hào)的辦法。你們?nèi)齻€(gè)商量一個(gè)方案出來(lái)，誰(shuí)死誰(shuí)活都無(wú)所謂，只要能保證1號(hào)和我百分之百存活，我就會(huì)和1號(hào)一起配合你們行動(dòng)；如果做不到的話，我就讓你們給我陪葬。”

3號(hào)囚徒聽了便對(duì)4號(hào)和5號(hào)說(shuō)：“我同意1號(hào)和2號(hào)的辦法，你們兩個(gè)商量一個(gè)方案出來(lái)，誰(shuí)死誰(shuí)活都無(wú)所謂，只要能保證1號(hào)、2號(hào)和我百分之百存活……”

4號(hào)和5號(hào)異口同聲地打斷3號(hào)的話：“你的意思就是叫我們兩個(gè)去死嘍？憑什么啊，大不了大家同歸于盡！”

可以想見，即便五名囚徒可以先交流再行動(dòng)，他們的存活概率也依然為0——因?yàn)樗麄兾鍌€(gè)人的行動(dòng)準(zhǔn)則都是利己第一、損人第二。