Re: [obm-l] Questão interessante ( Dos pesosdistintos)

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] Questão interessante ( Dos pesos distintos)

on 20.03.05 16:00, Robÿffffe9rio Alves at prof_roberio@yahoo.com.br wrote:

> DAdos n ( n maior ou igual do que 2 ) objetos de pesos distintos, prove que é possivel determinar qual o mais pesado fazendo 2n - 3 pesagens em uma balança de pratos. É esse número mínimo de pesagens que permitem determinar o mais leve e o mais pesado ? 
>
> Como faz?
>
> Faz por inducao.
>
> Pra n = 2 eh obvio: colocamos um objeto em cada prato e vemos imediatamente qual o mais pesado, com apenas 2*2 - 3 = 1 pesagem.
>
> Suponhamos que isso seja verdade pra n objetos.
>
> Se tivermos n+1 objetos, separamos um deles e, em 2n - 3 pesagens, descobrimos qual o mais pesado dentro os n restantes (pela hipotese de inducao).
>
> Em seguida, com mais uma pesagem (analoga ao caso n= 2) comparamos este objeto com aquele que separamos inicialmente.
> Total = 2n - 3 + 1 = 2n - 2 = 2(n+1) - 4 < 2(n+1) - 3 pesagens. 
>
> ***
>
> Este nao eh o numero minimo de pesagens.
>  
> O numero minimo de pesagens eh igual a n - 1.
>
> P_1: compara a_1 e a_2, obtendo max(a_1,a_2);
> P_2: compara max(a_1,a_2) e a_3, obtendo max(a_1,a_2,a_3);
> ...
> P_(n-1): compara max(a_1,a_2,...,a_(n-1)) e a_n, obtendo max(a_1,a_2,...,a_n).
>
> Repare que isso soh prova que o numero minimo de pesagens eh <= n-1 mas, por inducao, dah pra mostrar que este eh de fato o minimo.
>
>
> []s,
> Claudio.