Table of Contents
题目
为了给广告宣传做准备，Flightless Ostrich Farm需要测试它们的鸵鸟蛋到底有多结实。
关于蛋壳硬度，有一个“世界标准”：用这枚蛋从帝国大厦的不同楼层扔下，能承受而不碎的最高楼层，就定义为它的等级。
农场的测试员Oskar发现，如果他去纽约时只带一枚蛋，那么在最坏情况下，他必须从第\(1\)层开始一层层往上试，最多要试完整栋楼的\(102\)层。
那么如果他带两枚蛋，最坏情况下最少需要扔多少次？
分析
答案是\(14\)次。
关键在于：如果第一枚蛋在某一层摔碎了，第二枚蛋就只能在这层以下一层层线性试。所以第一枚蛋的投掷楼层不能等间隔安排，而要让“碎掉之后剩下可能需要补试的层数”逐步减少。
设最坏情况下总共允许扔\(n\)次。
第一次先在第\(n\)层扔第一枚蛋。
- 如果碎了，那么第二枚蛋只需检查第\(1\)层到第\(n-1\)层，最多再扔\(n-1\)次，总次数正好不超过\(n\)。
- 如果没碎，第二次就应再往上走\(n-1\)层，也就是到第\(n+(n-1)\)层。
为什么第二次只加\(n-1\)层？因为如果这一次碎了，那么下面还剩\(n-2\)次机会给第二枚蛋逐层检查，所以这一次跨过的新增楼层数最多只能是\(n-1\)。
照此继续，第一枚蛋的测试楼层应当依次是\(n, n+(n-1),n+(n-1)+(n-2),\dots\)。
这样无论第一枚蛋在哪一步碎掉，最坏情况下总次数都不会超过\(n\)。
帝国大厦有\(102\)层，那么：\(1+2+\cdots+n=\frac{n(n+1)}{2}\ge102\)。
简单试一下：
\[ \frac{13\cdot14}{2}=91<102, \qquad \frac{14\cdot15}{2}=105\ge102.\]
因此最小的\(n\)是\(14\)。
一种具体策略是把第一枚蛋依次从这些楼层扔下：\(14,27,39,50,60,69,77,84,90,95,99,102\)，而这些楼层之间的间隔依次是\(14,13,12,11,10,9,8,7,6,5,4,3\)。
例如，如果蛋在\(69\)层第一次摔碎，那么已知它在\(60\)层不碎，于是只需用第二枚蛋检查\(61\)到\(68\)层，最多再试\(8\)次；而此前第一枚蛋已经试了\(6\)次，总共仍是\(14\)次。
所以最坏情况下最少需要\(14\)次。
推广：两枚蛋的通用公式
如果楼高不是\(102\)层，而是一般的\(H\)层，那么两枚蛋、最坏情况下所需的最少投掷次数，就是满足\(\frac{n(n+1)}{2}\ge H\)的最小正整数\(n\)。
把它解出来，就是
\[ n=\left\lceil\frac{\sqrt{8H+1}-1}{2}\right\rceil.\]
也就是说，两枚蛋问题的本质就是找最小的三角数，使它至少覆盖全部楼层数。
再问：如果有三枚蛋
如果有三枚蛋，情况会更好。设\(F_k(n)\)表示有\(k\)枚蛋、最多扔\(n\)次时，最坏情况下最多能确定多少层。
每次先选一层扔一枚蛋：
- 如果碎了，那么楼下的问题变成“还剩\(k-1\)枚蛋，还能扔\(n-1\)次”，所以最多还能处理\(F_{k-1}(n-1)\)层。
- 如果没碎，那么楼上的问题变成“还剩\(k\)枚蛋，还能扔\(n-1\)次”，所以最多还能处理\(F_k(n-1)\)层。
再加上当前这一层，于是有递推式\(F_k(n)=F_{k-1}(n-1)+F_k(n-1)+1\)。
对三枚蛋来说，递推式就是
\[ F_3(n)=F_2(n-1)+F_3(n-1)+1.\]
这一步更直观的看法是：把允许投掷次数从\(n-1\)次增加到\(n\)次时，三枚蛋最多能多处理多少层？答案正是
\[ F_3(n)-F_3(n-1)=F_2(n-1)+1.\]
原因是：第一次扔在某一层，如果碎了，下面那一段最多只能交给“两枚蛋、还剩\(n-1\)次”的情形去处理，也就是\(F_2(n-1)\)层；再算上当前这一层，总共新增\(F_2(n-1)+1\)层。
而我们已经知道
\[ F_2(n-1)=\frac{(n-1)n}{2}.\]
所以每多给一次机会，三枚蛋所增加的可处理楼层数依次是
\[ 1,2,4,7,11,\dots\]
因为
\[ F_3(n)-F_3(n-1)=1+\frac{(n-1)n}{2}.\]
把前几项写出来就很清楚：
\[ F_3(1)=1, \quad F_3(2)=1+2=3, \quad F_3(3)=1+2+4=7, \quad F_3(4)=1+2+4+7=14.\]
一般地，就是把这些增量累加：
\[ F_3(n)=\sum_{t=1}^n\left(1+\frac{(t-1)t}{2}\right).\]
先把它展开、合并：
\[ F_3(n)=n+\frac{1}{2}\sum_{t=1}^n(t^2-t).\]
利用
\[ \sum_{t=1}^n t=\frac{n(n+1)}{2}, \qquad \sum_{t=1}^n t^2=\frac{n(n+1)(2n+1)}{6},\]
可得
\[ F_3(n)=n+\frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)}{2}\right).\]
继续化简：
\[ F_3(n)=n+\frac{n(n+1)(n-1)}{6}=\frac{n^3+5n}{6}.\]
回头再看，这个结果还恰好可以写成
\[ F_3(n)=n+\frac{n(n-1)}{2}+\frac{n(n-1)(n-2)}{6}=\binom{n}{1}+\binom{n}{2}+\binom{n}{3}.\]
因此在\(102\)层的情况下，只需找最小的\(n\)，使\(\frac{n^3+5n}{6}\ge102\)。
检验可得
\[ F_3(8)=\frac{8^3+5\cdot8}{6}=92<102, \qquad F_3(9)=\frac{9^3+5\cdot9}{6}=129\ge102.\]
所以如果有三枚蛋，最坏情况下最少只需要\(9\)次。
更具体地说，可以用一种逆推的办法来安排三枚蛋的投掷楼层。
既然三枚蛋时最坏情况允许\(9\)次，那么第一次扔完之后，若碎了，还剩两枚蛋和\(8\)次机会；而两枚蛋、\(8\)次最多能处理的楼层数是
\[ \frac{8\cdot9}{2}=36.\]
所以第一枚蛋可以先在第\(36\)层扔。
如果第\(36\)层没碎，那么此后若第二次摔碎，还会剩下两枚蛋和\(7\)次机会；而两枚蛋、\(7\)次最多能处理\(\frac{7\cdot8}{2}=28\)层，所以第二次可在第\(36+28=64\)层扔。
同理，第三次再往上加\(\frac{6\cdot7}{2}=21\)层，到第\(85\)层扔；再下一次加\(\frac{5\cdot6}{2}=15\)层，到第\(100\)层扔。
也就是说，本题中若三枚蛋一直都没碎，可以依次在第\(36,64,85,100\)层测试；若到第\(100\)层还没碎，那么上面只剩第\(101\)层和第\(102\)层，再继续测试即可。
这种写法的本质，就是把“两枚蛋在剩余次数下最多能处理多少层”依次算成\(36,28,21,15,10,6,3,1\)，再逐步往上累加。它们的和是
\[ 36+28+21+15+10+6+3+1=120,\]
已经超过\(102\)，所以三枚蛋用\(9\)次足够。
如果蛋的数量不限
如果蛋的数量不限，那么就不必再担心“摔碎以后只剩很少的蛋可用”这个限制了。每次都可以直接在当前尚未确定的楼层区间中点测试：
- 如果碎了，就说明临界楼层在更低的一半；
- 如果没碎，就说明临界楼层在更高的一半。
这样每扔一次，待确定的范围大约缩小一半，所以这时问题就变成了最普通的二分法。
对\(102\)层来说，最坏情况下所需次数大约是\(\lceil\log_2 102\rceil=7\)次。
也就是说，蛋越多，策略就越接近二分查找；而两枚蛋、三枚蛋这些情形之所以更麻烦，正是因为必须同时兼顾“当前这次是否会碎”和“碎了以后手里还剩多少枚蛋”。