pdf: ver caderno

Texto do desafio  “A moeda contrafeita“, de António Ferrão, do blog

 Ferrao.org :

 

« Imagine o leitor que está perante um conjunto de 27 moedas de ouro e uma balança mecânica de braços iguais. Dispõe apenas deste material.
É-lhe dito:
- Há uma moeda falsa.

- Que número mínimo de operações com a balança será necessário efectuar para se determinar com certeza qual é a moeda falsa? »

Ver meu comentário

http://problemasteoremas.wordpress.com/2008/04/20/matematica-de-1%c2%aa-por-um-matematico-de-1%c2%aa/#comment-251

Passo a expor um método para conseguir determinar a moeda falsa do conjunto das 27, sem se saber se ela é mais ou menos pesada do que as restantes.

Para facilidade de exposição designo o conjunto das moedas por

M=\lbrace m_1,m_2,\dots ,m_{27}\rbrace .

Divido este conjunto em três outros, com nove moedas cada, M_I,M_{II},M_{III}, respectivamente

M_I=\lbrace m_1,m_2,\dots ,m_{9}\rbrace

M_{II}=\lbrace m_{10},m_{11},\dots ,m_{18}\rbrace

M_{III}=\lbrace m_{19},m_{20},\dots ,m_{27}\rbrace .

A seguir faço as seguintes pesagens:

  • Passo 1 - coloco num dos pratos da balança as moedas do conjunto M_I e no outro as do M_{II}. Se a balança ficar em equilíbrio, a moeda falsa pertence ao conjunto M_{III} e prossigo para o passo 5. Senão, prossigo para o passo 2.
  • Passo 2 – substituo as moedas do prato mais elevado pelas de M_{III} e vejo se o pratos se equilibram, o que indicaria que uma das moedas do prato que estava mais elevado era mais leve. Se não houver equilíbrio da balança, vejo qual dos pratos pesa menos: se for o das moedas M_{III}, é porque uma das moedas do outro prato é mais pesada; caso contrário, uma das moedas do outro prato é mais leve. 
  • Passo 3 – das nove moedas que têm peso diferente, escolho seis e coloco três em cada prato. Se a balança ficar equilibrada é porque uma das três restantes é falsa.  Senão, a moeda falsa é a do prato mais leve ou mais pesado, conforme se tenha visto no passo 2 que a moeda falsa é mais leve ou mais pesada.
  • Passo 4 – coloco uma do grupo das falsas em cada prato: se a balança ficar equilibrada a falsa é a que ficou de fora. Caso contário, é a do prato mais leve ou mais pesado, conforme se tenha visto no passo 2 que a moeda falsa é mais leve ou mais pesada. FIM.
  • Passo 5 -  das nove moedas de M_{III}, escolho seis e coloco três em cada prato. Se a balança ficar equilibrada é porque uma das três restantes é falsa. FIM. Senão, prossigo para o passo 8.
  • Passo 6 – coloco uma do grupo das falsas em cada prato: se a balança ficar equilibrada a falsa é a que ficou de fora. FIM.  Senão houver equilíbrio da balança, vejo qual dos pratos pesa menos.
  • Passo 7 – comparo a moeda do prato que pesa menos com a moeda que ficou de fora: a que pesava menos é falsa se continuar a pesar menos,  caso contário é a que está no prato que pesa mais. FIM.
  • Passo 8 - transfiro duas moedas do prato mais leve para o mais pesado e uma do mais pesado para o mais leve, ficando duas moedas em cada prato. Podem acontecer três situações:
    • a balança ficar desequilibrada para o mesmo lado — a moeda falsa é a que não foi mexida; FIM.
    • a balança continuar desequilibrada, mas com inversão do sentido do desiquilíbrio — a moeda falsa é a que foi transferida do prato mais pesado; FIM.
    • a balançar ficar equilibrada — faço uma última pesagem no passo 9.
  • Passo 9 – escolho uma das duas moedas que não foram transferidas de prato e comparo o seu peso com qualquer das moedas de M_{I} ou M_{II}, que sei não ser falsa. Podem acontecer dois casos:
    • a balança ficar equilibrada — a moeda falsa é a que não foi pesada; FIM.
    • a balança ficar desequilibrada — a moeda falsa é a que está no prato mais pesado. FIM.

