2 Eggs 100 Floors puzzle

Suppose that there is a building with 100 floors. You are given 2 identical eggs. The most interesting property of the eggs is that every egg has it’s own “threshold” floor. Let’s call that floor N. What this means is that the egg will not break when dropped from any floor below floor N, but the egg will definitely break from any floor above floor N, including floor N itself.

For example, if the property of the eggs is that N equals 15, those eggs will always break on any floor higher than or equal to the 15th floor, but those eggs will never break on any floor below floor 15. The same holds true for the other egg since they are identical.

These are very strong eggs, because they can be dropped multiple times without breaking as long as they are dropped from floors below their “threshold” floor, floor N. But once an egg is dropped from a floor above it’s threshold floor

Here is the puzzle: What strategy should be taken in order to minimize the number of egg drops used to find floor N (the threshold floor) for the egg? Also, what is the minimum number of drops for the worst case using this strategy?

Remember that you are given 2 identical eggs which both have the same exact threshold floor.

Solution:

Here, we will discuss various approaches and try to improve the solution. Our main objective is to improve the worst case.

Approach 1: If you start from floor 1, if it doesn't break then floor 2 and so on.
Worst number of attempts needed = 100. So,
Worst case = 100
Best case = 1
But, we are not using 2 eggs. 

Approach 2: What if proceed like floor no. 2, 4, 6, ... so on.
Worst Case: 51
Best case: 2

Approach 3: 5, 10, 15 , ....
If it breaks on 5th floor, try 1, 2, 3 & 4. So in this case 5 attempts needed.
If it breaks on 10th, try 6, 7, 8 &9. ==>  6 attempts needed in worst case.
Similarly the worst case is if 100th floor is the threshold. It doesn't break till 95(19th attempt), breaks at 100th(20th attempt). We try 96, 97, 98 & 99.So, 
Worst case = 24.
Best case = 5 (actually 2, if threshold floor is 1).

So, we see that we have significantly improved the worst case from 100 in approach 1, to 51 in approach 2 , to 24 in approach 3. Thus, we are moving in the right direction. 
Lets try to increase the step size further to 10.

Approach 4: 10, 20, 30, .....
If it breaks at floor 10, try 1, 2, 3,...  9 = 10 attempts needed.
If it breaks at floor 20, try 11, 12, ..19 = 11 attempts
If it breaks at floor 30, try 21, 22, ..29 = 12 attempts
If it breaks at floor 40, try 31, 32, ..39 = 13 attempts
................................50                            = 14
................................60                            = 15
................................70..........................  = 16
................................80..........................  = 17
................................90..........................  = 18
...............................100.........................  = 19
Worst Case = 19.

So, we have improved further.

Approach 5: 

One important observation to note here is that our worst case depends on which floor is the threshold. After each step increase of 10 it increases by 1.
So, instead of stepping by equal floors each time the egg doesn't break, we can decrease the nest step jump by 1, so that the worst case remains same irrespective of which interval the threshold floor lies.

What if we go like 10->19->27->34->40->45->49->52->54->55

We can't reach 100.

So, what should be our starting point, so that we decrease the step step size by 1 after each jump, and still reach 100. We have to find the minimum possible starting point.

Let the starting step size be x.

x

x + x-1

x + x-1 + x-2 

x + x-1 + x-2 + x-3

...............

x + x-1 + x-2 + x-3 ......... + 2 + 1 = 100

x(x+1)/2 = 100

x*x + x - 200 = 0

x =  [-1 + sqrt(1 + 800) ] / 2

   =  (-1 + 28.30)/2

   = 27.30/2

   = 13.65

So, minimum value requires is 13.65

i.e. if we start at floor 13, we wouldn't reach 100th floor if we are decreasing step step size by 1 each time.

So out starting floor should be 14.

So the order should be 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99

if it breaks at 14  = 1 + 13 = 14 attempts in worst case[14, 1, 2, 3...13]

........................27 = 2 + 12 = 14 attempts .............[14, 27, 15, 16, ....26]

........................39 = 3 + 11 = 14

........................50 = 4 + 10 = 14

............................

.....................   90 = 9 + 5 = 14

........................95 = 10 + 4 = 14

........................99 = 11 + 3 = 14  

In last case if it breaks at 99th floor i.e., after 11 attempts, we try 96, 97 & 98, thus giving 14 attempts.

Further if it doesn't break at 99, we check 100th, thus giving 12 attempts.

So, the worst case would be that we have to check 14 times, and no more with 2 eggs to find the threshold floor.