Torre de Hanói
A Torre de Hanói é um quebra-cabeças matemático clássico. Três hastes, uma pilha de discos de tamanhos diferentes e duas regras rígidas: mova um disco de cada vez e nunca ponha um disco maior sobre um menor.
Três hastes e um cone de discos
O tabuleiro tem três hastes. Os discos têm todos tamanhos diferentes e encaixam nas hastes. No início, o conjunto inteiro está numa haste, ordenado por tamanho, o maior em baixo e o menor em cima, por isso a pilha forma um cone. O objetivo é mover essa torre inteira para outra haste.
As três regras
1. Mova apenas um disco de cada vez. 2. Um movimento pega no disco de cima de uma pilha e coloca-o noutra pilha, ou numa haste vazia. 3. Um disco maior nunca pode ficar sobre um menor. Essas três regras são o jogo todo. Com elas, cada posição válida é uma forma de distribuir os discos pelas hastes mantendo cada haste ordenada.
A solução mais curta é 2ⁿ − 1
O menor número de movimentos que resolve uma torre de n discos é 2ⁿ − 1. Um disco leva 1 movimento. Dois discos levam 3. Três levam 7, quatro 15 e cinco 31. Cada disco novo duplica a solução anterior e acrescenta o movimento que leva o disco maior: se n − 1 discos levam T movimentos, n discos levam 2T + 1. Essa recorrência é exatamente 2ⁿ − 1. Oito discos, a torre mais alta da aplicação PictorX, levam 255 movimentos. Não existe nenhum caminho válido mais curto.
Como funciona a recursão
Para mover n discos da haste de partida para a haste de destino, usando a haste restante como auxiliar: 1. Mova os n − 1 discos de cima da haste de partida para a haste auxiliar. 2. Mova o disco maior da haste de partida diretamente para a haste de destino. 3. Mova os n − 1 discos da haste auxiliar para a haste de destino, por cima do disco maior. O passo 2 é válido porque o disco maior pode ficar em qualquer haste. Os passos 1 e 3 são o mesmo quebra-cabeças, com um disco a menos. A chamada termina num único disco, que se move uma vez. Desenrolando-a, obtêm-se os 2ⁿ − 1 movimentos, e nenhum passo coloca alguma vez um disco maior sobre um menor.
A lenda dos 64 discos de ouro
O matemático francês Édouard Lucas apresentou o quebra-cabeças em 1883. Com ele contou uma lenda sobre um templo indiano em Kashi Vishwanath, onde sacerdotes movem uma pilha de 64 discos de ouro segundo estas mesmas regras. Quando for feito o último movimento, diz a lenda, o mundo acabará. Sessenta e quatro discos levam 2⁶⁴ − 1 movimentos: 18.446.744.073.709.551.615. A um movimento perfeito por segundo, dia e noite, são cerca de 585 mil milhões de anos. Os sacerdotes não vão terminar.
Jogue no PictorX
Abra Torre de Hanói e já há uma torre de quatro discos na haste de partida. Quinze movimentos é o mínimo. Arraste o disco de cima para outra haste, ou clique numa haste e depois na que quiser. As teclas 1, 2 e 3 fazem o mesmo. Um disco maior sobre um menor é recusado. Discos vai de 1 a 8, por isso pode comparar 1, 3, 7, 15, 31, 63, 127 e 255 com a fórmula. Passo reproduz um movimento de uma solução mais curta. Resolver reproduz o resto. «Ver 3 discos» mostra a estratégia recursiva em movimento. Desfazer e Refazer percorrem os seus movimentos. Guarde um PNG ou abra o tabuleiro no editor do PictorX.
Perguntas frequentes
Quais são as regras da Torre de Hanói?
Mova um disco de cada vez. Pegue no disco de cima de uma haste e coloque-o noutra haste. Nunca ponha um disco maior sobre um menor. A torre inteira começa numa haste e tem de terminar noutra.
Quantos movimentos leva a solução mais curta?
2ⁿ − 1. Um disco é 1 movimento, dois discos são 3, três são 7, quatro são 15 e cinco são 31. Cada disco acrescentado duplica a solução anterior e soma um movimento.
Quem inventou a Torre de Hanói?
O matemático francês Édouard Lucas apresentou-o em 1883. A história dos sacerdotes e dos 64 discos de ouro de Kashi Vishwanath é a lenda que associou ao quebra-cabeças.
Quanto tempo levariam 64 discos?
2⁶⁴ − 1 movimentos, ou seja, 18.446.744.073.709.551.615. A um movimento por segundo, são cerca de 585 mil milhões de anos.
Ferramentas relacionadas
Torre de Hanói
Mova uma torre de discos entre três hastes no seu navegador. Um disco de cada vez, nunca um maior sobre um menor. A solução mais curta tem 2ⁿ − 1 movimentos.
Agulha de Buffon
Deixe cair agulhas num chão com riscas no seu navegador. Conte os cruzamentos e veja a experiência de Buffon de 1777 estimar π.
Agulha de Buffon
O problema da agulha de Buffon de 1777: porque é que uma agulha largada sobre linhas paralelas estima π, como a probabilidade 2l/(πd) da agulha curta resulta da área sob uma curva do seno e porque é que a experiência converge devagar.
Círculos de multiplicação
Ligue cada número de um círculo ao seu múltiplo. Desenhe uma tabuada, uma cardioide ou uma figura de fio em papel, a giz ou em madeira.
A conjetura de Collatz
Explore o problema de Collatz 3n+1 no seu navegador. Percorra sequências de granizo, faça crescer uma árvore de Collatz geométrica e aproxime o fractal de Collatz contínuo.
Formiga de Langton
Execute a formiga de Langton no navegador. Veja a simetria, o caos e a autoestrada de 104 passos e depois experimente regras multicoloridas, várias formigas, uma grelha hexagonal e turmites.
Pronto para experimentar?
Abra o PictorX em seu navegador – sem instalação, sem necessidade de cartão de crédito para iniciar.
Jogar Torre de Hanói