This is the solution to the post I made earlier today. If you aren’t interested in the explanation, feel free to skip to the bottom.
On first appearance, this question looks like something that could be solved via binary search. In other words, you could divide the problem in half by dropping a sphere half-way up, and using that to determine whether to search up or down from that point.
This isn’t a bad solution, especially if the first sphere doesn’t break on the first few drops. A good case for this solution is the following. 5 drops before the first sphere breaks. Floors 50, 75, 88, 95, 98, 100. and then one additional drop to verify that the spheres break on the 99th floor or the 100th floor. 6 drops! not bad. A better case would be that the spheres are super fragile and break on the first floor. Then it would only take 2 drops. One on the 50th floor and one on the first floor. The problem is, we’re solving for the worst case. The worst case is that the sphere breaks on the 49th or 50th floor. Why? Because to verify which floor it breaks on. You drop the first sphere on the 50th floor and it breaks. Then you drop the second sphere 49 additional times (starting from the bottom of the stairs, because you can’t know if one of those lower floors is your actual answer). Worst case? 50 drops. Ouch.
So obviously we can do better. Now lets take my ex co-worker’s (Patrick and Justin’s) solution. This was also my second attempt to answer this question. Drop the first sphere at 10 floor intervals, starting from the bottom. The best case solution for this strategy is 2 drops. First sphere shatters on the 10th floor, and second sphere shatters on the 1st floor. Nice. How about worst case though? Worst case is the 99th or 100th floor. You drop the first sphere on floors 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 and then it shatters. Next you start from the 91st floor and work your way up 91, 92, 93, 94, 95, 96, 97, 98, 99. Worst case performance is 19. Not too shabby. Much better than the first solution. But still not the best.
I failed to make this next intuitive leap, which would have made the solution very apparent to me. Essentially, you need to find a way, such that every time you drop your first sphere, you reduce the number of possible times you’ll have to drop your second sphere. But you don’t need to be greedy. You don’t have to reduce the number of times you drop the second sphere by a lot. Just by a little. Only one less in fact.
But how can I reduce the number of times I have to drop the second sphere? Simple. Reduce the number of floors between each drop of the first sphere. If I drop the first sphere on the Nth floor and it breaks. Then my worst case is N-1 drops of the second sphere. 1 drop + N-1 drops = N drops.
If it doesn’t break on the Nth floor, then I know none of the floors below it have to be checked, but I’ve used one of my drops. So my next drop will occur from N -1 floors above the Nth floor. If it shatters now, then my worst case is N-2 drops of the second sphere. 2 drops + N-2 drops = N drops.
Now if it still hasn’t broken, I can just continue this pattern, by going up N-2 floors, then N-3 floors etc… until I reach the 100th floor. We effectively have a way to keep the worst case performace constant! Using this strategy and working backwards you can find that the best “N” to start from is 14. This is because 1+2+3+4+5+6+7+8+9+10+11+12+13+14 = 105. If N is too small to start out with then your interval will reach zero before you reach the top of the building, and you’ll have to make up the difference with extra drops.
Solution
So the final solution is to start on the 14th floor and drop a sphere. Then as long as the first sphere doesn’t break, move up the building in intervals that shrink by 1 floor. Once it breaks, start from the floor above the last place you dropped a sphere from that didn’t break and move your way up. Your worst case will always be 14 drops.
Later –
Joe
