Torre de Hanói e Relações de Recorrência

Neste post iremos tratar de um quebra-cabeças bastante interessante: A Torre de Hanói, esse jogo foi criado por Edouard Lucas inspirado em uma lenda, você pode saber um pouco mais da parte histórica clicando aqui.

Aqui trataremos de uma forma para solucionar este quebra cabeças com o menor número de movimentos possíveis. 

1. Explicando as regras do jogo:
   O jogo consiste em três pinos verticais fixados sobre uma superfície, no pino mais à esquerda temos $n$ discos de diferentes diâmetros empilhados, começando pelo disco de maior diâmetro na parte inferior, após isso o disco com o segundo maior diâmetro é colocado sobre o de maior diâmetro, e essa sequência se segue até obtermos uma "torre" como na figura acima. 
   O jogador deve mover todos os discos (um de cada vez) de um pino para outro qualquer, utilizando um dos pinos como auxiliar, de maneira que durante os movimentos um disco maior não fique sobre um disco menor.
Visualize a solução do quebra-cabeça para quatro discos:

   No exemplo acima foram feitos 15 movimentos, é possível que um iniciante neste jogo utilizaria mais movimentos para resolver, eu mesmo gastei mais movimentos que deveria quando joguei pela primeira vez,pergunto:
Você conseguiria resolver o problema dos 4 discos acima com menos movimentos?


Pensou? Mesmo sem saber sua resposta, eu lhe adianto a minha: NÃO!
Mas por que não? O motivo é que o jogo com $n$ disco é resolvido em no mínimo $2^n-1$ movimentos. Para provar isso lançaremos mão de uma ferramenta muito útil na matemática: As relações de recorrência.




2. Relações de Recorrência

   Uma relação de recorrência é uma equação onde cada termo de uma sequência é definido em função dos elementos anteriores. Assim, quando resolvemos uma relação de recorrência nós encontramos uma fórmula explícita que dá o termo geral da sequência, veja o exemplo:


Uma progressão aritmética é uma sequência onde é dado um dos termos, geralmente o primeiro ($a_1$), e sabemos que o próximo termo será o anterior mais a "razão" da sequência, de modo geral em uma P.A. o termo $a_n$ será da do por:

$$a_n=a_{n-1}+r$$

Que é equivalente a seguinte equação:
$$a_n-a_{n-1}=r$$

Essa equação nos diz que um termo qualquer de uma P.A. subtraído de seu antecessor será igual a razão ($r$). Temos aqui nossa relação de recorrência, iremos resolver essa relação para encontrar a fórmula geral do termo de uma P.A.

Note que,
$$a_n-a_{n-1}=r$$
$$a_{n-1}-a_{n-2}=r$$
$$\vdots$$
$$a_2-a_1=r$$
Ao somarmos todas as equações verificamos que os termos $a_{n-1},a_{n-2},\ldots,a_2$ se cancelam, restando apenas os termos $a_n$ e $a_1, no lado direito da igualdade temos $n-1$ fatores repetidos e iguais a $r$, assim podemos organizar a soma do seguinte modo:

$$a_n-a_1=(n-1)r$$ 

ou

$$a_n=a_1=(n-1)r$$

Que é a fórmula que já conhecemos. Utilizaremos agora essa ferramenta para mostrar que o número mínimo de movimentos na torre de hanói com $n$  discos é $2^n-1$.

3. Modelando o problema da torre da Hanói

   Iremos dividir as soluções de acordo com o número de discos presentes.

Para $n=0$ não há o que fazer, pois não há discos;

Para $n=1$ basta fazer $1$ movimento;

Para $n=2$ procedemos da seguinte forma, seja A e B os discos, movimentamos o disco A para o pino auxiliar, depois B para o outro pino, após isso trazemos o disco A para cima do disco B, resolvemos o problema com $3$ movimentos.

Para $n=3$ procedemos da seguinte forma: Resolvemos o problema para dois discos (3 movimentos), depois deslocamos o maior disco para o pino restante (1 movimento), por fim movemos os dois discos do outro pino para cima do disco maior (3 movimentos), totalizando $7$ movimentos.

Para $n=4$, Resolvemos o problema para três discos(7 movimentos), depois movemos o maior disco (1 movimento), após isso trazemos os três discos que estão no outro pino para cima do maior disco (7 movimentos), totalizamos $15$ movimentos.

De forma análoga procedemos para um número qualquer.

