Problem :

You are given two identical eggs. Given that you are standing in front of a 100 floor building, you have to find out the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to figure out the solution?

Solution:

Interval-1

We can start from the first floor and drop the egg. If it doesn’t break, move on to the next floor. If it does break, then we know the maximum floor the egg will survive is 0. If we continue this process, we will easily find out the maximum floors the egg will survive with just one egg. So the maximum number of tries is 100.

Interval-2:

Say we start at the second floor. If the egg breaks, then we can use the second egg to go back to the first floor and try again. If it does not break, then we can go ahead and try on the 4th floor (in multiples of 2). If it ever breaks, say at floor x, then we know it survived floor x-2. That leaves us with just floor x-1 to try with the second egg. So what is the maximum number of tries possible? It occurs when the egg survives 98 or 99 floors. It will take 50 tries to reach floor 100 and one more egg to try on the 99th floor so the total is 51 tries. Wow, that is almost half of what It may seem that picking any one interval with 19 tries would be correct.

Variable intervals

However, instead of taking equal intervals, we can increase the number of floors by one less than the previous increment.

For example, let’s first try at floor 14. If it breaks, then we need 13 more tries to find the solution. If it doesn’t break, then we should try floor 27 (14 + 13). If it breaks, we need 12 more tries to find the solution. So the initial 2 tries plus the additional 12 tries would still be 14 tries in total. If it doesn’t break, we can try 39 (27 + 12) and so on. Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + … + 1) before we need more than 14 tries. Since we only need to cover 100 floors, 14 tries is sufficient to find the solution.

Therefore, 14 is the least number of tries to find out the solution.

we had last time.

Interval-3

Using the same logic as the previous case with an interval of 3, we need a max of 35 tries to find out the information, that is, 33 tries to reach 99th floor and 2 more on 97th and 98th floor.

Interval | Maximum Tries |

1 | 100 |

2 | 51 |

3 | 35 |

4 | 29 |

5 | 25 |

6 | 21 |

7 | 20 |

8 | 19 |

9 | 19 |

10 | 19 |

11 | 19 |

12 | 19 |

13 | 19 |

14 | 20 |

15 | 20 |

16 | 21 |