■コマネチ大学数学科105講:多数決

 ベネチア国際映画祭のコンペティション部門に出品した「アキレスと亀」が9月20日に公開される、北野武こと、マス北野の「たけしのコマ大数学科」。

問題:海賊が100人で金貨100枚を山分けするとき、もっとも冷酷非情なメンバーが金貨を最大数獲得するためには、どんな提案をすれば良いか。

《ルール》
もっとも冷酷非情なメンバーが提案し、多数決をとる。賛成が半数に満たない場合、提案者は海に投げ込まれ、次に冷酷非情なメンバーが提案して同じ手順を繰り返す。

【遊び方】海賊が100人だと大変なので、海賊が5人の場合で考え、法則を見つけよう。始めに「START」ボタンを押し、キーボードの[←][→]で移動、金貨を分配する海賊のところで[↑]を押す。海賊が金貨を持っている場合は[↓]で金貨を没収することも可能。金貨の分配が終わったら「多数決をとる」ボタンを押す。

 この「海賊と金貨」の問題は、じつは本ブログで紹介した過去記事「書籍:[非公認]Googleの入社問題」にも、掲載されている。もっとも、海賊の人数は100人ではなく、冒頭のFlashのように5人の場合だ。

[非公認]Google入社試験」の問題
引用開始/*

You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)

偉い順に5人の海賊がいます。海賊の親分は、100枚の金貨をどうやって分配するかを決める権利があります。でも、残りの海賊たちが投票して、賛成が半分より少ない場合、親分は殺されます。親分が、自分の分け前をできるだけ多くしながら、生き延びるためには、どういう分け方をすればいいでしょう?

(ヒント:誰か1人が金貨の98%をもらうことになります)

*/引用終わり

 この問題文では、親分が分配の方法を提案、「残りの海賊たちが投票して(But the others get to vote on his plan,)」とあるので、親分は投票できないように受け取られるが、出所元のサイトが間違えたのかもしれない。

Blog Tips by Tihomir – Make Money Blogging
Crazy Questions at Google Job Interview

 で、もう一度、ルールを確認しておくと、海賊は皆、強欲で、一枚でも多く金貨を貰いたい。しかし、海賊は皆、冷酷非情なので、多数決で半数に満たない提案をした者は、たとえボスであっても、海に落とされる。そして、重要なのは、海賊は皆、強欲だが論理的であること。自分がボスになりたいからとか、あいつが気に食わないとか、そういった感情では動かず、論理的な行動をとることが前提条件だ^^; もちろん、提案者も多数決に参加できる。

 コマ大数学研究会は、お台場海岸で検証開始。エライ順(?)に、ダンカン(1)、アタル(2)、北郷(3)、Dr.コバ(4)、無法松(5)の順に並ぶ。

 まず、ダンカン(1)の提案は、「金貨はすべていただく。皆、オレについてこい!」というもの。当然、他の4人は反対なので、ダンカン(1)は海に落とされる。

 次にアタル(2)の提案は、残り4人の半数を賛成を得ればよいので、「自分と北郷に金貨50枚づつを山分け」当然、アタル(2)と北郷(3)が賛成で、Dr.コバ(4)と無法松(5)が反対するが、半数に達しているので成立。しかし、これでは、1枚でも多く金貨を獲得するという海賊のルールに反する。多数決は成立したのに、海に投げ込まれるアタル。

 北郷(3)は、1枚の金貨を遠くに投げ、Dr.コバ(4)と無法松(5)が取りに行っているあいだにトンズラをはかるという、根本的なルールを無視(船の上では、逃げる場所などない)。海にではなく、波打ち際の固い砂浜に叩きつけられる。

 最後にDr.コバ(4)と無法松(5)が残るのだが、Dr.コバ(4)のは「金貨はすべて自分がもらう」と提案。2人しかいないので、Dr.コバ(4)は賛成、無法松(5)が反対しても、賛成が半数に達しているので成立。こうして、Dr.コバが100枚の金貨を手にした。

 コマ大数学研究会の答えは、「99番目の海賊が金貨100枚を得る」。戦略としては、いい人を装い、99番目に並ぶというもの。マス北野から「海賊は皆バカだということだな」とツッコミが入る。

 マス北野は、海賊が2人のときから、3人のとき、4人のとき……と増やしていき、法則を見つける。結局、100人のときは、奇数番号の海賊に金貨を1枚ずつ渡し、残りを自分がもらう(自分:金貨51枚。奇数番号の海賊:49枚)。

 東大「野望メラメラ・シスターズ」の木村美紀と岡本麻希も、最小人数から数を増やしていく方法で考える。結局、50対50で半数の賛成を得ればよいので、49人の海賊たちに金貨を1枚ずつ渡し、残りは自分が得る(自分:金貨51枚、他の49人の海賊に金貨1枚)という答え。

 なぜ、他の海賊たちは、金貨を1枚もらうだけで「賛成」するのか、そこが、この問題のポイントだ。同じように2人の場合から考えてみよう。

