A Torre de Hanói é um quebra-cabeça clássico inventado no final do século XIX pelo matemático francês Édouard Lucas. Ele é composto por três hastes (ou pinos) e n discos de diferentes tamanhos, todos com furos no centro, inicialmente empilhados em ordem decrescente de tamanho em uma das hastes. A regra do jogo é simples: apenas um disco pode ser movido por vez, e nunca se pode colocar um disco maior sobre um menor.
Segundo uma lenda associada à criação do quebra-cabeça, os discos representam uma torre sagrada de ouro que está sendo transferida por monges em um templo. Essa torre teria 64 discos, e acredita-se que, ao completar a transferência, o mundo chegaria ao fim com um estrondo de trovão. No entanto, como esse processo exigiria 2^{64}-1= 18446744073709551615 movimentos, é razoável supor que algo aconteceria antes que a tarefa fosse concluída.
Considere a seguinte descrição de um algoritmo recursivo para resolver o problema com n discos:
  • Se há apenas um disco, ele é movido diretamente para a haste de destino.
  • Se há mais de um disco:
    (a) Move-se os n-1 discos superiores para uma haste auxiliar (recursivamente).
    (b) Move-se o maior disco restante diretamente para a haste de destino.
    (c) Move-se os n-1 discos da haste auxiliar para a haste de destino (novamente, recursivamente).
Com base na descrição do algoritmo, defina c_{n} como o número de movimentos necessários para resolver a Torre de Hanói com n discos.
(a) Encontre uma relação de recorrência que expressa c_{n} em função de c_{n-1}.
(b) Determine a condição inicial da sequência \left(c_{n}\right).
(c) Com base na recorrência obtida, calcule c_{1}, c_{2}, c_{3} e c_{4}.
(d) Conjecture uma fórmula fechada para c_{n} e prove-a por indução.

Passo 1

O enunciado pede para estudar a sequência \bigl(c_n\bigr) que conta o número de movimentos do algoritmo recursivo da Torre de Hanói com n discos. O conteúdo envolvido é equação de recorrência e prova por indução.

Passo 2

Para resolver n discos, o algoritmo faz:
  1. mover n-1 discos para a haste auxiliar em c_{n-1} movimentos;
  2. mover o disco maior em 1 movimento;
  3. mover os n-1 discos da haste auxiliar para a haste de destino em mais c_{n-1} movimentos.
    Logo,
c_{n} \;=\; c_{n-1} \;+\; 1 \;+\; c_{n-1} \;=\; 2\,c_{n-1} \;+\; 1.

Passo 3

Para n=1 há só um disco e ele vai direto para a haste de destino em um único movimento. Assim, a condição inicial é
c_{1} = 1.

Passo 4

Usando a recorrência e c_{1}=1:
c_{1}=1,\quad c_{2}=2\,c_{1}+1=2\cdot1+1=3,\quad c_{3}=2\,c_{2}+1=2\cdot3+1=7,\quad c_{4}=2\,c_{3}+1=2\cdot7+1=15.

Passo 5

Observando 1,3,7,15,\dots, conjecturamos a fórmula fechada
c_{n} = 2^{n} - 1.

Passo 6

Prova por indução em n:
Base n=1: 2^{1}-1=2-1=1=c_{1}.
Indutivo: suponha c_{k}=2^{k}-1. Então
c_{k+1}=2\,c_{k}+1=2\bigl(2^{k}-1\bigr)+1=2^{k+1}-2+1=2^{k+1}-1.
Logo a fórmula vale para todo n.

Resposta

(a) \displaystyle c_{n}=2\,c_{n-1}+1.
(b) c_{1}=1.
(c) c_{1}=1,\;c_{2}=3,\;c_{3}=7,\;c_{4}=15.
(d) \displaystyle c_{n}=2^{n}-1.

Exercícios relacionados