Você tem um prédio de 100 andares e dois ovos idênticos. Precisa encontrar o andar mais alto do qual é possível soltar um ovo sem que ele quebre. Qual é a estratégia ideal e qual é o número mínimo de quedas necessário no pior caso?

Question

Faria Lima Street · Accepted Answer

A estratégia ideal minimiza o número máximo de quedas no pior caso usando dois ovos. Se você soltar o primeiro ovo em intervalos fixos, por exemplo a cada 10 andares, e ele quebrar, então precisará testar cada andar um por um com o segundo ovo. Porém, isso pode ser melhorado reduzindo o intervalo a cada queda para equilibrar o pior caminho. O método mais eficiente é soltar o primeiro ovo do 14º andar, depois do 27º (14 + 13), depois do 39º (14 + 13 + 12), e assim por diante, reduzindo o passo em um a cada vez. Essa estratégia garante que o pior caso seja minimizado para 14 quedas. Ela equilibra o número de quedas antes de o primeiro ovo quebrar e o número de quedas necessárias com o segundo ovo depois desse ponto. É um exemplo de minimização do custo no pior caso por busca incremental otimizada.