A Torre de Hanói vem acompanhada de uma lenda. Em um templo na Índia há uma torre de 64 discos de ouro, e os monges continuam movendo os discos seguindo as regras. Quando terminarem de mover todos, o mundo acabará…

Mas quanto tempo leva, de verdade, mover 64 discos?

No mínimo 2⁶⁴−1 movimentos

Com n discos, o número mínimo de movimentos é 2ⁿ−1 (a explicação está no artigo sobre o mínimo de movimentos). Com 64 discos:

2⁶⁴−1 = 18.446.744.073.709.551.615 movimentos

Isso dá cerca de 18,4 quintilhões. É mais de 18 milhões de vezes um trilhão.

Movendo 1 disco por segundo

Imagine que um monge mova um disco por segundo, sem descanso e sem errar nenhuma vez. Dividindo pelo ano de cerca de 31,56 milhões de segundos (365,25 dias):

18.446.744.073.709.551.615 s ÷ 31.557.600 s ≒ 584,5 bilhões de anos

Para compararAnos
Mover 64 discos, 1 por segundocerca de 584,5 bilhões
Do nascimento do universo até hojecerca de 13,8 bilhões
Do nascimento da Terra até hojecerca de 4,6 bilhões

É cerca de 42 vezes a idade do universo. Mesmo que a lenda seja verdadeira, não parece haver motivo para se preocupar com o fim do mundo.

E se fosse um computador?

Imagine que, em vez de mãos humanas, um computador capaz de calcular 1 bilhão de movimentos por segundo siga a sequência. Ainda assim:

18.446.744.073.709.551.615 ÷ 1.000.000.000 ≒ 18,4 bilhões de segundos ≒ cerca de 585 anos

A regra de cada movimento é muito simples, mas, a cada disco a mais, o número de movimentos dobra. É um bom exemplo do que significa “crescer de forma exponencial”.

Até quantos discos dá para jogar à mão?

Movendo 1 disco por segundo, mesmo com o número mínimo de movimentos, o tempo é este.

Número de discosMínimo de movimentosA 1 por segundo
7 discos127cerca de 2 minutos
10 discos1.023cerca de 17 minutos
15 discos32.767cerca de 9 horas
20 discos1.048.575cerca de 12 dias

Para jogar em uma pausa, algo perto de 7 discos tem a duração certa. É por isso que o modo “Clássico” do app Torre de Hanói usa 7 discos.