Quantas pesagens em uma balança de pratos são necessárias para encontrar uma moeda falsa mais leve entre quatro moedas? Descreva um algoritmo para encontrar a moeda mais leve usando este número de pesagens.
Passo 1
O enunciado pede para achar, entre quatro moedas
, aquela que é falsa e mais leve, usando uma balança de pratos. O conteúdo envolve decisão em cada pesagem (três possíveis resultados: esquerda mais leve, direita mais leve ou equilíbrio) e teoria da informação para determinar o mínimo de pesagens.
Passo 2
Para saber quantas pesagens são necessárias, note que cada pesagem dá até três resultados distintos. Com
pesagens podemos distinguir até
situações diferentes. Como temos 4 moedas e uma delas é falsa, precisamos de
O menor
inteiro que satisfaz isso é
, pois
e
. Logo, no mínimo 2 pesagens são necessárias.
Passo 3
Descrição da primeira pesagem: coloque
no prato esquerdo e
no prato direito.
- Se a balança equilibrar, então nem
nem é falsa; sobram apenas e como candidatas. - Se a balança pender para um dos lados (digamos,
pesa menos que ), então a falsa está entre e e, mais precisamente, é a que estiver no prato mais leve.
Passo 4
Descrição da segunda pesagem, dependendo do resultado da primeira:
- Caso tenha sobrado o par
, pese contra . A mais leve é a falsa. - Caso a falsa esteja em
, pese contra . Novamente, a mais leve é a falsa.
Resposta
São necessárias 2 pesagens. O algoritmo é:
- Pesar
vs . - Pesar as duas moedas candidatas que sobraram nesse primeiro resultado; a mais leve é a falsa.