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 k pesagens, podemos distinguir no máximo 3^k situações distintas.

Passo 2

Aqui temos um conjunto de 10 moedas, exatamente uma é falsa, e não sabemos se ela é mais pesada ou mais leve. Isso gera
10 times 2 = 20
possíveis casos a identificar.

Passo 3

Pela estrutura de decisão com k pesagens e três resultados cada, o Teorema 5.1 impõe a desigualdade
3^k >= 20

Passo 4

Basta achar o menor k inteiro que satisfaça 3^k >= 20. Temos
3^2 = 9 < 20 e 3^3 = 27 >= 20,
logo o mínimo é k = 3.

Resposta

O número mínimo de pesagens é 3.

Exercícios de Livros Relacionados