作者badpriest (不良神父)
看板Inference
標題Re: [問題] 關於一題海盜搶錢的題目
時間Wed Mar 7 02:57:14 2012
※ 引述《craig100 (不要問,很‧恐‧怖)》之銘言：
: 先說 是在某個奧林匹亞測試題上看到的
: 題目內容大約如下:
: 有五個海盜 撿到了100金
: 他們決定 要用抽籤的方式來分錢
: 籤筒的籤有五支(上面寫1.2.3.4.5) 五個人一次就抽完
: 而，分錢的方法是:
: 由1號提出一個提案 只要"半數或半數以上"的人說ok 那就按照1的提案分錢
: 反之 把1推到海中 換考慮2號提議
: 依此類推
: 假設五個海盜都是非常會精打細算的
: 那麼 請問 1號該如何分 才可得到最多錢且不會死??
既然都很會精打細算,就從反方向來推看看
如果123都被推下海,只剩下45,那金幣一定會變成(100,0)
因為通過半數就ok,這樣5號一定不願意4號分配
(4號說OK,5號說no也沒用)
那如果剩下345號,反正4號一定會反對,且如讓4號決定5號會沒有錢拿
所以錢的分配就會是(99,0,1)
這樣5號最少有1個金幣,對5號來說比4號做決定的好,可得到半數以上(3號5號)OK的決定
如果剩下2345號,往上看的話,會知道3跟5是同一立場的
所以2不用想收買3號跟5號,給的金額就是(99,0,1,0)
這樣4號還有1枚金幣,比讓3號決定還好
所以...當有12345號的時候
2號4號不會希望1號決定
而3號5號不會想讓2號4號決定(一定沒金幣)
所以1號只要收買3號5號就好
(98,0,1,0,1)
這樣應該就是金幣拿最多,且保證一定不會死的方式
有錯請指教
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.102.16
1F：→ hirabbitt:跟上面的有什麼不一樣= =? 03/08 00:58
2F：推 up1205:很有深度 03/08 10:31
3F：→ AGM304:跟前幾篇比....深在哪? 03/08 11:35
4F：推 kailoven:如果真的夠精打細算...(98.0.1.0.1)八成會下水吧 03/08 16:40
5F：→ kailoven:如果我是5號給我一元 我就先讓他下去.... 03/08 16:40
6F：推 hs00:推樓上 無論是1或3號做決定 5號都只拿到1塊 也就是可以威脅 03/09 18:39
7F：→ hs00:1號必須給更多 否則就直接讓他死 03/09 18:39
8F：推 TERRY1213:(98,0,1,0,1) 不會下水阿 1號下水後 2號是(0,99,0,1,0) 03/13 02:40
9F：→ TERRY1213:3號5號根本拿不到錢 所以3號跟5號一定會投98,0,1,0,1 03/13 02:41
10F：推 DarkVampires:有被推下海vs沒被堆下海而沒得分錢，其考量有差嗎？ 11/15 14:04
11F：推 ETCSCAAC: 我記得沒錯的話 這題的前提是 要先活著 然後盡量多拿錢 11/26 11:59
12F：→ ETCSCAAC: 再盡量多殺人 所以這樣分的話1號會下水 因為對五號來 11/26 11:59
13F：→ ETCSCAAC: 說讓二號分可以拿一樣多錢 而且還能多殺一個一號 正確 11/26 11:59
14F：→ ETCSCAAC: 答案應該是(97,0,1,0,2) 11/26 11:59