Re: [obm-l] bola mais pesada/leve

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Wed, May 18, 2005 at 05:49:34PM -0300, Sÿffffe9rgio Canova Jÿfffffanior wrote:
> Eu tenho 12 bolas iguais e uma balança. Uma das bolas tem peso diferentes das
> demais. Como, com apenas 3 pesagens eu posso dizer qual a bola de peso
> diferente e dizer se ela é mais leve ou mais pesada?
> 
> Uma vez acho vi uma generalização deste problema que mostrava quantas
> pesagens são necessárias para n bolas.
> Só que não  consigo lembrar onde foi
> que vi isso. Alguém sabe demonstrar isso?
>É realmente possível? Onde posso
> encontrar essa demonstração? Obrigado

Este é um caso particular do problema proposto número 10 que aparece
na página 59 da Eureka número 2. A solução do caso particular aparece
na Eureka número 4, página 54. A solução do caso geral aparece na
Eureka número 6, página 42 (claro!).

O problema também foi discutido nesta lista em agosto de 2002, veja,
entre outras,
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200208/msg00213.html
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.1999a/msg00095.html

Separe as bolas em tres grupos de 4, bote o primeiro grupo em um prato,
o segundo grupo no outro prato e deixe o terceiro grupo de fora.
Se equilibrar (caso 1) sabemos que a bola diferente está entre as 4 que ficaram
de fora e que as outras 8 são normais. Se desequilibrar (caso 2) sabemos que as
4 de fora são normais; quanto às outras, há quatro que sabemos que *se*
forem diferentes *então* são pesadas, outras quatro que sabemos que *se*
forem diferentes *então* são leves.

No caso (1) coloque em um prato 3 bolas suspeitas (daquelas que ficaram
de fora da primeira vez) e no outro prato 3 bolas normais (das outras).
No caso (2) coloque em cada prato 2 moedas possivelmente pesadas e uma
possivelmente leve. A conclusão fica para vocês.

Em geral, com n >= 2 pesagens você resolve o problema para (3^n-3)/2 bolas.
Com (3^n - 1)/2 bolas ainda é possível descobrir qual é a bola diferente
mas nem sempre é possível dizer se ela é pesada ou leve.
Com (3^n + 1)/2 bolas nem sempre é possível descobrir qual é a bola diferente.

[]s, N.


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