Ajaxの本質、「非同期メッセージ型ウェブ・アプリケーション」のススメ
『恋はブックマーク』-ブックマーク・コメントはシャイな日本人向け?

ビル・ゲイツの面接試験-クイズ編・模範解答

050504_105431 先日の「ビル・ゲイツの面接試験-クイズ編」に対して、メール、トラックバック、mixiなどを通じて沢山の方から答えをいただいた。そこでここで模範解答を発表。さすがに難しかったのか、全問正解者はたった一名であった。予想した通り、第三問が難関であったようだ。

[第一問]多くの人が正しく答えた通り、手順は以下の通りである。
(1)8個の金貨のうち6個を適当に選び、3個づつ天秤に乗せて比べる。
(2)片方が軽かった場合(3)へ、釣り合った場合(4)へ。
(3)軽かった側の金貨のうち2個を適当に選び、1個づつ天秤に乗せて比べる。片方が軽ければそれが偽造品、釣り合えば残りの金貨が偽造品。
(4)(1)で天秤に乗せなかった金貨2個の重さを天秤で比べ、軽い方が偽造品。

[第二問]81個。
 天秤は、一回の操作で、「左が重い」・「釣り合う」・「右が重い」の3値の情報を与えてくれる。それを正しく利用すれば、一回の操作ごとに、答えの可能性を3分の一に減らすことが出来るのである。逆に言えば、一回の操作では答えが3通りある状態(つまり、3個の金貨のうちどれか一つが軽いと分かっている状態)から、どの金貨が偽造品か確定できている状態にまで絞り込めるのである。同じように二回の操作では、答えが9通りある状態(つまり、9個の金貨のうちどれか一つが軽いと分かっている状態)から、どの金貨が偽造品か確定できている状態にまで絞り込めるのである。つまり、k回の操作で、答えが「3のk乗」通りある状態(つまり、「3のk乗」個の金貨のうちどれか一つが軽いと分かっている状態)から、どの金貨が偽造品か確定できている状態にまで絞り込めるのである。この問題では、k=4なので、金貨の数は「3の4乗」となる。すなわち天秤を4回使えば、81個の金貨の中から偽造品を見つけることができるのである。

[第三問]13個
 この「偽造金貨が重いか軽いか不明」なケースにおいては、金貨がN個の場合、可能な答えはN通りではなく、2N通りとなる(1個目が軽い、1個目が重い、2個目が軽い、2個目が重い、…)。第二問の解説で述べたように、天秤を3回使える場合、最大27の可能性から一つの答えに絞り込むことが可能である。つまり、2Nが27を超えない最大の整数、N=13(金貨13個)が、最適の手順で天秤を3回使った場合に偽造品を見つけ出すことが出来る最大値である。

[第五問]金貨の数を2のべき乗である8にすることにより、二分法を使うようにミスリードしている。 
 少し前の記事でも書いたが、エンジニアは、8だとか16だとかいった2のべき乗に過敏に反応する性質がある。金貨の数を最大の9個にせず、あえて8個にすることにより、「これは金貨を半分に分けては比べていく二分法を使えば良いんだな」とミスリードするのである。面接に来た学生の多くがこのミスリードに引っかかるのだ。

[第六問]log23ビット。log23は2を底とした3の対数、約1.585。
 出題の時にも書いたが、この問題は、「情報理論」を単位をちゃんと取得した情報学科の学生にしか答えられない問題である。そんな学生であれば、1ビットでは0と1の2値を、2ビットでは0、1、2、3の4値を表すことができることは知っているので、天秤を一回使って得られる、「左が重い」・「釣り合う」・「右が重い」の3値のデータに含まれる情報量は、1ビットより多く、2ビットより少ないことは分かるはずだ。後は、高校でならった数学を応用して、log23ビットという答えにたどり着く。

 ちなみに、賢明な読者は気づいたと思うが、「第四問」の答えは今回はまだ提示しない。あまりに多くの人が第三問でつまづいてしまったために、このクイズのハイライトであり、一番面白い「第四問」にチャレンジする機会を与えずに答えを提示してしまのは、あまりにもったいないと思うのである。

 そこで、あらためて第四問を書き、今回の宿題とする(ブログで宿題を出してはいけないルールなど無い^^)。

