海盜分金——精選推薦

2024年3月30日發(作者：工作自評)

5個海盜搶到了100顆寶石，每一顆都一樣的

大小和價值連城。 他們決定這么分：

1。抽簽決定自己的號碼（1，2，3，4，5）

2。首先，由1號提出分配方案，然后大家5人

進行表決，當且僅當超過半數的人同意時，按

照他的提案進行分配，否則將被扔入大海喂鯊

魚。 3。如果1號死后，再由2號提出分

配方案，然后大家4人進行表決，當且僅當超

過半數的人同意時，按照他的提案進行分配，

否則將被扔入大海喂鯊魚。 4。以此類推

條件： 每個海盜都是很聰明的人，都能很

理智的判斷得失，從而做出選擇。 問題：

最后的分配結果如何？ 提示： 海盜判斷

原則 1.保命 2.盡可能多寶石 3.盡可能多殺

大家討論討論喔：）

收藏 分享

0

頂

?

踩

?

給每一條河每一座山取一個溫暖的名字

陌生人, 我也

2

#

greatjason

發表于 2003-7-7 05:21 | 只看該

作者

無

海盜分金問題全攻略:

小試牛刀

★原文轉載自網易數學建模Algorithm版

wangzong_hui的《海盜分幣問題》★

數學的邏輯有時會導致看來十分怪異的結

論。一般的規則是，如果邏輯推理沒有漏

洞，那么結論就必定站得住腳，即使它與

你的直覺矛盾。 1998年9月，加利福尼

亞州帕洛阿爾托的Stephen M. Omohundro

寄給我一道難題，它恰好就屬于這一類。

這難題已經流傳了至少十年，但是

Omohundro對它作了改動，使它的邏輯問

題變得分外復雜了。

先來看看此難題原先的形狀。10名海

盜搶得了窖藏的100塊金子，并打算瓜分

這些戰利品。這是一些講民主的海盜（當

然是他們自己特有的民主），他們的習慣

是按下面的方式進行分配：最厲害的一名

海盜提出分配方案，然后所有的海盜（包

括提出方案者本人）就此方案進行表決。

如果50%或更多的海盜贊同此方案，此方

案就獲得通過并據此分配戰利品。否則提

出方案的海盜將被扔到海里，然后下提名

最厲害的海盜又重復上述過程。

所有的海盜都樂于看到他們的一位同

伙被扔進海里，不過，如果讓他們選擇的

話，他們還是寧可得一筆現金。他們當然

也不愿意自己被扔到海里。所有的海盜都

是有理性的，而且知道其他的海盜也是有

理性的。此外，沒有兩名海盜是同等厲害

的——這些海盜按照完全由上到下的等級

排好了座次，并且每個人都清楚自己和其

他所有人的等級。這些金塊不能再分，也

不允許幾名海盜共有金塊，因為任何海盜

都不相信他的同伙會遵守關于共享金塊的

安排。這是一伙每人都只為自己打算的海

盜。最兇的一名海盜應當提出什么樣的分

配方案才能使他獲得最多的金子呢？

為方便起見，我們按照這些海盜的怯

懦程度來給他們編號。最怯懦的海盜為1

號海盜，次怯懦的海盜為2號海盜，如此

類推。這樣最厲害的海盜就應當得到最大

的編號，而方案的提出就將倒過來從上至

下地進行。

分析所有這類策略游戲的奧妙就在于

應當從結尾出發倒推回去。游戲結束時，

你容易知道何種決策有利而何種決策不

利。確定了這一點后，你就可以把它用到

倒數第2次決策上，如此類推。如果從游

戲的開頭出發進行分析，那是走不了多遠

的。其原因在于，所有的戰略決策都是要

確定：“如果我這樣做，那么下一個人會

怎樣做？”

因此在你以下海盜所做的決定對你來

說是重要的，而在你之前的海盜所做的決

定并不重要，因為你反正對這些決定也無

能為力了。

記住了這一點，就可以知道我們的出

發點應當是游戲進行到只剩兩名海盜——

