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

Life is beautiful: ビル・ゲイツの面接試験－クイズ編
で面白そうなクイズが掲載されていたのでやってみた。[第一問]はたしかにも載っていたような気がしますが。
以下解答。

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

というわけで2回で見つけられます。

［第二問］上の問題と同じ（他の金貨よりわずかに軽い偽造品が一つだけ混ざっている）条件で４回まで天秤を使っていいとすると、最大で幾つまでの金貨の中から偽造品を見つけ出すことが出来るでしょう。

一回の計測で3つのグループから1つを選ぶことができるので、残り1回の計測を残して金貨が3枚になればよい。これを再帰的に4回繰り返すので、答えは $3^4=81$ でしょ。

［第三問］今度は少し条件を変えて、偽造品は「本物と少し重さが違う」ことは分かっているのですが、重いのか軽いのかは不明だとします。この場合、３回まで天秤を使っていいとすると、最大で幾つまでの金貨の中から偽造品を見つけ出すことが出来るか予想してみてください。

偽造品が本物より軽いか重いかわからないので、一回の計測では1/2にしか絞れない。よって金貨が8枚なら $2^x>=8$ でxは3かな。

［第四問］第三問で予想した数の金貨の中から、天秤を３回だけ使って「本物と少し重さが違う」偽造品を見つける手順を示してください。

というわけで3回！！

［第五問］（心理学の問題）第一問で、私が金貨の数を９個ではなく８個としたのはどうしてでしょう。

うーむ。心理学の問題だからな。コンピュータの世界では9より8のほうが美しいから、とか。
たとえばプログラムを書いてて、「バッファは3バイトあれば十分に足りるのだけれどメモリを節約する必要なんてないし8バイトにしておこう」みたいな感じで。

［第六問］（情報科の学生のみ）天秤を一度使うごとに、ある一定の「情報」が得られるのですが、その情報量は何ビットでしょうか。

（もう学生じゃないけど）AとBに対して天秤を一度使ったとすると、

という3通りの情報？が得られるので1ビットじゃ足りなくて2ビット、かな。

このクイズのおかげで会社帰りの小一時間、退屈せずにすみました。感謝。
30分の面接だったら時間足りてないけどね。