コグノスケ

卵が割れる階数は？問題

Twitterで見かけて面白かった問題、解法をメモしておきます。

100階建てのビルから卵を落とします。卵はある階よりも低ければ割れませんが、ある階よりも高いと割れます。卵を2つ持っているとき、卵が何階で割れるか調べる方法を提示してください。そのとき卵を落とす最大の回数をできる限り小さくしてください。

という問題です。

基本的な考え方

1階から順に落とせば確実にわかりますが、最大の投擲回数が100回（卵が割れる階数が100Fのとき）になり、最適な方法ではありません。

卵が2個あることを利用し、1個目は複数階を一気に飛ばして（例10F, 20F, 30F, ...）投擲します。例えば10F飛ばしで試すとすると10F, 20F, 30Fで割れず40Fで割れたら、2個目は「最後に割れなかった階の1つ上の階」すなわち31Fから投擲します。このように試すともっと早く卵が割れる階数がわかります。

卵の投擲回数の最大値を計算すると、例えば10F飛ばしであれば1個目が最大10回（10F, 20F, 30F, ..., 90F, 100F）、2個目が最大で9回（x1F〜x9F）なので、19回（卵が割れる階数が99Fのとき）です。100回と比べるとだいぶ少なくなりましたが、まだ無駄が残っています。

答え

固定階数を飛ばす方法だと1個目と2個目の最大の投擲回数の和を見たとき、上の階になるほど悪化します。例えば、

• 卵が割れる階数が39F: 10F〜30Fまでで3回、31F〜39Fで最大9回 = 12回
• 卵が割れる階数が99F: 10F〜90Fまでで9回、91F〜99Fで最大9回 = 18回

1個目の投擲方法を変えて最初は10F飛ばし、次は9F飛ばし、その次は8F飛ばし、のようにすると投擲回数の最大値が悪化しないことに気づくと思います。

こんな表で示すとわかりやすいでしょうか。

1個目は12F, 25F, 37F, 48F, 58F, 67F, 75F, 82F, 88F, 93F, 97F, 100Fの順に投擲します。最大で12回です。割れたら最後に成功した階の1つ上の階から投擲すると、最大14回で卵が割れる階数がわかります。

最大の回数になるケースは12通りですが、一例として卵が割れる階数が99Fの場合を示します。12, 25, ..., 100（1個目が割れる）, 98, 99（2個目が割れる）の14回になります。

他には1個目を投げる階数を下記のようにしても良いです。

• 9F, 22F, 34F, 45F, 55F, 64F, 72F, 79F, 85F, 90F, 94F, 97F, 99F, 100F
• 10F, 23F, 35F, 48F, 56F, 65F, 73F, 80F, 86F, 91F, 95F, 98F, 100F

いずれも投擲回数は最大14回となります。