There is a nice logical puzzle which was mentioned as one from the technical interviews for IT people. Basically it refers to a well-known
egg dropping puzzle which I first time met in slightly different formulation:
Given a 100-storey building and 2 equal glass balls. Every ball breaks when it is dropped starting from certain storey, and does not break when dropped from any storey below (this storey is equal for both balls). Find the optimal algorithm of drop attempts (i.e. algorithm with minimal number of attempts) for which it is guaranteed that this storey is determined. (Of course, we assume that a ball can be reused, but not if it’s broken.)
The way I solved it does not require any extensive calculations, that is - “pure maths” :)
We can approach the problem from the other side, and let’s consider it for arbitrary number of balls and storeys.
For every number of balls B available and number of attempts N there exists a building with S storeys so that for N attempts we can determine the target storey, but we can’t determine it for (S+1)-storey building ("can" or "can’t" means determine it for sure, that is for the worst case using optimal algorithm). That is, we have a function of two positive integers S(B, N).
Consider the first attempt in our optimal algorithm for some B and N. There are two cases:
- The ball breaks at the storey. We have (B-1) balls left and the target storey is lower. That means, we may have maximum S(B-1, N-1) storeys lower.
- The ball does not break. We still have B balls left and the target storey is higher. That is, we may have maximum S(B, N-1) storeys.
Therefore, we’ve got S(B, N) = S(B-1, N-1) + S(B, N-1) + 1 (adding the storey from which we threw the ball).
Setting B = 1 in the formula we get S(1, N) = S(0, N-1) + S(1, N-1) + 1. Clearly, S(0, N-1) = 0 (we can’t determine any storey without balls), so S(1, N) = S(1, N-1) + 1. Since S(1, 1) = 1, we have S(1, N) = N. (This is actually quite clear without speculations provided above: having one ball we don’t have any choice other than throwing balls starting from the very first storey - otherwise, if we skip one or more and the balls breaks, we can’t know if it was that one or below).
Now set B = 2: S(2, N) = S(1, N-1) + S(2, N-1) + 1 = S(2, N-1) + N.
That is:
S(2, 1) = 1;
S(2, 2) = 1+2 = 3;
S(2, 3) = 1+2+3 = 6;
…
S(2, N) = 1+2+…+N = N*(N+1)/2.
Getting back to the original problem, we know that S(2, N) >= 100, but S(2, N-1) < 100, because we assume that the algorithm is optimal. From this we obtain N = 14 as the minimum required number of attempts for 2 balls and 100 storey building.
And here’s the algorithm, which can be concluded from the obtained formula S(N) = N*(N+1)/2:
First throw should be done from the 14th storey; second - from 14+13 = 27th storey, then from 27+12 = 39th e.t.c. until the first ball breaks. If it breaks after Xth attempt, we have the target storey between the previous and the current attempt’s storeys, and the difference between those two would always be 14-X. That is, we are left with the problem for 1 ball and (14-X)-storey building, and for such case we know that we determine the target storey for not more than 14-X attempts, so adding X attempts that we already used, we always determine the target storey for not more than 14 attempts.
Using our formula we can, of course, obtain formula for B=3 balls and more.
