Suponha que desejamos saber de qual janela de um prédio de 36 andares é seguro jogarmos ovos para baixo, de modo que os ovos não se quebrem ao atingirem o chão. Para tal, admitimos que:
• Um ovo que sobrevive a uma queda pode ser usado novamente.
• Um ovo quebrado deve ser descartado.
• O efeito da queda é o mesmo para todos os ovos.
• Se um ovo se quebra quando jogado de uma certa janela então ele quebrará se jogado de uma altura superior.
• Se um ovo sobrevive a uma queda então ele sobreviverá a uma queda menor.
• Não se sabe se da janela do primeiro andar os ovos quebram, e também não se sabe se da janela do último andar os ovos quebram.
Se temos apenas 1 ovo e queremos ter certeza de obter um resultado correto, o experimento deve ser guiado apenas por um único caminho: jogue o ovo pela janela do primeiro andar; se não se quebrar, jogue o ovo pela janela do segundo andar. Continue até que o ovo se quebre. Na pior das hipóteses, este método necessitará de 36 lançamentos para ser concluído. Suponha que 2 ovos estão disponíveis. Qual é o menor número de lançamentos de ovos necessários para garantir todos os casos?
Solução: 8 lançamentos. Acompanhe o raciocínio: jogamos o primeiro ovo do oitavo andar. Se quebrar, basta testar os 7 primeiros com o segundo ovo. Se não quebrar, o jogamos do 15o., depois do 21o., depois do 26o., depois do 30o., depois do 33o., depois do 35o. e finalmente do 36o.
Se ele quebrar por exemplo quando jogado do 26o. andar, basta testar o segundo ovo nos andares 22, 23, 24 e 25, para o que gastamos 4 + 4 = 8 lançamentos. A escolha dos andares se devem a 8 + 7 = 15, 8 + 7 + 6 = 21, 8 + 7 + 6 + 5 = 26, 8 + 7 + 6 + 5 + 4 = 30, 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36. O resultado não pode ser melhorado, pois se o primeiro ovo quebra no n-ésimo lançamento, devemos testar com o ovo restante todos os andares entre os usados nos (n – 1)-ésimo e n-ésimo lançamentos, no pior caso.
Assinar:
Postar comentários (Atom)
Nenhum comentário:
Postar um comentário