Torre de Hanói

A Torre de Hanói é um quebra-cabeça que consiste em uma pilha de discos de tamanhos decrescentes da base para o topo. O objetivo é transportar toda a pilha de sua posição original, indicada por A na figura, para a posição C. Os discos devem ser deslocados um de cada vez, podendo ser colocados na posição C ou em uma posição auxiliar B, mas de forma que um disco maior nunca fique em cima de outro menor em nenhuma situação.

Usualmente, esse quebra-cabeça tem uma base com três pinos para facilitar a operação. A figura mostra o jogo com quatro discos, mas a quantidade deles pode variar.

A questão é: qual a estratégia para deslocar a pilha de discos da posição original para a posição final com o menor número de movimentos possível? E quantos movimentos precisamos fazer?

Vamos imaginar que tenhamos apenas um disco. Neste caso, obviamente, basta um movimento: deslocar o único disco da posição A para a posição C.

Se tivermos dois discos, precisamos, primeiro, tirar o disco superior, colocando-o na posição B,  o que implica em um movimento. A seguir, deslocamos o segundo disco para a posição C. Finalmente, deslocamos o disco menor da posição B para a posição C, sobre o disco maior. Portanto, para deslocar dois discos de A para C precisamos deslocar o primeiro disco duas vezes e o disco maior, uma. Assim, o número total de movimentos é 1+2×1=3.

Se tivermos três discos, inicialmente precisamos deslocar os dois discos superiores para a posição B. Para isso, colocamos o disco menor na posição C, o segundo menor na posição B e o menor, em seguida, é colocado sobre ele. A seguir, desloca-se o disco maior para a posição C. A seguir, repete-se os movimentos para deslocar a pequena pilha da posição B para a posição C. Portanto, o número total de movimentos é 1+2× (1+2×1)=1+2+4=7.

Essa regra se repete. No caso de 4 discos, precisaremos fazer 1+2×(1+2×(1+2×1))=1+2+4+8=15 deslocamentos.

Se você reparar bem, esses números de movimentos são

1 disco: 2¹-1=1

2 discos: 2²-1=3

3 discos: 2³-1=7

4 discos: 2⁴-1=15

Você pode deduzir isso observando que as somas que aparecem mais acima são de progressões geométricas.

Estratégia

Um pouco de atenção também mostrará que se a quantidade de discos a serem deslocados de uma pilha para outra  for ímpar, o primeiro movimento é deslocar a primeira peça para a posição C. Se for par, o primeiro disco deve ir para a posição B.

Outra regra que você pode perceber é que nunca uma peça com o número par deve ser colocada sobre outra peça par (note a numeração das peças na figura) nem uma ímpar ser colocada sobre outra peça ímpar.

ESTE BLOG VIROU LIVRO. CLIQUE AQUI PARA VER