即1號和2號——的時候。這時最厲害的

海盜是2號，而他的最佳分配方案是一目

了然的：100塊金子全歸他一人所有，1號

海盜什么也得不到。由于他自己肯定為這

個方案投贊成票，這樣就占了總數的

50%，因此方案獲得通過。

現在加上3號海盜。1號海盜知道，

如果3號的方案被否決，那么最后將只剩

2個海盜，而1號將肯定一無所獲——此

外，3號也明白1號了解這一形勢。因

此，只要3號的分配方案給1號一點甜頭

使他不至于空手而歸，那么不論3號提出

什么樣的分配方案，1號都將投贊成票。

因此3號需要分出盡可能少的一點金子來

賄賂1號海盜，這樣就有了下面的分配方

案： 3號海盜分得99塊金子，2號海盜一

無所獲，1號海盜得1塊金子。

4號海盜的策略也差不多。他需要有

50%的支持票，因此同3號一樣也需再找一

人做同黨。他可以給同黨的最低賄賂是1

塊金子，而他可以用這塊金子來收買2號

海盜。因為如果4號被否決而3號得以通

過，則2號將一文不名。因此，4號的分

配方案應是：99塊金子歸自己，3號一塊

也得不到，2號得1塊金子，1號也是一塊

也得不到。

5號海盜的策略稍有不同。他需要收

買另兩名海盜，因此至少得用2塊金子來

賄賂，才能使自己的方案得到采納。他的

分配方案應該是：98塊金子歸自己，1塊

金子給3號，1塊金子給1號。

這一分析過程可以照著上述思路繼續

進行下去。每個分配方案都是唯一確定

的，它可以使提出該方案的海盜獲得盡可

能多的金子，同時又保證該方案肯定能通

過。照這一模式進行下去，10號海盜提出

的方案將是96塊金子歸他所有，其他編號

為偶數的海盜各得1塊金子，而編號為奇

數的海盜則什么也得不到。這就解決了10

名海盜的分配難題。

Omohundro的貢獻是他把這一問題擴

大到有500名海盜的情形，即500名海盜

瓜分100塊金子。顯然，類似的規律依然

成立——至少是在一定范圍內成立。事實

上，前面所述的規律直到第200號海盜都

成立。 200號海盜的方案將是：從1到

199號的所有奇數號的海盜都將一無所

獲，而從2到198號的所有偶數號海盜將

各得1塊金子，剩下的1塊金子歸200號

海盜自己所有。

乍看起來，這一論證方法到200號之

后將不再適用了，因為201號拿不出更多

的金子來收買其他海盜。但是即使分不到

金子，201號至少還希望自己不會被扔進

海里，因此他可以這樣分配：給1到199

號的所有奇數號海盜每人1塊金子，自己

一塊也不要。

202號海盜同樣別無選擇，只能一塊

金子都不要了——他必須把這100塊金子

全部用來收買100名海盜，而且這100名

海盜還必須是那些按照201號方案將一無

所獲的人。由于這樣的海盜有101名，因

此202號的方案將不再是唯一的——賄賂

方案有101種。

203號海盜必須獲得102張贊成票，

但他顯然沒有足夠的金子去收買101名同

伙。因此，無論提出什么樣的分配方案，

他都注定會被扔到海里去喂魚。不過，盡

管203號命中注定死路一條，但并不是說

他在游戲進程中不起任何作用。相反，204

號現在知道，203號為了能保住性命，就

必須避免由他自己來提出分配方案這么一

種局面，所以無論204號海盜提出什么樣

的方案，203號都一定會投贊成票。這樣

204號海盜總算僥幸揀到一條命：他可以

得到他自己的1票、203號的1票、以及

另外100名收買的海盜的贊成票，剛好達

到保命所需的50%。獲得金子的海盜，必

屬于根據202號方案肯定將一無所獲的那

101名海盜之列。

205號海盜的命運又如何呢？他可沒

有這樣走運了。他不能指望203號和204

