扔鸡蛋

经典题型——⾼楼扔鸡蛋确定鸡蛋破碎的临界楼层

问题：100层⾼楼，有两个完全⼀样的鸡蛋，假设从某⼀层上扔鸡蛋，恰好会破碎。通过最优策略找到使得鸡蛋破碎的临

界层需要扔多少次？

⼀、问题解读。

1.⾸先梳理题⼲。

从楼上投掷鸡蛋有两种结果，⼀种是破碎，⼀种是完好。

如果只有⼀个鸡蛋，只能从第⼀层开始投掷，如果第⼀层不碎，继续从第⼆层开始投掷，直到第N层恰好鸡蛋破碎，则需要N次确定鸡蛋恰好破碎

的临界层。

那么现在有两个鸡蛋，第⼀个鸡蛋为A，第⼆个鸡蛋为B，A先使⽤，当A破碎后B再使⽤，猜想这两个鸡蛋分别有什么作⽤？如何投掷才能最快知

道这个临界层呢？

2.为了更深刻理解题意，以及探索A与B分别起什么作⽤，尝试采⽤⼆分法。

①假设将（1,100）分为两个区间（1,50），（50,100）。

在50层投掷鸡蛋A，如果A破碎，则确定临界层在（1,50）范围。那么B只能从第1层开始投掷，直到找到临界层，这样次数达到50次之多。那么

B为什么不能从25层开始投掷呢，因为只有两个球，如果B在25层破碎，那么（1,24）这个范围是否包含临界层不得⽽知。

同样在50层时A没有破碎，那么确定临界层在（51-100）范围。B只能从51层开始投掷。

综上所述，将（1,100）分为两个区间（1,50），（50,100），在最坏的情况下，需要投掷50次，使得⽆法快速找到临界层。

②假设将（1,100）分为10个区间（1,10），（10,20），…，（90,100）。取10,20,30，...，80,90作为A鸡蛋每次投掷的层数，如果A第⼀次

在10层投掷未碎，则第⼆次在20层，依次类推。

如图1所⽰：

图1

从图中可以得到：

.⽆论鸡蛋A每次从以上哪层投掷，在最坏情况下鸡蛋B投掷的次数都是9(不包括第100层)⽽鸡蛋A在最坏情况下需要投掷9次，总的次数为

9+9=18.。第100层不需要投掷，由题⼲⽽知会碎。

.采⽤该⽅法，A投掷且破碎的次数是包含于范围（1,9）,是线性递增的，B的次数是固定的为9,两者不相关联。

③得出两个结论：

.如果采⽤多区间均分的⽅式，则A投掷且破碎的次数线性递增，B的次数固定，且关联性缺乏规律，⽆法找到最优解。

.鸡蛋A的作⽤是确定临界层的区间，鸡蛋B的作⽤在该区间查找临界层。

那么是否存在⼀组数据，A1,A2,A3...An，使得鸡蛋A在A1,A2,A3...An层投掷时A的次数，与在最坏情况下鸡蛋B投掷的次数相关联

且有规律?

⼆、提出假设。

假设在最坏情况下，A投掷的次数是A(k),B投掷的次数是B(k)。总的次数是K(K∊N)。

其中A(k)<=K,B(k)

存在K，使得三者存在⼀种关系：A(k)+B(k)=k.

三、推导。

如图2所⽰：

图2

①如果第1次A在A1层破碎，则A1,B1，K满⾜以下条件。

B1=K-1

A1=K

此处A1=K是为什么呢？。

推导如下：

A第⼀次在A1层投掷破碎，A的投掷次数为1。

则总的投掷次数为：B1+1=K=>B1=K-1

因此只有当A在第K层破碎时才满⾜B1=K-1。

②如果第1次A没有在A1层破碎，则第2次最坏情况下即A在A2层投掷且破碎，则A2,B2，K需要满⾜以下条件。

B2=K-2.

A2-A1-1=B2=K-2=>A2=A1+K-1.

③如果第2次A没有在A2层破碎，则第3次最坏情况下A在A3层投掷且破碎，则A3,B3，K满⾜以下条件。

B3=K-3.

A3-A2-1=B3=K-3=>A3=A2+K-2=>A3=K+K-1+K-2.

同理第n（n<=K）次时当且仅当n=K时，A(K)=K+K-1+K-2+K-3+...+2+1=>K(K+1)/2

结果如图3所⽰

图3

可得出：K(K+1)/2>=100

得出K>=14

依次为A每次投掷的层数为14,27,39,50,60,69,77,84,90,95,99,102,104,105.

四、结论。

最优策略：

第⼀步：A第⼀次从第14层开始投掷，如果破碎，B在（1,13）范围内由低层到⾼层开始投掷，直⾄找到临界层。

第⼆步：如果A没有在14层破碎，则第⼆次从27层开始投，然后⼜分为是否破碎两种情况，同理第⼀步，直到找到临界层。

综上所述，100层楼⾼，在最坏情况下，两鸡蛋⾄少需要投掷14次才能确定临界层。

五.其他算法

现在已知初始状态：鸡蛋数量和楼层数，以及在投掷鸡蛋是否破碎条件下如何选择。可知符合动态规划法的条件。

那么是否能采⽤更加“省事”的算法例如动态规划法解决问题呢？

下次探讨。