Dados n(n >= 2) objetos de pesos distintos, prove que é possível determinar o objeto mais pesado usando uma balança.

Passo 1

Resumindo o enunciado: temos n 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 n=2, basta pesar os dois objetos uma única vez. A balança indicará qual dos dois é mais pesado, logo o enunciado vale para n=2.

Passo 3

Hipótese de indução: suponha que, para algum k>=2, sempre seja possível encontrar o objeto mais pesado dentre k objetos distintos usando exatamente k-1 pesagens.

Passo 4

Passo de indução: considere agora k+1 objetos O1,O2,dots,Ok,Ok+1.
Pelo passo anterior, com k-1 pesagens nós determinamos o objeto mais pesado entre O1,dots,Ok; chame-o de Mk. Em seguida, fazemos uma pesagem comparando Mk com Ok+1. A balança indica o mais pesado entre eles, que é então o mais pesado dos k+1 objetos.

Passo 5

Concluímos que, para k+1 objetos, basta (k-1)+1=k pesagens para achar o mais pesado. Assim, por indução, para todo n>=2 podemos determinar o objeto mais pesado usando exatamente n-1 pesagens.

Resposta

Usando indução, provamos que com n-1 comparações na balança é sempre possível encontrar o objeto de maior peso.

Exercícios relacionados