[第四問]ここに13個の金貨があり、そのうち一つだけがとてもよく出来た偽造品で、他の金貨よりわずかに重さが違う(重いのか軽いのかは不明)ことだけが分かっています。天秤を使ってどの偽造品を見つけ出したいのですが、天秤を一回使用するたびにお金がかかるので、出来るだけ最小の手数で偽造品を見つける必要があります。どうしたら良いでしょう。

 ちなみに、この問題をためしに私の会社の社員(全員アメリカ人)に出した所、正解を出してきたエンジニアもいたのだが、以下のような答えも返ってきた。

・金貨を机の上にならべて天秤で何度も叩く。キズのつき方が他と異なるものが偽造品である。
・金貨を使って店で買い物をし、しばらくしてから返品することにより、偽造品を本物と取り替えてしまう。

まともな答えが出せない時は、こんな答えを返してくるところがいかにもうちの社員である(笑)。

Comments

通りすがり

>k=4なので、金貨の数は「4の3乗」となる

3の4乗じゃない?

satoshi

>3の4乗じゃない? 

ご指摘ありがとうございます。ミスタイプでした。

通りすがり2

すみません、書き込もうか迷ったのですが、
http://satoshi.blogs.com/life/2005/04/post_11.html
に倣ってあえて突っ込ませてもらいます。
[第六問]について
「左が重い」・「釣り合う」・「右が重い」の確率がそれぞれ1/3になるという
条件をみたせば得られる情報量は log3 になります。
確率に偏りがある場合は得られる情報量は起きた事象の事前確立によって変化し
平均ではより小さくなります。
たとえば模範解答の[第一問]で
(1)8個の金貨のうち6個を適当に選び、3個づつ天秤に乗せて比べる。
だと平均で得られる情報量は対数の底を2として
3/8log(8/3) + 2/8log(8/2) + 3/8log(8/3) = 1.56127812[bit]
となります。

[第四問]では、3回の天秤の使用で「偽造品を見つける」という
目的は果たせますが、[第三問]の解説にあるように、
N*2 = 26通りの中からひとつに絞ることはできないのではないでしょうか。
つまり模造品を見つけることができてもそれが本物より重いか軽いか特定できない場合があるます。
これも、実際に得られる情報がlog3より少ないためですね。

satoshi

 通りすがり2さん、するどい突っ込みですね。ここまで突っ込んでくる人がいるとは予想もしていませんでした。
 実際、「第四問」に用意している私の答えも、ある場合にのみ(確率は13分の1ですが)偽造コインが重いのか軽いのかを特定できないのです。つまり、私の手順では、3回天秤を使って、25通りの答えしか得られないのです。
 その考え方を応用すれば、ひょっとすると14個の金貨から3回の天秤の使用で偽造コインを見つけ出すことも不可能ではないかも知れないと思っているのですが、今の所、その手順を見つけ出すことはできていません。

Munegon

上記コメントの「25通りの答えしか得られないのです」について
引っ掛かりを覚えたので、コメントさせていただきます。

偽造コインが重いか軽いか特定できない確率は13分の1ですが
その事象に遭遇した時点では、偽造コインはシュレディンガーの猫のように
重いコインと軽いコインの状態が混在した状態にあると思うのです。
つまり、2通りの状態があたかも1通りに見えているだけであって
実際は2通りの答えが同時に得られたのだと考えられるのではないでしょうか?

また、天秤問題はどのような場合であっても偽造コインを特定できる
計測回数を求める問題であって、14個の金貨ではどうしても4回の計測が
必要になる状況が発生します。
「見つけ出すことも不可能ではない」が前提ならば、コインが100個であろうと
1000個であろうと僅か2回の計測で特定できる可能性はあるので
可能性の問題を考えるのは不適切ではないでしょうか。

satoshi

Munegonさん、「シュレディンガーの猫」まで来ましたか。またまたするどい突っ込みですね^^;

