A Torre de Hanói é um jogo com aplicações que podem ser basicamente usadas em escolas por professores que desejam melhorar e desenvolver o cognitivo de seus alunos.
Neste jogo, inventado pelo matematico francês Edouard Lucas em 1883, o objetivo e transferir os 7 discos colocados em ordem ascendente de tamanho (de cima para baixo) para um dos outros dois pinos livres (veja ilustração abaixo), na mesma ordem, e efetuando o menor número de movimentos. Somente um disco pode ser mudado de pino a cada movimento, e ele não pode ser colocado em cima de um disco menor.
Há uma lenda, imaginada pelo próprio Edouard Lucas, sobre a Torre de Hanói:
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 obedeceram e começaram o seu trabalho, dia e noite. Quando eles terminarem, a Torre de Brahma irá ruir e o mundo acabará.
Uma questão interessante é saber qual o menor número de movimentos necessários para resolver uma Torre de Hanói com n discos. A tabela abaixo mostra o menor número de movimentos possíveis com n discos (n = 1, ... , 7).
Pode-se demonstrar, usando indução matemática sobre n, que a fórmula para obter o menor número de movimentos necessários para resolver uma Torre de Hanói com n discos é dada por
Uma outra maneira de obter a fómula acima é observar que a sequência do número mínimo de movimentos (1, 3, 7, 15, 31, 63, 127, ... ) é uma Progressão Aritmético - Geométrica (PAG) e calcular seu termo geral.
O objetivo deste post, além de divulgar a Torre de Hanói e apresentar um outro tipo de sequência que ocorre com bastante frequência em problemas de recorrência, apesar de ser pouco explorada no ensino médio.
Definição. Uma PAG é uma sequência (an) tal que para todo n natural vale an+1 = qan + r, cujo termo geral é dado por
Definição. Uma PAG é uma sequência (an) tal que para todo n natural vale an+1 = qan + r, cujo termo geral é dado por
sendo a1, r e q constantes reais não nulas e q ≠ 1.
Exemplo: A sequência (1, 3, 7, 15, 31, 63, 127, ... ) é uma PAG com termo geral dado por
Convidamos você, amigo leitor, para fazer o download de um artigo nosso publicado na Revista do Professor de Matemática, vol. 73 de 2010. Neste artigo é dada uma abordagem simples com exemplos e aplicações do referido assunto.