號支持他的方案，因為如果他們投票反對

205號方案，就可以幸災樂禍地看到205

號被扔到海里去喂魚，而他們自己的性命

卻仍然能夠保全。這樣，無論205號海盜

提出什么方案都必死無疑。206號海盜也

是如此——他肯定可以得到205號的支

持，但這不足以救他一命。類似地，207

號海盜需要104張贊成票——除了他收買

的100張贊成票以及他自己的1張贊成票

之外，他還需3張贊成票才能免于一死。

他可以獲得205號和206號的支持，但還

差一張票卻是無論如何也弄不到了，因此

207號海盜的命運也是下海喂魚。

208號又時來運轉了。他需要104張

贊成票，而205、206、207號都會支持

他，加上他自己一票及收買的100票，他

得以過關保命。獲得他賄賂的必屬于那些

根據204號方案肯定將一無所獲的人（候

選人包括2到200號中所有偶數號的海

盜、以及201、203、204號）。

現在可以看出一條新的、此后將一直

有效的規律：那些方案能過關的海盜（他

們的分配方案全都是把金子用來收買100

名同伙而自己一點都得不到）相隔的距離

越來越遠，而在他們之間的海盜則無論提

什么樣的方案都會被扔進海里——因此為

了保命，他們必會投票支持比他們厲害的

海盜提出的任何分配方案。得以避免葬身

魚腹的海盜包括201、202、204、208、

216、232、264、328、456號，即其號碼

等于200加2的某一方冪的海盜。

現在我們來看看哪些海盜是獲得賄賂

的幸運兒。分配賄賂的方法是不唯一的，

其中一種方法是讓201號海盜把賄賂分給

1到199號的所有奇數編號的海盜，讓202

號分給2到200號的所有偶數編號的海

盜，然后是讓204號賄賂奇數編號的海

盜，208號賄賂偶數編號的海盜，如此類

推，也就是輪流賄賂奇數編號和偶數編號

的海盜。

結論是：當500名海盜運用最優策略

來瓜分金子時，頭44名海盜必死無疑，而

456號海盜則給從1到199號中所有奇數

編號的海盜每人分1塊金子，問題就解決

了。由于這些海盜所實行的那種民主制

度，他們的事情就搞成了最厲害的一批海

盜多半都是下海喂魚，不過有時他們也會

覺得自己很幸運——雖然分不到搶來的金

子，但總可以免于一死。只有最怯懦的

200名海盜有可能分得一份臟物，而他們

之中又只有一半的人能真正得到一塊金

子，的確是怯懦者繼承財富。

臨床醫學證明，數學建模可以有效的

抑制老年癡呆癥、小兒麻痹癥，以及

下肢血管靜脈曲張。

TOP

Echo

3

#

發表于 2003-7-7 05:25 | 只看該作者

無

這么快就給出答案了啊~~~

實習記者

TOP

4

dcyu

發表于 2003-7-7 05:45 | 只看該作者

無

發信人: starfish(金盆洗手，退隱江湖), 信區: Algorithm. 本篇人

氣: 35

#

小試牛刀

標 題: Re: 對海盜分金塊的疑問

發信站: 南京大學小百合站 (Mon Mar 31 12:04:49 2003)

本帖改編自《科學美國人》雜志中Ian Stewart的《兇猛海盜的邏

輯》

海盜，大家聽說過吧。這是一幫亡命之徒，在海上搶人錢財，奪人性

0

命，干的是刀頭上舔血的營生。在我們的印象中，他們一般都瞎一只

眼，用條黑布或者講究點的用個黑皮眼罩把壞眼遮上。他們還有在地

下埋寶的好習慣，而且總要畫上一張藏寶圖，以方便后人掘取。不過

大家是否知道，他們是世界上最民主的團體。參加海盜的都是桀驁不

馴的漢子，是不愿聽人命令的，船上平時一切事都由投票解決。船長

0

的唯一特權，是有自己的一套餐具--可是在他不用時，其他海盜是

