Imagine que você está em um prédio alto com um gato. O gato pode sobreviver a uma queda de uma janela baixa, mas morrerá se jogado de um andar alto. Como você pode descobrir a queda mais longa que o gato pode sobreviver, usando o menor número de tentativas?

Obviamente, se você tiver apenas um gato, poderá pesquisar apenas linearmente. Primeiro jogue o gato do primeiro andar. Se sobreviver, jogue-o a partir do segundo. Eventualmente, depois de ser jogado do chão f, o gato morre. Você sabe que o piso f-1 era o piso seguro máximo.

Mas e se você tiver mais de um gato? Agora você pode tentar algum tipo de pesquisa logarítmica. Digamos que a construção tenha 100 andares e você tenha dois gatos idênticos. Se você atirar o primeiro gato para fora do 50º andar e ele morrer, será necessário procurar 50 andares linearmente. Você pode melhorar ainda mais se escolher um piso inferior para sua primeira tentativa. Digamos que você opte por resolver o problema 20 andares por vez e que o primeiro andar fatal seja o número 50. Nesse caso, seu primeiro gato sobreviverá aos vôos dos andares 20 e 40 antes de morrer do andar 60. Você só precisa verificar os andares 41 a 49 individualmente. São 12 tentativas, o que é muito melhor do que as 50 que você precisaria se tentasse usar a eliminação binária.

Em geral, qual é a melhor estratégia e a pior complexidade possível para um edifício de dois andares com dois gatos? Que tal para n andares e m gatos?

Suponha que todos os gatos sejam equivalentes: todos sobreviverão ou morrerão de uma queda de uma determinada janela. Além disso, toda tentativa é independente: se um gato sobrevive a uma queda, é completamente ileso.

Isso não é lição de casa, embora eu possa ter resolvido isso uma vez na escola. É apenas um problema extravagante que me veio à cabeça hoje e não me lembro da solução. Pontos de bônus se alguém souber o nome desse problema ou do algoritmo da solução.