会社に行ったらなんかふらふらするので朝一で病院に行ったら、扁桃腺が脹れてるようで、熱が出てました。それで昼には家に帰って寝てたらちょっとはよくなったんですが、明日も休みそうです。ところで病院ってなんであんなに待たせるんでしょう。（熱があるっていうのに！）
この問題は、【問題２６９】海賊と金貨の応用問題です。今日あの問題の回答をＵＰしましたが、初めてご覧になる、という方は少なからず回答に驚いたんではないかと思います。多数決は平等、というのは幻想です。
この問題の元ネタはスティーブン・Ｍ・オモハンドロという方です。更に奇妙な回答が待っています。
【問題２９４－１】
２０１人の海賊が戦利品の金貨１００枚を山分けすることになりました。この海賊たちには親分から下っぱまで身分の違いがあって、山分けにあたって次のようなルールがあります。
まず親分が２０１人それぞれの取り分を提案します。全員の多数決で少なくとも半数以上の賛成があればその提案のとおりに山分けがされますが、賛成が半数に満たなければ、その提案者（親分）はその場で殺されて同じことのやり直しとなります。（親分が殺された場合は次はＮｏ．２が提案をすることになります）
こうして山分けの案がまとまるまでこのルールは繰り返されます。さて親分であるあなたはどのような山分け案を提案したらよいでしょうか。
もちろん、海賊同士は相談や共謀をすることはできませんし、皆、論理的かつ貪欲で誰も死にたくないと思っています。
【問題２９４－２】
上の問題で海賊が２０８人の場合、海賊の親分はどのような分配案を提示すべきでしょうか。
問題２９４－１の方は問題２９４－２を考えるにあたってのヒントのような問題になってます。元々の考え方の方は問題２６９の回答編をご覧ください。ちなみにオモハンドロは５００人の海賊という問題にしています。
１００枚しかないものをそれ以上の人数で分けるなんてそもそも不条理・・・と思ってしまいますが、論理は面白いです。
友達にすすめる
2006年04月03日
この記事へのトラックバック
海賊の分配パズル（思いつきメモ）
Excerpt: 私は『ビル・ゲイツの面接試験―富士山をどう動かしますか?』で初めて知ったのですが、二番目のURLによるとオリジナルはイリノイ大学のスティーブン・ランズバーグという人だそうです。 【問題２６９】海賊と..
Weblog: しいたげられたしいたけ
Tracked: 2008-08-30 02:24
親分が死にたくなかったらウエから順に010101010………っていけば親分0でも多数決では死ななそうです(次に沢山の金貨があれば親分は貰えます)がこれより人数が多い(金貨が少ない)時は無理っぽいのでやはりウエから順に101010101…と配れば良いと思います。
人数増えた次の問いでも同じです。
熱でた時にはポカリは必須ですよ！
おいら一度体温計で計れない手前まで熱でて死ぬところでした。
お大事にo(_ _*)o
で、２０８人の場合も同じで。
０か死か・・・何か変だな？
下位から0,1,0,1・・・と金貨を分配。
208人の場合は、自分に8枚だけ残して
下位から↑と同じように92枚だけ配布。
身分が上位の順に００１０１・・・０１０１と、親分も０枚になるように配分する。
②２０８人の時
番号が高い程、身分が上位になるように番号をつけて、２０８番(親分)に1枚、２０７、２０５、２０３、２０１番には０枚にして、残りの金貨９９枚を残った人達(２０６、２０４、２０２番、２００～１番)に１枚ずつ適当に配る。
③５００人の時
②と同様にして、５００番(親分)に１枚配る。４９９～２０１番の人達の中で番号が奇数の人達には(４９９、４９７、４９５、・・・２０３、２０１番)には０枚、残った人達に９９枚を1枚ずつ適当に配分。
てな感じでどうですかね？
金貨100枚で100人の賛成票を獲得できるので自分の取り分を0にすれば自分を含め賛成101票で202人までなら提案成立可能です。
203人になると102票が必要となり取り分0でも賛成する人が自分以外に1人以上必要です。つまりどんな提案でも102票獲得の可能性は低く確実に助かる方法はない。
204人の場合、No2の人は絶対親分になりたくないため取り分0でも賛成に回り、結果102票で提案成立。
205人の場合、No2No3は賛成するとは限らず確実な方法はない。
206人の場合、No2が賛成しても102票で確実に103票は取れず。
207人の場合、No2No3は賛成するが103票で過半数に及ばない。
208人の場合、No2No3No4が親が回ってこないように賛成するので104票獲得。提案成立。
つまりNo2No3No4には0枚であとは1枚ずつ100人に配分でOK。208人というのが微妙にポイントなので｢へぇー｣です。
私、【問題２６９】で「親分に有利なルール」といった内容をコメントしましたが浅はかでした。