5人の海賊のコイン分配問題
5人の海賊がいて、彼らは1位から5位にまでランク分けされています。1位の海賊は100枚の金貨をどのように分けるかというプランを提案する権利があります。残りの海賊はこのプランに投票する権利があり、賛成が半分に満たない場合には1位の海賊は殺されます。1位の海賊の分け前を最大にしてなおかつ彼が生き残るにはどうすればいいですか？（ヒント：一人の海賊は結局、金貨の98％で終わる）
まず大前提として、 「海賊はなるべく自分が死なないように行動する」 「(死なないならば)なるべくコインが多くなるように行動する」 と仮定しよう。 これを否定したら「死にたい…」とか「ちょっと損だけどBには以前から腹が立っていたので殺す」 なんて選択肢が出て論理パズルではなくなる。 パズルとして成立させるためにこの仮定を置いた方がいいと面接官に一応言っておく。
海賊をそれぞれA,B,C,D,Eとしよう。
１：まず、仮にEだけが生き残った場合、Eが100コインを手にする。
２：仮にDとEだけが生き残っている場合、 Dが1コインでも取ったならば、Eはその分配案に反対して100コイン取る方が得だから、 確実に反対するだろう。 Dは死にたくないので0,100の分配を提案する。 この提案でもEは「Dを殺しても殺さなくても100コインが手に入る」状況なので、 Dを殺す可能性がある。 なのでDは「DとEだけが生き残っている状態」自体を避けたい。
３：仮にCとDとEが生き残っている場合、 上記の考察よりDは「Cを殺して自分がトップになるとEに殺される可能性が出てくる」 「Cを殺してもコインは手に入らない」と考え、無条件に賛成する。 Dの賛成により「半数に満たない」条件は発動しないことが確定するので、 Cはどんな分配にしても殺されることはない。 よってCは100,0,0の分配を提案し、Dの賛成により可決される。
４：仮にBとCとDとEが生き残っている場合、上記の考察より、Cは 「Bを殺せば生きて100コインを手に入れられる」と考えるため無条件に反対する。 なのでBは生き残るためにはDとEに賛成させる必要がある。 Bが死んだ場合DとEはそれぞれ0コインしか受け取れないので、 それより多い分配を提示すれば確実に賛成する。 よってBは98,0,1,1の分配を提案し、DとEの賛成により可決される。
５：仮に全員が生き残っている場合、 B以下の4人は「Aを殺した場合に決定する98,0,1,1の分配」より多く分配されるのならば賛成し、 少なく分配されるのならば反対する。 Aは生き残るために最低2人が確実に賛成するようにしたい。 よってAが死んだ場合に0コインを受け取るCに対して1コイン、 1コインを受け取るDとEのどちらかに2コインを分配すればよい。 よってAの提案する分配は「97,0,1,2,0」もしくは「97,0,1,0,2」である。
「98%」というヒントは、 問題を訳した人が間違えたか、問題を作ったGoogleの人が間違えたか、 もしくは「ヒントと自分が考えた結果が食い違ったときに、 自分の考えを捨ててヒントにあわせた答えをひねり出すのか、 それとも自分の考えの正しさを信じてヒントが間違っていると考えるのか」 を観察するために意図的に入れられたブラフだろう。
追記、sshiさんより「「半数に満たない場合に」だから4のフェイズではDかEどちらかだけに1コインあげれば賛成2票になるんじゃ？/あ、「半数」の母数に自分がはいってないのかな。どっちなんだろ。」とのコメントが。和文問題文では「残りの海賊はこのプランに投票する権利があり」、 英文では「But the others get to vote on his plan」となっているので、自分は含まないという解釈が妥当かと思います。
しかし、仮に「自分も投票できる」という問題だとしたら、D,Eだけの時100,0、CDEの時99,0,1、BCDEの時99,0,1,0、ABCDEの時98,0,1,0,1となってあっさり98%の答えが出ます。
原文のブログは友達が受けた面接の内容をまた聞きで書いているだけのようなので、友達か著者のどちらかが題意を勘違いしたって可能性も考えられますね。
kazuhookuさんからこのページを教えてもらいました。 一息ついたときの小ネタ【回答集】: 【回答２６９】海賊と金貨。 このページの記述によればこの問題はイリノイ大学のスティーブン・ランズバーグという人が考案したものだそうな。で、その情報を元に軽く調べてみたところAmesa KZN Mathematics Journal, 2005, Vol. 9, pp. 38-40(PDF)に下のような記述がありました。(太字は僕の編集)
The following delightful puzzle was invented by Steven Landsberg (University of Illinois, Urbana-Champaign) and posed in the March 2005 Math e-Newsletter: Ten pirates have got their hands on a hoard of 100 gold pieces, and wish to divide the loot between them. They are democratic pirates, in their own way, and divide as follows. The fiercest pirate makes a proposal about the division, and everybody votes - one vote each including the proposer.はっきりと「提案した海賊も含めて全員で投票を行う」と書いてありますね。 ということで元ネタのブログの記述が間違いだったという結論でいいのではないかと思います。
