Thursday, August 28, 2008

Problem with a 100 floor building and two eggs

Q: 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. What is the minimum number of drops in the worst case?
You may have following assumptions:
* An egg that survives a fall can be used again.
* A broken egg must be discarded.
* The effect of a fall is the same for all eggs.
* If an egg breaks when dropped, then it would break if dropped from a
higher window.
* If an egg survives a fall then it would survive a shorter fall.

A: let the minimum number be N
#N: 100th floor, if the first egg succeed on 99th floor, we need the last one to test the 100th floor
#N-1: 99th, as we mentioned
#N-2: 97th, here we skip 98th, as when the drop #N-1 failed on 99th, we have the second egg and the #N drop on 98th floor
#N-3: 94th, here we skip 96th, and 95th floors, as if #N-2 drop fails, we can use the second egg starting from 95th floor, and goes up to 96th floor, at most 2 drops would determine the result
#N-4: 90th,
#N-5: 85th,
... ...

therefore, #N-i => 100-1-2-...-i = 100 - i*(i+1)/2 ==> #N-13 =>9th floor, which would be the first drop ==> N = 14.

No comments: