Thursday, April 22, 2010

Solution 1: Critical Height

Original problem:

You have an infinite supply of crystal balls that you take into a building with 1000 stories.

There is a critical height at which if you drop the ball from there, the ball would break. If the ball is dropped from the floors under that critical height, it would not break, but if it's dropped from the floors above, obviously, it breaks.

How many trials minimum do you need in order to determine the critical height?

Advanced version #1: If you only have a supply of $k$ balls, how many trials minimum do you need?

Advanced version #2: What is the strategy that would minimize the expected number of trials, given that you only have $k$ balls, if we treat the critical height as a random variable drawn uniformly from (1,...,1000)?

Note that the two advanced versions are two different questions and thus beget two different strategies.

Clarification: When I say "how many trials minimum do you need in order to determine the critical height" it formally means: find the smallest integer $N$ such that it's always possible to determine the critical height within $N$ trials, regardless of where the critical height is. Naturally, this $N$ will be expressed in terms of $k$ in the case of advanced version #1.

Solution to advanced version #1

First we make an observation that we only care about the number of floors that are possible candidates, and the actual floor height is irrelevant. For example, if we know that the critical height must be in the floor 10 to 30, or if we know that it must be in the floor 510-530, we can employ the exact same strategy in both of those situations. The number of minimum trials needed to solve both scenarios are the same, and any action we do in one scenario is directly translatable to the other scenario. We consider these two scenarios as equivalent problems.

Our second observation is that the possible candidates are always in the form of one contiguous block of floors. We start with a block of 1000 floors (floor 1 to 1000). Every time we drop a ball from a certain floor, say floor $a$ either it breaks or it doesn't break. If it breaks, then our next candidate is floor 1 to $a$, and if it doesn't, then our next candidate is floor $a+1$ to 1000. Every time we drop a ball, we divide one contiguous block into two (possibly unequal) halves and we eliminate one half, so we establish an invariant that our candidates are always one contiguous block of floors.

From the two observations above, we may define a function $f(n,k)$ as the minimum number of trials needed to solve the case with $n$ floors and $k$ balls. Without loss of generality (and for notational ease), we may assume that the floors are floor 1 to $n$.

Suppose our first drop is at floor $a$. As we described above, if it breaks, then we are left with $k-1$ balls to find the critical height among floor 1 to $a$. We need at least $f(a,k-1)$ trials to do this. Otherwise, we still have $k$ balls to find the critical height among floor $a+1,...,1000$. We need at least $f(1000-a, k)$ trials. So in the worst case, we need at least $f(n,k) = \max ( f(a,k-1) , f(n-a,k) ) + 1$ if our first drop is at floor $a$. However, we can choose $a$ to minimize the number of trials.
$$ f(n,k) = \min_{a} \left( \max ( f(a,k-1) , f(n-a,k) ) \right) + 1$$

For $k=1$, if we only have 1 ball, then the only possible strategy is to drop it sequentially from floor 1,2,... until it breaks. Thus $f(n,1) = n-1$ For example, if we know that the critical height is somewhere between floor 1 to 3, then we drop it at floor 1 and 2. If it doesn't break at floor 2, then we don't need to test floor 3 because it already know it breaks at floor 3.

Consider the case of $k=2$. Let $g(n) = f(n,2)$. From the recursion above, we have:
$$ g(n) = \min_{a} \left( \max ( a-1 , g(n-a) ) \right) + 1$$

Let $T(n)$ be the $n$-th triangular number. That is,
$T(0) = 0$
$T(1) = 1$
$T(2) = 1+2 = 3$
$T(3) = 1+2+3 = 6$
$T(n) = n(n+1)/2$
And let $T^{-1}(n)$ be the ceiling of the inverse triangular number.
That is
$T^{-1}(0) = 0$
$T^{-1}(1) = 1$
$T^{-1}(2) = T^{-1}(3) = 2$
$T^{-1}(4) = T^{-1}(5) = T^{-1}(6) = 3$
$T^{-1}(7) = T^{-1}(8) = T^{-1}(9) = T^{-1}(10) = 4$
and so on.

We claim that $g(n) = T^{-1}(n-1)$, which we shall prove by induction.
For small $n$ we can verify by hand that we can solve $n$ floors and that it's the minimal amount. In fact, for small $n$, $T^{-1}(n-1)$ agrees with $\log_2 n$ which is the information theoretic lower bound.

Now we proceed by strong induction.
$$ g(n) = \min_{a} \left( \max ( a-1 , T^{-1}(n-a-1) ) \right) + 1$$
Note that $T$ is a monotonically increasing function, which means $T^{-1}(n)$ is monotonically non-decreasing. But since the argument to the function is $n-a-1$, the second half of the max is actually non-increasing.

We wish to find $a$ that minimizes the max of two function, one of which is increasing and another non-increasing. The minimum must happen when the two functions intersect, that is when $a-1 = T^{-1}(n-a-1)$.

$$T^{-1}(n-a-1) = a-1$$
$$n-a-1 \leq T(a-1) = a(a-1)/2$$
$$n-1 \leq a+ a(a-1)/2 = a(a+1)/2 = T(a)$$
$$n-1 \leq T(a)$$
$$T^{-1}(n-1) \leq a$$

So the $a$ that minimizes is $T^{-1}(n-1)$, and for that value of $a$,
$f(n) = (a-1) + 1 = a = T^{-1}(n-1)$.

This completes our proof for $k=2$. For an example, suppose we have 11 floors and 2 balls, then our first drop should be at floor 4. If it breaks then we resort to the linear approach with our one remaining ball to discover which among floor 1,2,3,4 is the critical height. We can do it in 3 trials. If it doesn't break, then we drop it at floor 7. If it breaks at floor 7, then the critical floor must be floor 5, 6, or 7, which we can find in 2 trials. If it keeps not breaking, we drop it at floor 9, then 10. In any case, we will find it within 4 trials.

For case $k=3$, we do the same thing except we replace $T$ with $P$, the $n$ pyramidal number.
$P(0) = T(0) = 0$
$P(1) = T(1) = 1$
$P(2) = T(1) + T(2) = 4$
$P(3) = T(1) + T(2) + T(3) = 10$
$P(n) = n(n+1)(n+2) / 6$
The arguments in the proof still hold to establish feasibility and optimality of this strategy.

For general case $k$, we replace $P$ with $H_k$, the $n$-th hyper-pyramidal number:
$$H_k (n) = n(n+1)...(n+k-1) / k! = \binom{n+k-1}{k}$$
And the minimum number of trials is
$$f(n,k) = H_k^{-1}(n-1)$$

No comments:

Post a Comment