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

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

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