Princípio de Indução - PROFMAT/Parte 1

Vamos resolver aqui alguns exercícios utilizando o princípio de indução que estão no livro de Matemática Discreta do PROFMAT, com a intenção de estudar para ENQ. 

Questão 1) Dados $ 3^n $ objetos de pesos iguais, exceto um, mais pesado que os demais, mostre que é possível determinar este objeto com n pesagens em uma balança de pratos. 

Resolução: Primeiramente, vamos analisar alguns pesos.

Se n = 1, temos 3 objetos. Pode acontecer apenas uma das situações:

Situação 1) a balança desequilibrar e imediatamente sabemos qual objeto é o mais pesado. 

Situação 2) a balança equilibrar e o objeto mais pesado será o que não foi pesado. 

Em ambas as situações é necessário apenas uma pesagem. 

Se n = 2, temos 9 objetos. Agora, separando os objetos em grupos de três, pode acontecer apenas uma das situações:

Situação 1) a balança desequilibrar e imediatamente sabemos em qual grupo o objeto mais pesado está e assim repetimos o processo para n = 1. 

Situação 2) a balança equilibrar e assim o objeto mais pesado estará no grupo que não foi pesado e repetimos o processo para n = 1. 

Em ambas as situações é necessário duas pesagens. 

Agora, vamos provar que é possível identificar qual dos $ 3^n $ objetos é o mais pesado com n pesagens. 

Caso base: Já verificado para n = 1. 

Passo de indução: Vamos supor que é possível identificar qual dos $ 3^n $ objetos é o mais pesado com n pesagens. Agora, verificaremos se é possível determinar com n + 1 pesagens qual dos $ 3^{n+1} $ objetos é o mais pesado. 

Temos $ 3^{n+1} $ objetos que podem ser separados em 3 grupos de $ 3^n $ objetos. Pesando 2 desses, temos apenas uma das situações:

Situação 1) a balança desequilibra e imediatamente sabemos em qual grupo o objeto mais pesado está.

Situação 2) a balança equilibra e assim o objeto mais pesado estará no grupo que não foi pesado. 

Em ambas as situações, com apenas uma pesagem descobrimos qual grupo possui o elemento mais pesado. Para descobrir o objeto mais pesado do grupo de $ 3^n $ objetos, temos, por hipótese de indução, que são necessárias n pesagens. Assim, temos n + 1 pesagens para  $ 3^{n+1} $ objetos. 

Por indução, provamos que é possível descobrir com n pesagens qual é o objeto mais pesado entre os $ 3^n $.