两只玻璃球测 100 层

Glass Balls

专题: Brainteaser / 脑筋急转弯
难度: L4
来源: QuantQuestion

题目详情

一栋楼有 100 层。存在临界楼层 $X$ ：从 $X$ 或更高扔球会碎，从低于 $X$ 扔不会碎。

你有两只完全相同的玻璃球。

问：如何在最坏情况下用最少的投掷次数确定 $X$ ？

A building has 100 floors. You have two identical glass balls that will break if dropped from a certain threshold floor $X$ or higher, and will not break below that floor. You want to find $X$ in the minimum worst-case number of drops. What is the strategy?

解析

最优最坏次数为 14 次。

策略：第一只球用递减步长投掷（14, 27, 39, 50, ...），每次把剩余最坏次数保持为 14。

即第一次在 14 楼，若不碎则上移 13 层；再不碎上移 12 层……直到碎。

一旦碎了，第二只球在上一安全层与碎裂层之间线性逐层试。

因为需要最小 $n$ 使 $1+2+\cdots+n\ge 100$ ，最小 $n=14$ 。

Original Explanation

The worst-case minimum is 14 drops. Drop the first ball at floor $n$ , then $n+(n-1)$ , then $n+(n-1)+(n-2)$ , etc., until it breaks. Suppose it breaks on floor $n + (n-1) + \dots + (n-k+1)$ . Then you use the second ball to test floors one by one within that interval. Solve $n + (n-1) + \dots + 1 \ge 100$ ; the smallest $n$ is 14.