Throwing cats out of windows

Question

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?

Obviously, if you only have one cat, then you can only search linearly. First throw the cat from the first floor. If it survives, throw it from the second. Eventually, after being thrown from floor f, the cat will die. You then know that floor f-1 was the maximal safe floor.

But what if you have more than one cat? You can now try some sort of logarithmic search. Let's say that the build has 100 floors and you have two identical cats. If you throw the first cat out of the 50th floor and it dies, then you only have to search 50 floors linearly. You can do even better if you choose a lower floor for your first attempt. Let's say that you choose to tackle the problem 20 floors at a time and that the first fatal floor is #50. In that case, your first cat will survive flights from floors 20 and 40 before dying from floor 60. You just have to check floors 41 through 49 individually. That's a total of 12 attempts, which is much better than the 50 you would need had you attempted to use binary elimination.

In general, what's the best strategy and it's worst-case complexity for an n-storied building with 2 cats? What about for n floors and m cats?

Assume that all cats are equivalent: they will all survive or die from a fall from a given window. Also, every attempt is independent: if a cat survives a fall, it is completely unharmed.

This isn't homework, although I may have solved it for school assignment once. It's just a whimsical problem that popped into my head today and I don't remember the solution. Bonus points if anyone knows the name of this problem or of the solution algorithm.

Answer 1

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.

Answer 2

Thats a puzzle which is there on the internet as the one asked in google interview (don't know the veracity of that) but here is the solution

http://interviewpuzzle.blogspot.com/2010/03/google-interview-puzzle-2-egg-problem.html

Answer 3

Terminal velocity aside, in the 2-cat case, you could use exponential backoff. I.e. drop the first cat from floors 1, 2, 4, 8, 16, etc until you find an upper bound. The lower bound is the last successful drop. So use the second cat to do a linear search within that range.

Answer 4

I cannot read the google blogspot on this (thanks to works blogwall) but I don't think a straight binary style search would be best. The reason being that a binary search is based around the notion that the answer you are looking for has an equal chance of being at any index index in the list. However in this case the that is not true. In this case the answer will have a higher probability of being closer to one end of the range than the other. I have no idea how to factor that into the search, but it's an interesting thought.

Answer 5

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.

Answer 6

I believe this is best solved with the well-known Defenestration Pattern, most concisely written in the LOLCat programming language.

Answer 7

all this crazy talk about cats..and it's just a guess the number problem with minimum guesses (number of cats). there shouldn't be a need to artificially (and incorrectly) define infinity as part of the solution either. the variable should have been named upper-bound or max-try or some such. the problem definition (the cat thing) has some serious issues though, with people responding to animal cruelty potential and also the many facets of such a problem posed in real life, e.g. air-drag, gravity is acceleration, and other such real life parameters of the problem. so perhaps it should have been asked in a totally different way.

Answer 8

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

Answer 9

My solution http://is.gd/g9rqC is slightly different from the one given by Nikita Rybak. The main difference is that my formulation does a search on both dimensions, instead of just the "floors" dimension. I am sure Nikita is on to something, but I could not see the details.

In case of 2 cats, there is no difference in the formulae, but for higher number of cats, the answer could be different. [Nikita, since you have the code, do you mind running the alternative formulation through and see if the results are the same - if they are, then probably there is a proof of optimality - in that case your formulation is correct and more efficient than mine.]

Update: Added source code and some sample results.

Answer 10

f(m,n) wouldn't be any different for one cat than for 10. You start at the intersections between ranges and run it once, and then subdivide the resulting maximum by the number of cats, ad inf. No?

[edit] And if you want to take acceleration or friction into account, cross each table by the physical function, subdivide and assign based on that and remap the values to the original table.[/edit]

Answer 11

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.