卵の強度測定問題の思考プロセスと引き出すの増やし方

思考力を鍛え、その引き出しを増やす問題として、Googleの入社試験にも出たと言われている有名な卵の問題とその応用問題をご紹介します。

有名な「ビルの何階から落とすと卵が割れるかを卵を2つだけ使って調べる回数の問題」です。

卵の強度を調べる問題（その１）

実際に、ネットなどでGoogleの入社試験にも出たとされている問題です。
どのような思考のプロセスを経て正解にたどりついていくかをご紹介します。

【問題】

あなたは卵の強度テストを任されることになりました。
その方法は、卵を１００階建ての建物から落とし、何階までなら割れないかを確かめます。
同じ強度の卵を２つ渡され、この２つを使って、なるべく少ない試行回数で卵が割れない最高の階数を見つけてください。

だだし、卵は落として割れなかったら、その卵を何回でも再利用できます。
もちろん卵は全く同じ強度で、何回落としても、その強度は変わらないものとします。

【正解と解説】

数学科専攻の人や、数学が得意な人であれば、log2が出てくる無限級数であるメルカトル級数を利用して、法則性を見つけ出して解いていくという方法がありますが、ここではそんな難しい専門的な知識なしで解いていく方法を解説します。

卵が１つだけの場合は、１階から順番に落としていき、割れなかったら２階、さらにそこでも割れなかったら３階というように、１階から順番に試していく必要があるため、最大試行回数は１００回になってしまいます。

しかし、卵が２つある場合は、１つ目の卵を、何階かごとに落としていき、大雑把に検討をつけることができます。

１００＝１０×１０であるので、１０階ずつ区切って１つ目の卵を落としていけばいいかなと見当をつけます。

つまり、１０階ごとに１つ目の卵を落とし、１０階で割れなかったら２０階、２０階で割れなかったら３０階というように、１０、２０、３０、４０、５０、６０、７０、８０、９０、１００階を調べます。

もし、３０階で割れずに４０階で割れたとすれば、残ったもう１つの卵で、３１階から３９階まで、１つずつ階数をあげて割れるところを調べていけば随分と試行回数が節約できそうです。

この方法で行うと、最大試行回数は、１００階で割れずに９９階で割れた時になり、１つ目の卵の試行回数が１００階で割れなかったことも含めて１０階、２つ目の卵で９１階から９９階まで調べることになるので９回、合計１９回の試行回数が必要になります。

ここまではすぐに思いつくと思います。

ここで、一番試行回数が少なくするには、調べる試行回数を一定にしてあげることが大切になってきます。

すると例えば、最初は１０階、次は２０階ではなく１９階、その次は３０階ではなく２８階というように、区切る階数を１つずつ減らしていく必要があることに気づきます。

つまり、最初はＮ階から落とし、その次はＮー１階から・・・というようにしていくと、最大試行回数がＮ回で調べられるということがわかります。

つまり、

（Ｎ＋（Ｎー１）＋（Ｎー２）＋（Ｎー３）＋　・・・　＋　１）　≧　１００

この式に当てはまる最小の整数Ｎを計算すれば、それが最大試行回数になります。

式を整理すると

（Ｎ＋１）×　Ｎ／２　≧　１００

つまり、Ｎ×（Ｎ＋１）≧２００　となりますので、該当する最小整数Ｎは、１４になります。

答えは、最大試行回数は１４回

具体的な方法は、１つ目の卵を、１４、２７、３９、５０、６０、６９、７７、８４、９０、９５、９９、１００階から落としていき、割れた時点で１つ目の卵は終了。あとはその間を２つ目の卵で調べていきます。

例えば、７７階では割れず、８４階で割れたのであれば、７８階から８３階までを２つ目の卵で調べますが、７８階から卵を落としていき、割れなければ１階ずつ上げて調べていけばいいのです。

例えば、８３階で初めて割れる卵の強度であれば、１つ目の卵で１４、２７、３９、５０、６０、６９、７７、８４階の８回試行し、さらに２つ目の卵で、７８、７９、８０、８１、８２、８３階と６回試行しているので、合計８＋６＝１４回の試行でわかることになります。

卵の強度を調べる問題・応用問題（その２）

卵の問題の応用問題
さて、今度は応用問題に挑戦してみましょう。

今までの問題の知識や、解法の引き出しを利用して、さらに応用問題に挑んでみましょう。

【問題】

