卵が割れる階数を最小回数で求める問題の解答に対する証明について

きっかけ

もうだいぶ前の話だが、Twitterでこういう問題が流れてきた。(Googleの面接だったらしい。)

「あなたには卵が二つ与えられている。卵は二つともn階( 1 \leq n \leq 100)から落とすと割れてしまう。さて、nを求めるにはこの二つの卵を最低何回落とせば良いだろうか？」

この問題を見るのは初めてではないし、答えの数字まで覚えてしまっているが、僕には一つ疑問があった。ということで、適当に検索して上の方にあった「いかがでしたか？」と言わんばかりの解説サイトを見る。例えばこれだ。

xz4u.com

そして予想通り、この解説には問題点があることを改めて確認した。この解説では、「14回落とせばチェックができる」と書かれている。しかし、「14回が最小であること」の証明はどこにも書かれていない。これでは数学の証明としては明らかに0点だ。

そう、これが疑問である。 「この問題において、『14回』が最小であることはどうすれば証明できるか」というのを考えていこう。

経過

※この章は意欲ある訪問者の前にいきなり解答が出てくることを防ぐための「ネタバレ防止」のための章である。忙しい人は僕のつまらない失敗をすっ飛ばしてスクロールすると良いだろう。

さて、僕は最初物理学科らしく（？）、「卵を1回落とす試行あたりの情報量」を最大化するようなアルゴリズムを考えれば良い、と考えた。

卵が割れなかった時、0を書き、割れた時に1を順番に書いていくことを考える。卵を落とすアルゴリズムがfixされている時、この0と1という数字の羅列は1から100までの値に対応する。

つまり、「1が最大2回まで出現する長さnのビット列」で1から100を表現しているのだ。なので、1bitあたりの情報量をアルゴリズムの関数として表現し、変分法の要領で最大化すれば答えが出るのではないかと考えた。

...まあ想像に難くないと思うが、「1bitあたりの情報量をアルゴリズムの関数として表現」のあたりで僕は結局詰まってしまった。

実は、この考え方はかなり惜しいところをついており、次の次に述べる「別解」はこの考え方でいけるのだが、この時は結局、数学科の友人がちゃんとした証明を上げてくるまでずっと考えても分からなかった。

数学科の知り合いによる解法

僕が変分法で不毛な不等式評価ばかりを量産していた頃、突如として数学科の友人からメンションが届いた。あまりにも短かったので、最初の数秒間なんでこれが解答になってるかわからなかったほどだ。

しかし、このように一般化して考えると、卵2個のケースも簡単に解けてしまうのだ。やってみよう。

まず、卵m個とn回の試行で調べられる最大の階数を f(m, n)と表すことにしよう。（以下m,nは全て正の整数とする）

すると、問題は以下の問いに言い換えることができる。

「 f(2, n) \geq 100となる最小のnはいくつか？」

ここで「最大の階数」と定義したのがポイントだ。例えば卵が90階で割れて f(2, n)が例えば85だった場合、卵2個ではどう頑張っても85階までに割れるケースしか調べられないので、このケースだと足りない。

さて、話を戻そう。mとnのどちらかが1のケースではすぐに以下のことがわかる。

f(m, 1) = 1 \\ f(1, n) = n

まず、上のケースはいいだろう。卵が何個使えたとしても、1回しか試行が許されないのならば1階分しか調べることはできない。

次の卵1個n回のケースでは、下の階から順番に卵を落としていくことによって、最大でn階までチェックすることができる。

さて、帰納法を回すためにはm,nについてのfの漸化式が必要になるが、実は以下の事実がわかる。

f(m+1, n+1) = f(m+1, n) + f(m,n) + 1

これはなぜかというと、1回目の試行で卵が割れたか割れないかによってその後調べられる階数が決まるからである。例えば、1回目の試行をL階で行ったとしよう。

卵が割れた場合、求める階数はL以下であることがわかる。なので、 L \lt f(m, n)である場合、正確に割れる階数を求めることができる。（卵が割れているのでm+1がmになっていることに注意）

割れなかった場合、求める階数はLより大きいことがわかる。残りの卵がm+1個、残りの試行回数がn階なので、 f(m+1, n)階分に追加で上の方向を調べることができる。

これを合わせると、 f(m+1, n) + f(m,n) + 1になる。

ここまでくればあとは簡単である。 f(2, n + 1) = f(2, n) + f(1, n) + 1、つまり、 f(2, n + 1) = f(2, n) + n + 1かつ f(2, 1) = 1なので、漸化式を解くことができて、すぐに f(2, n) = \frac{n(n+1)}{2}であることがわかる。

そのあとは f(2, n) \geq 100を解いてやれば無事、 n \geq 14であることがわかる。

この方法の妙は、求める者である「試行回数」を先にこちら側で決めてしまうことだ。そうすることによって「頭の中で」試すことができるようになる。また、この考え方の優れているところは、任意のmとnについて、「何が最小回数なのか」「どうやれば最小回数になるか」も構成的にわかることである。さすがは数学科、というべきであろう。

小学生でも証明できる別解

さて、先程の方法は数学的帰納法（もしくは漸化式）なので高校生でないとわからない。しかし、実は「証明する」だけであれば小学生でもなんと理解できるのだ。

そのためには、「経過」で述べた「1が最大2回まで出現する長さnのビット列」という考え方が重要になる。

卵を落としながらnを求める試行を観察し、「卵が割れた時だけは1、割れなかったら0」というビット列を作ると、同じアルゴリズムを使っている限り、nが違うのであれば違うビット列が対応するはずである。（同じ試行結果で違う階数が対応するのであれば、それは違うやり方であるため）

ということは、「1が最大2回まで出現する長さnのビット列」の「ビット列の種類」が100以下の場合、「n回では（被りが出るので）調べ尽くせない」ということになる。

「1が最大2回まで出現する長さnのビット列が何種類あるか」は組み合わせを計算できるならば小学生でも計算することができる。 n\mathrm{C}_2 + n + 1だ。これが100を超えるのは「n=14」の時であるため、「少なくとも14回は必要」ということがわかる。

...ところで、「14回でできる」ということは先程のブログに書いてあった。この2つを組み合わせることで、「最小の回数は14回である」ということを証明できるのである。ロジックとしては、「不等式で下から評価して、等号が成立していればそれが最小値」というところである。

この方法であれば、（具体的なやり方を思いつかなければいけないが）小学生でも理解ができる。

これを思いついたのは翌日だった気がする。中々気持ちよかった。

終わりに

ということで証明であった。...ところで、「2階から卵を落としたら絶対割れるじゃん！」というのもありだろう。Googleの面接には合格できない気がするが。まあいいか。