作者puzzlez (渴望一份好工作)
看板puzzle
標題Re: [問題] 海盜分錢問題
時間Tue Jul 7 18:53:25 2009
※ 引述《TaksNo7 (去死團南部不分區會長)》之銘言：
: 有五個海盜要分100枚金幣
: 依序由第一個海盜提出分配方法
: 接著由剩下四位海盜表決 如果超過一半(包含一半)的人否決
: 那麼提出分配者就會被丟下海 然後由第二個海盜提出分配 剩下的人表決
: 以此類推
: 假設每位海盜都是絕頂聰明
: 而且為了自己最大利益著想
: 但會優先保命的情況下
: 則最後金幣的分配狀況會如何??
如果不細想這個問題的話
直覺會以為提出分配的人
一定要多分一點錢給表決的人
用高額買票的方式獲得支持
可是經過細想之後的答案分配卻很極端
是此題最耐人尋味之處
海盜分幣問題有很多版本
有的海盜有十人
有的只要獲得一半支持就算通過
不過大多數題目，提案者也可以參與表決
但此題卻禁止
原本以為這樣一來問題的解法會有很大的不同
但其實也沒有，只要用原來的解法就行了
也就是說
只要會算其中一題
那麼其他的再怎麼變也都會算了
解這題的最大秘訣在反推
假設現在只有ＣＤＥ三人
此時Ｅ就擁有極大的優勢
這是因為他自己的一票就佔了５０％
只要他一路否決到底
則所有金幣就歸他了
所以ＣＤ一定會支持Ａ或Ｂ
以避免人數剩下三人
因此假設現在有ＢＣＤＥ四人
Ｂ就可以拿喬了
他知道ＣＤ非支持他不可
否則性命堪慮
所以不用花金幣就可以買通了（感謝板友stimim的提醒）
其分配方法如下：
１００ ０ ０ ０
提案 贊 贊 否
Ｂ Ｃ Ｄ Ｅ
ＣＤ一定會支持，因為能保住命最重要
這時就可以回過頭來看題目了
題目裡有ＡＢＣＤＥ等五人
首先Ｂ是不可能支持Ａ的
因為上一個方案明顯對自己有利
所以Ａ必須要獲得ＣＤＥ三人的支持
Ａ得提供Ｂ給ＣＤ更大的優惠
ＣＤ才有支持Ａ的理由
於是Ａ起碼要分別給ＣＤ１枚金幣（還真小氣）
至於Ｅ也只需給１枚就行了
因為之後的Ｂ，是不可能分金幣給他的
Ｅ拿到１枚總比沒拿到好
於是Ａ的金幣分配可以是：
９７ ０ １ １ １
提案 否 贊 贊 贊
Ａ Ｂ Ｃ Ｄ Ｅ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.194.242.55
1F：推 stimim:在B那個地方，不是100 0 0 0 就好了嗎？ 07/07 18:58
2F：→ stimim:CD會以保命為優先，還是要投給他 07/07 18:58
3F：→ puzzlez:咦 好像有道理耶 噗哈 07/07 19:00
4F：推 northkk:錯了....若只剩4人, C 不管怎樣都不會支持B... 07/07 20:30
5F：→ northkk:只要 B 一掛, C 不管怎麼分, D 都會支持他,三票中得兩票 07/07 20:31
6F：→ puzzlez:為什麼呢？當只剩CDE三人時 E一定會否決掉C的呀..... 07/07 20:32
7F：→ puzzlez:你忽略掉 提案者不能投票的限制了..... 07/07 20:32
8F：→ northkk:反之, 因為只要輪到 C , E 就沒輒.... 07/07 20:32
9F：→ northkk:所以 B一定要給 E 一塊錢, 而 D 的部分則是比較詭異... 07/07 20:33
10F：→ northkk:理論上也要給 D 一塊錢, 就變成了98 0 1 1 07/07 20:34
11F：→ northkk:哦....提案者不能投票喔....我沒注意到... 07/07 20:35
12F：→ puzzlez:對呀 我一開始也沒注意到 是有人問我才驚覺到的...... 07/07 20:37
13F：推 northkk:那我可不可以這樣說.... 07/07 20:42
14F：→ northkk:如果最後只剩下 E, 然後他提出了一個方案(規定要提的) 07/07 20:43
15F：→ northkk:結果投票, 因為沒人有投票權, 總票數是0 07/07 20:43
16F：→ northkk:而否絕票也是0, 0/2 = 0, 否絕票達到總票數的一半 07/07 20:44
17F：→ northkk:於是 E 把它自己丟到海裏去..?? 07/07 20:44
18F：→ northkk:cow....是誰會覺得用這種方式分金幣的海盜理性啊?? 07/07 20:45
19F：推 maxine7:好清楚易懂的解答，推~ 07/07 21:02
20F：→ puzzlez:哈 北叔說的也頗有道理的耶...題目可能要再補一條...... 07/07 21:38
21F：→ puzzlez:此題還要附註一條：每人都希望別的海盜下海，在不違利益下 07/07 22:58
22F：→ puzzlez:否則DE兩人時 D可為求保命分配 0(D)、100(E)如果E不狠的話 07/07 22:58
23F：→ puzzlez:答案就會不那麼明確了 到底E會不會放過D? 所以要設此條件 07/07 22:59
※ 編輯: puzzlez 來自: 123.194.242.55 (07/08 06:52)
24F：→ rofellosx:這是建立在每人都分的到金幣的合理? 07/08 09:44
25F：→ rofellosx:如果有人想辦法把其他人都踢下海不當提案者呢? 07/08 09:44
26F：→ puzzlez:題目已經說了 以保命及得到最大利益為前提 07/08 09:46
27F：→ puzzlez:「有人想辦法把其他人都踢下海不當提案者呢」->誰辦得到呢 07/08 09:47
28F：→ puzzlez:意思是使用蠻力嗎？XDDD 這已不在推理問題的範圍之內.... 07/08 09:47
29F：推 xak:剩DE....D從E背後給他一刀....D就沒人投票就贏了 07/08 10:03
30F：→ puzzlez:那還不如一開始五人開打還比較快說^^" 07/08 10:11
31F：推 xak:這樣D要打贏四個才能賺100...不如殺一個就好了.... 07/08 11:47
32F：推 xuexiaomi:這個題目大大說的沒錯，其實不要執著於贊成跟否定這個詞 07/30 01:51
33F：→ xuexiaomi:解決方法就是用少數決的解決方法 07/30 01:52
34F：→ xuexiaomi:有看LiarGame並解有研究過的應該會解 07/30 01:52