« 乳というのは何と読むのだろう | トップページ | 久々にかなり風邪らしい風邪 »

Googleの5人の海賊の問題

Google の面接試験でどういう問題が出るのか。GIGAZINEにかなり前に紹介されている。 (Googleの面接試験、一体どのような質問をされるのか? - GIGAZINE)

この問題の17番。

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

解いていて、98%というヒントがどうしてもひっかかってしまった。 Google らしからぬヒントだ。こんなヒントを出す必要がなぜあるのだろうか?

そこでもう少し調べていたら、「連載 その51 問題の整理、単純化がキー」というページがみつかった。 ここに出ている設問51は、GIGAZINE の17番と殆ど同じ文章になっている。 「います」が「いる」になっているとか、「、」があるとか、そのレベルの違いしかない。

「連載 その51」には、途中の説明に次のように出ている。

そこで2人の場合を考えてみます。この場合上位の海賊は、同意者が自分たった1人でも、つまりどんなに他の1人の下位海賊が反対したとしても、同意者数はちょうど過半数を満たすので、命題のとおり上位海賊の意見は何であれ100%通って、生き残ることができます。

ここで問題なのは、誰が投票できるかということである。 問題文を読めば、

1位の海賊はプランを提案する権利がある

残りの海賊はこのプランに投票する権利がある

この2つの条件があることが分る。 二つ目の条件から、1位の海賊以外の「残りの海賊」が、投票する権利を持っていることは分る。しかし、1位の海賊に投票する権利があるかどうかはこの条件からは判断できない

日常会話であれば、わざわざ「残りの海賊は」というような表現を使った場合には、それ以外の海賊、即ち1位の海賊には投票する権利がないと解釈するのが自然かもしれない。 しかし、ここは論理パズルの中の世界なので、 論理的に少し厳密な解釈をして、 1位の海賊に投票権があるかどうかは定まっていないと考えるのが妥当だろう。 となると、1位の海賊に投票権がある場合とない場合に分けて、 2通りの解を示さなければならない。

この問題文だけから上位海賊の意見が100%通るという条件を決め付けてしまうようでは、地頭がいいとはとても言えないのではないか。 少なくとも、注意力が足りないか、厳密に解釈する能力が欠けているか、このどちらか、あるいは両方だろう。

この件について、西尾泰和のブログ: 5人の海賊のコイン分配問題によれば、元となった問題では全員で投票するということが明確に書いてあることがわかる。どこかでこの重要な情報が落っこちたのかもしれない。

さて、問題に戻ろう。 全員で投票するという条件であれば、「連載 その51」の解法で問題ない。 では、1位の海賊に投票権がないとどうなるか。 西尾氏の解法は合理的な思考によって、次の解を導いている。

「97,0,1,2,0」もしくは「97,0,1,0,2」

(数字は、1位から順に分配する金貨の数を示したものである。) これだとヒントの98%と合致しないのだが、 西尾氏は次のように考えたようだ。

「98%」というヒントは、 問題を訳した人が間違えたか、問題を作ったGoogleの人が間違えたか…

でも少し考えてみなさい。 海賊を1位からランクの順にA、B、C、D、Eという名前にしておく。 Dに2枚というプランを出したら、Eは納得できるだろうか。 俺に2枚くれ、と主張するに決まっている。 もちろんEに2枚のプランを出したら今度はDが納得しない。 しかも、DとEは海賊なのだ。こんなプランを出したら、DとEで殺し合いになるに決まっている

かくして、DとEのどちらかは死んで、4人の問題に帰着する。 Aは改めて自分に98枚、Bに0枚、Cに1枚、そしてDとEの生き残りに1枚を与えるというプランを出して、投票で可決されることになるだろう。 これが私の解答だ。Google のヒントはやはり正しいのだ。

|

« 乳というのは何と読むのだろう | トップページ | 久々にかなり風邪らしい風邪 »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/3035/55965155

この記事へのトラックバック一覧です: Googleの5人の海賊の問題:

« 乳というのは何と読むのだろう | トップページ | 久々にかなり風邪らしい風邪 »