Выбрасывать кошек из окон

Представьте, что вы находитесь в высоком здании с кошкой. Кошка может пережить падение из окна низкого этажа, но умрет, если ее бросить с высокого этажа. Как с наименьшим количеством попыток вычислить, какое самое длинное падение может выжить кошка?

Очевидно, что если у вас только одна кошка, вы можете искать только линейно. Сначала сбросьте кошку с первого этажа. Если выживет, закинуть со второго. В конце концов, будучи брошенным с этажа f, кошка умрет. Тогда вы знаете, что этаж f-1 был максимально безопасным.

Но что, если у вас более одной кошки? Теперь вы можете попробовать какой-нибудь логарифмический поиск. Допустим, в сборке 100 этажей и у вас есть два одинаковых кота. Если вы выбросите первую кошку с 50 этажа, и она умрет, то вам нужно будет обыскать только 50 этажей линейно. Вы можете добиться большего, если для своей первой попытки выберете этаж ниже. Допустим, вы решили решать проблему на 20 этажах за раз, и первый фатальный этаж - 50. В этом случае ваша первая кошка переживет полеты с 20-го и 40-го этажей, прежде чем умрет с 60-го этажа. Вам просто нужно проверить уровни с 41 по 49 индивидуально. Всего 12 попыток, что намного лучше, чем 50, которые вам понадобились бы, если бы вы попытались использовать двоичное исключение.

В общем, какова лучшая стратегия и наихудшая сложность для n-этажного здания с 2 кошками? А как насчет n этажей и m кошек?

Предположим, что все кошки эквивалентны: все они выживут или умрут при падении из данного окна. Кроме того, каждая попытка независима: если кошка выживает при падении, она совершенно невредима.

Это не домашнее задание, хотя я, возможно, однажды решил его для школьного задания. Это просто причудливая проблема, которая пришла мне в голову сегодня, и я не помню решения. Бонусные баллы, если кто-нибудь знает название этой проблемы или алгоритм решения.