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
bolas idênticas, sendo exatamente uma falsa e mais leve, e dispomos de uma balança de pratos iguais onde cabem até
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
pesagens conseguimos distinguir até
resultados diferentes. Como temos
bolas possíveis para a falsa, precisamos de
Para
temos
insuficiente, e para
temos
. Logo, no mínimo
pesagens são necessárias.
Passo 3
Uma estratégia que usa exatamente
pesagens é: na primeira pesagem colocamos
bolas de um lado e
bolas de outro. A partir do resultado, separamos dois casos principais:
Passo 4
Caso a balança fique em equilíbrio (ou seja, aquelas
bolas são todas verdadeiras), a falsa está entre as
não pesadas. Agora temos
pesagens sobrando e precisamos isolar a falsa em
candidatas. Fazemos:
– Segunda pesagem: escolhemos bola A e
bola B dessas
e pesamos A versus B.
– Segunda pesagem: escolhemos
- Se A baixa, A é a falsa.
- Se B baixa, B é a falsa.
- Se equilibrar, a falsa está entre as
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
bolas do prato mais leve. Agora temos ainda
pesagens para detectar a falsa em um grupo de
. Basta:
– Segunda pesagem: pegamos duas dessas três bolas, digamos X e Y, e pesamos X versus Y.
– 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ó usamospesagens, sobrando para eventuais verificações extras, mas o pior caso ainda será .
Resposta
No pior caso, são necessárias 3 pesagens.