You have two identical eggs and access to a 100-story building. Eggs can be very resistant or very fragile. Both are identical. You need to determine the highest floor from which an egg can be dropped without breaking. What is the MINIMUM number of throws you need in the WORST case to guarantee you find the critical floor?
Microsoft Classic
Home > Riddles > The 100-story building and the two eggs
The 100-story building and the two eggs
Hints
Show hints
- When the first egg is broken, the second searches floor by floor in the immediately preceding section.
- This produces the sequence of floors: 14,27,39,50,60,69,77,84,90,95,99,100.
- Optimality condition: find the smallest $k$ such that $1+2+\cdots+k=\frac{k(k+1)}{2}\ge 100$.
Solution
Show full solution
Answer: 14 launches in the worst case.
Optimal strategy (decreasing jumps):
If the first egg breaks in a jump, with the second you must linearly sweep the previous block. To match the worst case, the jumps are made of decreasing size:
$$ 14,13,12,11,\ldots $$
This produces the sequence of floors:
$$ 14,27,39,50,60,69,77,84,90,95,99,100. $$
When the first egg is broken, the second searches floor by floor in the immediately preceding section.
Optimality condition:
We need the smallest $k$ such that
$$ 1+2+\cdots+k=\frac{k(k+1)}{2}\ge 100. $$
- For $k=13$: $\frac{13\cdot 14}{2}=91<100$ (insufficient).
- For $k=14$: $\frac{14\cdot 15}{2}=105\ge 100$ (sufficient).
Therefore, the worst case guaranteed minimum is 14.
Related riddles
Keep practicing
If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.