Re: [obm-l] Moedas em sacos

["Rogerio Ponce" <rogerio_ponce@xxxxxxxxxxx>]

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