Re: [obm-l] Moedas em sacos

[Bruno Bruno <brunobbruno@xxxxxxxxx>]

Claudio, inspirado no seu racioc�nio consegui chegar a 883.
(Desculpe o pl�gio, mas gostei da sua id�ia)

Suponhamos que uma moeda normal pese P e uma moeda mais pesada pese P+Q.

1a pesagem:
Colocamos 441 sacos num prato e 441 no outro. Se ficarem iguais
obviamente ser� o outro saco, mas como isso � quase impossivel,
a balan�a indicar� em que prato est� o saco mais pesado e o tamb�m o
valor de Q, igual a 1/10 da leitura da balan�a.

2a pesagem:
Numeramos os 441 sacos de 0 a 440 e fazemos o seguinte:
Sacos de 0 a 20  --- nao pesamos.  
Sacos de 21 a 41 --- uma moeda na esquerda
Sacos de 42 a 62 --- duas moedas na esquerda
...
Sacos de 21k a 21k+20 --- k moedas na esquerda
...
Sacos de 210 a 230 --- 10 moedas na esquerda
Repetindo o processo com os outros sacos, para o lado direito da
balan�a, chegamos finalmente ate o saco 440.

Pesando, j� conhecido o valor de Q, chegamos a um grupo final de 21
sacos, dentre os quais estar� o mais pesado.

Terceira pesagem:
Renumerando os sacos de 0 a 20, faremos o seguinte:
N�o pesaremos o saco 0.
Colocaremos K moedas do saco K na esquerda (caso 0<K<11)
e colocaremos K moedas do saco K + 10 na direita (0<K<11)
Assim, concluiremos qual o saco mais pesado.

Por que acho (n�o tenho a menor certeza) que esse � o maior numero possivel:
A ultima pesagem pode ter no m�ximo 21 sacos. A 1a pesagem deve ser
usada para descobrirmos o valor de Q, fundamental para as proximas
pesagens. Assim, a 2a pesagem deve reduzir de (N-1)/2 para 21. Como
s�o 10 moedas em cada saco, podemos fazer 21 grupos, o que faz com que
(N-1)/2max = 21^2 = 441  => N=883

ps.: tentando rapidamente generalizar o problema, caso existam X
moedas em cada saco, Nmax = [(2X+1)^2]*2 + 1.  Ou caso existam X
moedas, e Y pesagens, Nmax = [(2X+1)^(Y-1)]*2+1
Ou ainda no remoto caso de haverem Z pratos (imaginem s�, uma balan�a
de prato com 3, 8, 20 pratos... ainda bem que isso � matematica, nao
fisica) Nmax = [(ZX+1)^(Y-1)]*Z + 1. Acho q me empolguei, desculpem.



On Tue, 15 Feb 2005 15:59:25 -0300, Rogerio Ponce
<rogerio_ponce@hotmail.com> wrote:
> Caro Claudio,
> como sempre a sua engenhosidade � bem vinda.
> Mas N pode ser ainda maior...
> Grande abra�o,
> Rog�rio.
> 
> >From: "claudio.buffara" > Ola' pessoal,
> > >
> > > Existem N sacos abertos com 10 moedas cada um.
> > > Um deles, defeituoso, tem 10 moedas iguais entre si, porem mais pesadas
> >que
> > > o padrao. Os outros sacos tem as 10 moedas com o peso padrao (a
> >principio
> > > desconhecido).
> > >
> > > Voce dispoe de uma balanca de 2 pratos, que fornece a diferenca de peso
> > > entre os pratos (prato da esquerda menos prato da direita).
> > >
> > > Qual o maior N que ainda permite a determinacao do saco defeituoso com
> > > apenas 3 leituras ?
> > >
> > > []'s
> > > Rogerio Ponce
> > >
> >
> >Eu achei N = 242 mas n�o sei provar que este � o maior N poss�vel.
> >
> >Suponhamos que uma moeda normal pese P e uma moeda mais pesada pese P+Q.
> >
> >PRIMEIRA PESAGEM:
> >Colocamos 121 sacos num prato e 121 no outro.
> >A balan�a indicar� em que prato est� o saco mais pesado e o tamb�m o valor
> >de Q, igual a 1/10 da leitura da balan�a.
> >
> >SEGUNDA PESAGEM:
> >Numeramos os 121 sacos que incluem o mais pesado de 0 a 120 e fazemos o
> >seguinte:
> >Sacos 0 a 10: 0 moedas no prato da E e 10 moedas no prato da D;
> >Sacos 11 a 21: 1 moeda no prato da E e 9 moedas no prato da D;
> >...
> >Sacos 11k a 11k+10: k moedas no prato da E e 10-k moedas no prato da D;
> >...
> >Sacos 110 a 120: 10 moedas no prato da E e 0 moedas no prato da D.
> >
> >(obs: estou supondo que mesmo ap�s colocar as moedas nos pratos da balan�a,
> >continuamos a saber de que saco elas vieram. Por exemplo, podemos empilhar
> >as moedas de um mesmo saco e operar a balan�a com cuidado de forma que as
> >pilhas n�o desabem)
> >
> >Suponhamos que o n�mero do saco mais pesado seja 11k + r (0 <= r <= 10).
> >Nesse caso, os pesos em cada prato ser�o:
> >E = 605P + kQ
> >e
> >D = 605P + (10-k)Q
> >Logo, leitura da balan�a = E - D = (2k-10)Q.
> >Como j� sabemos o valor de Q, ficaremos sabendo o valor de k.
> >
> >Ou seja, ap�s esta segunda pesagem, ficaremos sabendo que o saco mais
> >pesado � um dos 11 seguintes: 11k, 11k+1, ..., 11k+10.
> >
> >TERCEIRA PESAGEM:
> >Re-numeramos os 11 sacos que incluem o mais pesado de 0 a 10 e fazemos o
> >seguinte:
> >Saco 0: 0 moedas no prato da E e 10 moedas no prato da D;
> >Saco 1: 1 moeda no prato da E e 9 moedas no prato da D;
> >...
> >Saco m: m moedas no prato da E e 10-m moedas no prato da D;
> >...
> >Saco 10: 10 moedas no prato da E e 0 moedas no prato da D.
> >
> >Suponhamos que o saco mais pesado seja o m-�simo.
> >Os pesos em cada prato ser�o:
> >E = 55P + mQ
> >e
> >D = 55P + (10-m)Q.
> >
> >Leitura da balan�a = E - D = (2m-10)Q.
> >Como conhecemos Q, podemos determinar m e acabou.
> >
> >[]s,
> >Claudio.
> 
> _________________________________________________________________
> Chegou o que faltava: MSN Acesso Gr�tis. Instale J�!
> http://www.msn.com.br/discador
> 
> =========================================================================
> 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
> =========================================================================
>

=========================================================================
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
=========================================================================