經典益智謎題之海盜分金

05-02

《加勒比海盜5》不溫不火的上映著，作為海盜的死忠對本次的續集感覺一般沒啥亮點。觀映之餘，強迫症的腦海里又浮現出了那個經典的燒腦謎題：海盜分金（A Puzzle for Pirates）。

海盜分金謎題的加勒比海版本：

安妮女王復仇號上有500個海盜，一天他們洗劫了皇家港搶到了100枚金幣，現在海盜們準備瓜分金幣，但是分金幣必須要遵循《海盜法典》。法典規定：金幣不能分割；船上的海盜需要按照地位進行排序，地位越高的海盜編號越高；從編號最高的海盜開始提出金幣分配方案，船上的海盜（包括提出方案的那個）一起對方案進行表決，如果分配方案得到一半或以上的海盜支持，那麼方案就獲得通過，如果方案沒能得到半數支持，那麼提出該方案的海盜就將被逼迫跳海去餵魚，而後由編號第二大的海盜提出方案重複這一過程，直到某個海盜的方案獲得通過。

每個加勒比海盜首先想到的是確保自己的性命（人之常情），其次是獲得更多的金幣（海盜都是貪婪的），最後他們希望看到更多的其他海盜跳海（估計每個海盜都想獨佔安妮女王復仇號）。所有的海盜都嚴格遵循這個優先順序順序，並且他們都是完全理性的，他們也知道其他海盜是完全理性的。

現在的問題是安妮女王復仇號上會發生什麼？那些海盜能夠逃脫餵魚的命運？金幣又是怎樣分配的？

這個問題最早在文獻中出現應該是在1999年的《科學美國人》雜誌（Stewart Ian, A Puzzle for Pirates, Scientific American, 1999, pp. 98–99）。Stewart Ian對其進行了解答，原始文章可以戳A Puzzle for Pirates，題目的答案非常出人意料，想要理解清楚並不容易。在網路上這個問題也被討論了無數次，一個比較好的中文版解答可以參考Charlesgao的海盜博弈論。

這裡簡要概括一下解答的思路。正如Ian教授所說，解答這類策略謎題的關鍵在於逆向遞推，從最簡的情況出發先考察只剩兩個海盜的情況（海盜P2可以獨吞所有金幣），然後是剩三個海盜（海盜P3自己分得99枚金幣，1枚金幣用於收買P1），然後再是四個海盜、五個海盜...，從中尋找規律。推理後發現海盜應當將金幣分給別人以換取他們對方案的支持。當P201分配金幣時，他需要將所有金幣都用來收買別人，P202也是如此，而悲劇的P203的即使將所有金幣都用來收買人心也湊不夠102個贊成票，因此如果只有203個海盜分金幣的話，P203難逃一死。但是海盜P204就不同了，P204用100枚金幣收買到100個贊成票，加上自己一票，再加上P203為了保命而投的贊成票，票數剛好過半，所以204個海盜分金幣時海盜P204能存活。從這裡可以看到解答的關鍵點，某些海盜分金幣時，他們沒有足夠的金幣去收買別人，他們提出的任何方案都會被否決，所以他們生存的機會只能寄希望於編號更大的海盜的方案獲得通過，因而即使他們沒有被收買，他們有時也會贊成其他海盜的方案。

答案是海盜P500~457的方案被依次否決，他們全部跳海餵魚，P456收買了100個海盜，另外海盜P329~455為了保命了投贊成票，所以方案恰好能通過。一般的，p個海盜分g枚金幣的話，設 $q=left lfloor log_2 (p-2g) ight floor$ ，編號大於 $2g+2^q$ 的海盜會被餵魚，編號為 $2g+2^q$ 的海盜的方案能通過，分配方案不唯一，該海盜可以從 $g+frac {2^{q}-(-1)^q} {3}$ 個人中選g個人，分別用一枚金幣收買他們。

這裡我要說的是解答思路的一個小改變，以及得到的一點結果。之前的解答模式是從p-1個海盜分g枚金幣的解得出p個海盜分g枚金幣的解，現在我們試試從另一個方向突破。

