Dados n(n >= 2) objetos de pesos distintos, prove que é possível determinar qual o mais leve e qual o mais pesado fazendo 2 n-3 pesagens em uma balança de pratos. É esse o número mínimo de pesagens que permitem determinar o mais leve e o mais pesado?

Passo 1

O problema dá n objetos de pesos todos diferentes e pede para achar o mais leve e o mais pesado usando uma balança de pratos. Cada pesagem compara dois objetos e nos diz qual é mais pesado. Vamos descrever um algoritmo que, em no máximo 2n-3 pesagens, identifica o mínimo e o máximo.

Passo 2

Começamos comparando os dois primeiros objetos, digamos A1 e A2. Fazemos uma pesagem:
A1 ;vs; A2
Suponha, sem perda de generalidade, que A1 seja o mais leve e A2 o mais pesado até agora. Assim definimos dois candidatos:
  • candmin=A1,
  • candmax=A2.
    Isso custou 1 pesagem.

Passo 3

Agora, para cada um dos restantes n-2 objetos A3,A4,dots,An, procedemos assim:
1. Comparamos Ak com candmin.
  • Se Ak for mais leve, atualizamos candmin=Ak.
  • Caso contrário, comparamos Ak com candmax:
    • Se Ak for mais pesado, atualizamos candmax=Ak.
    • Caso contrário, Ak fica no meio e não altera nenhum candidato.
      Cada objeto pode desencadear até 2 pesagens (uma contra o mínimo, outra contra o máximo).

Passo 4

Contabilizando as pesagens:
  • 1 pesagem inicial entre A1 e A2,
  • para os n-2 objetos restantes, até 2 pesagens cada, total de 2(n-2).
    Logo o total é
1 + 2(n-2) ;=; 2n - 3
Assim obtemos de fato o mais leve e o mais pesado em no máximo 2n-3 pesagens.

Passo 5

Pergunta: esse valor é mínimo?
Não. Pode-se mostrar que qualquer algoritmo de comparação precisa de, em média, cerca de 1,5,n pesagens. De fato existe um método “torneio em pares” que encontra mínimo e máximo em
llceiltfrac3n2rrceil ;-;2
pesagens, e pode-se provar também que nenhuma estratégia faz menos do que esse número no pior caso. Para n par obtém-se exatamente tfrac3n2-2, e isso é melhor que 2n-3 sempre que n>=4.

Resposta

Não, o número mínimo de pesagens necessário e suficiente para achar simultaneamente o mais leve e o mais pesado é
llceiltfrac3n2rrceil -2,
que é menor que 2n-3 para n>=4.

Exercícios relacionados