I have the below homework question as an assignment of my Computer Science Foundation class.

Throwing eggs from a building. Suppose that you have an N story building, and plenty of eggs. Suppose also that an egg is broken if it's thrown off floor F or higher, and intact otherwise. First devise a strategy to determine the value of F such that the number of broken eggs is ~lg N when using ~lg N throws, then find a way to reduce the cost of ~2lg F when N is much larger than F.

I'm not entirely sure what the question is asking for. I believe, and what I attempted, is to provide an algorithm as a solution that has a runtime of log N.

From the description of the problem, I attempted to write a binary tree implementation. I'm not sure if this is correct. I'm not asking for an answer, but perhaps some guidance on what the problem is looking for.


In this task, the resources that you care about are not running time, but rather the number of throws and the number of eggs broken (in the worst case). Here is an example. Suppose that $N = 2$. An optimal algorithm, which throws at most two eggs and breaks at most one egg, goes as follows:

  1. Throw an egg from floor 1. If it breaks, the answer is $F=1$. Otherwise, continue.
  2. Throw an egg from floor 2. If it breaks, the answer is $F=2$. Otherwise, the answer is $F=3$.

(If $F=3$ is not a possibility, then we need only one throw.)

In this way, we can determine $F$ using at most $\sim N$ throws and one broken egg. There is a way to improve the number of throws to only $\sim \log N$, at the cost of potentially breaking up to $\sim \log N$ eggs.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.