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" <[EMAIL PROTECTED]> Reply-To: [email protected] To: "obm-l" <[email protected]> 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 =========================================================================
