A TORRE DE HANÓI
O problema seguinte
foi formulado e resolvido pelo matemático francês Édouard Lucas (1842 - 1891) em 1883,
no terceiro volume da sua obra Récréations mathématiques. O problema está
relacionado com um jogo que ficou conhecido como a TORRE DE HANÓI e que consiste,
muito simplesmente, num tabuleiro rectangular onde se devem fixar hastes verticais
(cilíndricas e iguais), e em n discos (circulares), não havendo dois discos com o mesmo
diâmetro. Cada disco tem um pequeno orifício no centro de forma a poder ser enfiado em
qualquer uma das hastes. No início do jogo, todos os discos devem ser enfiados na mesma
haste por ordem decrescente, ficando o maior na base da torre assim construída (cada
disco pode, portanto, representar um andar da torre).
O objectivo do jogo é transferir todos os
discos de forma a reconstruir a torre numa (qualquer) das outras hastes, obedecendo
às seguintes regras :
(i) Em cada movimento só
poderá ser transferido um disco ;
(ii) Em nenhum dos movimentos
poderá o jogador colocar um disco sobre outro de menor diâmetro.
No seu livro, Lucas conta uma história curiosa
em que afirma ter conhecido o jogo da Torre de Hanói através de N. Claus, um professor
de Filosofia e Cálculo no Colégio Li-Sou-Stian, na cidade de Bangkok, capital do reino
indochinês do Sião. O próprio Claus terá sabido do jogo, por acaso, numa das inúmeras
viagens que empreendia pela Indochina a fim de recolher informações sobre as muitas
obras dispersas do genial matemático siamês Fer-fer-tam-tam. Nessa viagem, Claus teria
visitado um templo riquíssimo na cidade santa de Benares - que, para os hindus, se situa
no centro do mundo - e teria assim conhecido a Lenda do Fim do Mundo. Segundo lhe
revelaram os cem monges do Templo de Benares, no Princípio do Mundo o deus Brahma
construíra uma torre, como indicámos acima, com 64 discos de ouro puro - a que os monges
chamavam a Torre de Brahma. E Brahma teria ordenado aos seus cem monges que recontruíssem
a Torre numa das outras hastes, transferindo um disco de cada vez e formando em cada
movimento uma torre semelhante à inicial. Quando a tarefa fosse concluída, a torre e o
templo ruiriam e o mundo terminaria. Seria o Fim da Humanidade...Bom ! Para sermos mais
rigorosos, será o Fim da Humanidade : a reconstrução da Torre exige 18446744073709551615
movimentos !! Um número com vinte algarismos! Consegue lê-lo? Se admitirmos que
os monges efectuam um movimento por segundo (o que é bastante improvável), serão
necessários 584942417355 anos para terminar o jogo, o que excede em
muito o "tempo de vida" previsto para o sol. O deus Brahma foi realmente muito
benevolente...
Já vimos qual o número de movimentos
necessários para terminar um jogo com 64 discos.
QUAL O NÚMERO MÍNIMO DE
MOVIMENTOS NECESSÁRIOS PARA COMPLETAR UM JOGO DE TORRE DE HANÓI??
Se pensarmos um pouco chegamos à conclusão de que o jogo pode sempre ser
terminado (embora possa ser impossível chegar ao fim do jogo durante a nossa vida).
Para isso basta usar o princípio de indução matemática. É claro que o jogo
termina quando consideramos apenas um disco. Suponhamos agora, por hipótese de indução,
que um jogo com n discos (n é um natural não nulo). Então para terminar um jogo
com (n + 1) discos, bastará seguir a estratégia seguinte:
1. Transferir os n discos do topo da torre
para uma haste diferente da original;
2. Mudar o disco da base (o maior) para a
haste que sobra e que, nesta altura, é a única que se encontra "vazia";
3. Tranferir a torre de n discos,
construída no passo 1, para a haste onde se encontra o disco maior.
Deste modo, pelo princípio de indução, o jogo tem solução qualquer que seja o número
de discos considerado. Continuando o raciocínio e utilizando o método de
substituição de diante para trás chegaríamos à conclusão que o número mínimo de
movimentos que são necessários para terminar um jogo da Torre de Hanói com n discos é
dado por uma sucessão cujo termo geral é
an = 2n - 1.
Muito provavelmente a maioria dos alunos conhece este jogo e certamente ficarão
entusiasmados ao saber que poderão conhecer o número de movimentos antecipadamente por
estudo da sucessão cujo termo geral se apresentou.
