You have absolutely identical 2 eggs and empty K-story building. You can throw eggs from any floor and see if it was broken or not. If not, you can reuse it again momentarily. You need to identify the lowest floor, starting from which eggs is broken if thrown (”breaking floor”) in minimum possible steps in worst case.
Solution is here: the-problem-of-eggs-and-a-building.pdf
Artem,
looks like simple binary search will give your log 2 (K) complicity which is much better than sqrt(K)?
Comment by crypto5 — July 27, 2009 @ 12:43 PM
Sorry, meant “complexity”.
Comment by crypto5 — July 27, 2009 @ 12:46 PM
crypto5, for log_2(K) complexity you will need log_2(K) eggs :)
Comment by Artem — July 27, 2009 @ 8:35 PM