As torres de Hanói
Este problema foi formulado e resolvido pelo matemático francês Édouard Lucas em 1883, estando relacionado com um jogo que ficou conhecido a TORRE DE HANÓI e, que consiste, muito simplesmente, num tabuleiro rectangular onde se devem fixar três hastes verticais (cilíndricas e iguais), e em n discos circulares, não havendo dois discos com o mesmo diâmetro. Cada disco tem um pequeno orifício no centro de forma a poder ser enfiado em qualquer uma das hastes. No início do jogo, todos os discos devem ser enfiados na mesma haste por ordem decrescente, ficando o maior na base da torre assim construída - cada disco pode, portanto, representar um andar da torre.
O objectivo do jogo
é transferir todos os discos de forma a reconstruir a torre numa (qualquer) das outras
hastes, obedecendo às seguintes regras:
(i) Em cada movimento só poderá ser transferido um disco;
(ii) Em nenhum dos movimentos poderá o jogador colocar um disco sobre outro
de menor diâmetro.
A Torre de Hanói. Qual o número mínimo de movimentos necessários para completar um jogo de Torre de Hanói?