On Wed, May 18, 2005 at 05:49:34PM -0300, S�ffffe9rgio Canova J�fffffanior wrote: > Eu tenho 12 bolas iguais e uma balan�a. Uma das bolas tem peso diferentes das > demais. Como, com apenas 3 pesagens eu posso dizer qual a bola de peso > diferente e dizer se ela � mais leve ou mais pesada? > > Uma vez acho vi uma generaliza��o deste problema que mostrava quantas > pesagens s�o necess�rias para n bolas. > S� que n�o consigo lembrar onde foi > que vi isso. Algu�m sabe demonstrar isso? >� realmente poss�vel? Onde posso > encontrar essa demonstra��o? Obrigado
Este � um caso particular do problema proposto n�mero 10 que aparece na p�gina 59 da Eureka n�mero 2. A solu��o do caso particular aparece na Eureka n�mero 4, p�gina 54. A solu��o do caso geral aparece na Eureka n�mero 6, p�gina 42 (claro!). O problema tamb�m foi discutido nesta lista em agosto de 2002, veja, entre outras, http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200208/msg00213.html http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.1999a/msg00095.html Separe as bolas em tres grupos de 4, bote o primeiro grupo em um prato, o segundo grupo no outro prato e deixe o terceiro grupo de fora. Se equilibrar (caso 1) sabemos que a bola diferente est� entre as 4 que ficaram de fora e que as outras 8 s�o normais. Se desequilibrar (caso 2) sabemos que as 4 de fora s�o normais; quanto �s outras, h� quatro que sabemos que *se* forem diferentes *ent�o* s�o pesadas, outras quatro que sabemos que *se* forem diferentes *ent�o* s�o leves. No caso (1) coloque em um prato 3 bolas suspeitas (daquelas que ficaram de fora da primeira vez) e no outro prato 3 bolas normais (das outras). No caso (2) coloque em cada prato 2 moedas possivelmente pesadas e uma possivelmente leve. A conclus�o fica para voc�s. Em geral, com n >= 2 pesagens voc� resolve o problema para (3^n-3)/2 bolas. Com (3^n - 1)/2 bolas ainda � poss�vel descobrir qual � a bola diferente mas nem sempre � poss�vel dizer se ela � pesada ou leve. Com (3^n + 1)/2 bolas nem sempre � poss�vel descobrir qual � a bola diferente. []s, N. ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
