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 comparar | Anos |
|---|---|
| Mover 64 discos, 1 por segundo | cerca de 584,5 bilhões |
| Do nascimento do universo até hoje | cerca de 13,8 bilhões |
| Do nascimento da Terra até hoje | cerca 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 discos | Mínimo de movimentos | A 1 por segundo |
|---|---|---|
| 7 discos | 127 | cerca de 2 minutos |
| 10 discos | 1.023 | cerca de 17 minutos |
| 15 discos | 32.767 | cerca de 9 horas |
| 20 discos | 1.048.575 | cerca 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.
