googleの面接での問題が興味深かったから解いてみたらヒントと違う答えになった

08 10月 2011 @ 3:54 AM

5人の海賊がいて、彼らは1位から5位にまでランク分けされています。
1位の海賊は100枚の金貨をどのように分けるかというプランを提案する権利があります。
残りの海賊はこのプランに投票する権利があり、賛成が半分に満たない場合には1位の海賊は殺されます。
1位の海賊の分け前を最大にしてなおかつ彼が生き残るにはどうすればいいですか？
（ヒント：一人の海賊は結局、金貨の98％で終わる）

これが問題。
で、色々考えてみて、上位の海賊が死んだ場合どうなるかを考えていったら解けた。

まず、1位から3位が死んで、4位と5位の海賊だけになった場合。
投票権は5位の海賊だけしか持たないため、4位の海賊は5位に100枚全部渡すしか生き残るすべはない。
従って、4位の海賊の提案は以下の通り。

4位 0
5位 100

ただし、それでも反対される可能性さえある。
5位の海賊は4位の海賊が死んでも100枚もらえるから。
従って、何が何でも4位の海賊は3位の海賊は生かしておかねばならない。
つまり、4位の海賊は3位の提案がどんなものであっても飲まねばならない。

3位から5位の海賊になった場合。
上記のため、4位の海賊は無条件に3位の提案に賛成する。
従って、3位の提案は以下の通りになる。

3位 100
4位 0
5位 0

2位から5位の海賊になった場合。
3位の海賊は自分がトップになれば100枚が確約されるので、少なくとも100枚もらえなければ反対する。
そして100枚もらったとしても反対する可能性がある。
4位, 5位の海賊はそうなれば0枚となることがわかっている。
必要な賛成者数は二人であるため、2位の提案は以下の通りになる。

2位 98
3位 0
4位 1
5位 1

4位と5位は0でも賛成する可能性はあるが、それでは3位がトップになった場合でも取り分は変わらないため、反対する可能性もあるため、1枚渡しておく必要がある。

そして、1位から5位まで全員生き残っている場合。
半数の票を取るためには二人の賛成をとる必要がある。
2位は自分がトップになれば98枚もらえるので、少なくとも98枚わたさなければこちらにつかない。
3位は、2位がトップになれば一枚ももらえないので、1枚もらえばこちらにつく。
4位、5位は1枚渡せばこちらにつく可能性があるが、トップが2位でも1枚はもらえるため、確実にするためには2枚渡さなければならない。
従って、1位が提案するプランは以下の二通りの可能性がある。