You have three eggs that are "unbreakable." You believe this claim to be nonsense and would like to test it. You want to see how high the egg's shells can withstand. Because this is in the distant future, you live in a building 1,000,000 stories tall. Because you're not made of time, you'd like to do this as quickly as possible.

What's the best strategy for determining exactly how high you can drop an egg from?

Hint (Highlight to read):
Binary search has a worst case of nearly 250,000, you can do much better than that. You know you're on the right track when your worst case is around 300, you'll know you have it when you're even less than that.

Answer:
The optimal strategy is not the one that follows. But it is LIKE the one that follows so you should read it over first and understand it.

First: Go to floor 10,000, test, if it breaks the move to the second stage of the strategy, if it doesn't, move up to floor 20,000, repeat.

Second: When you have one broken egg, move down 9,900 floors (to floor X0,100) and tests floors in multiples of 100 until the egg breaks.

Third: When the second egg breaks, move down 99 floors, and test the floors one at a time going up until the egg breaks.

But as it turns out, there is an even more optimal strategy than that. So what can we do to make the worst case better? Well right now there's a worst case penalty imposed whenever you go up floors. You're doing more testing without making the search space smaller.

It relies on triangle and tetrahedral numbers. Triangle numbers are like factorals for addition. 1, 1+2, 1+2+3, etc. They start out as 1, 3, 6, 10, 15, 21. Tetrahedral numbers is what you get when you add up the triangle numbers in the manner. 1, 1+3, 1+3+6... They start out as 1, 4, 10, 20, 35, 56...

To solve this let's consider 100 floors with two eggs. Our solution before would have us start at the 10th floor, then go up another 10 every time until the first egg broke. Worst case would be 19 attempts.

Using the formula 1/2(n)(n+1) for triangle numbers. The first triangle number larger than 100 is 14th (105). So we test the 14th floor. If it breaks then we go up 13 floors, then 12. So our worst case scenario is 14 tests. Rather than 19. I'll state that as a fact. The reason why should be obvious to the most casual observer.

So if we know that triangle numbers are the most efficient way to run the second stage in our three egg run, then we know that the first stage should be something similar. So we turn to tetrahedral numbers. Our plan is tetrahedral numbers -> triangle numbers -> natural numbers.

So finally, the solution is:

Phase 1: Using the formula 1/6(n)(n+1)(n+2) for tetrahedral numbers. The first tetrahedral number larger than 1,000,000 is the 181st (1,004,731). So we find the 181st triangle number, which is 16,471, and go to that floor. Test the egg. If it breaks move to phase 2. If it doesn't break, we move up 16,290 floors (this is the 180th triangle number) to floor 32,761. Test the egg. Etc.

Phase 2: Go back down to the last floor successfully tested. Using the formula 1/2(n)(n+1) for triangle numbers, we need to figure out the applicable number of floors to go up based on our search space. The good thing is this time the number will always come out round because of our floor choices in phase one. In fact, if you went up by the nth triangle number the last time, you should go up n floors. So let's say your egg broke on floor 32,761. You go back down to floor 16,471 then up 180 floors, then 179, etc. When your second egg breaks move to phase 3.

Phase 3: Go back down to the last floor successfully tested. Using the formula n for natural numbers (haha), we go up one floor at a time until the egg breaks.

Worst case for this method is 181 drops. Which is much better than the 298 drops for the other method, and way, way better than the 250,001 drops for the binary search.

Woah. How'd you get the tetrehedral number idea?

I wanted to keep the worst case and best case as close to the same as possible. Because the way to do that with 2 eggs is with triangle numbers, I wanted to chose the floors such that after the first egg broke I'm left with a triangle number of floors left. The obvious way to do this is through tetrahedral numbers.

Maybe I'm misunderstanding the problem, but I thought the easiest way would be to find the terminal velocity of the eggs.

Quiet you. RABBLE RABBLE.

That assumes the building isn't in a vacuum. This is, after all, the future with million-story buildings.

Because they're unbreakable, drop one from the top story. When it doesn't break, you're done.

How're you accounting for the stresses of the previous drops, anyway? :)

Except, when it does break, now you have to take way longer to find the floor.



Time Travel.

You have proven the claim false, though, which I thought was the main goal. Yesterday, via time travel.

I think this is the top three use of triangular numbers in history though.

Correct me if I'm wrong, but I believe there's a much simpler and more effective solution. I'm not sure if this method is what you're referring to when you say binary search, but if it is, then I think the worse case would be 20 drops, not 250,000, and the best case would also be 20. One could just start on the 500,000th floor and drop one. If it breaks, you move to the 250,000th floor, and if it doesn't, you move to the 750,000th. Then you drop another one, and (let's assume the first one broke and you're on the 250,000th floor) if it breaks, you move to the 125,000 floor. If not, go to the 375,000th floor. You continue in this fashion, and each time you cut the potential space in which the maximum dropping distance might be by half. After 10 drops, you'd have narrowed it down to under 1000 floors (1,000,000/(2^10)=976.5). After 20 drops, you'll know it exactly. Am I missing something here?

Doing a binary search as you've described, if you get 3 breaks in a row, you only know that the egg cannot withstand a drop from 125k floors. And you have no more eggs to test with.