# Dropping eggs (**)

You have two identical eggs with unusually strong shells, and a building that is N stories high. Assume floors are numbered using the American style (1..N) and that you test an egg on the n'th floor by dropping it from the top (ceiling) of that floor. You want to find the highest floor you can drop one of these eggs from without it breaking. How do you do this? Assume that if the egg doesn't break that it hasn't been weakened, and that it is OK if both of the eggs are broken when you have the answer, so long as you know exactly which floor it is safe to drop an egg from.

This problem has several variants. In an ascending order of difficulty here are several:

**100 Floors, Worst Case** Two eggs, N = 100. Specify parametrically or exactly which floors you should drop the eggs from so that in the worst case the number of drops is minimised.

**N Floors, Worst Case** Two eggs, N floors, where N is some positive integer greater than 2. Specify parametrically which floors you should drop the eggs from so that in the worst case the number of drops is minimised.

**100 Floors, Average Case** Two eggs, N = 100. Assume that the probability of an egg dropped from the n'th floor breaking is n/100. Specify parametrically or exactly which floors you should drop the eggs from so that the in the average case the number of drops is minimised.

**N Floors, Average Case** Two eggs, N floors, where N is some positive integer greater than 2. Assume that the probability of an egg dropped from the n'th floor breaking is n/100. Specify parametrically which floors you should drop the eggs from so that in the average case the number of drops is minimised.

**Extension 1:** In each case, for each problem, prove that your answer is correct.

**Extension 2:** The above problems, but optimise for the number of floors climbed up and down, rather than the number of drops.

Solving them in the order given is probably the easiest way to address the problem. You might also want to solve some sort of intermediate problem in between the cases where N = 100 and where N is least constrained. For example, solving N = 5M (ensuring that N is a multiple of 5) might suggest the general solution. Or it might not.