Two Glass Balls and a 100-Storey Building
You are given two identical glass balls and access to a 100-storey building. There is some threshold floor $X$ (an integer between $1$ and $100$) such that a ball dropped from floor $X$ or any higher floor shatters, while a ball dropped from any floor below $X$ survives and can be reused. A shattered ball is gone. It is possible that $X = 1$ (a ball breaks from every floor). You want to determine $X$ exactly by dropping balls from floors of your choice.
(a) What strategy minimises the worst-case number of drops, and what is that minimum number?
(b) Explain why no strategy can guarantee fewer drops.
Hints
- With only one ball you have to test floors one at a time from the bottom up. With two balls you can use the first ball for coarse jumps and the second ball for a fine scan of the interval where the first one broke.
- If you jump by a fixed step $k$, the worst case is about $100/k + k$ drops. You can do better by shrinking the step after each surviving drop so that the total drops stays constant no matter where the first ball breaks.
- With $n$ drops in the worst case, the first ball can go to floors $n, n + (n-1), n + (n-1) + (n-2), \ldots$, covering $n(n+1)/2$ floors. The smallest $n$ with $n(n+1)/2 \ge 100$ is $n = 14$.
Worked Solution
How to Think About It: The second ball forces a linear scan, so the first ball must be dropped so that whenever it breaks, the linear scan that follows is short enough. Make the worst case the same in every branch: if the first drop is at floor $n$ and it breaks, the scan of floors $1$ to $n-1$ costs $n - 1$ more drops, for $n$ total. If it survives, the next jump should be $n - 1$ floors so that a break there still costs $n$ total, and so on.
Quick Estimate: A fixed step of $10$ gives worst case $10 + 9 = 19$ drops. Decreasing steps do better: $n$ drops cover $n + (n-1) + \cdots + 1 = n(n+1)/2$ floors, so $n = 14$ covers $105 \ge 100$ while $n = 13$ covers only $91$.
Formal Solution:
*Step 1 -- Upper bound: the strategy.* Drop the first ball from floor $14$. If it breaks, test floors $1, 2, \ldots, 13$ in order with the second ball (at most $13$ more drops, $14$ total). If it survives, drop it from floor $14 + 13 = 27$; if it breaks, scan floors $15$ to $26$ (at most $12$ more drops, $14$ total). Continue with steps of $12, 11, \ldots$: the first-ball floors are $$14, \; 27, \; 39, \; 50, \; 60, \; 69, \; 77, \; 84, \; 90, \; 95, \; 99, \; 100 .$$ At each stage, if the first ball breaks on its $j$-th drop, the second ball scans at most $14 - j$ floors, so the total never exceeds $14$. The jumps reach floor $99$ after $11$ drops because $14 + 13 + \cdots + 4 = 99$; if the first ball survives the drop from floor $99$, then $X = 100$ (a twelfth drop from floor $100$ confirms it). Every value of $X$ from $1$ to $100$ is identified within $14$ drops.
*Step 2 -- Lower bound.* Suppose a strategy guarantees at most $n$ drops. Consider the sequence of floors used for the first ball while it survives: $f_1 < f_2 < \cdots$. If the first ball breaks at $f_j$ (its $j$-th drop), the remaining $n - j$ drops must be spent scanning floors $f_{j-1} + 1, \ldots, f_j - 1$ one at a time with the single remaining ball, so $f_j - f_{j-1} - 1 \le n - j$, i.e. $f_j - f_{j-1} \le n - j + 1$. Summing, $f_j \le n + (n-1) + \cdots + (n-j+1)$, and the first ball can be dropped at most $n$ times, so the highest floor that can be resolved is $$f_n \le n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2} .$$ For $100$ floors we need $n(n+1)/2 \ge 100$. Since $13 \times 14 / 2 = 91 < 100$ and $14 \times 15 / 2 = 105 \ge 100$, the minimum is $n = 14$. (A dynamic program over (balls, floors) confirms that the exact optimum for 2 balls and 100 floors is 14.)
Answer: (a) 14 drops. Drop the first ball from floors $14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100$ in turn until it breaks, then scan upward floor by floor with the second ball from just above the last surviving floor. (b) With $n$ worst-case drops the first ball can cover at most $n(n+1)/2$ floors; $13$ drops cover only $91 < 100$, so $14$ is optimal.
Intuition
The first ball buys coarse information and the second ball pays for the fine scan, so the design question is how to balance them. Equal steps waste effort because late breaks cost more; decreasing steps equalise the worst case across all break locations, and the number of floors $n$ drops can cover is the triangular number $n(n+1)/2$. Since $13 \times 14 / 2 = 91 < 100 \le 105 = 14 \times 15 / 2$, fourteen drops are necessary and sufficient. The structure is a resource-constrained search, the same trade-off you face when a probe (a test order, an experiment) is expensive and only a few can fail.