Torre de Hanói

Torre de Hanói, um jogo ou um quebra-cabeças?

  A torre de Hanói é um jogo de origem oriental, estilo quebra-cabeças, formado por 3 pinos em uma base. Em um dos pinos estão dispostos alguns discos uns sobre os outros, em ordem decrescente de diâmetro, de baixo para cima.
  A grande questão deste jogo, é passar todos os discos de um pino para outro qualquer, usando um dos pinos como referência, de tal forma que o disco maior sempre fique abaixo do menor.
  O número de discos pode variar sendo que o mais simples contém apenas três.
  Este jogo é usado para avaliar a capacidade de memória de trabalho, planejamento e solução de problemas
Como surgiu

  Existem diversas lendas a respeito da origem deste jogo, que inspirou Edouard Lucas a construir a Torre de Hanói. O nome Hanói é em homenagem a cidade de Hanói, em Vietnã.
  A lenda mais creditada é a respeito de um templo Hindu, centrado no Universo. Diz-se que Brahma (primeiro deus da trindade do hinduísmo) teria criado uma torre com 64 discos de ouro e mais duas estacas (pinos) equilibradas sobre uma base. Brahma pediu aos seus seguidores que movessem todos os discos de uma estaca para outra segundo as suas instruções. As regras eram simples: apenas um disco poderia ser movido por vez e nunca um disco maior deveria ficar por cima de um disco menor. Segundo esta lenda, quando todos os discos fossem transferidos de uma estaca para a outra, o templo iria desmoronar e teríamos o fim do mundo.


Solução do jogo

  É interessante observar que o número mínimo de "movimentos" para conseguir transferir todos os discos da primeira estaca à terceira é 2n - 1, sendo n o número de discos. Logo:

  Para solucionar um Hanói de 4 discos (animação ao lado), são necessários 15 movimentos (24 - 1 = 15).

Para solucionar um Hanói de 7 discos, são necessários 127 movimentos (27 - 1 = 127).

Para solucionar um Hanói de 15 discos, são necessários 32.767 movimentos (215 - 1 = 32.767).

  Para entender a lógica da Torre de Hanói é necessário analisar a construção de diferentes níveis da torre com o número mínimo de movimentos, tendo o nível anterior já formado, sendo que esses níveis são o número de peças desintegradas da torre original que irão formar outra torre com os menores discos.
  Para mover o primeiro disco da torre original, 1 movimento é gasto. Para mover o segundo da torre original, sendo que o primeiro já foi movido e será construída uma torre com os 2 menores discos, são gastos 2 movimentos. Para deslocar o terceiro disco formando nova torre com os três menores discos, tendo a torre com os dois menores já formada, são gastos 4 movimentos.
  Assim se sucede com os próximos discos até que o enésimo disco (o último) seja deslocado compondo uma torre com os outros discos, tendo uma torre com o penúltimo disco e os demais juntos já formada. A sucessão formada pela soma dos movimentos é uma sucessão (1, 2, 4, 8, ..., 2n).

A fórmula 2n - 1 é consequência de uma soma de uma progressão geométrica. Vejamos:

Para somarmos os termos de uma progressão geométrica usamos a fórmula



onde a1 é o primeiro termo, q é a razão e n é o número de termos. Na torre de Hanói, temos q = 2 e a1 = 1.




Pesquisa realizada no site:
http://matematica.com.br