Throwing cats out of windows

Question

According to a recent episode of Radiolab (about "Falling"), a cat reaches terminal velocity by the 9th floor. After that, it relaxes and is less likely to be hurt. There are completely uninjured cats after a fall from above the 30th. The riskiest floors are 5th to 9th.

You can easily write a little DP (dynamic programming) for the general case of n floors and m cats.

The main formula, a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n, should be self-explanatory:

• If first cat is thrown from k-th floor and dies, we now have k - 1 floors to check (all below k) and m - 1 cats (a[k - 1][m - 1]).
• If cat survives, there're n - k floors left (all floors above k) and still m cats.
• The worst case of two should be chosen, hence max.
• + 1 comes from the fact that we've just used one attempt (regardless of whether cat has survived or not).
• We try every possible floor to find the best result, hence min(f(k)) : for k in 1..n.

It agrees with Google result from Gaurav Saxena's link for (100, 2).

int n = 100; // number of floors
int m = 20; // number of cats
int INFINITY = 1000000;

int[][] a = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
    // no cats - no game
    a[i][0] = INFINITY;
}

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        // i floors, j cats
        a[i][j] = INFINITY;

        for (int k = 1; k <= i; ++k) {
            // try throw first cat from k-th floor
            int result = Math.max(a[k - 1][j - 1], a[i - k][j]) + 1;
            a[i][j] = Math.min(a[i][j], result);
        }
    }
}

System.out.println(a[n][m]);

You can easily find strategy (how to throw first cat), if you save best k in another array.

There's also a faster solution, not involving O(n^3) computations, but I'm a bit sleepy already.

edit
Oh yeah, I remember where I saw this problem before.

Imagine you're in a tall building with a cat. The cat can survive a fall out of a low story window, but will die if thrown from a high floor. How can you figure out the longest drop that the cat can survive, using the least number of attempts?

The best strategy for solving this problem is investigating, using the law of physics, the probability of your assumptions being true in the first place.

If you would have done so, you'd realize that the cat's chances of survival actually increase the higher the distance to ground is. Of course, assuming you throw it from an ever higher building, such as the petronas towers, and not an ever higher mountain, such as the mount everest.

Edit:
Actually, you'd see an unfinished camel distribution.
First, the probability of the cat dying is low (very low altitude), then it gets higher (low altitude), then again lower (higher altitude), and then again higher (very high altitude).

The graph for the probability of cat dying as a function of altitude above ground looks like this:
(finish at 3, because unfinished camel distribution)

Update:
A cat's terminal velocity is 100 km/h (60mph) [=27.7m/s = 25.4 yards/s].
Human terminal velocity is 210 km/h (130mph).[=75m/s = 68.58 yards/s]

Terminal velocity source:
http://en.wikipedia.org/wiki/Cat_righting_reflex

Credits:
Goooooogle

I need to verify later:
http://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov/WWW/K-12/airplane/termv.html

I first read this problem in Steven Skiena's Algorithm Design Manual (exercise 8.15). It followed a chapter on dynamic programming, but you don't need to know dynamic programming to prove precise bounds on the strategy. First the problem statement, then the solution below.

Eggs break when dropped from great enough height. Given an n-story building, there must be a floor f such that eggs dropped from floor f break, but eggs dropped from floor f-1 survive. (If the egg breaks from any floor, we'll say f = 1. If the egg survives from any floor, we'll say f = n+1).

You seek to find the critical floor f. The only operation you can perform is to drop an egg off some floor and see what happens. You start out with k eggs, and seek to drop eggs as few times as possible. Broken eggs cannot be reused (intact eggs can). Let E(k,n) be the minimum number of egg droppings that will always suffice.

1. Show that E(1,n) = n.
2. Show that E(k,n) = Θ(n**(1/k)).
3. Find a recurrence for E(k,n). What is the running time of the dynamic program to find E(k,n)?

---

Only 1 egg

Dropping the egg from each floor starting at the first will find the critical floor in (at-worst) n operations.

There is no faster algorithm. At any time in any algorithm, let g the highest floor from which the egg has been seen not to break. The algorithm must test floor g+1 before any higher floor h > g+1, else if the egg were to break from floor h, it could not distinguish between f=g+1 and f=h.

2 eggs

First, let's consider the k=2 eggs case, when n = r**2 is a perfect square. Here's a strategy that takes O(sqrt(n)) time. Start by dropping the first egg in increments of r floors. When the first egg breaks, say at floor ar, we know the critical floor f must be (a-1)r < f <= ar. We then drop the second egg from each floor starting at (a-1)r. When the second egg breaks, we have found the critical floor. We dropped each egg at most r time, so this algorithm takes at-worst 2r operations, which is Θ(sqrt(n)).

When n isn't a perfect square, take r = ceil(sqrt(n)) ∈ Θ(sqrt(n)). The algorithm remains Θ(sqrt(n)).

Proof that any algorithm takes at least sqrt(n) time. Suppose there is a faster algorithm. Consider the sequence of floors from which it drops the first egg (so long as it doesn't break). Since it drops fewer than sqrt(n), there must be an interval of at least n/sqrt(n) which is sqrt(n). When f is in this interval, the algorithm will have to investigate it with the second egg, and that must be done floor-by-floor recalling the 1-egg case. CONTRADICTION.

k eggs

The algorithm presented for 2 eggs can be easily extended to k eggs. Drop each egg with constant intervals, which should be taken as the powers of the kth root of n. For example, for n=1000 and k=3, search intervals of 100 floors with the first egg, 10 with the second egg, and 1 with the last egg.

Similarly, we can prove that no algorithm is faster Θ(n**(1/k)) by inducting from the k=2 proof.

Exact solution

We deduce the recurrence by optimising where to drop the first egg (floor g), presuming we know optimal solutions for smaller parameters. If the egg breaks, we have the g-1 floors below to explore with k-1 eggs. If the egg survives, we have n-g floors above to explore with k eggs. The devil chooses the worst for us. Thus for k>1 the recurrence

E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..n

Doesn't this assume you're using "The Same Cat"?

You can approach it mathematically, but that's the nice thing about math... with the right assumptions, 0 can equal 1 (for large values of 0).

From a practical stand-point, you can get 'Similar Cats", but you can't get "The Same Cat".

You could try to determine the answer empirically, but I would think that there would be enough statistical differences that the answer would be statistically meaningless.

You could try to USE "The Same Cat", but that wouldn't work, as, after the first drop, it's no longer the same cat. (Similarly to, onecan never step into the same river twice)

Or, you could aggregate the health of the cat, sampling at extremely close intervals, and find the heights for which the cat is "mostly alive" (opposed to "mostly dead" from "The Princess Bride"). The cats will survive, on average (up to the last interval).

I think I've strayed from the original intent, but if you're going the empirical route, I vote for starting as high as possible and continuing to drop cats as the height decreases until they statistically survive. And then re-test on surviving cats to be sure.