Use indução para mostrar que:
Uma Torre de Hanoi, com n peças, pode ser “resolvida” com 2^{n}-1 movimentos.

Passo 1

O enunciado pede para mostrar, por indução, que uma Torre de Hanoi com n peças pode ser resolvida com 2^{n}-1 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 n 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 as n peças do pino origem ao pino destino em exatamente 2^{n}-1 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 n (normalmente n=1).
  • Passo indutivo: assumir que a afirmação é verdadeira para n-1 (hipótese de indução) e então provar que isso implica que a afirmação é verdadeira para n.
    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 ( n=1). 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 é 1. A fórmula proposta dá
2^{1}-1 = 2-1 = 1.
Portanto a afirmação é verdadeira para n=1.

Passo 4

Intuição e recorrência. Para n\ge 2, considere as n 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 n-1 discos menores estejam fora do caminho — isto é, empilhados em algum outro pino (o pino auxiliar). Isso sugere uma estratégia natural:
  1. Mover os n-1 discos superiores do pino origem para o pino auxiliar (usando o pino destino como auxiliar nesse subprocedimento).
  2. Mover o maior disco (o de número n) do pino origem para o pino destino (isso custa exatamente um movimento).
  3. Mover os n-1 discos do pino auxiliar para o pino destino (usando o pino origem como auxiliar).
    Se chamarmos T(n) o número mínimo de movimentos necessários para mover n 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 n-1 discos; depois de mover o maior disco precisa mover os n-1 discos novamente. Isso leva à recorrência
T(n)=2\,T(n-1)+1.
Também já vimos que T(1)=1.

Passo 5

Prova por indução de que a solução da recorrência é T(n)=2^{n}-1.
Hipótese de indução: suponha que para algum k\ge 1 valha T(k)=2^{k}-1. Vamos provar que então T(k+1)=2^{k+1}-1.
Usamos a recorrência para n=k+1:
T(k+1)=2\,T(k)+1.
Pelo que assumimos (hipótese de indução), T(k)=2^{k}-1. Substituindo:
T(k+1)=2\bigl(2^{k}-1\bigr)+1.
Agora desenvolvemos a expressão passo a passo:
2\bigl(2^{k}-1\bigr)+1 = 2\cdot 2^{k}-2+1 = 2^{k+1}-1.
Logo T(k+1)=2^{k+1}-1. Isso completa o passo indutivo. Como temos o caso base T(1)=1, por indução matemática T(n)=2^{n}-1 para todo n\in\mathbb{N}.

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 2^{n}-1 movimentos: recursivamente mover n-1 discos, mover o maior, mover os n-1 discos restantes. Assim provamos existência de uma solução com 2^{n}-1 movimentos.
  • A mesma recorrência combinada com o argumento de que é preciso deslocar os n-1 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 n-1 outros têm de estar empilhados em outro pino, o que exige pelo menos T(n-1) movimentos; depois do movimento do maior, é preciso ainda pelo menos T(n-1) movimentos para colocar os n-1 discos sobre ele no destino. Assim qualquer algoritmo precisa de pelo menos 2\,T(n-1)+1 movimentos, e por indução isso implica que T(n)\ge 2^{n}-1. Como já construímos um algoritmo com exatamente 2^{n}-1, concluímos que 2^{n}-1 é o número mínimo de movimentos necessários.

Resposta

Com n peças, a Torre de Hanoi pode ser resolvida em 2^{n}-1 movimentos.

Exercícios relacionados