Throwing eggs from flooors, general case

82 Views Asked by At

The following problem and its solution is well-known: you have two eggs and you have to measure which is the first floor of a building (that has in this example 36 floors) from which if an egg is dropped it breaks. Find an algorithm the worst case scenario of which involves the smallest number of tries. The solution: throw an egg from the 8th floor, if it breaks throw the second one from the 1st, 2nd... until it breaks. If the first egg didn't break, throw it from the (8+7=) 15th floor, and proceed in similar fashion till the (8+7+6+5+...+1=) 36th floor. From this it is easy to see the general solution for two eggs but what is the case (minimum number of throws required) if we have $n$ eggs?