Re: um (dois) belo(s) problema(s)

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

   O problema das 13 e 14 moedas esta resolvido na Eureka 4...
Abracos,
          Gugu

>
>On Sun, 27 Jun 1999, albert bouskela wrote:
>
>> O prob. q. segue (apresentado na forma restrita) é  realmente muito bonito.
>> Pena q. sua solucão já seja do conhecimento de muitos.
>> A estes tantos, peço q. não divulguem a respectiva solução e q. tentem resolvê-lo na forma generalizada,
>> cuja solução só é do conhecimento dos iniciados.
>> A solução racional (não intuitiva) da forma restrita já é um belo desafio aos neófitos.
>> 
>> 1. FORMA RESTRITA
>> 
>> Seja um conjunto de 12 moedas. Onze são verdadeiras, uma é falsa.
>> A moeda falsa tem um peso DIFERENTE das demais onze moedas,
>> podendo ser mais leve ou mais pesada q. as moedas verdadeiras.
>> As onze moedas verdadeiras têm o mesmo peso.
>> Pede-se determinar, através de apenas 3 (três) pesagens, a moeda falsa.
>> As pesagens devem ser do tipo "comparação" entre os subconjuntos das 12 moedas.
>> Exemplo de uma pesagem: comparar 2 moedas com outras 2, deixando 8 isoladas.
>
>Na verdade é possível resolver o problema como formulado acima para 13
>moedas. O porém é que existe a possibilidade de que você ao final das
>pesagens saiba *qual* é a moeda falsa mas não saiba *se* ela é mais pesada
>ou mais leve que as demais.
>
>> 2. FORMA GENERALIZADA
>> 
>> Estabelecer uma relação ALGÉBRICA entre "m" e "n" , sendo:
>> m = número de moedas
>> m-1 = número de moedas verdadeiras (1 é falsa)
>> n = número mínimo, necessário e suficiente, de pesagens para a determinação da moeda falsa.
>
>É um belo problema, um clássico.
>
>Notem que há duas versões: uma em que devemos apenas determinar qual
>a moeda falsa e outra em que devemos também determinar se ela é mais
>leve ou mais pesada que as demais. A parte mais interessante do problema
>é demonstrar que é *impossível* resolver o problema com, digamos, 14
>moedas e 3 pesagens.
>
>[]s, N. 
>http://www.mat.puc-rio.br/~nicolau
>