Professor Paulo Sérgio Costa Lino
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 transferi-lo para o pino $3$, devemos retirar todos os $n-1$ pinos que estão em cima 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