Egg Dropping Problem

Suppose you have two eggs and you want to determine from which floors in a one-hundred floor building you can drop an egg such that it doesn’t break. You are to determine the minimum number of attempts you need in order find the critical floor in the worst case while using the best strategy.

  • If the egg doesn’t break at a certain floor, it will not break at any floor below.
  • If the eggs breaks at a certain floor, it will break at any floor above.
  • The egg may break at the first floor.
  • The egg may not break at the last floor.

If the eggs were unlimited, my best strategy would be using Binary Search. That is, we search from the 50th floor. If the egg breaks, we drop it again on the 75th floor. If the egg doesn’t break, we drop it on the 25th floor. Each time, we reduce the difference of the floors by half. By using this strategy, we would only use at most \log_2 {100} \approx 7 eggs and thus 7 attempts.

So, what makes this problem interesting? We have only 2 eggs! Now, I am going to reveal the first attempt of the best strategy, spoilers ahead!

Drop the egg on the 14th floor.

What’s so special about the 14th floor? If the egg doesn’t break on the that floor, that means the critical floor must be below 14. The second step of our strategy would be :

Drop the egg from the 1st to 13th floor.

Following this strategy, our maximum attempts would be 14 (when the eggs broke on all 13 floors). Now, what if the egg doesn’t break on the 14th floor? The strategy is :

Drop the egg on the 27th floor.

If the egg breaks, we need to search only from 15th floor to the 23rd floor, in total of 14 attempts, same as the worst case for when the egg broke on the 14th floor. Have you noticed the pattern yet? If the egg breaks on the 100th floor, we would drop the egg in a sequence of floor 14 \rightarrow 27 \rightarrow 39 \rightarrow 50 \rightarrow 60 \rightarrow 69 \rightarrow 77 \rightarrow 84 \rightarrow 90 \rightarrow 95 \rightarrow 99 \rightarrow 100 .

2 eggs, N floors

Now, we generalize the problem into N floors. Supposed that the maximum attempts for the best strategy is x. Then, we should drop the egg on the x floor, so that if the egg breaks we can apply linear search from the 1st floor to the x-1 th floor. If the egg doesn’t break, we would drop it on floor x + (x-1), x + (x-1) + (x-2) and so on until we reached the highest floor. Recognize this pattern? Yes, it’s an arithmetic sequence summation. The formula is

\displaystyle \frac{x(x+1)}{2} \geq N

We might not reach exactly on the Nth floor, so we need a summation at least greater than N.

The solution for x is trivial. However, the discussion on this problem has not end yet. In the next post, we shall discuss the case for k eggs, N floor and implement the algorithms for it. Stay tuned!

Advertisements
Egg Dropping Problem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s