20080912_01

 たとえば、3人の場合、一番下っ端の海賊(右端)は、この提案に反対すると、残りは2人になり、自分は金貨を1枚ももらえない。したがって、0枚よりも、金貨1枚でももらえるだけマシと考える。金貨1枚の条件をのむしかないのだ。同様に人数が増えた場合でも、金貨1枚の条件に反対すると、次のボスも論理的な強欲さで金貨の配分を行い、自分は金貨をもらえなくなるので、賛成せざるを得ないのだ。

 というわけで、マス北野と東大生は、答えが同じだが、ある海賊に注目したとき、金貨1枚と金貨0枚という条件が交互に現れる。ここに注目したマス北野がコマネチ・フィールズ賞を獲得した。

 さて、竹内薫センセの「美しき数学の時間」では、さらに、海賊の人数が500人になった場合、金貨100枚をどう配分したらいいかという問題の考察をした。

 金貨の枚数が足りないので、どう分配しても、金貨をもらえない人数のほうが多く「反対」票が集まってしまう。海賊が200人ですら、ボス(提案者)の獲得できる金貨の枚数は1枚だ。海賊が201人になると、海に落とされたくないので、自分の取り分は0枚という提案をせざるを得ない。203人になると、自分の取り分を0枚とする提案すら、金貨をもらえない海賊は「反対」するので、海に投げ込まれる。ところが、海賊が204人になると、ボスの次にエライ海賊(ナンバー2)が、この提案に反対すると、次は自分がボスで、203人の場合は、どんな提案をしたところで、海に投げ込まれることがわかっているので「賛成」にまわる。こうした、半数に達する提案が可能なパターンは、202人、204人、208人、216人、232人……456人で現れるという。この456人というのが、海賊500人の場合のボス(提案者)が海に投げ込まれない、最大の人数だ。この人数に達するまでは、どんな提案をしても、海に投げ込まれるってことね。う~ん、冷酷非情の海賊だ^^;

 海賊100人の問題は、スティーブン・ランズバーグ(Steven E. Landsburg)が考案した。また、海賊500人の問題は、ステッペン(スティーブン)・オモハンドロ(Stephen M. Omohundro)が1998年に発表した。この両問題については、イアン・ステュワート(Ian Stewart)という人が下記のPDFファイルで詳しく解説しているので、見てほしい。

 この記事では、ちゃんと、提案者も加わって投票できることが明記してある。

MATHEMATICAL RECREATIONS
A Puzzle for Pirates

 ※↑の記事は、下記で紹介する「Math Hysteria」という本にも掲載されている。

GoogleのBook検索で全文サーチ

