Torres de Hanoi, continuação

Quando você resolveu as Torres de Hanói com três discos, você precisou expor o disco inferior, o disco 3, para poder movê-lo do pino A para o pino B. Para expor o disco 3, você precisou mover os discos 1 e 2 do pino A para o pino livre, o pino C:

Espere um minuto — parece que dois discos se moveram em uma única etapa, violando a primeira regra. Mas eles não se moveram em uma única etapa. Você concordou que você pode mover os discos 1 e 2 de qualquer pino para qualquer pino, usando três etapas. A situação acima representa o que você tem após três etapas. (Mover o disco 1 do pino A para o pino B; mover o disco 2 do pino A para o pino C; mover o disco 1 do pino B para o pino C).

Mais ao ponto, movendo os discos 1 e 2 do pino A para o pino C, você resolveu um subproblema recursivamente: mover os discos 1 através de $n-1$‍ (lembre-se que $n=3$‍) do pino A para o pino C. Depois que você resolveu este subproblema, você pode mover o disco 3 do pino A para o pino B:

Agora, para terminar, você precisa resolver recursivamente o subproblema de mover os discos 1 através de $n-1$‍ do pino C para o pino B. Novamente, você concordou que você pode fazer isso em três etapas. (Mover o disco 1 do pino C para o pino A; mover o disco 2 do pino C para o pino B; mover o disco 1 do pino A para o pino B.) E você terminou:

E — você sabia que esta pergunta estava chegando — há algo especial sobre para quais pinos você moveu discos 1 a 3 de e para? Você poderia ter movido de qualquer pino para qualquer pino. Por exemplo, do pino B para o pino C:

Não importa como você o fatia, você pode mover os discos 1 ao 3 de qualquer pino para qualquer pino, movendo os discos sete vezes. Perceba que você move os discos três vezes para cada uma das duas vezes que você resolve recursivamente o subproblema de mover os discos 1 e 2, mais um movimento para o disco 3.

Que tal quando $n=4$‍? Porque você consegue resolver recursivamente o subproblema de mover os discos 1 ao 3 de qualquer pino para qualquer pino, você consegue resolver o problema para $n=4$‍:

Essa solução move os discos 15 vezes (7 + 1 + 7) e sim, você pode mover os discos 1 ao 4 de qualquer pino para qualquer outro pino.

Neste ponto, você pode ter percebido dois padrões. Primeiro, você pode resolver o problema das Torres de Hanói recursivamente. Se $n=1$‍, apenas mova o disco 1. Caso contrário, quando $n\ge 2$‍, resolva o problema em três etapas:

Em segundo lugar, resolver um problema para $n$‍ discos requer $2^n-1$‍ movimentos. Já vimos que isso é verdadeiro para:

Se você consegue resolver o problema para $n-1$‍ discos em $2^{n-1}-1$‍ movimentos, então você consegue resolver o problema para $n$‍ discos em $2^n-1$‍ movimentos. Você precisa de:

Somando os movimentos, você tem $2^n-1$‍.

Vamos voltar aos monges. Eles estão usando $n=64$‍ discos, portanto eles vão precisar mover um disco $2^{64}-1$‍ vezes. Esses monges são ágeis e fortes. Eles conseguem mover um disco por segundo, dia e noite.

Quanto tempo é $2^{64}-1$‍ segundos? Usando a estimativa aproximada de 365,25 dias por ano, isso resulta em 584.542.046.090,6263 anos. Ou seja, mais de 584 bilhões de anos. O sol tem apenas entre cinco e sete bilhões de anos antes de se transformar em uma supernova e nos engolir. Então, sim, o mundo terminará, e não importa quão tenazes os monges sejam, isso aconteceria bem antes de eles conseguirem mover todos os 64 discos para o pino B.

Pensando em outra maneira de usar esse algoritmo, além de prever o fim do mundo? A Wikipédia lista várias aplicações interessantes.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.