Membros

quarta-feira, 15 de fevereiro de 2012

A Torre de Hanói

A torre de Hanói é uma recreação matemática inventada por Edouard Lucas em [;1883;]. Este jogo consiste de três colunas verticais ou pinos. As peças são [;n;] discos de diâmetros diferentes com um furo em seu centro. O disco de maior diâmetro sempre está abaixo de um disco de menor diâmetro, formando assim uma torre. A torre de Hanói tem sido tradicionalmente considerada como um procedimento para avaliação da capacidade de memória de trabalho, e principalmente de planejamento e solução de problemas.

O problema consiste em transferir, todos os discos do primeiro pino para o terceiro pino, movimentando um disco de cada vez, usando qualquer outro pino como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação. O número de discos pode variar sendo que o mais simples contém apenas três. Para os leitores curiosos que desejam jogar online, recomendo este site: http://www.mazeworks.com/hanoi/

Temos uma história interessante sobre a torre de Hanói imaginada talvez pelo próprio Edouard Lucas:

No começo dos tempos, Deus criou a Torre de Brahma, que contém três pinos de diamante e colocou no primeiro pino [;64;] discos de ouro maciço. Deus então chamou seus sacerdotes e ordenou-lhes que transferissem todos os discos para o terceiro pino, seguindo as regras acima. Os sacerdotes então obedeceram e começaram o seu trabalho, dia e noite. Quando eles terminarem, a Torre de Brahma irá ruir e o mundo acabará.

Uma das perguntas iniciais que podemos formular é a seguinte:

Qual é o número mínimo de movimentos necessários para resolver a torre de Hanói com [;n;] discos?

A resposta é dada na seguinte proposição:

Proposição 1: Se [;T_n;] denota o número mínimo de movimentos necessários para transferir a torre com [;n;] discos do pino [;1;] para o pino [;3;], então [;T_n;] satisfaz a relação de recorrência:

[;\begin{cases}T_n = 2T_{n-1} + 1 \quad n \geq 2\\T_1 = 1\\\end{cases}\qquad (1);]


Demonstração: Para provar esta relação, observe que primeiro temos que transferir a torre com [;n-1;] discos para o pino central ou pino [;2;] através de [;T_{n-1};] movimentos conforme a figura abaixo.

Em seguida, transferimos o disco de maior diâmetro para o pino [;3;] conforme a figura abaixo. Finalmente passamos a torre com [;n-1;] discos para o pino [;3;].


Assim, precisamos de [;T_{n-1} + 1 + T_{n-1} = 2T_{n-1} + 1;] movimentos. Mas não sabemos se esta estratégia usa o menor número de discos. Portanto,

[;T_n \leq 2T_{n-1} + 1 \qquad (2);]

Considere agora o disco maior. Para transferí-lo para o pino [;3;], devemos retirar todos os [;n-1;] pinos que estão encima dele e para isso, precisaremos de no mínimo [;T_{n-1};] movimentos e se quisermos mudá-lo de lugar, devemos colocar o disco maior em um pino vazio e finalmente para colocar novamente os [;n-1;] discos sobre ele, precisamos no mínimo mais [;T_{n-1};] movimentos. Assim, para resolver o problema precisamos no mínimo de [;T_{n-1} + 1 + T_{n-1};] movimentos. Logo,

[;T_n \geq 2T_{n-1} + 1 \qquad (3);]

De [;(2);] e [;(3);], temos [;T_n = 2T_{n-1} + 1;] e sendo [;T_1 = 1;], segue o resultado.

Observação 1: Sendo [;T_{n-1};] um número natural, segue que [;T_n;] é ímpar para todo [;n \in \mathbb{N}^{\ast};].

Proposição 2: A expressão fechada para a recorrência [;(1);] é:

[;T_n = 2^n - 1 \qquad (4);]
para [;n \in \mathbb{N}^{\ast};].

Demonstração: Devido a presença da parcela [;1;], no segundo membro de [;(1);], a equação de recorrência é não-homogênea. Seja [;U_n = T_n + r;], onde [;r;] é uma parcela desconhecida que iremos determinar de modo que a nova equação de recorrência seja homogênea. Sendo [;U_{n-1} = T_{n-1} + r;], então

[;T_n = 2T_{n-1} + 1 \quad \Rightarrow \quad U_n - r = 2(U_{n-1} - r) + 1 \quad U_n = 2U_{n-1} - r + 1;]

Escolhendo [;r = 1;], obtemos uma equação homogênea. Sendo [;T_1 = 1;], então [;U_1 = T_1 + 1 = 2;], de modo que temos o seguinte problema de valor inicial

[;\begin{cases}U_n = 2U_{n-1} \quad n \geq 2\\U_1 = 2\\\end{cases}\qquad (5);]
Observe que

[;U_2 = 2U_1 = 2\cdot 2 = 2^2, \quad U_3 = 2U_2 = 2\cdot 2^2 = 2^3, \quad \ldots \quad, U_n = 2^n;]

De fato, suponhamos que a última expressão seja válida. Assim,

[;U_{n+1} = 2U_n = 2\cdot 2^n = 2^{n+1};]

Logo, [;T_n = U_n - r = 2^n - 1;].

Vemos deste modo que o número mínimo de movimentos para resolver a torre de Hanói aumenta consideravelmente com o número de discos conforme a tabela abaixo:
Corolário 1: Se o número de discos [;n;] na torre de Hanói é par, então [;3 \ \mid \ T_n;].

Demonstração: Se [;n = 2m;], então

[;P_n = P_{2m} = 2^{2m} - 1 = 4^m - 1 = (3 + 1)^m - 1;]

[;=\sum_{k=0}^{m}{3 \choose k}3^k - 1 = \sum_{k=1}^{m}{3 \choose k}3^k = 3\sum_{k=1}^{m}{3 \choose k}3^{k - 1};]

donde segue o resultado.

Corolário 2: Se o número de discos [;n;] na torre de Hanói é múltiplo de [;4;], então [;15 \ \mid \ T_n;].

Demonstração: Se [;n = 4m;], então

[;P_n = P_{4m} = 2^{4m} - 1 = 16^m - 1 = (15 + 1)^m - 1;]

[;=\sum_{k=0}^{m}{15 \choose k}15^k - 1 = \sum_{k=1}^{m}{15 \choose k}15^k = 15\sum_{k=1}^{m}{15 \choose k}15^{k - 1};]

donde segue o resultado.

Referências Bibliográficas:
- Shine, Carlos Yuzo. A Torre de Hanói. Colégio Etapa.
- Graham, Ronald. L., Knuth, Donald E. et. ali. Concrete Mathematics. Addison-Wesley Publishing Company, 1990.
- http://pt.wikipedia.org/wiki/Torre-de-Hanói

Gostará de ler também:
- Advinhando com o Sistema de Numeração Binário;
- Advinhando com os Dominós;
- O Jogo da Velha 3D.
Postado por Prof. Paulo Sérgio às 15.2.12
Marcadores: ,
Reações: 

3 comentários:

  2. Este assunto é muito interessante com vários artigos em revistas de computação. Vale a pena citar também que desconhece o número mínimo de movimentos para uma torre de 4 pinos e n discos. Obrigado pelo comentário e volte sempre.

    ResponderExcluir

  3. Oi, Prof. Paulo Sérgio. A Torre de Hanói é um ótimo exercício de lógica. Leitura agradável e bem organizada. Parabéns!

    ResponderExcluir

Assinar: Postar comentários (Atom)