Two Egg Problem Solution

30.07.2015 |

Episode #10 of the course “Challenging logic puzzles”

Using The Binary Search Method

Your first instinct (especially if you are a programmer) may be to solve this problem using the binary search method. So, you think that maybe by dividing the “result set” in half each time you will be able to solve the problem and find the threshold floor for the eggs. In this case the “result set” is the floors in the building, so you start at floor 50 since that is half of 100.

Let’s say we do start at the 50th floor, then what should we do if the egg breaks? This means that the answer is somewhere between the first and 50th floor. And we would be left with only 1 more egg since we started with 2 eggs. Now if we are following the binary search method, it seems that the next step would be to try dropping the remaining egg from the 25th floor. But what if it breaks at the 25th floor? Then we really don’t have an answer to the problem since we have not found the threshold floor for the eggs. Even if it doesn’t break and we decide to go to the next floor (which would be half of 25 or 12.5, which is approximately 13), then if it breaks at the 13th floor then we would still not have an answer to the problem.

Clearly the binary search method does not work for us here, because we only have 2 eggs. The binary search method would be good in a scenario where we have an infinite number of eggs, but we now have to change our strategy and find a better solution.

A new solution

Since we have to find the answer with 2 eggs then why not do something like this: we start by dropping one of the eggs on the 10th floor: if it doesn’t break then we continue on to the 20th floor, then 30th, 40th… up to 100 in intervals of 10 until the first egg actually breaks. If the egg breaks on the 10th floor then we know that the threshold floor must be either the 10th floor or one of the floors below it – the egg will definitely break on any floor above the 10th floor, so we can eliminate all of the floors above the 10th.

If the egg breaks on the 10th floor…

So, the answer must be between floors 1 through 10. We can take the 2nd egg and drop it from the first floor. If it does not break on the first floor, but it does break on the 2nd floor, then we know that the 2nd floor is the “threshold” floor. And if it doesn’t break on any of the floors between 2-8, then we just continue up until the 9th floor, and if it does not break on the 9th floor then we know that the 11th floor is our threshold floor. This will take a maximum of 10 drops to figure out the threshold floor in this instance.

What about the worst case solution? Well, the worst case using this method occurs when the threshold floor is the 100th floor. This means that we use 10 drops to get to the 100th floor, because we start from the 10th floor and go up in intervals of 10 up to the 100th floor, and the first egg will break on the 100th floor. And then we use another 9 drops with the 2nd egg because we have to test floors 90-99 to see if the threshold floor is somewhere in that range. This gives us a total of 19 drops, which is the absolute worst case scenario using this method.

Use the linear search method for this brainteaser

The simple search method we used above is called a linear search – which is simply a sequential search to find a particular value in a list of elements. In this case, the list of elements are floors in a building, and the value we are searching for is the threshold floor in that building for the eggs.

It should be clear to you now that a linear search is indeed necessary with the 2nd egg because we can not risk breaking the 2nd egg before we even find the answer – remember we only have 2 identical eggs and we must find the answer with only 2 eggs. This means that we have some freedom with the 1st egg, and that we can do some interesting work with it. So, now the question is can we improve upon the 19 drops used in the worst case scenario with our approach above?

2 Eggs 100 Floors Puzzle Solution

We want to minimize the number of drops for the worst case, while still using an approach that works well for other scenarios. So, how can we do this? Well, we should rephrase that question and ask ourselves what is really holding us back here? The main reason why it takes such a large number of drops in the worst case with our approach above (19 drops) is because in order to test out the higher floors of the building we have to start at the lower floors of the building, and at that point we have already used a large number of drops just to get to that point.

What we should try to get with our next approach is to try to reduce the worst case scenario by trying to make all possible scenarios take the same number of drops.

What if we tried to reduce the number of drops that would be required with the linear search (with the 2nd egg) after we get to one of the higher floors? This way we counteract the fact that getting to the higher floor took so many drops, and if we use less drops for the linear search we are balancing out the worst case.

Let’s try to figure this out using some simple algebra. Suppose we drop an egg from floor x. If the egg breaks, then we would have to go through the previous x-1 floors one by one using a linear search.

But, if the egg doesn’t break, in our original algorithm we would go up x floors to find the next floor to test from. Why not just go up x-1 floors instead of x floors? This would save us 1 drop if we have to do a linear search with the 2nd egg whenever the first egg breaks – because we would be doing the linear search from floors x+1 to floor ( (x+1) + (x-1)) instead of floors x+1 to floor (x+1) + x. So, that is 1 less egg drop. This means that the next floor that should be attempted to drop from is x + (x-1) if the egg does not break from floor x. And by the same reasoning the floor after that would be x + (x-1) + (x-2) if the egg does not break on floor x + (x-1).

This would go on to form a series that looks like this:

x + (x-1) + (x-2) + (x-3) + … + 1

The series above is what’s called a triangular series which is equal to x(x+1)/2. Because there are 100 floors in the building, we set the sum equal to 100 to solve for x:

x(x+1)/2 = 100

When the sum of the series above equals 100, we get x = 13.651, which rounds up to 14. This means that we should start from floor 14 (which is our x) and then move up x-1 (13) floors to floor 27 if the egg doesn’t break and then move up x-2 (12) floors to floor 39 and so on if the egg still does not break.

This is the number of drops required as we move up the floors in the building:

Screenshot 2015-07-29 12.05.30

2 Eggs 100 Floors Worst Case Solution

The solution for the worst case in this scenario occurs when the threshold floor is floor number 14 – because we will drop the first egg on floor 14, and it will break. Then we have to test floors 1-13 with the 2nd egg to see where the egg breaks again, and the egg will not break on any of those floors. But since the egg broke on the floor 14, we can conclude that the threshold floor is floor number 14.

 

Recommended book

“399 Games, Puzzles & Trivia Challenges Specially Designed to Keep Your Brain Young” by Nancy Linde

 

Share with friends: