Egg Dropping

From [wu : riddles]

you have two eggs. you need to figure out how high an egg can fall from a 100 story building before it breaks. the eggs might break from the first floor, or might even survive a drop from the 100th floor -- you have no a priori information. what is the largest number of egg drops you would ever have to do to find the right floor? (i.e. what's the most efficient way to drop the eggs and determine an answer?) you are allowed to break both eggs, as long as you identify the correct floor afterwards.

after you've solved the above problem, generalize. define the "break floor" as the lowest floor in a building from which an egg would break if dropped. given an n story building and a supply of d eggs, find the strategy which minimizes (in the worst case) the number of experimental drops required to determine the break floor.