Re: 海盜分鑽石的問題

看板Inference (推理遊戲)作者igod (igod)時間19年前 (2005/11/04 10:47)推噓4(4推 0噓 1→)

留言5則, 4人參與討論串6/7 (看更多)

※ 引述《OoNIJAoO ()》之銘言： : 有5個海盜 100顆鑽石 : 他們提出了一個方法來分這些鑽石: : 5個人依序提出分配最時的方法,如果過半,就OK : 沒有過半,(包括平手)那提議的人就要被丟到海裡餵鯊魚 : 請問: : 那第一個海盜如何提案才能不被丟到海裡,又能分到最多的鑽石底下的問題更複雜了,因為有500個海盜,100塊金子抱歉不知原文作者何人海盜的難題數學的邏輯有時會導致看來十分怪異的結論。一般的規則是，如果邏輯推理沒有漏洞，那麼結論就必定站得住腳，即使它與你的直覺矛盾。１９９８年９月，加利福尼亞州帕洛阿爾托的Ｓｔｅｐｈｅｎ　Ｍ．　Ｏｍｏｈｕｎｄｒｏ寄給我一道難題，它恰好就屬於這一類。這難題已經流傳了至少十年，但是Ｏｍｏｈｕｎｄｒｏ對它作了改動，使它的邏輯問題變得分外複雜了。　先來看看此難題原先的形狀。１０名海盜搶得了窖藏的１００塊金子，並打算瓜分這些戰利品。這是一些講民主的海盜（當然是他們自己特有的民主），他們的習慣是按下面的方式進行分配：最厲害的一名海盜提出分配方案，然後所有的海盜（包括提出方案者本人）就此方案進行表決。如果５０％或更多的海盜贊同此方案，此方案就獲得通過並據此分配戰利品。否則提出方案的海盜將被扔到海裏，然後下提名最厲害的海盜又重複上述過程。　所有的海盜都樂於看到他們的一位同夥被扔進海裏，不過，如果讓他們選擇的話，他們還是寧可得一筆現金。他們當然也不願意自己被扔到海裏。所有的海盜都是有理性的，而且知道其他的海盜也是有理性的。此外，沒有兩名海盜是同等厲害的－－這些海盜按照完全由上到下的等級排好了座次，並且每個人都清楚自己和其他所有人的等級。這些金塊不能再分，也不允許幾名海盜共有金塊，因為任何海盜都不相信他的同夥會遵守關於共用金塊的安排。這是一夥每人都只為自己打算的海盜。　最凶的一名海盜應當提出什麼樣的分配方案才能使他獲得最多的金子呢？　為方便起見，我們按照這些海盜的怯懦程度來給他們編號。最怯懦的海盜為１號海盜，次怯懦的海盜為２號海盜，如此類推。這樣最厲害的海盜就應當得到最大的編號，而方案的提出就將倒過來從上至下地進行。　分析所有這類策略遊戲的奧妙就在於應當從結尾出發倒推回去。遊戲結束時，你容易知道何種決策有利而何種決策不利。確定了這一點後，你就可以把它用到倒數第２次決策上，如此類推。如果從遊戲的開頭出發進行分析，那是走不了多遠的。其原因在於，所有的戰略決策都是要確定：”如果我這樣做，那麼下一個人會怎樣做？”因此在你以下海盜所做的決定對你來說是重要的，而在你之前的海盜所做的決定並不重要，因為你反正對這些決定也無能為力了。　記住了這一點，就可以知道我們的出發點應當是遊戲進行到只剩兩名海盜－－即１號和２號－－的時候。這時最厲害的海盜是２號，而他的最佳分配方案是一目了然的：１００塊金子全歸他一人所有，１號海盜什麼也得不到。由於他自己肯定為這個方案投贊成票，這樣就占了總數的５０％，因此方案獲得通過。　現在加上３號海盜。１號海盜知道，如果３號的方案被否決，那麼最後將只剩２個海盜，而１號將肯定一無所獲－－此外，３號也明白１號瞭解這一形勢。因此，只要３號的分配方案給１號一點甜頭使他不至於空手而歸，那麼不論３號提出什麼樣的分配方案，１號都將投贊成票。因此３號需要分出盡可能少的一點金子來賄賂１號海盜，這樣就有了下面的分配方案：３號海盜分得９９塊金子，２號海盜一無所獲，１號海盜得１塊金子。　４號海盜的策略也差不多。他需要有５０％的支援票，因此同３號一樣也需再找一人做同黨。他可以給同黨的最低賄賂是１塊金子，而他可以用這塊金子來收買２號海盜。因為如果４號被否決而３號得以通過，則２號將一文不名。因此，４號的分配方案應是：９９塊金子歸自己，３號一塊也得不到，２號得１塊金子，１號也是一塊也得不到。　５號海盜的策略稍有不同。他需要收買另兩名海盜，因此至少得用２塊金子來賄賂，才能使自己的方案得到採納。他的分配方案應該是：９８塊金子歸自己，１塊金子給３號，１塊金子給１號。　這一分析過程可以照著上述思路繼續進行下去。每個分配方案都是唯一確定的，它可以使提出該方案的海盜獲得盡可能多的金子，同時又保證該方案肯定能通過。照這一模式進行下去，１０號海盜提出的方案將是９６塊金子歸他所有，其他編號為偶數的海盜各得１塊金子，而編號為奇數的海盜則什麼也得不到。這就解決了１０名海盜的分配難題。　Ｏｍｏｈｕｎｄｒｏ的貢獻是他把這一問題擴大到有５００名海盜的情形，即５００名海盜瓜分１００塊金子。顯然，類似的規律依然成立－－至少是在一定範圍內成立。事實上，前面所述的規律直到第２００號海盜都成立。　２００號海盜的方案將是：從１到１９９號的所有奇數號的海盜都將一無所獲，而從２到１９８號的所有偶數號海盜將各得１塊金子，剩下的１塊金子歸２００號海盜自己所有。　乍看起來，這一論證方法到２００號之後將不再適用了，因為２０１號拿不出更多的金子來收買其他海盜。但是即使分不到金子，２０１號至少還希望自己不會被扔進海裏，因此他可以這樣分配：給１到１９９號的所有奇數號海盜每人１塊金子，自己一塊也不要。　２０２號海盜同樣別無選擇，只能一塊金子都不要了－－他必須把這１００塊金子全部用來收買１００名海盜，而且這１００名海盜還必須是那些按照２０１號方案將一無所獲的人。由於這樣的海盜有１０１名，因此２０２號的方案將不再是唯一的－－賄賂方案有１０１種。　２０３號海盜必須獲得１０２張贊成票，但他顯然沒有足夠的金子去收買１０１名同夥。因此，無論提出什麼樣的分配方案，他都註定會被扔到海裏去喂魚。不過，儘管２０３號命中註定死路一條，但並不是說他在遊戲進程中不起任何作用。相反，２０４號現在知道，２０３號為了能保住性命，就必須避免由他自己來提出分配方案這麼一種局面，所以無論２０４號海盜提出什麼樣的方案，２０３號都一定會投贊成票。這樣２０４號海盜總算僥倖揀到一條命：他可以得到他自己的１票、２０３號的１票、以及另外１００名收買的海盜的贊成票，剛好達到保命所需的５０％。獲得金子的海盜，必屬於根據２０２號方案肯定將一無所獲的那１０１名海盜之列。　２０５號海盜的命運又如何呢？他可沒有這樣走運了。他不能指望２０３號和２０４號支持他的方案，因為如果他們投票反對２０５號方案，就可以幸災樂禍地看到２０５號被扔到海裏去喂魚，而他們自己的性命卻仍然能夠保全。這樣，無論２０５號海盜提出什麼方案都必死無疑。２０６號海盜也是如此－－他肯定可以得到２０５號的支持，但這不足以救他一命。類似地，２０７號海盜需要１０４張贊成票－－除了他收買的１００張贊成票以及他自己的１張贊成票之外，他還需３張贊成票才能免於一死。他可以獲得２０５號和２０６號的支援，但還差一張票卻是無論如何也弄不到了，因此２０７號海盜的命運也是下海喂魚。　２０８號又時來運轉了。他需要１０４張贊成票，而２０５、２０６、２０７號都會支援他，加上他自己一票及收買的１００票，他得以過關保命。獲得他賄賂的必屬於那些根據２０４號方案肯定將一無所獲的人（候選人包括２到２００號中所有偶數號的海盜、以及２０１、２０３、２０４號）。　現在可以看出一條新的、此後將一直有效的規律：那些方案能過關的海盜（他們的分配方案全都是把金子用來收買１００名同夥而自己一點都得不到）相隔的距離越來越遠，而在他們之間的海盜則無論提什麼樣的方案都會被扔進海裏－－因此為了保命，他們必會投票支持比他們厲害的海盜提出的任何分配方案。得以避免葬身魚腹的海盜包括２０１、２０２、２０４、２０８、２１６、２３２、２６４、３２８、４５６號，即其號碼等於２００加２的某一方冪的海盜。　現在我們來看看哪些海盜是獲得賄賂的幸運兒。分配賄賂的方法是不唯一的，其中一種方法是讓２０１號海盜把賄賂分給１到１９９號的所有奇數編號的海盜，讓２０２號分給２到２００號的所有偶數編號的海盜，然後是讓２０４號賄賂奇數編號的海盜，２０８號賄賂偶數編號的海盜，如此類推，也就是輪流賄賂奇數編號和偶數編號的海盜。　結論是：當５００名海盜運用最優策略來瓜分金子時，頭４４名海盜必死無疑，而４５６號海盜則給從１到１９９號中所有奇數編號的海盜每人分１塊金子，問題就解決了。由於這些海盜所實行的那種民主制度，他們的事情就搞成了最厲害的一批海盜多半都是下海喂魚，不過有時他們也會覺得自己很幸運－－雖然分不到搶來的金子，但總可以免於一死。只有最怯懦的２００名海盜有可能分得一份髒物，而他們之中又只有一半的人能真正得到一塊金子，的確是怯懦者繼承財富。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.170.3.77