2 egg shells and 100 floors

There are two identical egg shells. Now they are very strong but are identical and have a breaking height (meaning, there is certain height below which they do not break, beyond which they will break). You have a 100 story building. Now you want to know using these two eggs, what is the minimum floor from which they will break. Come up with an efficient algorithm/ approach for it ?

I found this question to be pretty interesting, as it points to a way of solving problems. Answer below..








Solution :-

One thing most would figure out is to rephrase the question about efficiency as, whats the minimum number of drops you need to make to find which floor the egg breaks from.

The problem is harder as you are only allowed to throw 2 eggs. Thus, the second throw operation is a linear operation. Thus, the problem is reduced to finding a solution which requires minimum number for 2nd linear throw.

Let's say that x is the optimal number of throws required. And, for time being let's say x=20. Then,

You would do the first throw from 20th floor and if egg breaks you would do a linear operation of throws from 1st to 20th floor to find which floor the egg breaks.
However, if the egg doesn't break then you will throw from 39th floor, as you are now one throw less. Following this logic
20
39
57
73
88
102, etc. 20 is not the optimal number of floors, thus not the right answer. Basically you should be able to cover all the 100 floors with the second linear operation, without exceeding the optimal number of throws. lets call it x, thus it becomes,
x + (x-1) + (x-2) + ... + 1 = 100
x(x+1)/2=100
which implies x=14 which is the optimal number of throws required. Check the following.

Step Count

first drop from 14th if it breaks, try from 1-13, else - if it broke the count is : 1+13 14
drop from 27 if it breaks try from 15-26, else - if it broke the total number of throws is still 2+12 = 14
drop from 39 ...................................., else - 3 + 11 = 14
drop from 50....................................., else - 4+ 10 = 14
drop from 60....................................., else - 5 + 9 = 14
drop from 69....................................., else - 6 + 8 = 14
drop from 77....................................., else - 7 + 7 = 14
drop from 84....................................., else - 8 + 6 = 14
drop from 90....................................., else - 9 + 5 = 14
drop from 95....................................., else - 10 + 4 = 14
drop from 99....................................., else - 11 + 3 = 14
drop from 100....................................

So, one (well known) way to solve the problems is to assume the solution and workout backwards.

Now the twist, Whats the optimal number of trails if the number of eggs allowed was 3 ???