“鸡蛋和100层楼”有关问题的深入思考

“鸡蛋和100层楼”问题的深入思考

鸡蛋和100层楼问题

这个问题是这样的：给你两个一模一样的鸡蛋，假设鸡蛋在L层楼扔下来不会破，在L+1层楼扔下来会破，则鸡蛋的硬度为L（当然，鸡蛋在L层扔下来不破的话在比L低的层次扔下来也不会破，在L层扔下来破的话在比L高的层次扔下来也会破）。

你的任务是用最少的次数来测出这个鸡蛋的硬度。只要得出硬度即可，即使两个鸡蛋最后都碎了。

思路

想必很多人都知道问题的答案是14。做法是这样的：

1）先从14层扔下去。如果破了，只剩一个鸡蛋，此时从1层逐层向上试验。最坏情况下试到13层，这样一共14次就测出硬度来；

2）如果不破，就从14+13=27层扔下去。现在一共试了2次了。如果破了，同理此时只能从15层逐层向上测。最坏情况下试到26层，这样一共2+(26-15+1)=14次；

3）如果还是不破，就从27+12=39层扔下去。如果破了，同样可算出最坏情况下测出硬度的次数为3+(38-28+1)=14次；

4）如果还是不破，就从39+11=50层扔下去。如果破了，同样可算出最坏情况下测出硬度的次数为4+(49-40+1)=14次；

5）如果还是不破，就从50+10=60层扔下去。如果破了，同样可算出最坏情况下测出硬度的次数为5+(59-51+1)=14次；

6）如果还是不破，就从60+9=69层扔下去。如果破了，同样可算出最坏情况下测出硬度的次数为6+(68-61+1)=14次；

7）如果还是不破，就从69+8=77层扔下去。如果破了，同样可算出最坏情况下测出硬度的次数为7+(76-70+1)=14次；

8）如果还是不破，就从77+7=84层扔下去。如果破了，同样可算出最坏情况下测出硬度的次数为8+(83-78+1)=14次；

9）如果还是不破，就从84+6=90层扔下去。如果破了，同样可算出最坏情况下测出硬度的次数为9+(89-85+1)=14次；

10）如果还是不破，就从90+5=95层扔下去。如果破了，同样可算出最坏情况下测出硬度的次数为10+(94-91+1)=14次；

11）如果还是不破，就从95+4=99层扔下去。如果破了，同样可算出最坏情况下测出硬度的次数为11+(98-96+1)=14次；

12）如果还是不破，就从100层扔下去。此时已经测出硬度（破则硬度为99，不破则硬度为100），此时用的次数为12次。

证明

可能很少人会去想，为什么上面的思路是最优的？有没有可能其他做法得到的试验次数更小？这里给出我的一个证明。

假设某种思路下，你得出的结论为最少需要x次试验且x<14。记第k次试验的楼层为Lk，比如第一次实验的楼层为10的话，便是L1 = 10。

我们考虑最坏情况，假设第一次试验的结果为破了，只剩一个鸡蛋，你只能从1层逐层向上测。这样最坏情况下试到L1-1层，一共花费的次数为1+L1-1=L1。

因为最少试验次数为x，所以L1 <= x < 14。

假设第一次试验结果不破，第二次试验结果破了，接下来要逐层试验。注意已经用了2次机会，还剩下不到12次机会。所以同理，为了满足最坏情况下花费的总次数为不超过x，应有L2 < 14 + 12 = 26;

假设第2次试验结果还是不破，同理可以得到L3 < 26 + 11 = 37;

……

假设第12次试验结果还是不破，同理可以得到L < 14 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2  = 91；

假设第13次试验结果还是不破，同理可以得到L < 14 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 92；

注意到没？即使用了13次试验，你还是无法测出硬度出来。这样就证明了14是最优的。

同时以上也证明了思路的最优性质。

14是怎么算出来的

通过以上我们知道，我们的目标，就是要找尽可能小的x，使得从1加到x的和大于等于100。

即 x * (x + 1) / 2 >= 100, 可以解出最小的x便是14.

三个鸡蛋怎么办

到这里，我们可以总结一下。试验楼层选取的间隔是很有讲究的，在两个鸡蛋的例子中我们保持了总次数不会上涨。那对于三个鸡蛋的情况怎么保持？

某次试验后鸡蛋碎了，便剩下两个鸡蛋，这是我们已了解的情形。

给定两个鸡蛋和试验次数n，我们已经知道可以测试的最大楼层数为n * (n + 1) / 2，我们便有下表：

试验次数	1	2	3	4	5	6	7	8	9	10	11	12	13	14
能测的最大楼层数	1	3	6	10	15	21	28	36	45	55	66	78	91	105

顺便也给出1个鸡蛋的表：

试验次数	1	2	3	4	5	6	7	8	9	10	11	12	13	14
能测的最大楼层数	1	2	3	4	5	6	7	8	9	10	11	11	13	14

可以看到，表的第二行便是我们所要控制的楼层间隔。
相信大家已经知道怎么做了吧。

假设从第33层开始测，破了的话便最少需要总次数为8+1 = 9次（查表可知）。接下来的间隔应该就要是28了，这样就可以控制最少总次数不会上涨了。

设最少需要总次数为x，即求解 使得1*2/2 + 2*3/2 + 3*4/2 + … + x(x+1)/2  >= 100 的最小的x。可以解得x = 8。

这里注意的是，与共两个鸡蛋的情况有所不同，比如我们选择对于8次的36，鸡蛋破了，剩下来所需次数是8次，共所需次数是9；而对于共两个鸡蛋的情形，比如我们选择了对于14次的14，鸡蛋破了，剩下来所需次数是13，这里巧合的对应了前一个间隔.。所以大于两个个鸡蛋的情形要额外的增多一次。

所以最终答案应该是9，序列如下：

37，37+28+1=66, 66+21+1=88, 88+15+1=104超过100便取100

N个鸡蛋M层楼怎么办.

现在我们更清楚了，我们由N-1的表可以推出N的表，可以得出结论，记对于实验次数i，j个鸡蛋能测的最大层数为记为L(i, j)，则有：

L(i, N) = L(1, N-1) + L(2, N-1) + … + L(i, N-1)

求解 使得下面不等式成立的最小的x值xmin，N个鸡蛋M层楼所需的最小实验次数便是xmin+ 1.

L(1,N) + L(2,N) + L(3,N) + … + L(x,N) >= M

发觉此片博客 The Two Egg Problem 也分析得很精彩，大家可以去观赏下。

才疏学浅难念疏漏之处，欢迎各路大神指点~