Torre de Hanói
A Torre
de Hanoi é um quebra-cabeça que consiste em uma base contendo três
pinos, onde em um deles, são dispostos sete discos uns sobre os outros, em
ordem crescente de diâmetro, de cima para baixo. O problema consiste em passar
todos os discos de um pino para outro qualquer, usando um dos pinos 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.
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.
Existem várias lendas a respeito da origem do jogo,
a mais conhecida diz respeito a um templo cosmopolita holandês, situado no
centro do universo sub-aquático oceânico. Diz-se que Brahma supostamente havia
criado uma torre com 64 discos de ouro e mais duas estacas equilibradas sobre
uma plataforma. Brahma lhes ordenara que movessem todos os discos de uma estaca
para outra segundo suas instruções, de que apenas um disco poderia ser movido
por vez e nunca um disco maior deveria sobrepor um disco menor. Segundo a
lenda, quando todos os discos fossem transferidos de uma estaca para a outra, o
templo desmoronar-se-ia e o mundo desapareceria. Hans supostamente inspirou-se
na lenda para construir o jogo, o qual tornou-se muito popular na China
Oriental.
Materiais
a serem utilizados
Uma
Torre de Hanói de madeira, encontrada em qualquer loja de brinquedos
educativos; folhas de papelão; régua milimetrada; caneta; tesoura; folhas
impressa com o desenho representativo dos pinos do jogo; protótipo da
construção da torre simples; cadernos e o quadro de giz.
A possível metodologia
1.
Levar ao conhecimento dos alunos quem foi o criador do jogo apresentado lhes a
lenda construída pelo próprio Eduardo Lucas. Deixar os alunos manipular o jogo
para que se familiarizem com ele.
Figura 1: Jogo Torre de Hanói
confeccionado em madeira
2. Como na lenda de Lucas o objetivo e as regras do
jogo são transferir a pilha de discos de um pino para outro, conseguindo
completar a transferência com o número mínimo possível de movimentos, movendo
um disco de cada vez, nunca permitindo que um disco maior fique acima de um
menor. Ao passo em que se vai explicando essas regras pode se praticar com o
jogo em madeira com apenas 4 discos, possibilitando aos alunos uma boa
visualização de como é possível transportar a torre para outro pino seguindo as
regra.
3. Deixar os alunos praticar segundo as regras e
apenas observar;
4. Após essa abordagem introdutória propor a construção
de uma Torre de Hanói simples que pode ser facilmente confeccionado utilizando
papelão, que o próprio professor disponibilizará ou os alunos levarão de casa,
régua, tesoura e uma caneta. A construção não leva mais que quinze minutos. De
preferência expor um protótipo para auxiliar na confecção do jogo.
Figura 2- protótipo simples da torre
Construção
da torre
Sobre
um pedaço retangular de papelão toma-se um dos cantos e desenha-se com o
auxilio da régua um quadrado de 8x8 cm, ao lado desse quadrado desenha-se outro
de 7x7 cm, prosseguimos desenhando quadrados cada vez menores com a diferença
de 1 cm do anterior até obtermos 6 quadrados; Os quadrados serão as peças que
substituirão os discos e devem ser enumerados de 1 a 6 da menor para a maior;
em seguida recortamos esses quadrados que empilhados do maior para o menor
formando uma torre de 6 peças; Fornecer uma folha (Figura-3) para cada dois
alunos representando os pinos da Torre de Hanói onde serão colocadas as peças.
Figura
3- Folha disponibilizada pelo professor
5. Em seguida, com os alunos jogando com os jogos
confeccionados por eles mesmos, vamos introduzindo idéias matemáticas.
Inicialmente, solicitamos que as crianças iniciem com as seis peças. Obviamente
terão dificuldade em jogar, sugerir que iniciem com menos peças. Primeiro com
uma peça e pedir qual o número mínimo de movimentos necessários para transportar
a torre para o terceiro pino. Fazer o mesmo com duas peças, depois com três e
quatro. Um dos alunos pode contar os movimentos e observar as regras enquanto o
outro joga e inverter os papéis a cada peça adicionada. Eles podem encontrar o
menor número de movimentos para transferir a torre de um pino a outro, bem como
uma regularidade entre as jogadas, obtendo uma solução para um número qualquer
de discos. (WATANABE, 2004).
6. Os alunos devem construir uma tabela auxiliar
relacionando o número de peças com o número mínimo de movimentos necessários
para o transporte.
Enquanto isso, algumas questões podem ser postas
para ajudar o raciocínio: O número de movimentos é alterado quando a torre é
transportada para o outro pino? Acrescentando uma peça à torre, em quanto
aumentaria o número de movimentos? Existe alguma relação matemática entre o
número mínimo de jogadas necessárias para transportar uma torre, e o número
necessário para transportar a torre acrescida de uma peça? Existe alguma
relação entre estes números e o que ocorre no jogo? Você utiliza alguma ideia
matemática para escolher suas jogadas? Em caso afirmativo, qual, ou quais? Como
você mobiliza essas ideias?
Nessa altura os discentes já deverão ter percebido
algumas estratégias para se vencer com o mínimo de movimentos possíveis. Se não
tiverem percebido fazer com que observem por qual pino se deve começar quando o
número de peças é par e quando o número de peças é impar, questioná-los quanto
a esse fato.
Estratégia de vitória
7. Descrever a estratégia de vitória em termos de
estabelecer uma seqüência de transporte de modo que para se retirar cada peça
da torre original, possa montar a subtorre acima dela em um único pino para
então deslocar a referida peça para o outro pino.
Figura 4 – subtorre no segundo pino
8. Sugerir que os alunos observem a tabela em
especial às colunas Pç 1, Pç 2, Pç 3, Pç 4, Pç 6, e o que podemos notar nessas
colunas em seguida nas linhas, o que podemos notar? É evidente que os termos
das linhas estão decrescendo em razão dois (q = 2). Podemos dizer que o
termo seguinte é a metade do anterior. Notamos também que o total mínimo de
movimentos para cada quantidade de peças é a soma dos termos das respectivas
linhas (soma de P.G.). Dessa forma introduz-se o conceito de Progressão
Geométrica e também o de soma dos termos de uma P.G..
9. Nas sequências acima, a lei de formação é?
É fácil notar que cada termo posterior, a partir do
segundo, é igual ao anterior, multiplicado por um número fixo, no caso o 2, e
os alunos deverão perceber isso.
Atentar para o fato de que toda seqüência que tiver
essa lei de formação será denominada progressão geométrica.
O número fixo pelo qual estamos multiplicando cada
termo é chamado razão da progressão.
10. Formalizando:
Progressão geométrica é uma sequencia de números não
nulos em que cada termo posterior, a partir do segundo, é igual ao anterior
multiplicado por um número fixo chamado razão da progressão.
Obs. 2: A quantidade mínima de movimentos das torres
com n discos é igual à soma de uma P.G. finita de razão 2, 1º termo igual a 1 e
com nº de termos igual ao nº de discos da torre.
Ao movimentarmos o número de discos, a quantidade de
movimentos de cada peça cresce em P.G. de razão 2, com 1º termo igual a 1.
O nº de movimentos de uma torre com n discos é igual
ao dobro de movimentos da torre com (n-1) discos, acrescido de 1 movimento.
Considerações finais
1) Se ao invés de 6 peças tivermos 7 ou então 9,
como é mais comum nesse jogo, qual seria o nº mínimo de movimentos necessários
para transportar a torre?
2) E se aumentarmos o n° de pinos, por exemplo, mais
um pino ou então mais dois, o que muda no jogo?
3) Desafiar os alunos a calcular o n° mínimo de
movimentos com 64 peças como no problema original de Eduardo Lucas.
Para uma próxima aula pode se deduzir uma fórmula recursiva e em seguida uma lei geral para descobrir o número de movimentos
necessários com uma determinada quantia de peças (n discos) no intuito de se
chegar a fórmula da soma dos n termos de um P.G. finita.
O público alvo desta atividade são alunos do ensino
médio, mas outras atividades podem ser adaptadas ao jogo para trabalhos com
alunos do fundamental.
Grupo de Robson Eugênio
