海盜的難題

《海盜的難題》由會員分享，可在線閱讀，更多相關《海盜的難題（6頁珍藏版）》請在裝配圖網上搜索。

1、海盜的難題海盜的難題數學的邏輯有時會導致看來十分怪異的結論。一般的規則是，如果邏輯推理沒有漏洞，那么結論就必定站得住腳，即使它與你的直覺矛盾。1998 年 9 月，加利福尼亞州帕洛阿爾托的 Stephen M.Omohundro 寄給我一道難題，它恰好就屬于這一類。這難題已經流傳了至少十年，但是 Omohundro 對它作了改動，使它的邏輯問題變得分外復雜了。先來看看此難題原先的形狀。10 名海盜搶得了窖藏的 100 塊金子，并打算瓜分這些戰利品。這是一些講民主的海盜（當然是他們自己特有的民主），他們的習慣是按下面的方式進行分配：最厲害的一名海盜提出分配方案，然后所有的海盜（包括提出方案者本人

2、）就此方案進行表決。如果 50%或更多的海盜贊同此方案，此方案就獲得通過并據此分配戰利品。否則提出方案的海盜將被扔到海里，然后下提名最厲害的海盜又重復上述過程。所有的海盜都樂于看到他們的一位同伙被扔進海里，不過，如果讓他們選擇的話，他們還是寧可得一筆現金。他們當然也不愿意自己被扔到海里。所有的海盜都是有理性的，而且知道其他的海盜也是有理性的。此外，沒有兩名海盜是同等厲害的這些海盜按照完全由上到下的等級排好了座次，并且每個人都清楚自己和其他所有人的等級。這些金塊不能再分，也不允許幾名海盜共有金塊，因為任何海盜都不相信他的同伙會遵守關于共享金塊的安排。這是一伙每人都只為自己打算的海盜。最兇的一名海

3、盜應當提出什么樣的分配方案才能使他獲得最多的金子呢？為方便起見，我們按照這些海盜的怯懦程度來給他們編號。最怯懦的海盜為 1 號海盜，次怯懦的海盜為 2 號海盜，如此類推。這樣最厲害的海盜就應當得到最大的編號，而方案的提出就將倒過來從上至下地進行。分析所有這類策略游戲的奧妙就在于應當從結尾出發倒推回去。游戲結束時，你容易知道何種決策有利而何種決策不利。確定了這一點后，你就可以把它用到倒數第 2 次決策上，如此類推。如果從游戲的開頭出發進行分析，那是走不了多遠的。其原因在于，所有的戰略決策都是要確定：“如果我這樣做，那么下一個人會怎樣做？”因此在你以下海盜所做的決定對你來說是重要的，而在你之前的海

4、盜所做的決定并不重要，因為你反正對這些決定也無能為力了。記住了這一點，就可以知道我們的出發點應當是游戲進行到只剩兩名海盜即 1 號和 2 號的時候。這時最厲害的海盜是 2 號，而他的最佳分配方案是一目了然的：100 塊金子全歸他一人所有，1號海盜什么也得不到。由于他自己肯定為這個方案投贊成票，這樣就占了總數的 50%，因此方案獲得通過。現在加上 3 號海盜。1 號海盜知道，如果 3 號的方案被否決，那么最后將只剩 2 個海盜，而 1 號將肯定一無所獲此外，3 號也明白 1 號了解這一形勢。因此，只要 3 號的分配方案給 1 號一點甜頭使他不至于空手而歸，那么不論 3 號提出什么樣的分配方案，1

5、 號都將投贊成票。因此 3 號需要分出盡可能少的一點金子來賄賂 1 號海盜，這樣就有了下面的分配方案：3 號海盜分得 99 塊金子，2 號海盜一無所獲，1 號海盜得 1 塊金子。4 號海盜的策略也差不多。他需要有 50%的支持票，因此同 3 號一樣也需再找一人做同黨。他可以給同黨的最低賄賂是 1 塊金子，而他可以用這塊金子來收買 2 號海盜。因為如果 4 號被否決而 3 號得以通過，則 2 號將一文不名。因此，4 號的分配方案應是：99 塊金子歸自己，3 號一塊也得不到，2 號得 1 塊金子，1 號也是一塊也得不到。5 號海盜的策略稍有不同。他需要收買另兩名海盜，因此至少得用 2 塊金子來賄賂

6、，才能使自己的方案得到采納。他的分配方案應該是：98 塊金子歸自己，1 塊金子給 3 號，1 塊金子給 1 號。這一分析過程可以照著上述思路繼續進行下去。每個分配方案都是唯一確定的，它可以使提出該方案的海盜獲得盡可能多的金子，同時又保證該方案肯定能通過。照這一模式進行下去，10 號海盜提出的方案將是 96 塊金子歸他所有，其他編號為偶數的海盜各得 1 塊金子，而編號為奇數的海盜則什么也得不到。這就解決了 10 名海盜的分配難題。Omohundro 的貢獻是他把這一問題擴大到有 500 名海盜的情形，即500 名海盜瓜分 100 塊金子。顯然，類似的規律依然成立至少是在一定范圍內成立。事實上，前

