Existem nove bolas de marfim e uma delas por ser falsa tem peso menor. Dispondo de uma balança que em cada prato cabem no máximo três bolas, pede-se o número mínimo de pesagens para se descobrir a bola falsa.

Passo 1

O enunciado diz que temos 10 bolas idênticas, sendo exatamente uma falsa e mais leve, e dispomos de uma balança de pratos iguais onde cabem até 3 bolas em cada lado. Queremos achar a bola falsa no menor número de pesagens. O que vamos usar é a ideia de que cada pesagem dá três resultados possíveis (esquerda baixa, direita baixa ou equilíbrio) e organizar uma estratégia que, em qualquer caso, encontre a bola falsa.

Passo 2

Em termos de teoria da informação, cada pesagem emite uma resposta ternária, então com k pesagens conseguimos distinguir até
3^k
resultados diferentes. Como temos 10 bolas possíveis para a falsa, precisamos de
3^k >= 10
Para k=2 temos 3^2=9<10 insuficiente, e para k=3 temos 3^3=27>=10. Logo, no mínimo 3 pesagens são necessárias.

Passo 3

Uma estratégia que usa exatamente 3 pesagens é: na primeira pesagem colocamos 3 bolas de um lado e 3 bolas de outro. A partir do resultado, separamos dois casos principais:

Passo 4

Caso a balança fique em equilíbrio (ou seja, aquelas 6 bolas são todas verdadeiras), a falsa está entre as 4 não pesadas. Agora temos 2 pesagens sobrando e precisamos isolar a falsa em 4 candidatas. Fazemos:
– Segunda pesagem: escolhemos 1 bola A e 1 bola B dessas 4 e pesamos A versus B.
  • Se A baixa, A é a falsa.
  • Se B baixa, B é a falsa.
  • Se equilibrar, a falsa está entre as 2 restantes C e D.
    – Terceira pesagem: pesamos C versus uma bola verdadeira. Se C baixa, C é falsa; caso contrário, é D.

Passo 5

Caso a balança fique desnivelada na primeira pesagem (por exemplo, o lado esquerdo mais leve), sabemos que a falsa está entre aquelas 3 bolas do prato mais leve. Agora temos ainda 2 pesagens para detectar a falsa em um grupo de 3. Basta:
– Segunda pesagem: pegamos duas dessas três bolas, digamos X e Y, e pesamos X versus Y.
  • Se X baixa, X é a falsa.
  • Se Y baixa, Y é a falsa.
  • Se equilibrar, a falsa é a terceira que não foi pesada.
    Nesse caso só usamos 2 pesagens, sobrando 1 para eventuais verificações extras, mas o pior caso ainda será 3.

Resposta

No pior caso, são necessárias 3 pesagens.

Exercícios de Livros Relacionados