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.
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.
Nenhum comentário:
Postar um comentário