Wednesday, May 11, 2016

Let us first assume that the number of drops required are N.

If the egg breaks at maximum number of tries, we will have N - 1 drops till it does not break. Thus we must drop the first egg from the height N. Now if the first drop of the first egg does not break the egg, we can have N - 2 drops for the second egg if the first egg breaks in the second drop.

Let us put that into a valid example for better understanding. Suppose we need 16 drops. Now let us drop the egg from the sixteenth floor, if it breaks, we will try all the floors below sixteen. Suppose it does not breaks, then we have 15 drops left and we will drop it from 16+15+1 = 32nd floor. This is because if it breaks at 32nd floor, we can try all the way down to 17th floor in fourteen tries making the total tries to be 16. 

Let us assume that 16 is the correct answer

1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45.....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 we can easily do in the end as we have enough drops to complete the task.

Seeking the above case, we must note that we have achieved it in 14 or 14 drops but we still need to find out the optimal one. We know from above that the optimal one will require 0 linear trials in the last step.

Thus we can say that

(1+p) + (1+ (p-1)) + (1+ (p-2)) + .........+ (1+0) >= 100.

Let 1+p=q which is the answer we are looking for

q (q+1)/2 >=100

q=14

Thus the optimal number of drops required are 14.

Drops will be tried at floor number 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. How? Just move up 14, 13, 12 .... Floor till it breaks or does not.

No comments:

Post a Comment