作者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