1. Quantas pesagens em uma balança de pratos são necessárias para encontrar uma moeda falsa entre oito 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.
      *9. Quantas pesagens em uma balança de pratos são necessárias para encontrar uma moeda falsa entre 12 moedas se a moeda falsa for mais leve do que as outras? Descreva um algoritmo para encontrar a moeda mais leve usando este número de pesagens.

Passo 1

O enunciado traz dois problemas de “moeda falsa” usando balança de pratos. No problema 8 temos 8 moedas e a falsa pode ser tanto mais pesada quanto mais leve. No problema 9 temos 12 moedas e sabemos que a falsa é mais leve. O conteúdo usado é análise de informação em cada pesagem (cada pesagem tem três resultados possíveis: esquerda desce, direita desce ou equilíbrio) e construção de algoritmos que dividem as moedas em grupos adequados.

Passo 2

Para o problema 8 precisamos distinguir 8 moedas e ainda saber se a falsa é mais leve ou mais pesada, totalizando 8\times2=16 hipóteses. Em n pesagens obtemos 3^n resultados distintos. Logo buscamos o menor n tal que
3^n \ge 16.
Testando, 3^2=9<16 e 3^3=27\ge16. Portanto n=3.

Passo 3

Algoritmo em 3 pesagens para 8 moedas C_1,\dots,C_8:
1ª pesagem: pese \{C_1,C_2,C_3\} contra \{C_4,C_5,C_6\}.
  • Se equilibrar, a falsa está em \{C_7,C_8\}.
    2ª pesagem: pese C_7 contra C_8.
  • Se desequilibrar, a mais pesada ou a mais leve será a falsa e já sabemos o sentido.
  • Se equilibrar (impossível nesse ramo), seria contradição.
  • Se desbalancear (por exemplo, esquerda desceu), a falsa está em \{C_1,C_2,C_3,C_4,C_5,C_6\} e sabemos se ela é pesada ou leve comparando o sentido do desvio.
    2ª pesagem: escolha três moedas do lado baixo e três do alto de forma simétrica, por exemplo pese \{C_1,C_2,C_4\} vs \{C_3,C_5,C_6\}.
  • Se equilibrar, a falsa é a não pesada das duas que restaram deste grupo de seis; faça a 3ª pesagem entre essas duas para identificá-la e seu tipo (leve/pesada).
  • Se não equilibrar, resta um grupo de três no qual já sabemos se procuramos a mais pesada ou a mais leve.
    3ª pesagem: pese duas dessas três; ou encontra logo a falsa ou, se equilibrar, sabemos que é a terceira.

Passo 4

Para o problema 9 temos 12 hipóteses (já que a falsa é sempre mais leve). Buscamos n tal que
3^n \ge 12.
Novamente 3^2=9<12 e 3^3=27\ge12, logo n=3.

Passo 5

Algoritmo em 3 pesagens para 12 moedas C_1,\dots,C_{12}, falsa mais leve:
1ª pesagem: pese \{C_1,\dots,C_4\} vs \{C_5,\dots,C_8\}.
  • Se equilibrar, a falsa está em \{C_9,C_{10},C_{11},C_{12}\}.
  • Se um lado subir, a falsa está nesse lado que subiu.
2ª pesagem (supondo que o grupo de 4 suspeitas seja G): pese 2 moedas de G contra 2 moedas conhecidas boas.
  • Se equilibrar, a falsa fica entre as 2 não pesadas de G.
  • Se um lado subir, a falsa é a que está nesse lado que subiu.
3ª pesagem: compare as duas candidatas ou pese uma candidata contra uma moeda boa. Em qualquer caso identifica-se qual é a falsa.

Resposta

(8) São necessárias 3 pesagens.
(9) São necessárias 3 pesagens.

Exercícios de Livros Relacionados