Quando se resolve a Torre de Hanói com o menor número de movimentos, a sequência tem regularidades surpreendentemente bonitas. Aqui apresentamos, em ordem, as regras encontradas na sequência mínima (2ⁿ−1 movimentos) para mover uma torre de n discos da esquerda para a direita. Os discos são numerados 1, 2, 3… do menor para o maior.

Quantas vezes cada disco se move é uma potência de 2

Na sequência mínima, o número de vezes que cada disco se move é fixo. Com n discos, o disco k se move 2ⁿ⁻ᵏ vezes.

Disco (com 4 discos)Vezes que se move
18 vezes
24 vezes
32 vezes
41 vez
Total15 vezes

O maior disco se move 1 vez, o seguinte 2, o seguinte 4… dobrando a cada tamanho menor. Somando, 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ−1, que coincide exatamente com o mínimo de movimentos.

A razão se entende com a mesma ideia da fórmula do mínimo de movimentos. Para mover n discos, move-se 2 vezes uma torre de n−1 discos. Por isso, os discos menores que o n se movem o dobro de vezes que quando se movem n−1 discos.

Qual disco se move em qual movimento

Na sequência mínima de 4 discos, os números dos discos movidos, do movimento 1 em diante, ficam assim.

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

O 1 aparece de 2 em 2 movimentos, entre eles o 2 aparece de 2 em 2, entre eles o 3… É a mesma forma da sequência de comprimentos dos traços de uma régua (curto, médio, curto, longo…).

Essa sequência se obtém logo escrevendo o número do movimento em binário.

MovimentoBinárioZeros no finalDisco movido
1101
21012
31101
410023
510101
611012
711101
8100034

No movimento m, o disco movido é o de número “quantidade de zeros no final de m em binário + 1”. Nos movimentos de número ímpar, o binário termina em 1, então sempre se move o 1. É a razão do “nos movimentos ímpares, mova o 1” no artigo sobre como resolver.

Além disso, as hastes de origem e de destino também se obtêm só com cálculos em binário (artigo sobre o algoritmo).

A ligação com o código Gray

Ao contar em binário a partir de 0, o número de dígitos que mudam a cada passo varia (de 0111 para 1000, mudam 4 dígitos). Uma forma de escrever números em que a cada passo muda só 1 dígito se chama “código Gray”.

OrdemCódigo GrayDígito que muda (da direita)
0000―
10011
20112
30101
41103
51111
61012
71001

A sequência dos dígitos que mudam, “1 2 1 3 1 2 1”, é exatamente igual à dos discos movidos na Torre de Hanói. Vendo cada disco como um dígito binário e pensando “esse dígito muda = esse disco se move”, a sequência mínima da Torre de Hanói é o mesmo que percorrer o código Gray em ordem.

O sentido em que os discos giram

No artigo sobre como resolver, dissemos que o 1 sempre gira no mesmo sentido. Na verdade, os outros discos têm a mesma regra.

  • Os discos de número ímpar (1, 3, 5…) giram todos no mesmo sentido do 1.
  • Os discos de número par (2, 4, 6…) giram todos no sentido oposto ao do 1.

Ao mover a torre da esquerda para a direita, com uma quantidade ímpar de discos o 1 gira no sentido “esquerda → direita → meio”, e com uma quantidade par, “esquerda → meio → direita”. Nenhum disco muda de sentido até o fim.

Há ainda outra regra, apresentada em Como resolver com 10 discos. Na sequência mínima, nunca se põe um disco ímpar diretamente sobre um ímpar, nem um par sobre um par.

São 3ⁿ disposições, no total

Quantas disposições dos discos seguem as regras? Cada disco pode ficar em qualquer uma das 3 hastes, e a ordem dos discos na mesma haste fica determinada, do maior para o menor, então são 3ⁿ disposições.

Número de discosDisposições
3 discos27
5 discos243
7 discos2.187
9 discos19.683

E de qualquer disposição dá para chegar a qualquer outra, seguindo as regras. Também se sabe que, se você representar cada disposição por um ponto e ligar com linhas os pontos que se alcançam em 1 movimento, sai uma figura muito parecida com o “triângulo de Sierpinski”, com triângulos pequenos aninhados em um grande.

O modo “Desafios” do app Torre de Hanói cria seus problemas, de forma a chegar à forma do modelo, a partir de todas essas disposições. Mesmo em ★5 com 9 discos, os desafios são propostos depois de calcular o mínimo de movimentos para todas as 19.683 disposições.