Drop egg to find the threshold for breaking

There is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.

My initial thoughts:
This is similar as binary search. If we have unlimited number of eggs, we only need 7 (\log_{2}100) to find N. But we only have 2 eggs. We can then still do binary search until the egg breaks, then do a linear search. Let us assume N = 78. We then do as follows:

  1. Drop a egg from level 50. The egg does not break. We then know N is between 51 to 100.
  2. Drop the egg from level 75. The egg does not break. We then know N is between 76 to 100.
  3. Drop the egg from level 88. The egg breaks. We then know N is between 76 to 87.
  4. Drop the egg from level 76. The egg does not break. We then know N is between 77 to 87.
  5. Drop the egg from level 77. The egg does not break. We then know N is between 78 to 87.
  6. Drop the egg from level 78. The egg break. We then know N is exactly 78.

This works fine for some number. But assume N = 49. The first drop will break the egg. So we know N is between 1 to 49. We then need to drop the second egg for 49 times until we find N = 49.

Solutions:
Goal: Create a system for dropping Egg1 so that the most drops required is consistent, whether Egg1 breaks on the first drop or the last drop.

  1. A perfectly load balanced system would be one in which Drops of Egg1 + Drops of Egg2 is always the same, regardless of where Egg1 broke.
  2. For that to be the case, since each drop of Egg1 takes one more step, Egg2 is allowed one fewer step.
  3. We must, therefore, reduce the number of steps potentially required by Egg2 by one drop each time. For example, if Egg1 is dropped on Floor 20 and then Floor 30, Egg2 is potentially required to take 9 steps. When we drop Egg1 again, we must reduce potential Egg2 steps to only 8. That is, we must drop Egg1 at floor 39.
  4. We know, therefore, Egg1 must start at Floor X, then go up by X-1 floors, then X-2, …, until it gets to 100.
  5. Solve for X+(X-1)+(X-2)+…+1 = 100 X(X+1)/2 = 100 -> X = 14.

Hence, We go to Floor 14, then 27, then 39, … This takes 14 steps maximum.

Advertisements

1 Comment (+add yours?)

  1. Ishaan
    May 26, 2012 @ 17:06:39

    Thanks for following up on this. I initially thought of the same log solution as well but turns out the one listed in solutions works better for all cases.

    Cheers

    Reply

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

%d bloggers like this: