5個海盜搶得100枚金幣後，討論如何進行公正分配？

01-21

分配原則是：
（1）抽籤確定各人的分配順序號碼（1，2，3，4，5）；
（2）由抽到1號簽的海盜提出分配方案，然後5人進行表決，如果方案得到超過半數的人同意，就按照他的方案進行分配，否則就將1號扔進大海喂鯊魚；
（3）如果1號被扔進大海，則由2號提出分配方案，然後由剩餘的4人進行表決，當且僅當超過半數的人同意時，才會按照他的提案進行分配，否則也將被扔入大海；
（4）依此類推。

這裡假設每一個海盜都是絕頂聰明而理性，他們都能夠進行嚴密的邏輯推理，並能很理智的判斷自身的得失，即能夠在保住性命的前提下得到最多的金幣。假設每一輪表決後的結果都能順利得到執行，那麼抽到1號的海盜應該提出怎樣的分配方案才能使自己既不被扔進海里，又可以得到更多的金幣呢？

正好上周喝酒，有個同事提出這個問題賭酒。酒精讓腦袋轉速加快，在眾人討論提示下很快明白了解題關鍵。

解題關鍵是理解每個海盜最期望的結果，以及每個提案能夠接受最差的結果，並且要逆推。

假設1、2、3都掛了，輪到4提出方案，無論4什麼方案，5是一定反對的。因為此時只有50%的人同意，未超半數，4喂鯊魚，5獨吞100金幣。有人要問了：難道4提出啥都不要，把金子都給了5，5還會投反對票嗎？這個問題很好，答案與智商、邏輯一概無關，只和人性有關。那叫啥的古人曾經曰過：金幣要獨吞，斬草要除根！

對於4而言：3死，4必死。無論3提任何方案，4都得保住3，對比錢，還是命比較重要啊！

假設1、2都掛了，輪到3提出方案，他知道4是他的最大粉絲，無論方案如何，為了保命一定投贊成票。所以，3必然提出（100，0，0）的方案，並且肯定會獲得2：1的通過。

對於3而言：1、2都掛了是他最好的結果，所以，他無論如何都會推動這件事！

假設1都掛了，輪到2提出方案，他知道最想他死的人就是3，但是，他也知道4、5是可以爭取的，因為如果2死了，3就獨吞100金幣，4、5連毛線都沒。2最終會提出（98，0，1，1）的方案，他知道對於4、5而言，這是最好的結果：4不但不會死，還會有1個金幣；而5，也算是比啥都沒有好。

對於2而言：1掛了是他最好的結果，所以，他也將推動這件事！

輪到1了，根據上面的推斷：2無論如何都會要1死，3知道1死了他將啥都得不到，4、5可能最大的收益是1個金幣。那就用金幣拉拉票唄，3比較好打發，看看4、5誰比較不厚道就把不厚道的那份給比較厚道的那位，總之自己加上兩票就行了：

1、大家都有點：97，0，1，1，1

2、給4多點：97，0，1，2，0

3、給5多點：97，0，1，0，2

引用鄺石:

假設1、2、3都掛了，輪到4提出方案，無論4什麼方案，5是一定反對的。因為此時只有50%的人同意，未超半數，4喂鯊魚，5獨吞100金幣。有人要問了：難道4提出啥都不要，把金子都給了5，5還會投反對票嗎？這個問題很好，答案與智商、邏輯一概無關，只和人性有關。那叫啥的古人曾經曰過：金幣要獨吞，斬草要除根！

這一處不對。答案牽扯到了人性，可這是純粹的推理題，而原題也註明了：假設每一輪表決後的結果都能順利得到執行。所以，當4號提出所有金幣給5號時，5號沒有理由拒絕，3號死或不死，對4號的生死均無影響。

重新推理一次。

如果只剩4、5的時候，4隻有一個方案保證活命，那就是：0，100。

如果剩下3、4、5的時候，3擁有絕對的支配權。上文已提到，如果只剩兩個海盜，那麼4號將拿不到一分金幣，所以只要給4號1枚以上的金幣，就能拉攏。

於是3號利益最大化的方案是：99、1、0（2:1）。

