卵２個で、落としたら割れる階を特定する

８月２９日木曜日、晴れ

先日の日記に書いた Google 入社試験で出たとかいう卵２個問題、あれのワーストケースの回数は１４回、だそうだ。おもしろい……。

Puzzle | Set 35 (2 Eggs and 100 Floors) - GeeksforGeeks

Suppose that we wish to know which stories in a 100-story building are safe to drop eggs from, and which will cause the eggs to break on landing. What strategy should be used to drop eggs such that total number of drops in worst case is minimized and we find the required floor.
We may make a few assumptions:
・An egg that survives a fall can be used again.
・A broken egg must be discarded.
・The effect of a fall is the same for all eggs.
・If an egg breaks when dropped, then it would break if dropped from a higher floor.
・If an egg survives a fall then it would survive a shorter fall.

『１００階建てのビルから卵を落としたとして、どの階までなら割れないか、そしてどの階からだと割れるか、知りたいとします。その階を見つけるには、そしてその階を決めるためにかかる最大の回数を一番小さくするにはどうしたらいいでしょうか。
次の仮定が成り立つとします。
・落として割れなかった卵はもう一度使えます
・割れた卵は二度と使えません
・落下時の衝撃はどちらの卵でも変わりません
・落とした卵が割れたら、それより上の階から落としても割れます
・落とした卵が割れなかったら、それより下の階から落としても大丈夫』

＊　＊　＊

卵が一つしか無かったら、１階から順に１００階まで調べていくしかない。

先日考えたのは１０階ごと登っては落として、まず二桁目を決める。しかるのちに二つ目の卵を階の９つ下の階から１階ずつ順に登っては落として一桁目を決める。
すると最悪のケースは１００階で割れるときで、まず一つ目の卵を１０回落とす必要がある。次に９１階から９９階まで割れないことを確かめて、１００階だと特定できる。すなわち１９回の試行が必要になる。

＊　＊　＊

ところで１０階が割れる階だとして、その特定には一つ目を１０階から落として割り、二つ目を１階から９階まで落としてみて割れない。つまり１０回の試行が必要。
２０階が割れる階だとすると、その特定には１０階から落としても大丈夫だった一つ目を２０階から落として割り、１１階から１９階までは割れないことを確かめる。すなわち１１回の試行が必要。
３０階だと、一つ目を割るために３回落として、二つ目を９回、都合１２回。
以下同様にして４０階なら１３回、５０階なら１４回と、割れる階が上になるほど特定のための回数が増えていってしまうことがわかる。

ここから逆に、一つ目の卵を落として割れなかったときに、次に落とすために登る階数をひとつずつ減らしていく、という方法が考えられる。

たとえば１回目を１０階から落としたなら、（そして割れなければ）２回目は９階上の１９階から落とす。
もしここで割れたら（最悪のケース、１９階が割れる階だとして）１１階から１８階の８回の試行で特定できる。一つ目の卵で２回落としているので都合１０回。これなら１０階が割れる階だった時の１０回の試行と変わらない。
１９階から落として割れなかったら、今度は８階加えた２７階から落とす。ここで割れたら２０階から２６階までの最大７回の試行で特定できる。一つ目を３回落としているので、ここでも１０回の試行で特定できている。

１つ目を落とす最初の階をＮだとして、１回ごと登る階数を少なくすることから

Ｎ＋（Ｎ－１）＋（Ｎ－２）＋　…　＋２＋１＝１００

を満たすと考えられる。
左辺の等差数列の和は高校数学の知識を使うとＮ（Ｎ＋１）／２だとわかる。（ちょうど三角形の形に数が増えていく。底辺の長さＮ、高さＮ＋１）

Ｎ↑２＋Ｎ−２００＝０

中学で習う解の公式を使って求めたＮのうち、正の数はおよそ１３.６５。整数に丸めて１４となる。

＊　＊　＊

つまり最初は１４階から落とす。
割れたら１階から１３階まで順に試す。（最悪で１４回）
割れなければ１４階の１３階分上、２７階から落とす。
割れたら１５階から２６階までの試行。（一つ目の２回と二つ目の１２回で最悪１４回）
２７階で大丈夫なら＋１２で３９階から。
……

１４、２７、３９、５０、６０、６９、７７、８４、９０、９５、９９、１００、という具合に一つ目の卵が割れる階を探すことになる。

ワーストケースはここに挙げた１００階以外のすべての階で、特定に１４回かかる。それ以外の階で割れるときは１３回以下で特定できる。

＊　＊　＊

卵が三つあったらどうなるかも考えていて、手元のメモではワーストケースで９回、となっている。