Os casos possíveis são então:

  • Passo 1, Passo 5, Passo 6: 3 pesagens
  • Passo 1, Passo 5: Passo 6, Passo 7: 4 pesagens
  • Passo 1, Passo 5, Passo 8: 3 pesagens
  • Passo 1, Passo 5, Passo 8, Passo 9: 4 pesagens
  • Passo 1, Passo 2, Passo 3, Passo 4: 4 pesagens

Por este método consegue-se isolar a moeda falsa em 4 pesagens no máximo.

NOTA: por abuso de linguagem digo prato mais leve e mais pesado querendo significar o prato com o conjunto de moedas menos ou mais pesado.

[Correcção de 15-5-2008: no passo 5 e nos casos possíveis - ver comentário de António Ferrão.]

ADENDA de 15-5-2008: uma abordagem que parte do princípio que a moeda falsa é mais leve do que as restantes, devido a haver pouquíssimos metais mais densos do que o ouro (veja comentário de António Ferrão), traduz-se, com uma forma de esquematização idêntica à de acima, em:

Faço as seguintes pesagens:

  • Passo 1 - coloco num dos pratos da balança as moedas do conjunto M_I e no outro as do M_{II}. Se a balança ficar em equilíbrio, a moeda falsa pertence ao conjunto M_{III}. Se desiquilibar a moeda falsa é uma das que está no prato mais leve.
  • Passo 2 – das nove moedas que incluem a falsa,  escolho seis e coloco três em cada prato. Se a balança ficar equilibrada é porque uma das três restantes é falsa.  Senão, a moeda falsa está no prato mais leve.
  • Passo 3 – coloco uma do grupo das falsas em cada prato: se a balança ficar equilibrada a falsa é a que ficou de fora. FIM.  Se não houver equilíbrio da balança, vejo qual dos pratos pesa menos: nele está a moeda falsa. FIM.

Estas 3 pesagens são suficientes para identificar a moeda falsa.

(Adaptado do comentário de  Luisa Novo  no post http://ferrao.org/2008/04/moeda-contrafeita.html:

« 3 pesagens no mínimo.

1ª em conjuntos de nove moedas em cada prato
2ª em conjuntos de 3 em cada prato
3ª uma em cada prato 

Sempre que a balança equilibre com 2 conjuntos, a moeda falsa estará 3º conjunto no grupo que ficou de fora. Cada vez que a balança desequilibrar a moeda estará no prato com menos peso. » )

\bigskip

Este método é generalizável a qualquer conjunto de 3^n moedas, em que apenas uma seja mais leve do que as restantes. São suficientes n pesagens para identificar a moeda contrafeita.

\bigskip

Neste post
poderá encontrar, em inglês, um problema semelhante para 8 moedas.
\bigskip

NOVA ADENDA de 15-5-2008: nesta entrada de António Chaves Ferrão
\bigskip

\bigskip

poderá encontrar uma explicação sobre a ligação deste problema à teoria da informação de Shannon,  e a consideração da possibilidade teórica de fabricar  « uma moeda contrafeita por deposição electrolítica de uma camada externa de ouro num núcleo de volfrâmio. Como este metal possui a mesma massa volúmica que o ouro, fica aberta uma terceira hipótese, a de que a moeda contrafeita tenha o mesmo peso que as genuinas. O problema, colocado nestes termos, deixa de poder ser resolvido com recurso a uma balança. »
\bigskip

 
[16-5-2008: Alterado título anterior: Moeda Falsa]
[21-8-2008: corrigido "se não" para "senão"]
[4-11-2008: corrigido lapso no nome do leitor/comentador "Frazão" para "Ferrão"]