Google and eggs

One of the famous "google puzzle" - questions asked while applying for a job in Google.

There's a 100 stories building, and you have 2 eggs. You need to find out which is the highest story you can throw the egg from, and it will stay intact with the minimal throws possible. If you threw and egg and it did not break, you may throw it again. We assume that egg always breaks when throws from 100th story.

First solution

Simply throw an egg starting from 1th story and go up until egg breaks. In the worst case you need 99 throws.

Second solution

Start from 50th floor than go up (if egg does not break) or down (if breaks). In the worst case you need 50 throws (1+49).

General solution

Take number N  (N > 0 and N < 100) than start throwing the first egg by 100/N, 2 * (100/N), 3* (100/N) until 100 is reached or egg breaks (assume that it is k*(100/N) story). Than take the second egg (or first if still in one piece) and start throwing from (k-1)(100/N).

The number of trials in the worst case is (100/N) -1 + N-2.

The question : what is the minimum of this function ?

Solution, very simple using basic analysis

(derivative) 


The F is minimal when F'(N) is equal 0, so it is minimal for N=10.

Answer

The worst case takes place if the "breaking" store is 100.
So you throw egg starting from 10,20... to 90 (9 trials). Then start 91...98 (8 trials) - it is not necessary to throw egg when 98th store does not break.
The minimum number of throws is 17.

Addition remark.

The worst case takes place when the breaking store is 89.  In this case the number of throws is 16 (8+8). In the case of 99 floor we still have 2 eggs. So we can throw from 93 and 96th floor and go on accordingly using less than 16 throws

So the final answer is: 16 throws.