「夫子憮然曰、鳥獣不可與同羣。吾非斯人之徒與、而誰與。
「論語」微子、第十八、六

2012/07/23

二つの卵(解答)

今日もまだそれほど暑くない。 珈琲、果物、ヨーグルトののち、 納豆、焼き海苔、蕪の糠漬、浅蜊の味噌汁、御飯の朝食をとり、 お弁当を詰めて出勤。 昼食の持参のお弁当。茄子とピーマンと鶏肉のレッドカレー。 茄子が余っていたので、つい使ってしまったが、 レッドカレーの味にあわないし、色も悪くなるなあ。 夕方退社して帰宅。 夕食は、目刺しを焼いて、冷奴(茗荷と生姜)、玉葱のピクルス、 じゃがいもと若布の味噌汁、大和芋のとろろ御飯(大葉と自家製ポン酢)。 食後の散歩がてら、近所の図書館まで本を借りに行く。 帰宅してお風呂に入り、湯上がりにグレープフルーツを半分。

昨日の 「二つの卵」パズルの解答。
答は 14 回。 まず、14 階の窓から卵を一つ落とす。もし、割れてしまったら、 もう一つの卵を使って、一階から 13 階まで順番に試していく(最悪の場合で 1 + 13 = 14 回)。 もし、割れなかったら、さらに 14 - 1 = 13 階分上がって 27 階から卵を落とす。 もし、割れてしまったら、もう一つの卵を使って、15 階から 26 階まで順に試す (最悪の場合で 1 + 1 + 12 = 14 回)。 もし、割れなかったら、さらに 13 - 1 = 12 階分上がって……、 と以下、これを繰り返す。どの場合でも最悪は 14 回で卵の強さが判明する。 実際、最後まで卵が割れない場合でも、 14 + 13 + 12 + ... + 1 = 105 > 100 なので、OK。

卵が三つ、あるいは一般に n 個の場合を解く鍵は (卵が二つの時もそうなのだが)、 このパズルの本質が「再帰」であると気付くことにある。 つまり、上の解答をよくよく見直してみると、 まず最初の階で卵を落とし、 もし割れなかったら、 その階より上の階に対して、同じパズルを解くことになり、 もし割れたら、 その階より下の階に対して、卵が一つ少ない同じパズルを解くことになる。 つまり、このパズルを解くには、一段階小さな、このパズルを解けばよいわけで、 それを解くには、さらに一段階小さな、このパズルを解けばよいわけで、 さらにそれを解くには……と、どんどん遡って行くと、 最終的には卵が一つでビルが一階建ての場合に帰着し、答が得られる。

このパズルは IT 業界で人気があるようだ。 gxxgle 社やMS 社の面接試験に出たという都市伝説があるが、 本当かどうか定かでない。 このパズルの面白く詳しい解説として、 blog 記事 "The Two Egg Problem"(英文)がある。 また最近翻訳された、 「続・とっておきの数学パズル」(P.ウィンクラー著/坂井公・他訳/日本評論社) にも紹介されており、その記述によれば、初出は "Which Way Did the Bicycle Go"(D.E.Konhauser, D.Velleman, S.Wagon, 1996)という本かも知れない。