《※追記:9月14日》
 金貨の枚数を2倍した数が、海賊の数より大きければ、「賛成」を得られる提案をすることができることは、わかってもらえたと思う。逆に、金貨の枚数×2<海賊の数の場合、金貨をもらえない海賊のほうが多くなるので、「反対」票が多くなる。しかし、それでも、半数の「賛成」を得ることができることがある。記事中でも説明したが、この辺のしくみについて、もう少し考察しよう。それは、金貨を得ることよりも、海に投げ込まれたくないほうが優先されるためだ。海賊はエライ順に並んでいて、ボスが海に投げ込まれると、次にエライ海賊がボスになる。自分がボスになったとき、いかなる提案をしたとしても、海に投げ込まれるのなら、現在のボスの提案に「賛成」したほうが良いと論理的な海賊は考える。

20080913_02

(※Clickすると拡大表示)

 ステッペン・オモハンドロの問題は「海賊が500人で金貨が100枚」の場合だが、ここでは、簡略化して、「海賊が50人、金貨が10枚」の場合を考えてみた(表は、海賊19~52人の場合を表示)。海賊50人の場合は、海賊の総数が36人になったとき、提案が成立する。次に成立する人数は52人なので、最初のボスを始め、14人のボスは、海に落とされる運命にある。海賊は、ボスが次々と海に落とされ、海賊の人数が減っていったとき、自分が海に落とされる場面を帰納的に推論し、現在のボスの提案に対して「賛成」「反対」を決めるわけね。海賊は自分がボスになったとき、生き延びる提案することができるなら、「反対」票を入れる。つまり、海賊の数-(金貨の数×2)=残りの海賊。この残りの海賊の数が、2^nならば、自分が生き残る提案ができるというわけだ。

 海賊が500人の場合もシミュレートしたかったが、Flashでは「for~next」のループ数が増えると、処理が追いつかず、警告を発するので、海賊の数は最大200人、金貨の数は最大100枚とした。海賊の数、金貨の数を設定し、「多数決」ボタンを押してほしい。海賊2人の場合から表示しているので、「多数決」ボタンを押しても、同じように見えるけれど、テキストをスクロールさせて、確認してね^^;

 充分に金貨があるうちは、ボスは、多くの金貨を手にすることができるが、海賊の人数に対し、金貨の枚数が少ないと、反乱がおきる。さながら、売上好調の会社の社長は安泰だが、売上が落ちると、社長の首を挿げ替える。現実の社会も冷酷非情のようだ。

 秋田名物ハタハタ簡単ではございますが、お後がよろしいようで……(番組を見ていない人には、なんのことかわからない、ナハナハ;; ※ナハナハは沖縄名物ではなく、(C)せんだみつお。これも通じないかも><;自爆)
《※追記:おわり》

[非公認]Google入社試験
[非公認]Google入社試験
竹内薫/編・著
徳間書店

Math Hysteria
Math Hysteria
Fun and Games With Mathematics

Ian Stewart/著
出版社: Oxford Univ Pr (T) (2004/7)

Comadaidvd_01
たけしのコマ大数学科DVD1
(第1期)

Comadaidvd_02
たけしのコマ大数学科DVD2
(第2期)

※コマネチ大学数学科の「過去問題」はこちらから。
コマネチ大学数学科:2006年度全講義リスト
コマネチ大学数学科:2007年度全講義リスト


“■コマネチ大学数学科105講:多数決” への2件の返信

  1. たけしのコマ大数学科#105

    たけしのコマ大数学科#105(番組的には103回)
    (旧名称・たけしのコマネチ大学数学科)
    フジテレビ 2008年9月11日 深夜OA
     
    今回のテーマは、
    「多数決」
    DVDBOX第2期発売:2008年07月16日
     
    【DVD】
    たけしのコマ大数学科
    DVDBOX 1
    ¥5,284
    【N…

  2. 「海賊と金貨」のパズル(海賊の人数より金貨が少ないケース)

    昨日書いた「基本形」の続き。多分全3回の2回目。 金貨の枚数が少なくなった場合を考えよう。金貨が3枚までなら、ボスの取り分が減るだけでこの分配方法で問題は生じない。 P1=1、P2=0、P3=1、P4=0、P5=1。 金貨が2枚となったら、どうなるだろう?ボスは処刑されないために…

コメントは受け付けていません。