Question

de um conjunto de 25 moedas de ouro sabe-se que uma falsa e pesa menos do que as restantes existe disponível uma balança de pratos que no entanto apenas pode efectuar um máximo 3 pesagens Descobre um algoritmo que permite encontrar alguma moeda falsa usando a balança de pratos

Answer 1

Boa noite,  

Primeiro devemos obter alguns dados:

• Restrição = 3 pesagens;
• 1 moeda é falsa e pesa menos

Os dado acima são as principais informações para a resolução do nosso exercício.

Como você pode ver temos uma restrição no processo de descoberta da moeda falsa, que é o fato de a balança realizar apenas 3 pesagens;

Assim, precisamos organizar as 25 moedas de tal forma que seja possível realizar a pesagem de todo o conjunto em apenas três tentativas;

Uma forma de realizar o procedimento é dividir as 25 moedas em três grupos, os quais denominaremos de G1, G2 e G3.

G1 = 9 moedas

G2 = 9 moedas

G3 = 9 moedas

Inicialmente pesaremos

• G1 e G2 = se a balança se mantiver em equilíbrio ambos os grupos apresentam moedas verdadeiras, assim, saberemos que a moeda falsa encontra-se ou em G3 ou nas 7 moedas que não foram pesadas. Porém, se um deles baixar teremos uma moeda falsa;

Supondo que G1 ou G2 tenham apresentado desequilíbrio (mais leve):

• Separar G1 / G2 em três grupos de 3 moedas que chamaremos de:
• GG1 = 3 moedas
• GG2 = 3 moedas
• GG3 = 3 moedas
• Pesar GG1 em comparação a GG2, se houver equilíbrio a moeda falsa está em GG3;

Supondo que o grupo GG3 tenha apresentado a moeda falsa:

• Realizamos a 3ª pesagem colocando uma moeda em cada prato da balança;
• Se houver equilíbrio, a moeda falsa é a que ficou sem pesar;
• Se um dos lados ceder, este possuirá a moeda falsa;

• Apenas quatro moedas e pesar ambas. Se a balança ceder em um dos lados, o lado mais baixo apresentará a moeda falsa, e então basta pesar as duas moedas restantes em comparação.
• Porém, de a balança apresentar equilíbrio a moeda sem pesar será a falsa;

Supondo que G1 e G2 tenham apresentado equilíbrio:

• Retirar uma moeda de G3 e pesar as 7 moedas com as demais 7 moedas restantes;
• Se houver equilíbrio, as três moedas restantes apresentam a moeda falsa, e neste caso pesamos um em cada prato e verificamos se há equilíbrio ou desequilíbrio;

Se as 7 moedas pesadas acima apresentarem desequilíbrio:

• Pesar 3 moedas em cada prato;
• Se houver desequilíbrio, a moeda está em um dos pratos
• Se houver equilíbrio, a moeda restante é falsa

Espero ter ajudado =D