7、面所述的規律直到第 200 號海盜都成立。200 號海盜的方案將是：從 1 到 199 號的所有奇數號的海盜都將一無所獲，而從 2 到 198 號的所有偶數號海盜將各得 1 塊金子，剩下的 1 塊金子歸 200 號海盜自己所有。乍看起來，這一論證方法到 200 號之后將不再適用了，因為 201號拿不出更多的金子來收買其他海盜。但是即使分不到金子，201 號至少還希望自己不會被扔進海里，因此他可以這樣分配：給 1 到 199號的所有奇數號海盜每人 1 塊金子，自己一塊也不要。202 號海盜同樣別無選擇，只能一塊金子都不要了他必須把這100 塊金子全部用來收買 100 名海盜，而且這 100 名海

8、盜還必須是那些按照 201 號方案將一無所獲的人。由于這樣的海盜有 101 名，因此202 號的方案將不再是唯一的賄賂方案有 101 種。203 號海盜必須獲得 102 張贊成票，但他顯然沒有足夠的金子去收買101 名同伙。因此，無論提出什么樣的分配方案，他都注定會被扔到海里去喂魚。不過，盡管 203 號命中注定死路一條，但并不是說他在游戲進程中不起任何作用。相反，204 號現在知道，203 號為了能保住性命，就必須避免由他自己來提出分配方案這么一種局面，所以無論 204 號海盜提出什么樣的方案，203 號都一定會投贊成票。這樣 204號海盜總算僥幸揀到 一條命：他可以得到他自己的 1 票、2

9、03 號的 1 票、以及另外 100 名收買的海盜的贊成票，剛好達到保命所需的 50%。獲得金子的海盜，必屬于根據 202 號方案肯定將一無所獲的那 101 名海盜之列。205 號海盜的命運又如何呢？他可沒有這樣走運了。他不能指望203 號和 204 號支持他的方案，因為如果他們投票反對 205 號方案，就可以幸災樂禍地看到 205 號被扔到海里去喂魚，而他們自己的性命卻仍然能夠保全。這樣，無論 205 號海盜提出什么方案都必死無疑。206 號海盜也是如此他肯定可以得到 205 號的支持，但這不足以救他一命。類似地，207 號海盜需要 104 張贊成票除了他收買的 100 張贊成票以及他自己的

10、 1 張贊成票之外，他還需 3 張贊成票才能免于一死。他可以獲得 205 號和 206 號的支持，但還差一張票卻是無論如何也弄不到了，因此 207 號海盜的命運也是下海喂魚。208 號又時來運轉了。他需要 104 張贊成票，而 205、206、207 號都會支持他，加上他自己一票及收買的 100 票，他得以過關保命。獲得他賄賂的必屬于那些根據 204 號方案肯定將一無所獲的人（候選人包括 2 到 200 號中所有偶數號的海盜、以及 201、203、204 號）?，F在可以看出一條新的、此后將一直有效的規律：那些方案能過關的海盜（他們的分配方案全都是把金子用來收買 100 名同伙而自己一點都得不到

11、）相隔的距離越來越遠，而在他們之間的海盜則無論提什么樣的方案都會被扔進海里因此為了保命，他們必會投票支持比他們厲害的海盜提出的任何分配方案。得以避免葬身魚腹的海盜包括 201、202、204、208、216、232、264、328、456 號，即其號碼等于 200加 2 的某一方冪的海盜?，F在我們來看看哪些海盜是獲得賄賂的幸運兒。分配賄賂的方法是不唯一的，其中一種方法是讓 201 號海盜把賄賂分給 1 到 199 號的所有奇數編號的海盜，讓 202 號分給 2 到 200 號的所有偶數編號的海盜，然后是讓 204 號賄賂奇數編號的海盜，208 號賄賂偶數編號的海盜，如此類推，也就是輪流賄賂奇數編號和偶數編號的海盜。結論是：當 500 名海盜運用最優策略來瓜分金子時，頭 44 名海盜必死無疑，而 456 號海盜則給從 1 到 199 號中所有奇數編號的海盜每人分 1 塊金子，問題就解決了。由于這些海盜所實行的那種民主制度，他們的事情就搞成了最厲害的一批海盜多半都是下海喂魚，不過有時他們也會覺得自己很幸運雖然分不到搶來的金子，但總可以免于一死。只有最怯懦的 200 名海盜有可能分得一份臟物，而他們之中又只有一半的人能真正 得到一塊金子，的確是怯懦者繼承財富。