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
pesagens, podemos distinguir até
cenários. Como há
moedas e a falsa pode ser mais pesada ou mais leve, totalizamos
cenários distintos. Logo, precisamos de
tal que
Testando valores inteiros de
, vemos que
e
. Portanto, o número mínimo de pesagens é
.
Passo 3
Vamos rotular as moedas por
,
,
e
.
Primeira pesagem: coloque contra
.
Primeira pesagem: coloque
- Se equilibrar, então nem
nem são falsas, e a moeda falsa está em . - Se
descer (ou seja, mais pesado que ), a falsa é ou (pesada) ou (leve). - Se
subir (ou seja, mais leve que ), a falsa é ou (leve) ou (pesada).
Passo 4
Segunda pesagem: procede conforme o resultado da primeira.
- Caso a primeira tenha equilibrado, pese
contra (sabendo que é genuína).
- Se equilibrar, então
é a falsa; como = , o desvio só aparece ao comparar com qualquer genuína: se quiser, pode concluir pesado ou leve. - Se
descer, é a falsa e é mais pesada. - Se
subir, é a falsa e é mais leve.
- Caso a primeira tenha dado
mais pesado que , pese contra (sabendo que é genuína).
- Se equilibrar, então
é a falsa e, por ter sido “mais leve” em relação a , concluímos que é leve. - Se
descer, então é a falsa pesada. - Se
subir, esse resultado é impossível dentro do nosso cenário (sinal de inconsistência).
- Caso a primeira tenha dado
mais leve que , pese contra (sabendo que é genuína).
- Se equilibrar, então
é a falsa e é pesada. - Se
subir, então é a falsa leve. - Se
descer, impossível neste cenário.
Com essas duas pesagens distinguimos todos os
cenários (quatro moedas
duas naturezas).
Resposta
São necessárias 2 pesagens.