可以借來用的。船上的唯一懲罰，就是被丟到海里去喂魚。

現在船上有若干個海盜，要分搶來的若干枚金幣。自然，這樣的問題

他們是由投票來解決的。投票的規則如下：先由最兇猛的海盜來提出

分配方案，然后大家一人一票表決，如果有50%或以上的海盜同意這

個

方案，那么就以此方案分配，如果少于50%的海盜同意，那么這個提

出

方案的海盜就將被丟到海里去喂魚，然后由剩下的海盜中最兇猛的那

個海盜提出方案，依此類推。

我們先要對海盜們作一些假設。

1)每個海盜的兇猛性都不同，而且所有海盜都知道別人的兇猛性，也

就是說，每個海盜都知道自己和別人在這個提出方案的序列中的位

置。

另外，每個海盜的數學和邏輯都很好，而且很理智。最后，海盜間私

底下的交易是不存在的，因為海盜除了自己誰都不相信。

2)一枚金幣是不能被分割的，不可以你半枚我半枚。

3)每個海盜當然不愿意自己被丟到海里去喂魚，這是最重要的。

4)每個海盜當然希望自己能得到盡可能多的金幣。

5)每個海盜都是現實主義者，如果在一個方案中他得到了1枚金幣，

而

下一個方案中，他有兩種可能，一種得到許多金幣，一種得不到金

幣，

他會同意目前這個方案，而不會有僥幸心理。總而言之，他們相信二

鳥在林，不如一鳥在手。

6)最后，每個海盜都很喜歡其他海盜被丟到海里去喂魚。在不損害自

己利益的前提下，他會盡可能投票讓自己的同伴喂魚。

現在，如果有10個海盜要分100枚金幣，將會怎樣？

0

要解決這類問題，我們總是從最后的情形向后推，這樣我們就知道在

最后這一步中什么是好的和壞的決定。然后運用這個知識，我們就可

以得到最后第二步應該作怎樣的決定，等等等等。要是直接就從開始

入手解決問題，我們就很容易被這樣的問題擋住去路：'要是我作

這

樣的決定，下面一個海盜會怎么做？'

以這個思路，先考慮只有2個海盜的情況（所有其他的海盜都已經被

丟

到海里去喂魚了）。記他們為P1和P2，其中P2比較兇猛。P2的最佳

方

案當然是：他自己得100枚金幣，P1得0枚。投票時他自己的一票就

足

夠50%了。

往前推一步。現在加一個更兇猛的海盜P3。P1知道--P3知道他知道

--如果P3的方案被否決了，游戲就會只由P1和P2來繼續，而P1就

一

枚金幣也得不到。所以P3知道，只要給P1一點點甜頭，P1就會同意

他

的方案（當然，如果不給P1一點甜頭，反正什么也得不到，P1寧可投

票讓P3去喂魚）。所以P3的最佳方案是：P1得1枚，P2什么也得不

到，

P3得99枚。

P4的情況差不多。他只要得兩票就可以了，給P2一枚金幣就可以讓

他

投票贊同這個方案，因為在接下來P3的方案中P2什么也得不到。P5

也

是相同的推理方法只不過他要說服他的兩個同伴，于是他給每一個在

P4方案中什么也得不到的P1和P3一枚金幣，自己留下98枚。

依此類推，P10的最佳方案是：他自己得96枚，給每一個在P9方案中

什

么也得不到的P2，P4，P6和P8一枚金幣。

下面是以上推理的一個表（Y表示同意，N表示反對）：

P1 P2

0 100

N Y

P1 P2 P3

1 0 99

Y N Y

P1 P2 P3 P4

0 1 0 99

N Y N Y

P1 P2 P3 P4 P5

1 0 1 0 98

Y N Y N Y

??

P1 P2 P3 P4 P5 P6 P7 P8 P9 P10

0 1 0 1 0 1 0 1 0 96

N Y N Y N Y N Y N Y

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

0

現在我們將海盜分金問題推廣：

1)改變一下規則，投票中方案必須得到超過50%的票數（只得到50%票

