Dados
objetos de pesos distintos, prove que é possível determinar qual o mais leve e qual o mais pesado fazendo
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á
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
pesagens, identifica o mínimo e o máximo.
Passo 2
Começamos comparando os dois primeiros objetos, digamos
e
. Fazemos uma pesagem:
Suponha, sem perda de generalidade, que
seja o mais leve e
o mais pesado até agora. Assim definimos dois candidatos:
-
, -
.
Isso custoupesagem.
Passo 3
Agora, para cada um dos restantes
objetos
, procedemos assim:
. Comparamos
com
.
- Se
for mais leve, atualizamos . - Caso contrário, comparamos
com : - Se
for mais pesado, atualizamos . - Caso contrário,
fica no meio e não altera nenhum candidato.
Cada objeto pode desencadear atépesagens (uma contra o mínimo, outra contra o máximo).
- Se
Passo 4
Contabilizando as pesagens:
-
pesagem inicial entre e , - para os
objetos restantes, até pesagens cada, total de .
Logo o total é
Assim obtemos de fato o mais leve e o mais pesado em no máximo
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 pesagens. De fato existe um método “torneio em pares” que encontra mínimo e máximo em
Não. Pode-se mostrar que qualquer algoritmo de comparação precisa de, em média, cerca de
pesagens, e pode-se provar também que nenhuma estratégia faz menos do que esse número no pior caso. Para
par obtém-se exatamente
, e isso é melhor que
sempre que
.
Resposta
Não, o número mínimo de pesagens necessário e suficiente para achar simultaneamente o mais leve e o mais pesado é
que é menor que
para
.