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 discos3 hastes4 hastes
3 discos75
4 discos159
5 discos3113
6 discos6317
7 discos12725
8 discos25533
10 discos1.02349
64 discoscerca de 18,4 quintilhões18.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:

  1. Mova os k discos de cima, usando as 4 hastes, para uma haste que não seja a de destino.
  2. 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).
  3. 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.