4.Considere o problema de identificar uma moeda falsificada usando uma balança de dois pratos.Suponha,como fizemos no Exemplo 5.18,que 1 moeda de um conjunto de 10 é falsa,mas desta vez suponha que a moeda falsificada pode ser ou mais pesada ou mais leve.O que o Teorema 5.1 diz sobre o número mínimo de pesagens neste caso?
Passo 1
Estamos no contexto do problema da moeda falsa com balança de dois pratos e três resultados possíveis em cada pesagem (pratos em equilíbrio, prato esquerdo mais pesado ou prato direito mais pesado). O Teorema 5.1 diz que, se fazemos
pesagens, podemos distinguir no máximo
situações distintas.
Passo 2
Aqui temos um conjunto de
moedas, exatamente uma é falsa, e não sabemos se ela é mais pesada ou mais leve. Isso gera
possíveis casos a identificar.
Passo 3
Pela estrutura de decisão com
pesagens e três resultados cada, o Teorema 5.1 impõe a desigualdade
Passo 4
Basta achar o menor
inteiro que satisfaça
. Temos
logo o mínimo é
.
Resposta
O número mínimo de pesagens é
.