ちなみに、14個のコインに関して、「見つけ出すことも不可能ではない」という表現はあいまいでした。「3回の計測で必ず偽造コインを特定できるアルゴリズムを見つけ出すことも不可能ではない」と言いたかったんです。

閻魔大王

黙って、コメントを削除するのは、やめてよ!
間違ったことや嫌がらせをしているのじゃないんだから。
ただ、インターネットで発表する以上、最低限のマナーは、守ろうよ。
 せっかく、鋭い頭を持っているんだから、謙虚になればもっと成長できるよ。
 14枚のコインから偽物を見つけるのは、1枚、本物のコインを利用できるなら可能(ただし、軽重の判別ができないときもある。)
 ほかに1枚以上の本物のコインが利用できないときは、3回の天秤計測では、13枚が上限。このことはいろいろ証明可能だろうけど、「satoshi」さんの得意そうな情報理論の初歩で考えるのが最もやさしいかもね。Knuth先生の大好きな「平衡3進数」で考えるとすぐだよね。

閻魔大王

追伸
平衡三進数を利用すれば、
「任意回の計測で最大枚数のコインから偽物を判別するアルゴリズム」
を具体的にプログラム(具体的手順を出力する)するのも簡単ですよ。教えましょうか?

satoshi

 闇魔大王さん、コメント削除の件、少し過敏に反応しすぎたのかもしれませんね、申し訳ありません。時々他人を不愉快にするためだけに入るような攻撃的なコメントがあると、即刻削除しているのですが、少し早合点したようです。「他人のコメントは削除しない」のもマナーであれば、「コメント欄が荒れないようにする管理する」のも私の責任なので、私としては、「不必要に攻撃的なコメントは削除する」ことでバランスを取っています。ブログが掲示板よりも荒れないのは、私のようなバランスで管理している人が多いからだと理解しています。

 この問題を最初に聞いたのは、小学生の時に数学の先生から(つまり昭和40年代)でしたね。最初に印刷物で見たのは、多湖明氏の「頭の体操」という本でした。どちらも9個の問題でした。マイクロソフトに入ったのち、私が最初にこの問題を面接に利用し、他の面接官たちにも広まったり本で紹介されたりした、との認識でいます。最初は9個で出題していたのですが、同僚の一人が「9個より8個の方がエンジニアが引っかかりやすい」と指摘して以来、8個に変更しました。

 ちなみに、14個の問題は1個本物を使えば解けると気がついた人は3人目です。すばらしいですね。プログラムは遠慮しておきます。頭の体操ができれば十分なので。

閻魔大王

この問題の起源は「D.Schell が1945年American Mathematical Monthly 誌上で提起した」とされています。その後1945年から1950年ごろまで誌上でかなり議論されたようです。
「14個の問題は~3人目」だそうですが、日本では優秀な人がもっとたくさんいますよ。私の周りだけでも、中学生のときや、高校生のときに解いていた人がいます。
 14個どころではなく、「N回の測定で最大何枚まで判定できるか」という一般化を独力で考察している方がインターネット上にも何人か居られるようです。
 数学的に厳密に証明するのは、「問題の定式化の仕方」、「必要条件、十分条件の吟味」などなかなか面白いと思います。数学の得意な高校生のよい刺激になると思います(特別な知識は不要)。情報理論からの考察は明快ですが面白みにかけると思いませんか(機械的にプログラムまで書けてしまうほど単純)?
最後に偽コインの未解決と思われる問題(私は詰め切れていません)を提起しておきましょう。
「N枚のコインの中にK枚(kは0以上N未満)の偽物(軽重不明)が含まれているとき最低何回の天秤測定で判別できるか」
 元(?)マイクロソフトのプライドをかけて挑戦してみてください。

閻魔大王

