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 C_1,C_2,C_3,C_4, 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 k pesagens podemos distinguir até 3^k situações diferentes. Como temos 4 moedas e uma delas é falsa, precisamos de
3^k \ge 4.
O menor k inteiro que satisfaz isso é k=2, pois 3^1=3<4 e 3^2=9\ge4. Logo, no mínimo 2 pesagens são necessárias.

Passo 3

Descrição da primeira pesagem: coloque C_1 no prato esquerdo e C_2 no prato direito.
  • Se a balança equilibrar, então nem C_1 nem C_2 é falsa; sobram apenas C_3 e C_4 como candidatas.
  • Se a balança pender para um dos lados (digamos, C_1 pesa menos que C_2), então a falsa está entre C_1 e C_2 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 \{C_3,C_4\}, pese C_3 contra C_4. A mais leve é a falsa.
  • Caso a falsa esteja em \{C_1,C_2\}, pese C_1 contra C_2. Novamente, a mais leve é a falsa.

Resposta

São necessárias 2 pesagens. O algoritmo é:
  1. Pesar C_1 vs C_2.
  2. Pesar as duas moedas candidatas que sobraram nesse primeiro resultado; a mais leve é a falsa.

Exercícios de Livros Relacionados