《海盜的難題》由會(huì)員分享,可在線(xiàn)閱讀,更多相關(guān)《海盜的難題(6頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、海盜的難題海盜的難題數(shù)學(xué)的邏輯有時(shí)會(huì)導(dǎo)致看來(lái)十分怪異的結(jié)論。一般的規(guī)則是,如果邏輯推理沒(méi)有漏洞,那么結(jié)論就必定站得住腳,即使它與你的直覺(jué)矛盾。1998 年 9 月,加利福尼亞州帕洛阿爾托的 Stephen M.Omohundro 寄給我一道難題,它恰好就屬于這一類(lèi)。這難題已經(jīng)流傳了至少十年,但是 Omohundro 對(duì)它作了改動(dòng),使它的邏輯問(wèn)題變得分外復(fù)雜了。先來(lái)看看此難題原先的形狀。10 名海盜搶得了窖藏的 100 塊金子,并打算瓜分這些戰(zhàn)利品。這是一些講民主的海盜(當(dāng)然是他們自己特有的民主),他們的習(xí)慣是按下面的方式進(jìn)行分配:最厲害的一名海盜提出分配方案,然后所有的海盜(包括提出方案者本人
2、)就此方案進(jìn)行表決。如果 50%或更多的海盜贊同此方案,此方案就獲得通過(guò)并據(jù)此分配戰(zhàn)利品。否則提出方案的海盜將被扔到海里,然后下提名最厲害的海盜又重復(fù)上述過(guò)程。所有的海盜都樂(lè)于看到他們的一位同伙被扔進(jìn)海里,不過(guò),如果讓他們選擇的話(huà),他們還是寧可得一筆現(xiàn)金。他們當(dāng)然也不愿意自己被扔到海里。所有的海盜都是有理性的,而且知道其他的海盜也是有理性的。此外,沒(méi)有兩名海盜是同等厲害的這些海盜按照完全由上到下的等級(jí)排好了座次,并且每個(gè)人都清楚自己和其他所有人的等級(jí)。這些金塊不能再分,也不允許幾名海盜共有金塊,因?yàn)槿魏魏1I都不相信他的同伙會(huì)遵守關(guān)于共享金塊的安排。這是一伙每人都只為自己打算的海盜。最兇的一名海
3、盜應(yīng)當(dāng)提出什么樣的分配方案才能使他獲得最多的金子呢?為方便起見(jiàn),我們按照這些海盜的怯懦程度來(lái)給他們編號(hào)。最怯懦的海盜為 1 號(hào)海盜,次怯懦的海盜為 2 號(hào)海盜,如此類(lèi)推。這樣最厲害的海盜就應(yīng)當(dāng)?shù)玫阶畲蟮木幪?hào),而方案的提出就將倒過(guò)來(lái)從上至下地進(jìn)行。分析所有這類(lèi)策略游戲的奧妙就在于應(yīng)當(dāng)從結(jié)尾出發(fā)倒推回去。游戲結(jié)束時(shí),你容易知道何種決策有利而何種決策不利。確定了這一點(diǎn)后,你就可以把它用到倒數(shù)第 2 次決策上,如此類(lèi)推。如果從游戲的開(kāi)頭出發(fā)進(jìn)行分析,那是走不了多遠(yuǎn)的。其原因在于,所有的戰(zhàn)略決策都是要確定:“如果我這樣做,那么下一個(gè)人會(huì)怎樣做?”因此在你以下海盜所做的決定對(duì)你來(lái)說(shuō)是重要的,而在你之前的海
4、盜所做的決定并不重要,因?yàn)槟惴凑龑?duì)這些決定也無(wú)能為力了。記住了這一點(diǎn),就可以知道我們的出發(fā)點(diǎn)應(yīng)當(dāng)是游戲進(jìn)行到只剩兩名海盜即 1 號(hào)和 2 號(hào)的時(shí)候。這時(shí)最厲害的海盜是 2 號(hào),而他的最佳分配方案是一目了然的:100 塊金子全歸他一人所有,1號(hào)海盜什么也得不到。由于他自己肯定為這個(gè)方案投贊成票,這樣就占了總數(shù)的 50%,因此方案獲得通過(guò)?,F(xiàn)在加上 3 號(hào)海盜。1 號(hào)海盜知道,如果 3 號(hào)的方案被否決,那么最后將只剩 2 個(gè)海盜,而 1 號(hào)將肯定一無(wú)所獲此外,3 號(hào)也明白 1 號(hào)了解這一形勢(shì)。因此,只要 3 號(hào)的分配方案給 1 號(hào)一點(diǎn)甜頭使他不至于空手而歸,那么不論 3 號(hào)提出什么樣的分配方案,1
5、 號(hào)都將投贊成票。因此 3 號(hào)需要分出盡可能少的一點(diǎn)金子來(lái)賄賂 1 號(hào)海盜,這樣就有了下面的分配方案:3 號(hào)海盜分得 99 塊金子,2 號(hào)海盜一無(wú)所獲,1 號(hào)海盜得 1 塊金子。4 號(hào)海盜的策略也差不多。他需要有 50%的支持票,因此同 3 號(hào)一樣也需再找一人做同黨。他可以給同黨的最低賄賂是 1 塊金子,而他可以用這塊金子來(lái)收買(mǎi) 2 號(hào)海盜。因?yàn)槿绻?4 號(hào)被否決而 3 號(hào)得以通過(guò),則 2 號(hào)將一文不名。因此,4 號(hào)的分配方案應(yīng)是:99 塊金子歸自己,3 號(hào)一塊也得不到,2 號(hào)得 1 塊金子,1 號(hào)也是一塊也得不到。5 號(hào)海盜的策略稍有不同。他需要收買(mǎi)另兩名海盜,因此至少得用 2 塊金子來(lái)賄賂
6、,才能使自己的方案得到采納。他的分配方案應(yīng)該是:98 塊金子歸自己,1 塊金子給 3 號(hào),1 塊金子給 1 號(hào)。這一分析過(guò)程可以照著上述思路繼續(xù)進(jìn)行下去。每個(gè)分配方案都是唯一確定的,它可以使提出該方案的海盜獲得盡可能多的金子,同時(shí)又保證該方案肯定能通過(guò)。照這一模式進(jìn)行下去,10 號(hào)海盜提出的方案將是 96 塊金子歸他所有,其他編號(hào)為偶數(shù)的海盜各得 1 塊金子,而編號(hào)為奇數(shù)的海盜則什么也得不到。這就解決了 10 名海盜的分配難題。Omohundro 的貢獻(xiàn)是他把這一問(wèn)題擴(kuò)大到有 500 名海盜的情形,即500 名海盜瓜分 100 塊金子。顯然,類(lèi)似的規(guī)律依然成立至少是在一定范圍內(nèi)成立。事實(shí)上,前
7、面所述的規(guī)律直到第 200 號(hào)海盜都成立。200 號(hào)海盜的方案將是:從 1 到 199 號(hào)的所有奇數(shù)號(hào)的海盜都將一無(wú)所獲,而從 2 到 198 號(hào)的所有偶數(shù)號(hào)海盜將各得 1 塊金子,剩下的 1 塊金子歸 200 號(hào)海盜自己所有。乍看起來(lái),這一論證方法到 200 號(hào)之后將不再適用了,因?yàn)?201號(hào)拿不出更多的金子來(lái)收買(mǎi)其他海盜。但是即使分不到金子,201 號(hào)至少還希望自己不會(huì)被扔進(jìn)海里,因此他可以這樣分配:給 1 到 199號(hào)的所有奇數(shù)號(hào)海盜每人 1 塊金子,自己一塊也不要。202 號(hào)海盜同樣別無(wú)選擇,只能一塊金子都不要了他必須把這100 塊金子全部用來(lái)收買(mǎi) 100 名海盜,而且這 100 名海
8、盜還必須是那些按照 201 號(hào)方案將一無(wú)所獲的人。由于這樣的海盜有 101 名,因此202 號(hào)的方案將不再是唯一的賄賂方案有 101 種。203 號(hào)海盜必須獲得 102 張贊成票,但他顯然沒(méi)有足夠的金子去收買(mǎi)101 名同伙。因此,無(wú)論提出什么樣的分配方案,他都注定會(huì)被扔到海里去喂魚(yú)。不過(guò),盡管 203 號(hào)命中注定死路一條,但并不是說(shuō)他在游戲進(jìn)程中不起任何作用。相反,204 號(hào)現(xiàn)在知道,203 號(hào)為了能保住性命,就必須避免由他自己來(lái)提出分配方案這么一種局面,所以無(wú)論 204 號(hào)海盜提出什么樣的方案,203 號(hào)都一定會(huì)投贊成票。這樣 204號(hào)海盜總算僥幸揀到 一條命:他可以得到他自己的 1 票、2
9、03 號(hào)的 1 票、以及另外 100 名收買(mǎi)的海盜的贊成票,剛好達(dá)到保命所需的 50%。獲得金子的海盜,必屬于根據(jù) 202 號(hào)方案肯定將一無(wú)所獲的那 101 名海盜之列。205 號(hào)海盜的命運(yùn)又如何呢?他可沒(méi)有這樣走運(yùn)了。他不能指望203 號(hào)和 204 號(hào)支持他的方案,因?yàn)槿绻麄兺镀狈磳?duì) 205 號(hào)方案,就可以幸災(zāi)樂(lè)禍地看到 205 號(hào)被扔到海里去喂魚(yú),而他們自己的性命卻仍然能夠保全。這樣,無(wú)論 205 號(hào)海盜提出什么方案都必死無(wú)疑。206 號(hào)海盜也是如此他肯定可以得到 205 號(hào)的支持,但這不足以救他一命。類(lèi)似地,207 號(hào)海盜需要 104 張贊成票除了他收買(mǎi)的 100 張贊成票以及他自己的
10、 1 張贊成票之外,他還需 3 張贊成票才能免于一死。他可以獲得 205 號(hào)和 206 號(hào)的支持,但還差一張票卻是無(wú)論如何也弄不到了,因此 207 號(hào)海盜的命運(yùn)也是下海喂魚(yú)。208 號(hào)又時(shí)來(lái)運(yùn)轉(zhuǎn)了。他需要 104 張贊成票,而 205、206、207 號(hào)都會(huì)支持他,加上他自己一票及收買(mǎi)的 100 票,他得以過(guò)關(guān)保命。獲得他賄賂的必屬于那些根據(jù) 204 號(hào)方案肯定將一無(wú)所獲的人(候選人包括 2 到 200 號(hào)中所有偶數(shù)號(hào)的海盜、以及 201、203、204 號(hào))。現(xiàn)在可以看出一條新的、此后將一直有效的規(guī)律:那些方案能過(guò)關(guān)的海盜(他們的分配方案全都是把金子用來(lái)收買(mǎi) 100 名同伙而自己一點(diǎn)都得不到
11、)相隔的距離越來(lái)越遠(yuǎn),而在他們之間的海盜則無(wú)論提什么樣的方案都會(huì)被扔進(jìn)海里因此為了保命,他們必會(huì)投票支持比他們厲害的海盜提出的任何分配方案。得以避免葬身魚(yú)腹的海盜包括 201、202、204、208、216、232、264、328、456 號(hào),即其號(hào)碼等于 200加 2 的某一方冪的海盜?,F(xiàn)在我們來(lái)看看哪些海盜是獲得賄賂的幸運(yùn)兒。分配賄賂的方法是不唯一的,其中一種方法是讓 201 號(hào)海盜把賄賂分給 1 到 199 號(hào)的所有奇數(shù)編號(hào)的海盜,讓 202 號(hào)分給 2 到 200 號(hào)的所有偶數(shù)編號(hào)的海盜,然后是讓 204 號(hào)賄賂奇數(shù)編號(hào)的海盜,208 號(hào)賄賂偶數(shù)編號(hào)的海盜,如此類(lèi)推,也就是輪流賄賂奇數(shù)編號(hào)和偶數(shù)編號(hào)的海盜。結(jié)論是:當(dāng) 500 名海盜運(yùn)用最優(yōu)策略來(lái)瓜分金子時(shí),頭 44 名海盜必死無(wú)疑,而 456 號(hào)海盜則給從 1 到 199 號(hào)中所有奇數(shù)編號(hào)的海盜每人分 1 塊金子,問(wèn)題就解決了。由于這些海盜所實(shí)行的那種民主制度,他們的事情就搞成了最厲害的一批海盜多半都是下海喂魚(yú),不過(guò)有時(shí)他們也會(huì)覺(jué)得自己很幸運(yùn)雖然分不到搶來(lái)的金子,但總可以免于一死。只有最怯懦的 200 名海盜有可能分得一份臟物,而他們之中又只有一半的人能真正 得到一塊金子,的確是怯懦者繼承財(cái)富。