Tuesday, April 7, 2009

Dropping K Swarovsky balls

Someone asked for a variant of the Dropping Swarovski Crystals problem where you have m balls available and n floors. In this case, what is the number of drops needed?

Let's see: we can formulate the problem with 2 balls as a recursion problem. Let f(k) the maximum number of floors we can test with k drops and using 2 balls. If a ball breaks at a floor k, we need to start from the very ground up to the k floor and test all the k floors. If the ball is not breaking we need to test f(k-1). Therefore, the recursion is f(k) = f(k-1) + k. In other words f(k) = sum_i=1,..k i = k (k+1) / 2. We need to find the minimum k such that k(k+1)/2 > 100. This can be solved by direct test and we find that 14 (15/2) = 105. The number of test we obtain is 14. If we want to know what are the floor to test we can "unroll" the recursion and find the actual floors.

Now suppose you have 3 balls, can you see the problem as a recursion one? And what about m balls?