Análise da Torre de Hanói

O matemático Frances Édouar Lucas criou em 1883 um desafio elegante conhecido como Torre de Hanói. Nele temos oito discos, inicialmente empilhados em ordem decrescente em um de seus três pinos. O objetivo é transferir toda a torre para outro pino, movendo um disco de cada vez e nunca movendo um disco maior sobre o menor.

                Lucas agregou ao seu brinquedo a lenda de que uma torre ainda maior conhecida como Torre de Brahma, que supostamente teria 64 discos de ouro, cujos pinos em que eram colocados, teriam a forma de agulhas feitas de diamante. No inicio, Deus teria colocado estes disco de ouro na primeira agulha e ordenado que um grupo de sacerdotes inicia-se a transferência para a terceira agulha seguindo as regras descritas acima. Os sacerdotes trabalham dia e noite nesta tarefa, quando a terminarem, a torre desabara e junto dela o mundo irá acabar.

                Para solucionar o desafio, precisa-se entender como funciona a solução, que consiste em utilizar os 2 pinos vazios trocar de posição, agora surge o questionamento: Quantos movimentos são suficientes para completar a tarefa?

                Utilizando a generalização nós podemos redimensionar o problema para menos, com as Torres de Brahma tendo 64 discos e as de Hanói tendo 8, procura-se a resposta para n discos.  Utilizando pequenas quantidades fica fácil ver como se transfere uma torre contendo um ou dois discos e com uma pequena quantidade de experimentos descobre-se como transferir uma torre de três.

                Incluindo uma notação T para a quantidade de trocas, teremos T(n) para indicar o numero de trocas necessárias através dos pinos seguindo as regras de Lucas, tem-se inicialmente T(0) = 0, T(1) = 1 e T(2) = 3.

                Mudar a perspectiva e tentar um caso maior experimentando com três discos:

1. Pela experimentação a melhor opção é mover os dois discos superiores para o pino do meio.

2. Espalha-se os dois pinos superiores  com o maior no meio.

3. Volta a empilhar no meio para liberar o terceiro pino.

NOTA: Aqui se te a primeira pista para se transferir n discos, sabemos que para movimentar dois discos temos 3 movimentos, como visto até agora se confirma que T(2) = 3.

4. O único deslocamento do maior disco para o terceiro pino

NOTA: Agora vem a segunda pista para a generalização, aonde o maior disco se movimenta uma única vez, somando no total dos três movimentos já realizados ou T(2) + 1.

5. Volta a espalhar os discos superiores.

6. Liberando assim a movimentação do disco do intermediário.

7. Terminada a transferência, repare que os passos 7, 6, e 5 são respectivamente os passos 3, 2 e 1 utilizando um pino diferente.

NOTA: Tem-se a pista final aonde foram realizados mais três movimentos para os dois discos superiores, repetindo que T(2) = 3, com o total final sendo T(2) + 1 + T(2) = 7.

Buscando um padrão generalizado, para n = 3, temos os (n – 1) discos menores para mudar com T(n-1) movimentos, 1 deslocamento do disco maior e novamente (n – 1) discos menores de volta sobre o maior com mais T(n – 1) movimentos. Aonde se obtém o numero de trocas de discos com no mínimo 2 * T(n - 1) + 1.

Tendo descoberto a formula geral em cima um conjunto de igualdades como o mostrado acima é um caso de recorrência ou relação recursiva, aonde temos o valor limite e a equação de uso geral em termos de valores que o precedem.

Em termos de solução, o ideal seria obter uma resposta direta, analisando os resultados obtidos com a equação recorrente teríamos T(3) = 2*3+1 = 7; T(4) = 2*7+1 = 15; T(5) = 2*15+1 = 31; T(6) = 2*31+1 = 63. A sequencia 0, 1, 3, 7, 15, 31, 63 resulta na dedução de uma nova formula:

Através da indução matemática prova-se a afirmação acima usando o teste para o menor valor de n como base, neste caso T(0) e a partir dele provamos os valores restantes para n > 0, aonde se substitui a chamada recorrente pela nova formula:

Concluída prova, pode-se calcular através da expressão de forma fechada o numero de movimentos necessários facilmente, retornando ao ponto em que os sacerdotes estão movendo os discos da torre de Brahma, sabemos os mesmos terão de realizar 2 elevado a 64 menos 1 movimentos, algo em torno de 18 quintilhões, o que provavelmente explica o motivo nenhum apocalipse Hindu ter ocorrido. E o desafio da torre de Hanói requer 255 movimentos para completar a tarefa.

Encontrar a função matemática para o desafio ajuda na compreensão do problema e como solucionar o mesmo, o assunto será finalizado na próxima postagem com as rotinas que calculam o total de movimentos e um programa que irá descrever passo a passo os movimentos dos discos entre os pinos.