Re: [obm-l] Moedas em sacos

["Qwert Smith" <lord_qwert@xxxxxxxxxxx>]

Legal, eu tinha limitado a ultima pesagem a 21 sacos fazendo

Prato 1:
1 moeda do saco 1
2 moedas do saco 2
3 moedas do saco 3
...
10 moeadas do saco 10

Prato 2:
1 moeda do saco 11
2 moedas do saco 12
3 moedas do saco 13
...
10 moedas do saco 20

saco 21 ficando de fora da pesagem

Certamente menos eficiente que seu metodo porem usava o fato que nao 
precisamos pesar todos os sacos.

De cara ja da pra aumentar N de 242 pra 287
Faz exatamente oque vc fez e deixa 45 sacos de fora... se os pratos nao 
acusarem diferenca na primeira pesagem usamos meu metodo pouco eficiente de 
pesar 21 sacos de cada lado com 3 sobrando.  Dai ou a terceira pesagem 
resolve entre os 21 sacos do prato mais pesado ou entre os 3 sacos que nunca 
foram pra balanca.  Certamente usando o seu metodo mais eficiente vai dar 
pra deixar de fora bem mais que 45 na primeira pesagem, mas ainda nao fiz as 
contas.  A questao e...como provar que o seu metodo e de fato o mais 
eficiente?

>From: "claudio.buffara" <claudio.buffara@terra.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: "obm-l" <obm-l@mat.puc-rio.br>
>Subject: Re: [obm-l] Moedas em sacos
>Date: Tue, 15 Feb 2005 14:57:21 -0300
>
>On Sat, 12 Feb 2005 10:57:42 -0200, Rogerio Ponce
>wrote:
> > 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.


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