返回题库

两球 100 层

strategy that will minimize the number of drops

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

题目详情

你在一栋 100 层楼里有两只玻璃球。若从楼层号小于 XX 的楼层扔下去球不会碎；从楼层号大于等于 XX 的楼层扔下去球一定会碎。

你想确定 XX。什么策略能使“最坏情况”下所需扔落次数最小？

英文原题

You are holding two glass balls in a 100- story building. If a ball is thrown out of the window, it will not break if the floor number is less than X, and it will always break if the floor number is equal to or greater than X. You would like to determine X. What is the strategy that will minimize the number of drops for the worst case scenario?

解析

最优策略是“递减步长”扔：设最坏情况下最多扔 tt 次。

先从第 tt 层扔；若不碎，再从第 t+(t−1)t+(t-1) 层扔；再不碎则加 (t−2)(t-2)，依此类推。

若某次碎了，则剩下一只球，只需在上一次安全楼层与当前楼层之间逐层线性测试；由于步长递减，保证总次数不超过 tt。

要覆盖到 100 层，需要

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

最小满足者为 t=14t=14（14⋅15/2=10514\cdot 15/2=105）。

因此最小的最坏情况扔落次数是 14\boxed{14}，并按步长 14、13、12、… 的楼层序列投掷（到 100 截止）。

英文解析

The optimal strategy is the "decreasing step" approach: assume that in the worst case, the ball will break at most tt times.

First, drop the ball from the tt-th floor; if it does not break, drop it from the t+(t−1)t+(t-1)-th floor; if it still does not break, add (t−2)(t-2)to the floor number, and so on.

If the ball breaks at some point, only one ball remains, so we only need to perform a linear test floor by floor between the last safe floor and the current floor. Because the step size decreases, this guarantees that the total number of drops does not exceed tt.

To cover up to 100 floors, we need:

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

The smallest value satisfying this is t=14t=14 (since 14⋅15/2=10514\cdot 15/2=105).

Therefore, the minimum number of drops in the worst case is 14\boxed{14}, and the floors to drop from follow the sequence of step sizes 14, 13, 12, … (up to floor 100).