如果是還剩2、3、4、5的情況，主動權在2號手裡。

——2號必須死亡，3號才能利益最大化，所以不用考慮3號的利益；

——4號則只需1枚以上的金幣即可拉攏；

——5號則處於悲劇的地位，因為只剩三個海盜的情況下，他是必然無法分得金幣，於是2號只需分給5號1枚以上的金幣，5號就會同意。

於是2號利益最大化的方案是：98、0、1、1（3:1）。

問題又來了，在2號和3號提出的方案中，4號都能獲得1枚金幣，那麼4號會選擇誰的方案呢？由於只考慮邏輯，所以就將4號的選擇設為隨機（50%），可以得出——

如果2號想要保證絕對能夠活命，最保險的方案應該是：97、0、2、1（3:1）。

最後是全部存活的情況，1號只需得到兩個海盜的支持即可通過方案。

——2號成本太高，直接放棄其利益即可；

——3號此時的想法截然不同，因為1如果死了，他將必然得不到利益，於是1號只需分給3號1枚以上的金幣，3號將必然同意方案；

——4號則複雜一些，他在2號的方案中能得到1~2枚金幣，所以1號若想要保證4號的支持，則需要在4號身上投資2~3枚金幣；

——最後是5號，在2號的方案中他能獲得1枚金幣，所以1號必須在他身上投資1~2枚金幣，5號成本比4號低，所以1號可以放棄4號選5號。於是得出如下結論：

1號利益最大化的方案：98、0、1、0、1（3:2）；這個方案50%會死亡。

1號最保險的方案：97、0、1、0、2（3:2）；該方案保證活命。

拓展到m枚金幣n個海盜分配的情形。

如果問題描述多上這些假設：1.海盜優先保自己的命 2.儘可能讓自己金幣最多 3.在有可能得到金幣2枚或0枚與一定得到1枚對比，海盜更加保險，會贊同保守方法1枚的分配方法。 4.利益相同方法下選擇儘可能殺人的方法。以上4點優先度為1最優2其次然後3最後4。

那麼題目就很簡單了。

...

以上就是剩下1，2，3...人的時候，他們的最優分配方案，並且一定會通過。

(同一行有下滑線的說明這些人其中有1人會得到2枚金幣，其他人0枚金幣)。

思路就是數學歸納法的思路，n個人的分配方案基於n-1個人的分配方案，證明過程很簡單，按照上圖情形進行嚴格的數學歸納法即可。最後最優分配方案如下：

當n&<=2m時，

提出方案的人為1號，則每隔一人(除了最後一人)給其一枚金幣即可。也就是奇數標號的給1

枚金幣。並且

n偶數時，再給最後1個人1枚金幣。

n奇數時，偶數標號(除去最接近自己的那人)+最後1人中選擇自己看上去最順眼的一個給其2枚

金幣，其他人0枚金幣。

當然其中一種最傻瓜式的最優分配方案就是，從1號開始每間隔一人(所有奇數標號不包括自己)發一枚金幣，然後再給最後1人再發一枚金幣即可。

當n&>2m時，

令f(k)=2^k，即2的冪次方。

n=2m+f(1)-1=2m+1時，標號為2的人一個金幣(2號分配時只能得0枚，所以一定贊成)，然後從1號開始隔號給金幣(最後一個人沒有)。此為最優方案。

n=2m+2時，1號無法存活。

n=f(0)=2m+f(2)-1=2m+3時，2號由於怕死，即使給0個金幣，仍然會贊同。所以，(
3; 從6開始包括6之後的標號為偶數的；還有最後一個人)一共m+1個人，隨意選m個人每人給1個金幣即可。此為最優方案

當n=2m+f(k)-1 ,k&>=3時，從1至f(k-1)標號均怕死，即使給0個金幣，仍會贊同。
然後再從後面的人中任意選擇m個人，每人都給1個金幣。此為最優方案。

其餘的n&>2m的情形，1號都無法存活，然後降為n-1的情形不斷遞歸求解。

證明：t個人後面湊齊k個人能夠0個金幣贊同超過半數，求k值。

2(K+m)&>=k+t+1 得可取 k=t-2m+1

然後就是數學歸納法，得到t,
t+k, t+k+2k, t+k+2k +4k ,…

