hanoi

A TORRE DE HANÓI
Carlos Yuzo Shine - Colégio Etapa

Artigo baseado em aula ministrada na IV Semana Olímpica, Salvador - BA

• Nível Iniciante.

A Torre de Hanói é um dos quebra-cabeças matemáticos mais populares. Ele foi inventado por Edouard Lucas em 1883.

1. Peças
As peças são n discos de tamanhos diferentes e todos com um furo em seu centro e três pinos onde são colocados os discos. Certamente podem ser encontrados em qualquer loja de brinquedos.

2. Regras e objetivos do jogo
Inicialmente os discos formam uma torre onde todos são colocados em um dos pinos em ordem decrescente de tamanho.

Devemos transferir toda a torre para um dos outros pinos de modo que cada movimento é feito somente com um disco, nunca havendo um disco maior sobre um disco menor.

3. A Pergunta que será calada
Queremos saber qual é o menor número de movimentos necessários para resolver uma torre de Hanói com n discos.

Há uma história (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 saserdotes 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á.
4. Estudando o problema
Para resolver um problema (não só este, mas vários outros problemas na matemática) que envolve n coisas, ajuda ver o que acontece para valores pequenos de n. Vejamos alguns casos.
• n = 1. Fazemos

1 movimento foi suficiente.

• n = 2. Fazemos

3 movimentos deram.

• n = 3. Fazemos

7 movimentos deram.

Mas é claro que não podemos fazer só isso. Não podemos ficar observando o que acontece para todos os valores de n! Então temos que começar a tirar algumas conclusões.

5. Como resolver o