Dados
objetos de pesos distintos, prove que é possível determinar o objeto mais pesado usando uma balança.
Passo 1
Resumindo o enunciado: temos
objetos com pesos todos distintos e dispomos de uma balança de comparação que, dada uma dupla de objetos, diz qual deles é mais pesado. O objetivo é provar que, usando a balança, sempre podemos identificar o objeto mais pesado. O conteúdo é seleção pelo máximo e vamos usar prova por indução.
Passo 2
Caso base: se
, basta pesar os dois objetos uma única vez. A balança indicará qual dos dois é mais pesado, logo o enunciado vale para
.
Passo 3
Hipótese de indução: suponha que, para algum
, sempre seja possível encontrar o objeto mais pesado dentre
objetos distintos usando exatamente
pesagens.
Passo 4
Passo de indução: considere agora
objetos
.
Pelo passo anterior, com pesagens nós determinamos o objeto mais pesado entre
; chame-o de
. Em seguida, fazemos uma pesagem comparando
com
. A balança indica o mais pesado entre eles, que é então o mais pesado dos
objetos.
Pelo passo anterior, com
Passo 5
Concluímos que, para
objetos, basta
pesagens para achar o mais pesado. Assim, por indução, para todo
podemos determinar o objeto mais pesado usando exatamente
pesagens.
Resposta
Usando indução, provamos que com
comparações na balança é sempre possível encontrar o objeto de maior peso.