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.

user_557771 · Answer

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).

Throwing cats out of windows

8 Answers