返回题库

鸡蛋掉落

Egg Drop

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

题目详情

你有两枚完全相同的鸡蛋，置于一栋 100 层的大楼中。你不知道鸡蛋会从哪一层开始摔碎。若在低于第 XX 层的高度扔下，鸡蛋不会碎；否则鸡蛋会碎。问在最坏情况下，为了确定 XX，最少需要扔多少次？

You have two identical eggs in a 100-story building, you don't know the floor the eggs will break on. If an egg is dropped at an elevation under story XX, then the egg will survive; else, the egg breaks. What is the minimum number of drops required to determine XX in the worse-case scenario?

解析

设临界楼层为 XX。关键是让第一枚鸡蛋的试探步长依次递减：先在第 kk 层扔，再在第 k+(k−1)k+(k-1) 层、k+(k−1)+(k−2)k+(k-1)+(k-2) 层继续尝试，依此类推。

如果第一枚鸡蛋在第 ii 次时碎了，那么只需要用第二枚鸡蛋在线性检查前一个区间里剩下的至多 i−1i-1 层。因此，这种策略的最坏情况总扔掷次数就是 kk。

为了覆盖 100 层，需要 1+2+⋯+k=k(k+1)2≥100.1 + 2 + \cdots + k = \frac{k(k+1)}{2} \ge 100.

计算可得： 13⋅142=91<100,14⋅152=105≥100.\frac{13\cdot14}{2}=91<100, \qquad \frac{14\cdot15}{2}=105\ge100.

所以最小可行的 kk 是 14.\boxed{14}.

也就是说，最坏情况下至少需要 14 次。

Original Explanation

Let the unknown critical floor be X.We have two identical eggs and 100 floors.Strategy: Drop first egg at floor k,  k+(k−1),  k+(k−1)+(k−2),  …        (increments k,k−1,k−2,… ).If the first egg breaks on the i-th drop, then you need at most i−1 dropswith the second egg to linearly search the remaining interval.Thus, the worst-case number of drops is k.To cover all 100 floors: k+(k−1)+(k−2)+⋯+1    ≥100.⇒k(k+1)2≥100.Solve: 13⋅142=91<100,14⋅152=105≥100.∴k=14.\begin{aligned} &\text{Let the unknown critical floor be } X. \\ &\text{We have two identical eggs and 100 floors.} \\[6pt] &\text{Strategy: Drop first egg at floor } k, \; k+(k-1), \; k+(k-1)+(k-2), \; \dots \\ &\;\;\;\;\text{(increments } k, k-1, k-2, \dots). \\[6pt] &\text{If the first egg breaks on the $i$-th drop, then you need at most $i-1$ drops} \\ &\text{with the second egg to linearly search the remaining interval.} \\[6pt] &\text{Thus, the worst-case number of drops is } k. \\[6pt] &\text{To cover all 100 floors: } \\ &k + (k-1) + (k-2) + \cdots + 1 \;\;\ge 100. \\[6pt] &\Rightarrow \frac{k(k+1)}{2} \ge 100. \\[6pt] &\text{Solve: } \\ &\frac{13 \cdot 14}{2} = 91 < 100, \\ &\frac{14 \cdot 15}{2} = 105 \ge 100. \\[6pt] &\therefore \boxed{k = 14}. \end{aligned}