Fórmula da Torre de Hanói

Uma torre de n discos pode ser movida em 2ⁿ − 1 movimentos, e não em menos. Veja de onde vem esse número e por que não dá para fazer melhor.

Mínimo de movimentos = 2ⁿ − 1

Experimente com 3 discos

De onde vem 2ⁿ − 1

Seja T(n) o menor número de movimentos para n discos. Para mexer no maior disco, todos os outros precisam sair da frente e ficar no pino que sobra: são T(n − 1) movimentos. Depois o disco maior se move uma vez. Por fim, os n − 1 discos menores são levados para cima dele, outra vez T(n − 1) movimentos. Em três passos:

1. mova os n − 1 discos menores para o pino do meio;
2. mova o disco maior para o último pino;
3. mova os n − 1 discos menores para o último pino.

T(n) = 2 · T(n − 1) + 1, com T(0) = 0

Isso gera 1, 3, 7, 15, 31, … Cada número é uma unidade a menos que uma potência de dois. Para ver que é sempre assim, some 1 aos dois lados: T(n) + 1 = 2 · (T(n − 1) + 1). A quantidade T(n) + 1 dobra a cada disco e começa em 1, então é 2ⁿ, e T(n) = 2ⁿ − 1.

Experimente com 4 discos

Prova por indução, em versão curta

Queremos mostrar que T(n) = 2ⁿ − 1 para todo n.

• Base: com 1 disco, basta 1 movimento, e 2¹ − 1 = 1.
• Passo: se vale para n, então T(n + 1) = 2 · (2ⁿ − 1) + 1 = 2ⁿ⁺¹ − 1, que é a fórmula para n + 1.

Falta ver que ninguém consegue menos. Em algum momento o disco maior precisa se mover. Nesse instante ele está sozinho no topo do seu pino e o pino de destino está vazio, então os outros n − 1 discos estão todos no terceiro pino: já foram movidos, o que custou pelo menos T(n − 1). Depois, eles ainda precisam ser levados até o destino, outros T(n − 1) no mínimo. Logo o total nunca é menor que 2 · T(n − 1) + 1.

Experimente com 5 discos

Como saber qual é o próximo movimento

Não é preciso lembrar da recursão inteira. Metade dos movimentos é sempre do menor disco, que anda de dois em dois movimentos, sempre no mesmo sentido, em círculo pelos três pinos:

• com um número ímpar de discos, ele vai do primeiro pino ao último, depois ao do meio, e assim por diante;
• com um número par de discos, ele vai do primeiro pino ao do meio, depois ao último, e assim por diante.

Nos movimentos entre dois deslocamentos do menor disco, só um outro disco pode se mover, então não há escolha. Se você seguir essa regra, termina em exatamente 2ⁿ − 1 movimentos. Para ver a solução passo a passo a partir de qualquer posição, use o solucionador.

Experimente com 4 discos

Quanto tempo levaria uma torre grande

Os números crescem muito depressa. A um movimento por segundo, sem erro e sem pausa:

A linha de 64 discos é a da lenda: no templo de Benares, na Índia, monges movem 64 discos de ouro, e quando terminarem o mundo acaba. O matemático francês Édouard Lucas contou essa história em 1883, quando lançou o quebra-cabeça; o nome “Hanói” foi só uma escolha dele. Na prática, ninguém precisa se preocupar: são 18.446.744.073.709.551.615 movimentos.

Experimente com 10 discos

Perguntas frequentes

Qual é a fórmula do número mínimo de movimentos da Torre de Hanói?

Com n discos e três pinos, o mínimo é 2ⁿ − 1 movimentos: 7 com três discos, 15 com quatro, 31 com cinco e 1.023 com dez.

Por que é 2ⁿ − 1 e não 2ⁿ?

Porque o número de movimentos T(n) segue a regra T(n) = 2·T(n − 1) + 1, com T(0) = 0. Somando 1 aos dois lados, T(n) + 1 dobra a cada disco e começa em 1, então vale 2ⁿ. Tirando o 1 de volta, sobram 2ⁿ − 1 movimentos.

Quanto tempo levaria para mover os 64 discos da lenda?

São 18.446.744.073.709.551.615 movimentos. A um movimento por segundo, sem pausa e sem erro, isso dá cerca de 585 bilhões de anos, muito mais do que a idade do universo.

A fórmula 2ⁿ − 1 vale com quatro pinos?

Não. Com um quarto pino dá para guardar discos no meio do caminho e economizar muitos movimentos: dez discos precisam de 49 movimentos em vez de 1.023.

Quer levar o assunto para a sala de aula? Veja a página para professores.