返回题库

两枚鸡蛋的 100 层扔蛋问题

Two Eggs Dropping Puzzle

专题
Brainteaser / 脑筋急转弯
难度
L4

题目详情

你在一栋 100 层楼里，有两枚完全相同的玻璃鸡蛋。想找出从哪一层开始扔会碎的临界楼层 NN（即从 NN 层扔不碎、从 N+1N+1 层扔会碎）。

问：为了在最坏情况下保证找到 NN，最少需要扔多少次？

You are in a 100-story building and have two identical glass eggs. You want to find the highest floor from which an egg can be dropped without breaking, which we'll call the "critical floor" NN. What is the minimum number of drops you need to guarantee finding NN in the worst-case scenario?

解析

两枚蛋的经典最优策略是用“递减步长”来平衡两种最坏情况：

第一次从第 tt 层扔。

  • 若碎了，则剩下一枚蛋，只能从 1 到 t−1t-1 线性搜索，最多再扔 t−1t-1 次，总共 tt 次；
  • 若不碎，则下一次从第 t+(t−1)t+(t-1) 层扔；再不碎则加 (t−2)(t-2)，依此类推。

要覆盖到 100 层，需要

t+(t−1)+⋯+1=t(t+1)2≥100.t+(t-1)+\cdots+1=\frac{t(t+1)}{2}\ge 100.

最小满足者为 t=14t=14（因为 14⋅15/2=105≥10014\cdot 15/2=105\ge 100，而 13⋅14/2=91<10013\cdot 14/2=91<100）。

因此最坏情况下最少需要 14\boxed{14} 次。