Torre de hanói

A Torre de Hanói é um "quebra-cabeça" que consiste em uma base contendo três pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo. Pergunta-se: quantos movimentos são necessários para uma torre com 5 discos?

Como o primeiro disco a ser retirado é o menor deles, podemos deslocá-lo para o pino mais distante da torre. Depois, deslocamos o segundo disco para o pino do meio e em seguida o primeiro disco para o segundo. O terceiro disco é deslocado para o terceiro pino, o primeiro retorna ao topo do primeiro pino e o segundo disco é colocado por cima do terceiro, seguido pelo primeiro. Sobraram os discos 4 e 5 no primeiro pino. Como o pino do meio (segundo) está vazio, tiramos o disco quatro e o colocamos nele. Em seguida, retiramos o primeiro disco do terceiro pino e o colocamos por cima do quarto. O segundo voltará por cima do quinto e o primeiro é colocado em seguida. Passamos o terceiro disco para cima do quarto e depois o primeiro disco para o terceiro pino. Logo depois, colocamos o segundo disco por cima do terceiro e do quarto e em seguida o primeiro. Passamos, por fim, o quinto disco para o terceiro pino (podemos chamá-lo de pino final) e desmontamos a sequência que fizemos no pino do meio até que sejam colocados todos os discos por cima do quinto no pino final, totalizando 31