Descobrir a Moeda Falsa

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"]

 

About these ads

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Problemas com as etiquetas . ligação permanente.

8 respostas a Descobrir a Moeda Falsa

  1. Caro Américo Tavares
    Fui consultar a Tabela Periódica dos Elementos, para saber quais os metais mais de massa volúmica superior ao ouro. Eis o que encontrei:
    Rénio, Ósmio, Irídio, Platina e Urânio, além de alguns transuranianos (sem isótopos estáveis). Todos me pareceram demasiado exóticos para um pobre contrafactor. É certo que não fui taxativo em dizer que a moeda falsa era menos densa, porque me pareceu essa ideia estranha.
    A primeira hipótese descrita no passo 5 não chega a isolar completamente a moeda falsa, pelo que uma nova pesagem se torna necessária. Quer dizer que não é possível terminar este procedimento com duas pesagens, precisamente por estar orientado para a optimização.

  2. Caro António Ferrão

    O passo 5 tinha um erro, que lhe agradeço, e que entretanto corrigi no meu post. Como estava, de nada serviam os passos 6 e 7! Foi um lapso, mas que até me levou a enumerar falsamente os casos possíveis, que também corrigi.

    Não havendo outros erros, mantém-se a conclusão: 4 pesagens, no máximo, excepto se houver um método que, nos meus pressupostos, consiga identificar a moeda contrafeita em menos pesagens. Se houver, não o descobri.

    Sei que a solução correcta já foi há muito apresentada, na condição que como comentado no seu blog se considera estar subentendida, encarando a natureza física do problema.

    Quanto a mim, apenas pretendi conceber um método que fosse independente de se saber a priori se a moeda falsa seria mais ou menos pesada que as restantes.

    Obrigado pelo seu comentário

    ADENDA de 15-5-2008, 10.52: Não acho que esta minha maneira de ver este assunto seja melhor que a que esteve na sua ideia. Até vejo uma contradição na minha abordagem: não atender à parte física do problema, que é para ser resolvido com uma balança, ou seja, um instrumento de medida mecânico.

  3. racamles diz:

    outro dia me passaram o mesmo problema com 40 moedas e 4 pesagens…..nao consegui resolver….voce acredita que devo seguir pelo mesmo caminho demonstrado acima?

  4. Se fossem 91=3^4 moedas e se soubesse que uma seria mais ou menos pesada, poderia seguir o método de Luisa Novo referido acima, dividindo em grupos de três e no fim chegaria a 4 pesagens. Mas o seu caso é diferente. E também é diferente do caso que exponho, porque com 40 moedas não pode formar grupos de três. À primeira vista parecem-me ser necessárias mais pesagens.

  5. Frederico Lourenço diz:

    é possível a resolução do problema com 40 moedas e 4 pesagens, determinando qual é a moeda diferente, não podendo determinar se ela é mais leve ou mais pesado do conjunto. A propósito o desafio ao racamles foi proposto por mim

  6. Caro Frederico Lourenço,

    Como não tem ponto de interrogação, parece-me que não está a perguntar, mas a afirmar ser possível.

    Se quiser revelar algo mais, força!

    Obrigado pelo seu comentário e visita.

    Américo

  7. ACHO QUE ERA O QUE EU ESTAVA PRECIZANDO,POR ISSO AQUI VAI AS MINHAS NOTAS DE AGRADECIMENTO, BOM CONTEÚDO POS ADISPOSIÇÃO DOS LEITORES

  8. erika jessica diz:

    prezardo americo tavares como posso resolver essa questão das pesagens usando oito moedas e podendo realizar apenas duas pesagens? desde ja lhe agradeço.
    erika jessica

Deixar uma resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

WordPress.com Logo

Está a comentar usando a sua conta WordPress.com Log Out / Modificar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Log Out / Modificar )

Facebook photo

Está a comentar usando a sua conta Facebook Log Out / Modificar )

Google+ photo

Está a comentar usando a sua conta Google+ Log Out / Modificar )

Connecting to %s