Quantas pesagens em uma balança de pratos são necessárias para encontrar uma moeda falsa entre quatro moedas se a moeda falsa puder tanto ser mais pesada quanto mais leve do que as outras? Descreva um algoritmo para encontrar a moeda falsa usando este número de pesagens.

Passo 1

O enunciado pergunta quantas pesagens em uma balança de pratos são necessárias para, entre quatro moedas, identificar qual é a falsa e ainda descobrir se ela é mais pesada ou mais leve que as demais. O conteúdo envolvido aqui é de informação em experimento multinário, pois cada pesagem tem três resultados possíveis (esquerda desce, direita desce ou equilíbrio). Vamos usar essa ideia de contagem de possibilidades para achar o número mínimo de pesagens e em seguida apresentar um algoritmo concreto que atinja esse mínimo.

Passo 2

Cada pesagem tem três resultados possíveis, de modo que, com k pesagens, podemos distinguir até 3^k cenários. Como há 4 moedas e a falsa pode ser mais pesada ou mais leve, totalizamos 4\times 2 = 8 cenários distintos. Logo, precisamos de k tal que
3^k \ge 8.
Testando valores inteiros de k, vemos que 3^1=3<8 e 3^2=9\ge8. Portanto, o número mínimo de pesagens é 2.

Passo 3

Vamos rotular as moedas por A, B, C e D.
Primeira pesagem: coloque A contra B.
  • Se equilibrar, então nem A nem B são falsas, e a moeda falsa está em \{C,D\}.
  • Se A descer (ou seja, A mais pesado que B), a falsa é ou A (pesada) ou B (leve).
  • Se A subir (ou seja, A mais leve que B), a falsa é ou A (leve) ou B (pesada).

Passo 4

Segunda pesagem: procede conforme o resultado da primeira.
  1. Caso a primeira tenha equilibrado, pese C contra A (sabendo que A é genuína).
  • Se equilibrar, então D é a falsa; como C = A, o desvio só aparece ao comparar D com qualquer genuína: se quiser, pode concluir D pesado ou leve.
  • Se C descer, C é a falsa e é mais pesada.
  • Se C subir, C é a falsa e é mais leve.
  1. Caso a primeira tenha dado A mais pesado que B, pese A contra C (sabendo que C é genuína).
  • Se equilibrar, então B é a falsa e, por ter sido “mais leve” em relação a A, concluímos que B é leve.
  • Se A descer, então A é a falsa pesada.
  • Se A subir, esse resultado é impossível dentro do nosso cenário (sinal de inconsistência).
  1. Caso a primeira tenha dado A mais leve que B, pese A contra C (sabendo que C é genuína).
  • Se equilibrar, então B é a falsa e é pesada.
  • Se A subir, então A é a falsa leve.
  • Se A descer, impossível neste cenário.
Com essas duas pesagens distinguimos todos os 8 cenários (quatro moedas \times duas naturezas).

Resposta

São necessárias 2 pesagens.

Exercícios de Livros Relacionados