[obm-l] O problema das pesagens

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

On Thu, Jun 17, 2004 at 10:21:53AM -0300, Vania Ioott wrote:
> Muuuuuuuuuuito obrigada!
 
>   Vania Ioott wrote:
> 
>   > Eu tenho 12 bolinhas idênticas e apenas 1 com peso diferente. Usando uma 
>   > balança de pratos e fazendo apenas 3 pesagens, quero saber qual delas 
>   > tem peso diferente e se esta é mais leve ou mais pesada que as outras.
> 
>   Aff, mais difícil do que parece inicialmente:


Já responderam, mas se você procurar nos arquivos da lista deve encontrar
a versão geral:

Dadas n bolinhas com uma diferente das outras, determine f(n), o número
mínimo necessário de pesagens em uma balança de dois pratos para determinar
qual é a que tem peso diferente e se esta é mais leve ou mais pesada que
as outras.

e a variação:

Dadas n bolinhas com uma diferente das outras, determine g(n), o número
mínimo necessário de pesagens em uma balança de dois pratos para determinar
qual é a que tem peso diferente (sem necessariamente determinar se esta é
mais leve ou mais pesada que as outras).

A resposta é f(n) = teto(log3(2n+2)) e g(n) = teto(log3(2n)).
Aqui log3(x) significa logaritmo na base 3 de x e teto(x) é o menor
inteiro maior ou igual a x.

Em particular, com 13 bolinhas ainda é possível determinar qual é
a diferente mas é impossível garantir que você sempre saiba se ela
é mais pesada ou mais leve.

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