Re: [問題] 五個海盜分寶石
※ 引述《kamcindy (kamcindy)》之銘言：
: 5個海盜搶到了100顆寶石，每一顆都一樣的大小和價值連城。他們決定這麼分：
: 1． 抽籤決定自己的號碼（1，2，3，4，5）
: 2． 首先，由1號提出分配方案，然後大家5人進行表決，當且僅當超過半數的人同意時，按照他的提案進行分配，否則將被扔入大海餵鯊魚。
: 3． 如果1號死後，再由2號提出分配方案，然後大家4人進行表決，當且僅當超過半數的人同意時，按照他的提案進行分配，否則將被扔入大海餵鯊魚。
: 4． 以次類推
: 條件： 每個海盜都是很聰明的人，都能很理智的判斷得失，從而做出選擇。
: 問題：第一個海盜提出怎樣的分配方案才能夠使自己的收益最大化？
: 如果你是聰明人，不妨在留言板裡寫上你的答案。
好像有聽過大蓋的方法，不過實際去想過，所以可能會有錯哦XD
=================================================
先從只有 (4，5) 2個人來看
4號只有提出(0個，100個)，才不會被5號殺，trivial
=================================================
再看(3，4，5) 3個人的
3號只要讓4號拿到的寶石多於0個，就可以得到4號的支持
所以3號可提出(99個，1個，0個)
=================================================
再看(2，3，4，5) 4個人的
2號需要再兩個人的支持
由於3號拿最多，所以不需要他的支持了，只要他的寶石
所以分給4，5號比原本多一個寶石，就會得到他們的支持了
(97個，0個，2個，1個)
=================================================
最後看(1，2，3，4，5) 5個人的
此時，1號需要再兩個人的支持，所以可以拿走剩下兩個寶石多的人的寶石
當然只好抽走2號和4號的寶石囉，然後分給3號和5號多一個
(97個，0個，1個，0個，2個)
=================================================
我不確定有沒有錯哦
剛剛才想的@@
大致上的方法，應該就是當共有n個人的時後
先看需要幾個人的支持，假設需要x人
考慮n-1時的情況
把前n-1-x多寶石的人寶石全抽走，然後需要他們支持的人各多一個寶石
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.35.24.190
討論串 (同標題文章)
Inference 近期熱門文章
3
13
PTT遊戲區 即時熱門文章
68
140