A Torre de Hanói comum tem 3 hastes. E se acrescentarmos uma haste, passando para 4? As regras são as mesmas: mover a torre inteira para outra haste, 1 disco por vez, sem pôr um disco grande sobre um menor.
Com uma haste a mais, os movimentos caem muito
Há mais um lugar para guardar discos, então tirá-los do caminho fica bem mais fácil. Comparando o mínimo de movimentos, a diferença cresce quanto mais discos há.
| Número de discos | 3 hastes | 4 hastes |
|---|---|---|
| 3 discos | 7 | 5 |
| 4 discos | 15 | 9 |
| 5 discos | 31 | 13 |
| 6 discos | 63 | 17 |
| 7 discos | 127 | 25 |
| 8 discos | 255 | 33 |
| 10 discos | 1.023 | 49 |
| 64 discos | cerca de 18,4 quintilhões | 18.433 |
Com 3 hastes, mover 64 discos leva cerca de 584,5 bilhões de anos a 1 movimento por segundo (Quanto tempo levam 64 discos?). Com 4, são 18.433 movimentos, cerca de 5 horas a 1 por segundo. Se os monges da lenda tivessem acrescentado uma haste, o mundo teria acabado no mesmo dia.
O “quebra-cabeça dos queijos” de Dudeney
Quem divulgou a Torre de Hanói com 4 hastes foi o autor de quebra-cabeças inglês Henry Dudeney. No livro The Canterbury Puzzles (Os quebra-cabeças de Canterbury), de 1907, ele a propôs como o “quebra-cabeça de Reve”. Reve (Reeve) era o administrador de uma propriedade rural.
No problema de Dudeney, em vez de discos, são 8 queijos de tamanhos diferentes, movidos entre 4 banquinhos. Não se pode pôr um queijo grande sobre um menor. A resposta são 33 movimentos, igual ao de 8 discos na tabela acima.
O método de Frame e Stewart
Em 1941, J. S. Frame e B. M. Stewart publicaram, cada um, a mesma ideia de como mover com poucos movimentos usando 4 hastes. Para mover uma torre de n discos:
- Mova os k discos de cima, usando as 4 hastes, para uma haste que não seja a de destino.
- Mova os n−k discos restantes para a haste de destino, usando só 3 hastes, sem a haste onde estão os k discos (2ⁿ⁻ᵏ−1 movimentos).
- Mova os k discos afastados no passo 1, usando as 4 hastes, para a haste de destino.
São esses 3 passos. Os passos 1 e 3 são versões menores do mesmo problema, então dá para usar a ideia de recursão (artigo sobre o algoritmo). Resta escolher quantos discos (k) deixar em cima para dar o menor número. Com 8 discos, afastar primeiro os 4 ou 5 de cima é o que dá menos, 33 movimentos.
O “mínimo” que levou quase 100 anos para ser provado
Sabia-se que o método de Frame e Stewart move com poucos movimentos. Mas se não existia um método com ainda menos ninguém conseguiu provar por muito tempo.
Com 3 hastes, o mínimo se prova logo a partir de um único fato: “no momento em que o maior disco se move, todos os outros precisam estar juntos em uma haste” (fórmula do mínimo de movimentos). Com 4, no momento em que o maior disco se move, os outros podem estar divididos de qualquer jeito entre as 2 hastes restantes, e o número de sequências possíveis explode.
Examinando por computador todas as disposições, confirmou-se que esse método é o mínimo até cerca de 30 discos. E em 2014, cerca de 100 anos depois da proposta de Dudeney, o matemático francês Thierry Bousch provou que o método de Frame e Stewart é o mínimo para qualquer quantidade de discos. Com 5 hastes ou mais, diz-se que ainda não há prova.
Dá para testar você mesmo
A Torre de Hanói com 4 hastes se faz com o método de papelão do artigo sobre como fazer, desenhando 4 círculos como lugares. Veja se consegue mover 3 discos em 5 movimentos e 4 discos em 9. Dá para sentir com o corpo a diferença em relação a 3 hastes.
