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.)

(In reply to re(2): by Cheradenine)

Actually, you're on the right track. Ender's idea of dividing the 100 floors into "ranges" doesn't account for the fact that with the strategy for division into floor ranges that he is proposing the 90-100 range is more "expensive" than the 1-10 range, and therefore these ranges are not "equal".

For these ranges to be truly equal, we must balance the size of the range witht he "cost" of establishing that the floor we need lies within that range.

So lower ranges should be bigger than higher ranges. This way they are costlier to search thought, but cheaper to reach, and a balance is achieved.

Posted by levik on 2002-10-01 07:46:29