Two Eggs and a Hundred Floors
The puzzle
A building has a hundred floors. There is some floor N such that an egg dropped from floor N or below survives, and an egg dropped from any floor above N breaks. An egg that survives a drop is undamaged and can be dropped again.
You have two eggs. Find N while minimising the number of drops you might need in the worst case.
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Dropping every ten floors needs up to nineteen drops. Work out where those nineteen come from and you will see what to fix.
Hint 2
Each time the first egg survives, you have one fewer drop left to spend on the second. The step size should shrink to match.
Show the answer Hide the answer
Fourteen. Drop the first egg from floor 14, then 27, 39, 50, 60, 69, 77, 84, 90, 95, 99 and 100 - each step one floor shorter than the last.
How to get there
Start from the familiar plan: drop the first egg every ten floors, and when it breaks, walk the second egg up from the last safe floor. The worst case is the egg breaking at floor 100 - ten drops to get there, then nine more to check floors 91 to 99. Nineteen. The trouble is that the two halves are unbalanced: early breaks cost little, late breaks cost a lot.
Balance them. If the first drop is from floor k and the egg breaks, the second egg must check floors 1 to k-1 one at a time, so that path costs k drops in total. To keep the worst case at k, the next drop can only go up k-1 floors, the one after that k-2, and so on.
The highest floor reachable is therefore k + (k-1) + (k-2) + ... + 1, which is k(k+1)/2. For that to reach 100 you need k(k+1)/2 >= 100, and k = 13 gives 91 while k = 14 gives 105. So fourteen.
The drops are 14, then +13 to 27, +12 to 39, +11 to 50, +10 to 60, +9 to 69, +8 to 77, +7 to 84, +6 to 90, +5 to 95, +4 to 99, +3 which is past the top so stop at 100. Whenever the first egg breaks, the second walks the gap below it, and the total is fourteen every time.
The technique worth keeping
When a strategy has a cheap branch and an expensive branch, the worst case is the expensive one, and you improve it by moving cost into the cheap branch until the two are equal. The decreasing step size is what equalises them here, and the triangular number falls straight out of it.