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

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

8月29日木曜日、晴れ

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

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.

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

* * *

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

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

* * *

ところで10階が割れる階だとして、その特定には一つ目を10階から落として割り、二つ目を1階から9階まで落としてみて割れない。つまり10回の試行が必要。
20階が割れる階だとすると、その特定には10階から落としても大丈夫だった一つ目を20階から落として割り、11階から19階までは割れないことを確かめる。すなわち11回の試行が必要。
30階だと、一つ目を割るために3回落として、二つ目を9回、都合12回。
以下同様にして40階なら13回、50階なら14回と、割れる階が上になるほど特定のための回数が増えていってしまうことがわかる。

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

たとえば1回目を10階から落としたなら、(そして割れなければ)2回目は9階上の19階から落とす。
もしここで割れたら(最悪のケース、19階が割れる階だとして)11階から18階の8回の試行で特定できる。一つ目の卵で2回落としているので都合10回。これなら10階が割れる階だった時の10回の試行と変わらない。
19階から落として割れなかったら、今度は8階加えた27階から落とす。ここで割れたら20階から26階までの最大7回の試行で特定できる。一つ目を3回落としているので、ここでも10回の試行で特定できている。

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

N+(N-1)+(N-2)+ … +2+1=100

を満たすと考えられる。
左辺の等差数列の和は高校数学の知識を使うとN(N+1)/2だとわかる。(ちょうど三角形の形に数が増えていく。底辺の長さN、高さN+1)

N↑2+N−200=0

中学で習う解の公式を使って求めたNのうち、正の数はおよそ13.65。整数に丸めて14となる。

* * *

つまり最初は14階から落とす。
割れたら1階から13階まで順に試す。(最悪で14回)
割れなければ14階の13階分上、27階から落とす。
割れたら15階から26階までの試行。(一つ目の2回と二つ目の12回で最悪14回)
27階で大丈夫なら+12で39階から。
……

14、27、39、50、60、69、77、84、90、95、99、100、という具合に一つ目の卵が割れる階を探すことになる。

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

* * *

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

この記事が気に入ったら、サポートをしてみませんか?
気軽にクリエイターの支援と、記事のオススメができます!
東京暮らし、子らの父で妻の夫。工学研究科情報工学専攻修士。職業プログラマー。 ゲーム好き、アニメ好きのはずが、最近はどちらにも時間を割り当てられない。