初始t可取2m+1，所以，k=2，然後1也可以看成2^0，所以有：

取t=2m，有 2^0 +t-1，2^1+t-1, 2^2 + t-1，…2^p+t-1

當n取以上序列時，1號湊夠了跟他一起保命的人，一起存活。

總結：

n&<=2m以及n=2^p+2m-1 (p&>=0)時，1號可以存活，並有最優分配方案，其它情形1號無法存活，詳細的所有僅有的最優方案上文已經進行說明。

最後再想如果題目改成投票大於等於半數也行的情形。

分析了一下，分析思路跟原來的一模一樣。而且發現，等於半數也行，此時的題目求解與原問題相比較簡化了許多，不論是最終結論還是所有僅有的最優存活方案都大大簡化了，很容易求解。

結論：

當n&<=2m+1時，從1開始的所有奇數標號的人每人給1個金幣即可，此為最優分配方案。

當n=2m+2時，從3開始的所有奇數標號外加2號一共m+1個人，任意取m個人每人給1個金幣即可。此為最優分配方案。

當n&>=2m+3時，

當n=2m+2^p (p&>=2)時，有存活方案，此時從1到2^(p-1)標號的人都只能得到0枚金幣並且為了存活會選擇贊同，然後，其它的人中任意取m個人每人給1個金幣即可。此為最優分配方案。

其它情形，1號海盜沒有存活方案，降為n=n-1情形繼續分析。

總結：

n&<=2m以及n=2m+2^p (p&>=0)時，1號可以存活，並有最優分配方案，詳細方案上文已經進行說明。

@林宇鵬借鑒鵬兄的規則：

半數及以上通過分配方案（殺不死人的分配方案）：

規則：

1.海盜優先保自己的命；

2.儘可能讓自己金幣最多；

3.利益相同方法下選擇儘可能殺人的方法；

（優先順序依次遞減）

抽籤確定各人的分配順序號碼（5，4，3，2，1 ），由大到小依次提出分配方案（改一下順序便於圖表表示）

總人數為n，總金幣為m：

超過半數通過分配方案（殺死人的分配方案）：

規則：

1.海盜優先保自己的命；

2.儘可能讓自己金幣最多；

3.利益相同方法下選擇儘可能殺人的方法。

（優先順序依次遞減）

1.抽籤確定各人的分配順序號碼（5，4，3，2，1 ），由大到小依次提出分配方案（改一下順序便於圖表表示）；

2.優先照顧照顧後分配者；

（求余，向上取整）

沒有人覺得題設不合理嗎。5個聰明絕頂的海盜會同意這個"公平"的分金幣的方法，然後讓第一個人佔盡便宜？

偶然刷到這個問題，看了一下各位的答案，都忽略了一個分配原則：

提出方案者是具有表決權的。

這個題，原題是得到半數同意就不會死吧？不是超過半數。

不過分析模式是沒變的，但是原題要更有意思些。

5個海盜分配100個金幣還是相當容易計算的，正如前面鄺石所答的那樣，1號海盜的最優方案肯定是 96，0，0，2，2，而且會通過。

P.S，如果你夠狠，98，0，0，1，1 也可以，有可能通過（不保證，4,5反正都是1個金幣，看4，5的心情和平時關係如何了）。

由此問題拓展出來的，500個海盜分100個金幣（金幣是完整無法分割的），這個就相當有難度了，詳情參見：海盜分金幣_100金幣應該如何分配5個海盜/500個海盜？

論證過程較複雜，這裡只引用結論：

當500名海盜運用最優策略來瓜分金子時，頭44名海盜必死無疑，而456號海盜則給從1到199號中所有奇數編號的海盜每人分1塊金子，問題就解決了。

由於這些海盜所實行的那種民主制度，如果是按強弱來決定排位，他們的事情就搞成了最厲害的一批海盜多半都是下海餵魚，不過有時他們也會覺得自己很幸運——雖然分不到搶來的金子，但總可以免於一死。只有最怯懦的200名海盜有可能分得一份臟物，而他們之中又只有一半的人能真正得到一塊金子，生存法則的確是怯懦者繼承財富。