Jogada Mais: Torre de Hanói

A Torre de Hanói é um quebra-cabeça composto por uma base contendo três hastes. Em uma das haste são dispostos um número de discos uns sobre os outros, em ordem crescente de diâmetro como mostra a figura abaixo.

O problema consiste em passar todos os discos de uma haste para uma das outras, de maneira que um disco maior não fique sobre um menor em nenhuma situação. O objetivo do jogo é conseguir passar todos os discos de uma haste para outra com a menor quantidade de movimentos possíveis.

A torre de Hanói, também conhecida por torre de bramanismo ou quebra-cabeças do fim do mundo, foi inventada e vendida como brinquedo, no ano de 1883, pelo matemático francês Edouard Lucas. Sua inspiração foi a lenda de Hindu, a qual falava de um templo em Benares, cidade Santa da Índia, onde existia uma torre sagrada do bramanismo, cuja função era melhorar a disciplina mental dos jovens monges. De acordo com a lenda, no grande templo de Benares, de baixo da cúpula que marca o centro do mundo, há uma placa de bronze sobre a qual estão fixadas três hastes de diamante. Em uma dessas hastes, o deus Brahma, no momento da criação do mundo, colocou 64 discos de ouro puro, de modo que o disco maior ficasse sobre a placa de bronze e os outros decrescendo ate chegar ao topo.

O desafio que os monges receberam foi de transferir a torre formada pelos discos, de uma haste para a outra, usando a segunda como auxiliar com as restrições de movimentar um disco por vez e de nunca colocar um disco maior sobre um menor. Os monges deveriam trabalhar com eficiência noite e dia, quando terminassem o trabalho, o templo seria transformado em pó e o mundo acabaria. O fim do mundo ainda pode ser discutido, mas não há duvida quanto ao desmoronamento do templo.

Veja a seguir como podemos encontrar uma fórmula geral para uma partida envolvendo n discos.