Note que o número necessário de movimentos para a solução forma uma sequência, dada por $1,3,7,15,\ldots$. O leitor mais atento irá perceber que a sequência se trata das potências de $2$ menos $1$, veja:

$$1=2^1-1$$

$$3=2^2-1$$

$$7=2^3-1$$ 

$$15=2^4-1$$ 

Deste modo, para $n$ discos teremos que realizar $2^n-1$ movimentos.

A fórmula geral encontrada não foi deduzida, é intuitiva, é uma previsão, apesar de estar correta, como veremos adiante, se baseia na observação, portanto estamos "chutando" o resultado. Portanto, realizaremos uma dedução mais rigorosa que esta, para tal fim utilizaremos relações de recorrência.

Primeiramente temos que encontrar tal relação. Ora, observamos que para resolver a torre com $n$ discos basta resolver o problema para $n-1$ discos, depois mover o maior disco e após isso mover os $n-1$ discos para cima do maior disco, assim o problema está resolvido. Mas para resolver o problema para $n-1$ discos temos que olhar para $n-2$  discos, e para resolver o anterior temos que olhar para $n-3$ discos, e assim sucessivamente até termos 1 disco.

Seja $T(n)$ o número de movimentos necessários para resolver o problema para $n$ discos, assim olhamos para $n-1$ discos, isso gasta $T(n-1)$ movimentos, deslocamos o maior disco para o pino restante, isso gasta mais 1 movimento, após isso movemos os $n-1$  discos para cima do maior disco, isso gasta $T(n-1)$ novamente, temos que o total de movimentos foram:

$$T(n)=2T(n-1)+1$$ 

E isso vale para os demais discos, temos aqui nossa relação de recorrência. Para encontrar o termo geral reordenamos a equação da seguinte forma:

$$T(n)-2T(n-1)=1$$ 

$$T(n-1)-2T(n-2)=1$$ 

$$T(n-2)-2T(n-3)=1$$ 

$$\vdots$$ 

$$T(2)-2T(1)=1$$

$$T(1)-2T(0)=1$$ 

Por definição $T(0)=0$, pois representa o número de movimentos necessários para mover $0$ discos, ou seja, não é necessário fazer nada. Veja que, ao contrário da P.A., não podemos simplesmente somar cada equação, pois cada termo a partir de $T(n)$ aparece 3 vezes, 1 vez positivo e 2 vezes negativo, assim teríamos o primeiro termo seguido da subtração dos termos restantes até $2T(0)$, confira você este fato.

Para obter progresso é necessário que multipliquemos a segunda equação por 2, a terceira por 4, a quarta por 8, ..., e a última por $2^{n-1}$:

$$T(n)-2T(n-1)=1$$ 

$$2T(n-1)-4T(n-2)=2$$ 

$$4T(n-2)-8T(n-3)=4$$ 

$$\vdots$$ 

$$2^{n-1}T(1)-2^nT(0)=2^{n-1}$$

Ao somarmos cada equação vemos que os termos $2T(n-1),4T(n-2),8T(n-3),\ldots,2^{n-1}T(1)$ irão se cancelar, restando apenas

$$T(n)-2T(0)=1+2+\cdots+2^{n-1}$$ 

Por definição $T(0)=0$ e as parcelas à direita da equação formam uma P.G. de razão $2$, e sua soma é igual a $2^n-1$ (confira), assim a equação se reduz à:

$$T(n)=2^n-1$$

Esta é a fórmula do número mínimo de movimentos necessários para movermos $n$ discos na torre de Hanói e resolver o problema.  

4. Fatos interessantes
   A solução para a torre de hanói se torna cada vez mais demorada a medida que os números aumentam, se você gastar 1 segundo para mover cada disco você levará:

1. 30 segundos para resolver 5 discos;
2. 4 minutos e 15 segundos para resolver 8 discos;
3. 17 minutos e 3 segundos para resolver 10 discos;
4. 9 horas, 6 minutos e 7 segundos para resolver 15 discos;
5. 12 dias, 3 horas, 16 minutos e 16 segundos para resolver 20 discos;
6. Aproximadamente 34 anos e meio para resolver 30 discos.

Veja que a quantidade de movimentos necessários aumenta absurdamente a medida que a quantidade aumenta, de fato essa quantidade aumenta exponencialmente, podemos representar esse crescimento com a função $f(x)=2^x-1$  . Veja:

Veja que a quantidade de movimentos cresce absurdamente à medida em que o número de discos aumentam.


Você pode encontrar uma versão deste jogo aqui. 


Até mais !