Use indução para mostrar que:
Uma Torre de Hanoi, com
peças, pode ser “resolvida” com
movimentos.
Uma Torre de Hanoi, com
Passo 1
O enunciado pede para mostrar, por indução, que uma Torre de Hanoi com
peças pode ser resolvida com
movimentos. Informações e condições do problema que vamos usar (regras clássicas da Torre de Hanoi):
- Há três pinos (origem, auxiliar e destino).
- As
peças têm tamanhos distintos e estão inicialmente empilhadas no pino origem, da maior embaixo para a menor em cima. - Em cada movimento pode-se deslocar apenas a peça do topo de um pino para o topo de outro pino.
- Nunca se pode colocar uma peça maior sobre uma menor.
O objetivo é mostrar que existe um procedimento que leva aspeças do pino origem ao pino destino em exatamente movimentos (e, a seguir, também vamos argumentar que não é possível com menos).
Passo 2
Explicando o método que o enunciado pediu: indução matemática. Indução funciona em duas partes:
- Caso base: verificar que a afirmação é verdadeira para um valor inicial de
(normalmente ). - Passo indutivo: assumir que a afirmação é verdadeira para
(hipótese de indução) e então provar que isso implica que a afirmação é verdadeira para .
Ao usar indução aqui, vamos também descrever um procedimento que mostra como executar os movimentos; esse procedimento leva naturalmente a uma relação de recorrência que será usada na prova.
Passo 3
Caso base (
). Com apenas uma peça, para levá-la do pino origem ao pino destino basta um único movimento: pegar a peça e colocá-la no pino destino. Assim o número de movimentos é
. A fórmula proposta dá
Portanto a afirmação é verdadeira para
.
Passo 4
Intuição e recorrência. Para
, considere as
peças empilhadas no pino origem. Pense no maior disco (o de baixo). Para movê-lo do pino origem para o pino destino é necessário que os
discos menores estejam fora do caminho — isto é, empilhados em algum outro pino (o pino auxiliar). Isso sugere uma estratégia natural:
- Mover os
discos superiores do pino origem para o pino auxiliar (usando o pino destino como auxiliar nesse subprocedimento). - Mover o maior disco (o de número
) do pino origem para o pino destino (isso custa exatamente um movimento). - Mover os
discos do pino auxiliar para o pino destino (usando o pino origem como auxiliar).
Se chamarmoso número mínimo de movimentos necessários para mover discos de um pino a outro seguindo as regras, esse raciocínio mostra que qualquer solução que faça isso precisa, antes de mover o maior disco, ter movido os discos; depois de mover o maior disco precisa mover os discos novamente. Isso leva à recorrência
Também já vimos que
.
Passo 5
Prova por indução de que a solução da recorrência é
.
Hipótese de indução: suponha que para algum
valha
. Vamos provar que então
.
Usamos a recorrência para
:
Pelo que assumimos (hipótese de indução),
. Substituindo:
Agora desenvolvemos a expressão passo a passo:
Logo
. Isso completa o passo indutivo. Como temos o caso base
, por indução matemática
para todo
.
Passo 6
Interpretação prática (construção do algoritmo) e comentário sobre minimalidade:
- A construção do Passo 4 dá um algoritmo explícito que atinge exatamente
movimentos: recursivamente mover discos, mover o maior, mover os discos restantes. Assim provamos existência de uma solução com movimentos. - A mesma recorrência combinada com o argumento de que é preciso deslocar os
discos antes e depois de mover o maior mostra também que nenhum algoritmo pode usar menos movimentos: para que o maior disco seja deslocado, todos os outros têm de estar empilhados em outro pino, o que exige pelo menos movimentos; depois do movimento do maior, é preciso ainda pelo menos movimentos para colocar os discos sobre ele no destino. Assim qualquer algoritmo precisa de pelo menos movimentos, e por indução isso implica que . Como já construímos um algoritmo com exatamente , concluímos que é o número mínimo de movimentos necessários.
Resposta
Com
peças, a Torre de Hanoi pode ser resolvida em
movimentos.