A Torre de Hanói

Prévia do material em texto

ANA PAULA BRAGA
ENGENHARIA ELÉTRICA
TUTOR(A) VANESSA DA LUZ VIEIRA
 A Torre de Hanói é um dos quebra-cabeças matemáticos mais populares. Ele foi inventado por Edouard Lucas em 1883.
1. As peças são n discos de tamanhos diferentes e todos com um furo em seu centro e três pinos onde são colocados os discos. Certamente podem ser encontrados em qualquer loja de brinquedos.
 
2. Regras e objetivos do jogo
Inicialmente os discos formam uma torre onde todos são colocados em um dos pinos em ordem decrescente de tamanho.
Devemos transferir toda a torre para um dos outros pinos de modo que cada movimento é feito somente com um disco, nunca havendo um disco maior sobre um disco menor.
 
3. A Pergunta que será calada
Queremos saber qual é o menor número de movimentos necessários para resolver uma torre de Hanói com n discos.
Há uma história (imaginada pelo próprio Edouard Lucas) sobre a torre de Hanói:
No começo dos tempos, Deus criou a Torre de Brahma, que contém três pinos de diamante e colocou no primeiro pino 64 discos de ouro maciço. Deus então chamou seus sacerdotes e ordenou-lhes que transferissem todos os discos para o terceiro pino, seguindo as regras acima. Os sacerdotes então obedeceram e começaram o seu trabalho, dia e noite. Quando eles terminarem, a Torre de Brahma irá ruir e o mundo acabará.
4. Estudando o problema
Para resolver um problema (não só este, mas vários outros problemas na matemática) que envolve n coisas, ajuda ver o que acontece para valores pequenos de n. Vejamos alguns casos.
· n = 1. Fazemos
1 movimento foi suficiente.
 
· n = 2. Fazemos
 
3 movimentos deram.
 
· n = 3. Fazemos
 
 
7 movimentos deram.
Mas é claro que não podemos fazer só isso. Não podemos ficar observando o que acontece para todos os valores de n! Então temos que começar a tirar algumas conclusões.
 
5. Como resolver o problema com n discos?
Vamos olhar o caso n = 3 mais perto. Observe os três primeiros movimentos:
 
Note que o que fizemos foi mesmo para resolver o caso n = 2. O próximo movimento foi
Isto é, passamos o disco maior para o pino sem discos.
Agora, veja os três últimos movimentos:
 
Novamente fizemos o mesmo que foi feito para o caso n = 2, só que transferindo agora a “subtorre” para o pino onde estava o disco maior.
Agora, imaginemos uma torre com n discos. Imagine também que sabemos resolver o problema com n – 1 discos.
Podemos transferir os n – 1 discos de cima para um pino vazio:
Depois passamos o disco maior para o outro pino vazio:
Por fim, colocamos os n – 1 discos menores sobre o disco maior:
Assim, podemos resolver o problema com n discos. Por exemplo, para resolver o problema com 4 discos, transferimos os 4 – 1 = 3 discos de cima para um pino vazio (já sabemos fazer isso!), depois passamos o disco maior para o outro pino vazio e por fim colocamos os 3 discos sobre o disco maior. Para resolver o problema com 5 discos, transferimos os 5 – 1 = 4 discos de cima para um pino vazio e assim por diante.