Início > Desafios > Desafio das 12 moedas

Desafio das 12 moedas

Deixarei o desafio das 12 moedas como passatempo para os leitores. A melhor resposta será publicada em uma publicação futura como resposta ao desafio das 12 moedas. O desafio é o seguinte:

Você tem em suas mãos 12 moedas aparentemente idênticas, mas sabe que uma delas, falsificada, tem massa ligeiramente diferente das demais e é mais leve! Usando apenas uma balança de dois pratos, você conseguiria descobrir em 3 medições, qual a moeda diferente? Como você faria isso?

OBS: Evite pesquisar a resposta no Google, pois assim não terá nenhuma graça! Procure exercitar um pouco seu cérebro e aproveitar essa data tão especial para resolver esse simples desafio.

Fonte: http://www.vivendoentresimbolos.com/2014/05/6-de-maio-dia-nacional-da-matematica.html

  1. Um antigo aluno
    05/06/2016 às 2:20

    Um fato que pode ser interessante para alguns leitores: um procedimento semelhante ao usado para resolver esse problema é muito utilizado em programação e é chamado de busca binária.

    Tentarei ilustrar qual a vantagem de utilizar esse método com um problema básico:
    Imagine uma lista ordenada de números quaisquer. Um exemplo seria
    1, 3, 4, 6, 8, 9, 10, 11, 12, 15, 16, 17, 18

    Agora é desejado saber se um número específico está nessa lista. Por exemplo, o número 15 está nessa lista?

    Um ideia inicial seria olhar elemento por elemento (lembre-se que é um computador fazendo isso) até chegar ao fim da lista ou chegar ao elemento desejado. No primeiro caso, 15 não estaria na lista, e o contrário acontece no segundo caso.

    Bom, essa ideia funciona. Na lista de exemplo, o computador avaliaria 10 elementos até achar o 15, resultando em 10 comparações (guarde esse número).

    A busca binária começa olhando o elemento do meio (no caso, o 11). Como a lista está ordenada, ele faz a comparação e “percebe” que o 15 está à direita do 11. A partir daqui ele considera apenas uma sub-lista:
    12, 15 16, 17, 18

    A busca binária realiza novamente o procedimento inicial e escolhe o elemento central (no caso, o 16). Ele novamente “percebe” que o 15 está a esquerda e passa a considerar somente a sub-lista:
    12, 15

    Iniciando novamente o processo, a busca binária escolhe o elemento central (quando há um número par de elementos, escolhe-se, por conveniência, o elemento mais à esquerda). O algoritmo então identifica que o 15 está a direita e passa a considerar a sub-lista:
    15

    A busca binária escolhe o elemento central e identifica que é o número procurado.
    Sem ser muito rigoroso, o algoritmo da busca binária encontrou o número fazendo basicamente 4 comparações.

    Vê-se então qual a vantagem de utilizar a busca binária. Reduziu-se de 10 para 4 comparações. Essa redução parece ser pequena, mas é porque esse é um caso pequeno. Em casos maiores, a redução é absurda.

    A busca binária procura “encurralar” o número desejado, semelhante ao problema das moedas.🙂

  2. Um antigo aluno
    22/05/2015 às 16:24

    na primeira pesagem, coloca-se 6 moedas em cada prato. Evidentemente, o lado mais leve (o qual chamarei de A) conterá a moeda falsificada.

    na segunda pesagem, coloca-se em cada prato metade das moedas que estava no prato A, tendo, então, três moedas de cada lado. Dessa forma, mais uma vez, o lado mais leve (chamado de B) conterá a moeda falsificada.

    Na terceira pesagem, coloca-se uma moeda das que estava no lado B em cada prato. Dessa forma, se:

    1. a balança se equilibrar, significa que as duas moedas nos pratos são verdadeiras, então a falsa é aquela que está de fora.
    2. a balança pender para um dos lados, o lado mais leve conterá a moeda falsificada.

  1. No trackbacks yet.

Deixe seu comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: