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
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
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
discos:
- Se há apenas um disco, ele é movido diretamente para a haste de destino.
- Se há mais de um disco:
(a) Move-se os
discos superiores para uma haste auxiliar (recursivamente).
(b) Move-se o maior disco restante diretamente para a haste de destino.
(c) Move-se os
discos da haste auxiliar para a haste de destino (novamente, recursivamente).
Com base na descrição do algoritmo, defina
como o número de movimentos necessários para resolver a Torre de Hanói com
discos.
(a) Encontre uma relação de recorrência que expressa
em função de
.
(b) Determine a condição inicial da sequência
.
(c) Com base na recorrência obtida, calcule
e
.
(d) Conjecture uma fórmula fechada para
e prove-a por indução.
Considere a seguinte descrição de um algoritmo recursivo para resolver o problema com
(a) Move-se os
(b) Move-se o maior disco restante diretamente para a haste de destino.
(c) Move-se os
(a) Encontre uma relação de recorrência que expressa
(b) Determine a condição inicial da sequência
(c) Com base na recorrência obtida, calcule
(d) Conjecture uma fórmula fechada para
Passo 1
O enunciado pede para estudar a sequência
que conta o número de movimentos do algoritmo recursivo da Torre de Hanói com
discos. O conteúdo envolvido é equação de recorrência e prova por indução.
Passo 2
Para resolver
discos, o algoritmo faz:
- mover
discos para a haste auxiliar em movimentos; - mover o disco maior em 1 movimento;
- mover os
discos da haste auxiliar para a haste de destino em mais movimentos.
Logo,
Passo 3
Para
há só um disco e ele vai direto para a haste de destino em um único movimento. Assim, a condição inicial é
Passo 4
Usando a recorrência e
:
Passo 5
Observando
, conjecturamos a fórmula fechada
Passo 6
Prova por indução em
:
Base :
.
Indutivo: suponha . Então
Base
Indutivo: suponha
Logo a fórmula vale para todo
.
Resposta
(a)
.
(b) .
(c) .
(d) .
(b)
(c)
(d)