Two eggs and a 100-floor building

Question

There is a building with 100 floors. There is some threshold floor T such that an egg dropped from floor T or higher breaks, and an egg dropped from any floor below T survives (and can be reused). You have exactly two identical eggs. Find the minimum number of drops that guarantees you can identify T in the worst case.

Accepted Answer

The answer is 14 drops. With only one egg you'd have to go floor by floor from the bottom (a break wastes your only egg), costing up to 100 drops. Two eggs lets the first egg "jump" and the second egg "clean up." Setting up the trade-off. Suppose the first egg's jumps have sizes s1, s2, s3, \dots (first jump to floor s1, next to s1 + s2, etc.). If the first egg breaks on its i-th drop, the second egg must test the si - 1 floors in that block one at a time. So the worst case for that block is i + (si - 1) drops. To make the worst case equal across all blocks, we want i + (si - 1) constant. Tha…

Two eggs and a 100-floor building

Your answer

More Brainteasers questions