さて、応用問題です。
あなたは卵の強度テストを任されることになりました。
その方法は、卵を１００階建ての建物から落とし、何階までなら割れないかを確かめます。
今度は同じ強度の卵を３つ渡され、この３つを使って、なるべく少ない試行回数で卵が割れない最高の階数を見つけてください。

だだし、卵は落として割れなかったら、その卵を何回でも再利用できます。
もちろん卵は全く同じ強度で、何回落としても、その強度は変わらないものとします。

【正解と解説】

今度は卵が３つ使えます。
考え方は、卵が２つの時と同じです。
そこで、（Ｎ＋１）×　Ｎ／２　≧　１００の式を応用して、視点をちょっとずらして考えます。

卵が３つ使えるのであるから、１つ目の卵で大雑把に区画分けして検討をつけ、その区画を２つ目と３つ目の卵で調査していけばいいことになります。

ということで、後ろから考えていきます。
２つ目と３つ目の卵で、何階分までなら、最大試行回数がＮ回で済むのかを逆に割り出していきます。

最大試行回数をＮ回、Ｎ回で測定可能な階数をｘとします。
すると
（Ｎ＋１）×　Ｎ／２　≧　ｘ の式で計算できます。
変形してみると
Ｎ（Ｎ＋１）≧２ｘ

Ｎ＝１０のとき、ｘ＝５５
Ｎ＝９のとき、ｘ＝４５
Ｎ＝８のとき、ｘ＝３６
Ｎ＝７のとき、ｘ＝２８
Ｎ＝６のとき、ｘ＝２１
Ｎ＝５のとき、ｘ＝１５
Ｎ＝４のとき、ｘ＝１０
Ｎ＝３のとき、ｘ＝６

ここで、卵が２つのときと同じ考え方で、一番試行回数が少なくするには、調べる試行回数を一定にしてあげることが大切になってきます。

つまり、１つ目の卵の試行回数が１つ増えるごとに、２つ目と３つ目での試行回数が１つ減るようにしていきます。

１つ目の卵を落とす階の間隔を、Ｎの時のｘ、Ｎー１の時のｘ、Ｎー２の時のｘ、・・・にしていけばいいのです。

具体的には、次のようになります。

１００階を２つに分けて考えた時、１つ目の卵を落とす階は、５５、１００階になります。

この時のトータルの最大試行回数は、１＋１０＝２＋９＝１１回になります。
１００階を３つに分けて考えた時、１つ目の卵を落とす階は、４５、８１、１００階になります。

この時のトータルの最大試行回数は、１＋９＝２＋８＝３＋７＝１０回になります。
１００階を４つに分けて考えた時、１つ目の卵を落とす階は、３６、６４、８５、１００階になります。

この時のトータルの最大試行回数は、１＋８＝２＋７＝３＋６＝４＋５＝９回になります。

１００階を５つに分けて考えた時、１つ目の卵を落とす階は、４つに分けた時と比べて、２つ目・３つ目の試行回数を１つ減らすと、２８、４９、６４、７４、８０、・・・となってしまい１００階到達しないので、全体の試行回数が増えてしまいます。

従って、最大試行回数は９回

１つ目の卵を落とす階は、３６、６４、８５、１００階になります。
２つ目の卵を落とす階は、（８、１５、２１、２６、３０、３３、３５階）＋（４３、４９、５４、５８、６１、６３階）＋（７０、７５、７９、８２、８４階）＋（９０、９４、９７、９９階）になります。

残りは、３つ目の卵で調査します。

例えば、６２階が卵が割れる最小階だったとします。
すると、１つ目の卵は３６階で割れず、６４階で割れますが、ここで既に２回試行しています。

次に２つ目の卵は、４３、４９，５４，５８、６１階で割れず、６３階で割れますが、これを確認するには、６回の試行が必要です。

最後にまだ割れていない３つ目の卵で６２階で割れるかどうかをチェックするのにもう１回の試行が必要になります。

つまり、全体での試行回数は、２＋６＋１＝９回となり、導いた解答と一致しています。

同様に１番試行回数が多くなりそうな９９階でもみてみましょう。
すると、１つ目の卵は３６、６４、８５階で割れず、１００階で割れますが、ここで既に４回試行しています。

次に２つ目の卵は、９０、９４，９７階で割れず、９９階で割れますが、これを確認するには、４回の試行が必要です。

従って、全体での試行回数は、４＋４＝８回になります。

もし、９８階であれば、９７階で割れ、９９階で割れないことを確認し、さらに３つ目の卵で９８階で割れるかどうかを確認しなければならないので、もう１回試行回数が多くなり、全体での試行回数は９回になり、導いた解答と一致しています。