數的方案的提出者也會被丟到海里去喂魚），那么如何解決10個海

盜

分100枚金幣的問題？

2)不改變規則，如果讓500個海盜分100枚金幣，會發生什么？

3)如果每個海盜都有1枚金幣的儲蓄，他可以把這枚金幣用在分配方

案

中，如果他被丟到海里去喂魚，那么他的儲蓄將被并在要分配的金幣

堆中，這時候又怎樣？

通過對規則的細小改變，海盜分金問題可以有許多變化，但是最有趣

的大概是1)和2)（規則仍為50%票數即可）的情況，本帖只對這兩種

情

況進行討論。

首先考慮1)。現在只有P1和P2的情形變得對P2其糟無比：1票是不

夠的，

可是就算他把100枚金幣都給P1，P1也照樣會把他丟到海里去。可是

P2

很關鍵，因為如果P3進行分配方案的話，即使他一枚金幣也不給P2，

P2也會同意，這樣一來P3就有P2這張鐵票！P3的最佳方案就是：獨

吞

100枚金幣。

P4要3張票，而P3是一定反對他的，而如果不給P2一點甜頭，P2也

會反

對，因為P2可以在P3的方案中得救，目前為什么不把P4丟到海里

呢？

所以要分別給P1和P2一枚金幣，這樣P4就有包括他自己1票的3

票。P4

的方案為：P1，P2每人1枚金幣，他自己98枚。

P5的情況要復雜點，他也要3票。P4是會反對他的，所以不用給，給

P3一枚金幣就能使他支持自己的方案，因為在接下來的P4方案中他什

么也得不到。問題是P1和P2：只要其中有一個支持就可以了。可是只

給1枚金幣是不行的，P4方案中他們一定有1枚金幣可得，所以只要

在

他們中隨便選一個，給2枚金幣，另一個就對不起了，不給。這樣P5

的方案是：自己97枚，P3得1枚，P1或P2得2枚。

0

P6的方案建立在P5的上面，只要給每個P5方案中不得益的海盜1枚

金幣。

要注意的是，P1和P2都應該看作在P5方案中不得益的：他們可能得

2枚，

可是也可能1枚不得，所以只要P6給他們1枚金幣，根據'二鳥

在林，

不如一鳥在手'的原則，就可以讓他們支持P6的方案。所以P6的

方案

是唯一的：P1，P2，P4每人1枚金幣，P6自己拿97枚。

這樣繼續下去，P9的方案是：P3，P5，P7每人1枚金幣，然后在P1，

P2，P4，P6中任選一人給2枚金幣，P9自己得95枚。最后，P10的方

案

是唯一的：P1，P2，P4，P6，P8每人1枚金幣，P10自己得95枚。

2)是最有趣的（提醒：我們回到50%票即可的規則）。原題解中的推理

過程直到200個海盜都是成立的：P200給每個偶數號的海盜1枚金

幣，

包括他自己，其他海盜什么也得不到。從P201開始，繼續推理就變得

有點困難了：P201為了不被丟到海里去，必須什么也不留給自己，而

給從P1到P199中所有奇數號海盜每人1枚金幣，從而爭取到100

票，加

上他自己1票，逃過一劫。P202也什么都得不到，他必須用這100枚

金

幣買通100個從P201的方案中什么也得不到的海盜，要注意到現在這

個

方案不是唯一的：P201的方案中得不到金幣的海盜是所有奇數號的海

盜，有101個（包括P201），所以有101種方案。

P203必須得到102票，除了自己的1票外，他只有100枚金幣，所以

只能

買到100票，所以可憐的家伙就被丟到海里喂魚了。但是，P203是個

很

重要的角色，因為P204知道如果自己的方案不被通過，P203也一樣會

完蛋，所以他有P203的一張鐵票。所以P204可以大出一口氣：他自

己

一票，加上P203一票，然后加上用100枚金幣買的確100票，他就得

救

了！100個有幸得到1枚金幣的海盜，可以是P1到P202中任何100

