O Empire State Building tem 102 andares. Determine o maior andar do qual um ovo pode ser jogado sem quebrar, utilizando o menor número possível de experimentos. Existem apenas dois ovos para realizar o experimento.
ZARA CHALLENGE: Em homenagem aos 10 anos do ZARA em 2022, resolva para um prédio de 2022 andares e 10 ovos disponíveis para o experimento.
Parabéns a todos que se desafiaram a solucionar o Giant Puzzle #11! Admiramos imensamente aqueles que se arriscam a pensar fora da caixa e a encontrar soluções criativas para problemas complexos.
Considerando 𝑛 andares e 𝑘 ovos, seja 𝑓(𝑛, 𝑘) o número mínimo de experimentos necessários para se encontrar, com certeza, o maior andar do qual um ovo pode ser jogado sem quebrar.
Se jogarmos o ovo do andar 𝑖 (1 ≤ 𝑖 ≤ 𝑛), há duas possibilidades a serem analisadas: por um lado, se o ovo quebrar, temos agora apenas 𝑘 − 1 ovos, mas há apenas 𝑖 − 1 andares para olhar. Por outro lado, se o ovo não quebrar, continuamos com 𝑘 ovos, mas temos 𝑛 − 𝑖 andares para olhar.
Com isso, podemos escrever a seguinte equação de recorrência (lembrando que já gastamos um experimento ao lançar o ovo do andar 𝑖):
Com as condições de contorno 𝑓(𝑛, 1) = 𝑛 e 𝑓(0, 𝑛) = 0, é possível encontrar 𝑓(𝑛, 𝑘) utilizando, por exemplo, programação dinâmica. Para os valores específicos do puzzle e do challenge, temos:
i) Puzzle: 𝑓(102,2) = 14
ii) Challenge: 𝑓(2022,10) = 11