2006年04月03日

【回答269】海賊と金貨

問題編は一息ついたときの小ネタ【問題269】を参照ください。

この問題の元ネタはマーティン・ガードナーではないか、ということを問題編のところで言ってましたが、もう少し詳しい書籍があって、それによると、イリノイ大学のスティーブン・ランズバーグという人が考案した、ということのようです。(その問題では海賊は10人でした)
そして更にそこから応用編の問題などが作られたりしていて、これがまた面白いです。ということで、今日の問題編の方はこの応用編の問題にしようかと考えています。


【回答269】
これは帰納法で解いていきます。まずは二人の場合にどうなるかを見てみます。二人の場合、親分は自分が100枚の金貨をとる、と提案するのが論理的です。この提案に下っぱが反対したところで、自分が賛成して多数決で半数をとれるからです。

次に三人の場合だとどうでしょう。二人の場合だと、一番の下っぱは何ももらえないことがわかっています。ということは、一番の下っぱにとっての最優先戦略は、親分の提案が通ることということになります。(親分の提案が通らなかったらその親分は殺され、あとは二人になってしまう=何ももらえない、からです)

論理的な親分は下っぱがそう考えることを予想します。そこで、この一番の下っぱに最低限の金貨さえ与えれば賛成してくれるだろう、と考えます。一方、この下っぱさえ賛成してくれれば多数決で勝つので、No2には何も与える必要はありません。

ということで、この場合の親分は自分が99枚、No2には0枚、一番の下っぱに1枚という提案をして、自分と一番下っぱの賛成を得ます。

四人のときも同じように考えます。考えやすいように、一番下っぱから親分までそれぞれn1、n2、n3、n4とおきます。(親分はn4です)n4は少なくとも自分ともう一人、計2名の賛成を得る必要があります。
ところで、このときのn2の戦略はn4の提案が通ることです(先ほどと同じ考え方です)。また、n1、n3にとってはn4の提案が通らない(=n4を殺して三人にする)方が得です。

ということで、n4はn2だけ、最低限の金額で買収します。提案はn4が99枚、n3が0枚、n2が1枚、n1が0枚です。

やっと五人のケースにきました。今度も下っぱからn1、n2、n3、n4、n5とおきます。五人なので、n5は今度は二人から賛成を得る必要があります。親分が殺されて4人になったときに何ももらえないのは、上のケースからn1とn3の二人です。言い換えると、n1とn3はn5の提案が通ることが最優先戦略となります。
なので、n5である親分は分配案を、こう提案します。

自分が98枚をとる。No2には0枚、No3には1枚、No4には0枚、No5には1枚を渡す。

これにNo3とNo5が賛成をしてめでたく分配されるのでした。


友達にすすめる




posted by fakerholic at 22:09| Comment(9) | TrackBack(1) | 頭の体操クイズネタ回答集 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
0枚では山分けとは言わないと思います。
Posted by 英心 at 2007年12月10日 01:11
その回答は”賛成しても反対しても同じ数の金貨しか得られないときはなるべく人死にを出さないような選択をする”という前提が必要です。
この問題への正に論理的な回答は”条件の不足により回答不可能”です
Posted by at 2011年01月20日 04:33
随分遅レスになっちゃいますが、回答内に"同じ金貨しか得られないとき"、という場面がないのでその批判は的を射ていませんよ。
条件は充分足りています。
Posted by at 2011年04月27日 15:09
この人数とルール下では毎回取り分が無いと悟ったNo.2とNo.4は以後海賊団を抜ける。No.1、No.3(Aとする)、No.5(Bとする)の3人が残った場合、次回の山分けではAは取り分が無くなるので、これによりAが抜ける。同様に次はBの取り分が無くなり、Bは抜ける。海賊団の維持と今後の継続的な収益を考えると、親分が短期的な利益を追求して行動するのは得策ではない。海賊団や戦闘での貢献度等によって配分すべき。
Posted by at 2012年03月14日 08:52
>自分が98枚をとる。No2には0枚、No3には1枚、No4には0枚、No5には1枚を渡す。

これは、以下のように書くべきところの誤記ですよね。
「自分(No5)が98枚をとる。No1には1枚、No2には0枚、No3には1枚、No4には0枚を渡す。」

Posted by 通りすがり at 2012年08月12日 08:57
グリーングリーン!!きゃほきゃほわはははは。CMの長●大好きなんだけど!!
Posted by 出会いはグリーにおまかせ!! at 2012年09月16日 04:11
一枚の金貨の価値が相当あれば納得ですが、
1枚で下が納得するか分からないので。

私の案に賛成する人は挙手をしてください。
いっせーので挙手を初めて、私以外に早い順に挙手をした2名と私で金貨を山分けしましょう。

親分のぞいた4名の共謀もできず、みな強欲なので4名中2票は確実に取れるとおもいます。

それで案は過半数を超えて可決。

配分は山分けという曖昧な表記から1/3づつしても良いでしょうし、案が可決されてから、適当に2人には数枚づつ渡しても山分けという定義は外れないとおもいます、。
Posted by at 2015年11月19日 00:39
この問題で、「提案が否決されたときボスが殺される」という条件は、まったく不要ですよね。
「1枚は0枚よりまし」が最優先されている考え方の解答方針を認めているから。
けれども、それは問題文には明確には記されておらず、ただ「…貪欲に…」という文言から「1枚は0枚よりまし」を導き出しているにすぎないのです。「…貪欲…」に「他の捉え方があるとは考えないとするのが論理パズルだ」と決めつけているのです。
まあ、論理パズルはそのような面があるのは容認できるのですが、わたしはやはり「…貪欲…」という語句で問題文を書くのは、誤解を招きやすいので、不備だと言われても仕方ないかなと思います。めんどくさくても、問題文は他に捉えようのない文言にすべきだと思いました。

例えば、
最下位の2人は絶対に殺されないことになります。
それを考慮すれば、最下位の者は本来賛成するところで反対でもしておけば、「2番目の下位の者がボスになったとき、もしかしたら恩義を感じてくれて2枚くれるかもしれない」と考え、最初のボスの提案に反対するという暴挙に出るかもしれない。それを期待するのも「…貪欲…」と言えます。しかし「このような「貪欲」は論理的じゃない」と片付けられ、排除されます。(私自身もそれを排除しました。)
でも、このようなイチャモンを付けられることのない問題文を書くべきである、ということが言いたいことであり、めんどくさいけど書けると思います。
Posted by よい子 at 2015年12月06日 14:03
n4(親分),n3,n2,n1のとき、
n4が99枚、n2に1枚が最適解になる理由が解りません 

n4が99枚、n1が1枚の山分けの場合でも、
n1から賛成を得られる筈です。
(n1がここで反対しても、次の親分(n3)から
与えられる金貨は同じく1枚だけになるので、
敢えてここでn4の提案を反対する理由がありません。)

なので、そもそもの問題である、n5の解は、
n5に98枚、n3〜n1のうち2人に1枚ずつ。
だと思います。
Posted by なみろう at 2016年05月11日 01:18
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:


この記事へのトラックバック

海賊の分配パズル(思いつきメモ)
Excerpt: 私は『ビル・ゲイツの面接試験―富士山をどう動かしますか?』で初めて知ったのですが、二番目のURLによるとオリジナルはイリノイ大学のスティーブン・ランズバーグという人だそうです。 【問題269】海賊と..
Weblog: しいたげられたしいたけ
Tracked: 2008-08-30 02:24
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。