Puzzle: 2 crystal balls, 100 storey building, find no. of drops required?

Puzzle: There are two identical crystal balls and one needs to find out which is the maximum floor in a 100 storey building from where the balls can fall before they break. In the most efficient way, what will be the maximum number of drops required to find the right floor in any possible scenario? The balls are allowed to be broken (if required) while finding the right floor.

Solution: The maximum drops required will be 14 to find the right floor considering all possible scenarios.

The approach should be to drop the first crystal ball from a floor and if it breaks then try dropping the second crystal ball (of course until it breaks) from the floor next to the previously tested floor until one less than that floor from where the first crystal ball broke when dropped.

In the most efficient way, the maximum number of trials needed should be kept to the minimum possible. We have a maximum of 100 floors, so we need to divide these floors in such a way that the sum of the number of trials consumed by first crystal ball and that of the second crystal ball (if the first breaks) remains the minimum. For this to happen we need to reduce the difference between the previously tested floor and the next floor to test the first ball from every time by 1 as the first balls has already been dropped by those many times. Confused? Let's try to understand it this way: Suppose we drop the first ball from the Nth floor for the first time then we'll require a maximum of N drops if the first ball breaks as in this case the second ball will be tried from floor #1 to floor #(N-1). If the first ball doesn't break then we'll have to select the next floor to test the drop of the first ball from. This can't be more than (N-i) from the previously tested floor where i = 1 ... N-1 for every subsequent step in this order only. Reason being, if we test the first ball from a higher floor and if the ball breaks then we may require to test the second ball more number of times and hence the maximum attempts may exceed N in this case. Similarly, if we test the first ball from a lower floor then we'll require to test the first ball more than N times if it doesn't break at all.

Obviously this N will of course be dependent upon the maximum number of floors which is 100 in our case. Putting N = 14, we will require the first ball test from floor #14, #(14 + 14 - 1 = 27), #(27 + 14 - 2 = 39), #(39 + 14 - 3 = 50), #(50 + 14 - 4 = 60), #(60 + 14 - 5 = 69), #(69 + 14 - 6 = 77), #(77 + 14 - 7 = 84), #(84 + 14 - 8 = 90), #(90 + 14 - 9 = 95), #(95 + 14 - 10 = 99), and finally from #100. The test will continue until we reach #100 OR the first ball breaks in which case the second crystal ball will be used for the floors lying between the floor where the first ball breaks and the previously tested floor.

I doubt if there is any easy formula to find out this number N, but we can certainly reach this by using a heuristic approach. As we move on we consume trials at every stage and this should always be kept in mind. This is the reason why we can't keep the difference between the previously tested floor and the next floor to test from as constant for the first crystal ball drop.

For N = 14, if the first ball doesn't break at all then we need to try a maximum of 12 times and if it breaks the very first time itself then we may require to try a maximum of 14 times (1 by the first ball from floor #14 and a maximum of 13 by the second ball from floor #1 ... #13). Similarly, if the first ball breaks at floor #27 then maximum attempts required will again be 14 (2 by first ... [from floor #14 and from floor #27] plus 12 by second [from floor #15 ... floor #26]). And and so on. Thus we see that in this case if the first ball breaks at any of the floors then we need a maximum of 14 attempts to figure out the correct floor and if it doesn't break at all then we'll done with a maximum of 12 attempts only.