卵の割れる高さを特定する問題
以前 Twitter で以下のような問題が話題になっていた。
あるビルの 1 ~ 100 階のどこかから卵を落とすことを考える。ある整数$ N (1 \leq N \leq 101)が存在し、卵は $ N 以上の階から落とすと割れ、 $ N未満の階から落とすと割れないことがわかっている。一度割れた卵はもう使うことができない。卵を2つ持っている時、$ Nを特定するために必要な卵を落とす回数の最大値を最小化する落とし方と、その最小値を求めよ。
---
落とす回数の最大値の最小値が$ xであるとする。
卵が一つしか無い状態であれば、$ Nとしてあり得る範囲を小さい順に全て試す必要が生まれることがわかる。もし最初に$ x+1 以上の階に落として割れた場合、2つ目の卵で$ 1 .. xの範囲の最大$ x回落とす必要が生じ合計$ x+1回以上落とす必要が生まれうるため、最初に落とす階は$ x以下である必要がある。逆に$ x以下の階で落とせば、割れた場合の落とす回数の最大値は$ x以下となるため矛盾しない。
1つ目の卵が割れなかった場合、1つ目の卵を落とした階を$ a とすると$ Nは$ a+1以上であることがわかるため、 $ 100 - a階建てのビルにおける同じ問題の答えを求め、それに既に落とした卵の分の 1 を足せばこの問題の答えが得られる。
ここで、$ 100 - aが小さい方が必要な落とす回数は小さくなるため、$ aは大きい方が良く、最初に落とすのは$ x階が最善であることがわかる。
また、この部分問題の答えに 1 足した値が$ x以下であることから、この部分問題の答えは$ x-1以下である必要があり、上記同様にこの部分問題で最初に落とすべき階は$ x-1であることがわかる。
これを繰り返すと、落とす最善の階は各部分問題の1段目から数えて $ x, x-1, x-2, .., 1となる。
各部分問題で判定できる「その階が $ Nであるか」の範囲はその部分問題で1つ目の卵を落とした階までの範囲であるから、この和が 100 以上である必要があり、逆にそうであれば$ Nを特定することができる。
よって $ x は $ \sum_{i=1}^{k} i \geq 100 を満たす最小の $ k で、これを解けば $ x = 14 が得られる。
---
ところで、この問題に対して「〜のようにすれば〜回で特定できる」と回答しているものが多くあったのだけれど、それが最小であることの証明、少なくともそれに対する言及もされなければならなそうと思った。