两球 100 层：最小化最坏情况扔落次数的策略

strategy that will minimize the number of drops

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

题目详情

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

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

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?

解析

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

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

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

要覆盖到 100 层，需要

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

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

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