You have two identical eggs, and are given the task of figuring out the highest floor of a 100-story building from which an egg can be dropped safely (meaning that it doesn't break). You have no prior information about this matter, so for all you know a fall from the first floor might break the egg, but then again, it might be strong enough to survive a 100-story drop.

You need to conduct experiments by dropping the eggs from various levels in the building to solve the problem. You are allowed to break both eggs as long as you come up with an answer.

Find a strategy to minimize the maximum number of drops you would have to do. What is this number? (For example if your strategy is dropping an egg from first, then second, then third floors, and so on until it breaks, the maximum number of drops is 100.)

There are two values that need to be considered - the number of divisions that the first egg drop splits the building into (N), and the size of those divisions (S). For example, dropping on every 50th floor creates 2 division of size 50, while dropping every 20th floor creates 5 divisions of size 20.

N times S needs to equal 100 or greater to catch all the floors, while N plus S needs to be minimized, since that value is equal to one more than the maximum number of drops. The minimum is when N and S are the same; namely, 10.

So the strategy is drop an egg at the 10th floor. If it breaks, drop the other egg at the 1st, 2nd, 3rd, etc. floors until that egg breaks - then you'll know the floor.

If the first egg doesn't break on the 10th floor, drop it off the 20th. If it breaks there, drop the second one off the 11th, 12th, etc.

If the first egg doesn't break on the 20th, repeat this for the 30th, 40th, ... 100th floors. The worst case would be where it breaks on either the 99th or 100th floor, needing 10 drops of the first egg (10, 20, ..., 90, and 100, where it breaks), and 9 drops of the second (91, 92, ..., 98, and 99, where it either breaks or doesn't) If it breaks on the 99th, then it can be dropped 98 floors safely; if not, it can be dropped 99 floors.

Posted by Ender on 2002-10-01 06:46:03