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

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

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

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

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

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