Re: [obm-l] Moedas em sacos

["Qwert Smith" <lord_qwert@xxxxxxxxxxx>]

Ok N=927 and counting...
veja o meu reply pro email do Claudio

>From: Bruno Bruno <brunobbruno@gmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Re: [obm-l] Moedas em sacos
>Date: Tue, 15 Feb 2005 18:30:04 -0300
>
>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
>=========================================================================


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