改めて、模範解答を読んでみました。少し問題があるようですね。「模範解答」と言う以上訂正したほうがいいと思いますよ。

 第2問 「3の4乗通り~」は、必要条件に過ぎません。すなわち判別できる上限が81枚と言うだけで、実際にできるかどうかは、十分条件として吟味する必要があります。このことは、高校数学程度でも、等式の証明などでよく出てきますよね。すなわち等号の成立条件の吟味が大切です。
 第3問 「13枚~」も同じく可能な上限に過ぎません。十分性を示すべきです。また、模範解答と「ひょっとすると14個の金貨から3回の天秤の使用で偽造コインを見つけ出すことも不可能ではないかも知れないと思っているのですが、今の所、その手順を見つけ出すことはできていません」とのsatoshiさんの2005.6.8のコメントの整合性はどうなっているのですか。必要条件として上限を示しておきながら、それ以上の14枚も可能かもしれないなんて変ですよね?

satoshi

 閻魔大王さん、この手の問題が本当に好きなんですね。確かに、この問題に関して言えば、「必要条件」の提示を求めたかったのですが、一般の人にも分かる言葉に落とす段階で、数学的な厳密度は落ちてしまいましたね。

 14個以上に関しては、「表裏が判別しなくても良ければ…」というヒントを与えたくなかったので、これも少し不明確に成りました。

 ちなみに、私のブログはもう少し肩の力を抜いて気楽に読んでいただけると助かります。あまりここまで真面目なツッコミをされると、気楽に書いている私としては申し訳なく思えてしまいます。

閻魔大王

あれれ??
いつから文科系人間に宗旨替えしたのかな?

 私は、この手の問題が特に好きなわけではありません。以前に、面白そうなので少し考えたことがあるだけです。ただ、satoshiさんは気楽に書いているつもりかもしれませんが、「ビルゲイツの名」の権威のもと、あいまいな議論が流布してはまずくありませんか?それで今回歴史なども少し調べてみました。
 そもそもパズルとしては、難しいほうで、それこそ理科系人間は、はまりやすいのかもしれません。それだけにある程度論理の厳密さが必要だと思います。
 「必要条件の提示を求めたかった。」では、まったく意味が無いのではないですか。必要条件は、判別可能な最大数を示すだけ、すなわちそれより多い枚数では判別不可能ということを示すだけです。実際に可能なことを、なんら保障するものではありません。
 だからこそ第4問で具体的手順が問題になるのでしょう? 3回の測定では13枚が上限とわかってもその具体的手順は、なかなか難しく工夫もいるのではないですか。もしなんらかの方法で、具体的手順の存在が示されなければ、もちろん13枚が上限とはいえませんよね。
 以上、結構まじめなつもりです。

 次は、ツッコミになるのかな?
「14個以上に~表裏~」??? 「表裏」は「軽重」の間違いですよね。
 私も、ツッコミや荒らしをするつもりは毛頭ありませんので、訂正ないしは正確な解答を提示いただければこれで終わりにいたします。

大天使ミカエル

コインパズルの参考サイト結構ありますよ。

http://web2.incl.ne.jp/yaoki/nise.htm
特にこのサイトのパート4

http://oshiete1.goo.ne.jp/kotaeru.php3?q=30706
あまりよくまとまっていないけど、色々議論しているみたい。

大天使ミカエル

satoshiさん、誤りは訂正したら?
せっかく参考サイトを教えてあげたんだから、少しは勉強したらいいのに。
 わかったような薀蓄を述べても、本当はよく理解していないこと丸出しですよ。

petem

4年も経っていまさらなんですが、第3・4問の回答として。
18個でも可能だったのですが確認していただいてよろしいですか?


まずは6個ずつのグループABCに分割します。

1回目)AとBを天秤にかけ、A>B , AY , X

3回目)MとNではなく、『1・2回目の計測で正しいことが確定した金貨』とMを測定する。
これが釣り合ったなら、偽者はN。
釣り合わなかったら、偽者はM。

本物と判明した金貨を破棄せず再利用すればこれでいけると思うのですがいかがでしょうか?

Verify your Comment

Previewing your Comment

This is only a preview. Your comment has not yet been posted.

Working...
Your comment could not be posted. Error type:
Your comment has been posted. Post another comment

The letters and numbers you entered did not match the image. Please try again.

As a final step before posting your comment, enter the letters and numbers you see in the image below. This prevents automated programs from posting comments.

Having trouble reading this image? View an alternate.

Working...

Post a comment

Your Information

(Name is required. Email address will not be displayed with the comment.)