我們先看看海盜分0枚金幣時會怎麼樣。對於分0枚金幣的情況，這時海盜們不用關心分配方案了，他們投票時只需專註於保命和看別人跳海。這裡逆向遞推依然適用，只剩兩個海盜時他們都能存活，剩三個海盜時由於海盜P1和P2性命無憂所以他們樂於看P3跳海，而四個海盜時P3為了自己保命他需要保住P4。歸納起來就是，對於p個海盜分0枚金幣的情況，編號小於等於 $2^{left lfloor log_2 p ight floor}$ 的海盜能存活。

現在來考慮分g枚金幣的情況，我們只關注海盜的存活情況。海盜數量小於等於2g所有海盜都能活，接著考慮2g+p個海盜分g枚金幣。在海盜P(2g+p)提出的分配方案中，他應該將g枚金幣都用來收買人心，在不影響結論的前提下假設所有被收買海盜的編號都小於等於2g，也就是說前面的2g個海盜中投贊成和反對的票的人數相等；那麼為了讓方案獲得通過，還需要後面的那p個海盜中有 $left lceil frac p 2 ight ceil$ 個人投贊成票，而且這p個海盜沒有金幣可分，影響他們決策的只有保命和看跳海，這樣就轉化為p個海盜分0枚金幣的情況了！

表述地更抽象更一般話一些：設分配方案通過需要達到的贊成率為r（0<r<1），且p個海盜分g枚金幣時所有海盜都能存活，用 $S(r,g)$ 表示滿足上麵條件的p組成的序列（集合），我們姑且把它叫做存活序列吧。原始問題中r=1/2，因此分0枚金幣的存活序列是

$S left ( frac 1 2,0 ight )= left { 2^n | n in mathbb{N}_0 ight }$

而分g枚金幣的情況是

$S left ( frac 1 2,g ight )= left { 1,2,3,...,2g-1,2g ight } cup left {2g+2^n | n in mathbb{N}_0 ight }$

稍微推廣一下：當 $0< r leq frac 1 2$ 且 $frac g r in mathbb{N}$ 時，類似地不考慮前面g/r個海盜，而在海盜P(g/r+p)提出的方案中，他將g枚金幣都用來收買人心，前面g/r個海盜中總有g個海盜能被收買（這裡需要用到條件r<=1/2），假設所有被收買海盜的編號都小於等於g/r，即前g/r個海盜的贊成率剛好是r；那麼為了讓方案獲得通過，還需要後面的那p個海盜中有 $left lceil rp ight ceil$ 個人投贊成票，同樣的這p個海盜沒有金幣可分，這樣就又轉化為p個海盜分0枚金幣的情況了，用公式表述就是

$S left ( r,g ight )= left { 1,2,3,...,frac g r ight } cup left {frac g r+x| x in S(r,0) ight }$

現在我們來求 $S left ( r,0 ight )={ x_n }$ ，這裡我們將對r的限制放寬到 $0< r < 1$ ，列出遞推式

$x_n=left{egin{matrix}1& ,n=1\ x_{n-1} + min_{y in mathbb{N}} { frac{y}{x_{n-1}+y} geq r} &,n>1end{matrix} ight.$

化簡一下得

$x_n=left{egin{matrix}1& ,n=1\ left lceil { frac{x_{n-1}}{1-r} } ight ceil &,n>1end{matrix} ight.$

特別地，當 $r=frac {j-1} j, jgeq 2$ 時 $x_n=j^{n-1}$ ；而當 $r=frac 1 k,kgeq 2$ 時

$x_n=left{egin{matrix}1& ,n=1\ left lceil { frac{kx_{n-1}}{k-1} } ight ceil &,n>1end{matrix} ight.$

這裡再提一下，當k=3和k=4時， ${ x_n }$ 分別是OEIS（The On-Line Encyclopedia of Integer Sequences在線整數數列百科全書）的A061419和A087192。

綜合起來就可以得到r=1/k時的生存序列 $S(frac 1 k,g)$ 了。

哎~當個海盜也不容易啊，當船長更要冒生命危險啊，反倒是地位最低的海盜最安全~不過我們的目標是星辰大海！

2017.6.10