Saturday, July 5, 2008

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.



Share/Save/Bookmark


7 comments:

Anonymous said...

There is an easy formula. With 2 crystal balls and 'n' floors, root(2*n) is the max no. of attempts.

Geek said...

The formula certainly fits in this case. But, it'll be great if you can share how actually did you reach to this formula. Keep visiting/posting!

Anonymous said...

I think it is worst case 50, best case 7. Here is why... Think of it as an array I would want to divide each time as long as the ball did not break. So if I divide (100 / 2 = 50) and the ball breaks, bummer I have to go all the way down to up up to 50 to see if it breaks again and I may have to go all the way to 49 (that's 50 worst case). But if it does not break at 50 I would divide again (100 - 50 / 2 + 50 = 75), (100 - 75 / 2 + 75 = 87), (100 - 87 / 2 + 87 = 93), (100 - 93 / 2 + 93 = 96), (100 - 96 / 2 + 96 = 98), (100 - 98 /2 + 98 = 99).

Geek said...

I guess you probably misinterpreted the puzzle. Let me put it differently, it asks you to use the most efficient way to find the maximum number of drops you would need even in the worst case i.e., it asks you to devise a strategy in which you would need the least (that's because you got to find the 'most efficient' app) number of drops to find the correct floor in any possible scenario - of course including the worst case. If you can keep the worst case attempts to minimum, the number of best case attempts would anyway either be the same or less.

Evidently you can find the correct floor in a maximum of 14 drops even in the worst case, if you follow the strategy explained in the article above.

What you have said above says the worst case would be 50, but then that's obviously not the most efficient way as there is at least another approach (described above) in which the worst case is taking only 14 drops. Hope this helps. Keep posting!

Pratik Poddar said...

Lets say that I would drop at f(m) when I am dropping for the m_th time without breaking.

So, we know m + f(m) - f(m-1) - 1 = 1 + f(1) -1 for all m

So, when going to 100, we would see that its the last number..
So, for m = f(1), f(m) >= 100 {or nfloors in general case}

f(2) = 2f(1)-1
f(3) = f(2) + f(1) -2
f(4) = f(3) + f(1) -3
...

So, f(k) = kf(1) - k(k-1)/2
At
k= f(1)
f(k) >= nfloors
Let
k^2 + k >= 2*nfloors

k >= sqrt(2nfloors) - 0.5

For nfloors =100
k >= 13.6
So, k = 14
Answer.....

For more puzzles like this, see
http://pratikpoddarcse.blogspot.com/

Geek said...

An effort from you to elaborate your solution li'l more will be highly appreciated. Thanks for your participation.

Pratik Poddar said...

Very similar problem:
http://pratikpoddarcse.blogspot.in/2012/02/original-problem-atm-money-withdrawal.html