Solução do problema da Torre de Hanoi

Propus há uns posts atrás (link) a resolução desse interessante problema de contagem: Qual o número mínimo de movimentos para resolver uma Torre de Hanoi com n discos? Resolverei agora e demonstrarei usando uma das armas mais potentes disponíveis no meu ferramental matemático: a indução.

Retomando o tema, a Torre de Hanoi é um quebra-cabeça clássico que consiste em uma base com três postes dispostos em linha. O objetivo é passar todos os discos do poste do meio, onde começam, para algum dos outros dois, movendo apenas uma peça de cada vez e nunca colocando um disco maior em cima de um menor. Se você não tem uma Torre de Hanoi por perto para fazer as experimentações desejadas pode usar esse site.

Vamos começar do início então. Partindo do número 1, vamos fazer algums experiências para tentar intuir uma fórmula. Um disco exige um mínimo de 1 movimento para a solução; dois discos pedem 3 movimentos; três discos precisam de 7 movimentos; quatro discos requerem 15 movimentos. Já é possível notar uma relação? Aparentemente o número de movimentos (M) para resolver uma torre de n discos é dado pela n-ésima potência de 2 diminuída de uma unidade.

Já sabemos que essa solução é satisfatória para os primeiros valores de n, mas como saber se vale sempre? Como saber se para valores enormes de n essa função não se comporta de maneira estranha? Provarei que a solução proposta é válida sempre utilizando a indução matemática.

Em primeiro lugar, preciso saber se a solução é válida para o primeiro valor possível. De fato, para n=1 obtemos M=1, o que é correto.

Agora vamos supor que essa solução é válida para n. Se provarmos que ela é também válida para n+1 a demonstração está completa. Digamos que tívéssemos uma torre de n discos e acrescentamos mais um. Pense na figura a seguir dessa forma: uma torre genérica de n discos com um disco embaixo.

Primeiro precisaremos passar todos os discos da torre de n discos para um dos outros dois postes. Para isso sabemos que precisamos de movimentos.

Passaremos o disco maior agora para o outro poste, o que nos dá mais um movimento. Até agora temos então movimentos.

E agora toda a pilha deve ir para cima do disco maior, somando mais uma vez os movimentos e nos deixando com, no total, movimentos.

Assim, teremos:

Supondo que a fórmula funciona para n concluimos que funciona também para n+1. Assim, como sabemos que ela funciona para 1, podemos concluir pelo princípio da indução matemática que a fórmula funciona para qualquer .

Quanto ao princípio da indução, sugiro que leia um pouco a respeito caso não tenha entendido, mas basta pensar como uma imensa fila de situações. Se eu sei que depois de uma que dá certo a próxima também dá certo basta que a primeira funcione para que todas funcionem.