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