個：因

為其中的偶數號的從P202的方案中什么也得不到，如果P204給他們

中

某個海盜1枚金幣，這個海盜一定會贊同這個方案；而編號為奇數的

海

盜呢，只是有可能從P202的方案中得益罷了（可能性為100/101），

所

以根據'二鳥在林，不如一鳥在手'的原則，如果能得到1枚

金幣，他

也會贊同這個方案。

接下去P205是不能把希望放在P203和P204這兩張票上的，因為就算

他

被丟到海里去，P203和P204還可以通過P204的方案機會活下來。

P206

雖然可以靠P205的鐵票，加上自己1票和100枚金幣搞到的100票，

只有

102票，所以他也被丟到海里喂魚。P207好不了多少，他需要104

票，

而他自己以及P205和P206的鐵票加上100枚金幣搞到的100票只有

103票

--只好下海。

P208運氣比較好，他同樣也要104票，可是P205，P206，P207都會投

票

贊成他的方案！加上他自己的1票和買來的100票，他終于逃脫了做

魚

食的命運。

這樣我們就有了一種可以一直推下去的新邏輯。海盜可以什么也不留

給自己，買上100票，然后依靠一部分一定會被丟下海的海盜的鐵

票，

從而讓自己的方案通過。有這樣運氣的海盜分別是P201，P202，

P204，

P208，P216，P232，P264，P328和P456??我們看到這樣的號碼是

200

加上一個2的次冪。

哪些海盜是受益者呢，顯然鐵票是不用（不能）給金幣的。所以只有

上一個幸運號碼及他以前的那些海盜才有可能得到1枚金幣。于是我

們

得到500海盜分100枚金幣的結論是：前44個最兇猛的海盜被丟進海

里，

然后P456給P1到P328中的100個海盜每人1枚金幣。

就這樣，最兇猛的海盜被丟進海里，而比較兇猛的什么也得不到，而

只有最溫柔的那些海盜，才有可能得到1枚金幣。正如《馬太福音》

所

說：'溫柔的人有福了，因為他們必承受地土！'

【 在 beareye 的大作中提到: 】

:

: 剛剛又看到了這個問題，有個疑問，我覺得這個問題不太嚴密。

: 簡單起見設只有3個海盜A,B,C分100個金塊，如果A提出按照

100，0，0分配應該

是可?.

: 因為如果海盜B不同意，那么海盜A被殺掉，但是B同樣也是一塊

都拿不到，而且

還有?.

: 的危險。

: 同樣是1塊金塊都拿不到，一種情況沒有危險，一種情況有被殺掉

的危險，如果

是你?.

: 擇哪種？

--

鳳凰臺上鳳凰游，鳳去臺空江自流。

吳宮花草埋幽徑，晉代衣冠成古丘。

三山伴落青天外，二水中分白鷺洲。

總謂浮云能蔽日，長安不見使人愁。

/dcyu

TOP

whatperson

發表于 2003-7-7 18:02 | 只看該作者

無

樓上引用的文章都是"分配方案有50%或以上的人同意,方案通過

5

#

新生入學

";

而摟主的題是"分配方案有一半以上的人同意才通過"

我的分析是:

無論第四個人(4)提什么方案,第五個人(5)一定反對;這樣,(4)為了保

命,一定同意(3)的任何方案;

所以,(3)的方案是3)--100,(4)--0,(5)--0;

這樣,(2)只要給(4),(5)最少的好處,就能得到他們的支持(否則他們什

么也得不到),再加上自己有75%的人支持自己的方案;即(2)--98,(3)--

0,(4)--1,(5)--1;

(1)的方案必須再得到另外兩個人的支持才能通過,(3)只要得到1顆寶

石就支持(1),(4)或(5)只要得到2顆寶石就支持(1);

所以,(1)的方案是(1)--97,(2)--0,(3)--1,(4)--2,(5)--0;或者是

(1)--97,(2)--0,(3)--1,(4)--0,(5)--2;

不知道大家同意我的分析么?討論討論