Throwing cats out of windows

问题:

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.

回答1:

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.

回答2:

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.

回答3:

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

回答4:

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

回答5:

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.

回答6:

I took a slightly different method to produce a solution.

I started by working out the maximum floor that could be covered using x cats and y guesses using the following method.

Start with 1 floor and keep increasing the number of guesses while keeping track of floors checked, which guess they were checked on and how many cats were remaining for each floor.
Repeat this up to y times.

This very inefficient code to compute the given answer but nonetheless useful for small number of cats / floors.

Python code:

def next_step(x, guess):
  next_x = []
  for y in x:
    if y[0] == guess:
      if y[1] != 1:
        next_x.append((guess+1, y[1] - 1))
    next_x.append(y)
    if y[0] == guess:
      next_x.append((guess+1, y[1]))
  return next_x

x = [(1, TOTAL_NUM_CATS)]
current_floor = 1
while len(x) <= TOTAL_NUM_FLOORS:
  x = next_step(x, current_floor)
  current_floor += 1
  print len(x)

For 2 cats the maximum floors that can be identified in x guesses is:
1, 3, 6, 10, 15, 21, 28...

For 3 cats:
1, 3, 7, 14, 25, 41, 63...

For 4 cats:
1, 3, 7, 15, 30, 56, 98...

After extensive research (mostly involving typing numbers sequences into OEIS) I noticed that the maximum floors for x follows a combination piecewise pattern.

For 2 cats:
n < 2 : 2^n - 1
n >= 2 : C(n, 1) + C(n, 2)

For 3 cats:
n < 3 : 2^n - 1
n >= 3 : C(n, 1) + C(n, 2) + C(n, 3)

For 4 cats:
n < 4 : 2^n - 1
n >= 4 : C(n, 1) + C(n, 2) + C(n, 3) + C(n, 4)

From here I took the easy approach of simple incrementing n until I pass the required number of floors.

Python code:

def find_smallest(floors, eggs):
  maximum_floors = 0
  n = 0
  while maximum_floors < floors:
    maximum_floors = 0
    n += 1
    if n < eggs:
      maximum_floors = 2**n - 1
    else:
      count = 0
      for x in xrange(1, eggs+1):
        maximum_floors += combination(n, x)
  print n

This gives the correct solution for (100, 2) = 14.
For anyone that wishes to check something less trivial, it gives (1 000 000, 5) = 43.

This runs in O(n) where n is the answer to the problem (the more cats the better).
However I'm sure a somebody with a higher level of mathematics could simplify the piecewise formulas to compute in O(1).

回答7:

O(m*(n^(1/m))) algorithm.

Let 'x' be the maximum number of attempts needed.  

m = 1 => linear => x=n

m = 2:  
Let the floors be split into 'k' partitions. The first cat is thrown at the end of each partition (max 'k' times). 
When it dies, the second cat is used to go up from the beginning of this partition.   
x = k + n/k.   
Minimize x by diff wrt k and setting = 0, to get k = n^(1/2) and x = 2 * n^(1/2).

m = 3:  
x = k + 2*(y^(1/2)), where y = n/k  
diff wrt x and set = 0, to get k = n^(1/3) and x = 3 * n^(1/3)

for general m:  
x = m * n^(1/m). 

回答8:

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.

回答9:

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.