sexta-feira, 1 de julho de 2011

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 !

12 comentários:

  1. Olá Diego. Muito legal esta postagem!! Acho que não é uma boa ideia começar a resolver um com 30 discos!
    Abraço.
    Pedro R.

    ResponderExcluir
  2. Existe uma lenda hindu quanto a criação do jogo da torre de hanói, a lenda diz que uma torre com 64 discos de ouro foi construída no centro do universo, as regras são as mesmas e quando todos os discos fossem movidos para a outra torre o universo se acabaria, no nosso caso, se gastassemos 1 segundo em cada movimento poderíamos afirmar que o universo iria acabar em aproximadamente 600 trilhões de anos!!!

    Obrigado pela visita e volte sempre!

    ResponderExcluir
    Respostas
    1. Olá, Diego!!
      Fiz os cálculos e encontrei pouco menos de 600 BIlhões de anos. Confere??
      Olha só: 2^64-1 = 1,84467440737*10^19 movimentos.
      Se cada movimento for feito em 1s, então, dividindo por 60, passaremos a ter 3,07445734562*10^17 minutos.
      Dividindo novamente por 60, teremos 5,12409557603*10^15 horas.
      Dividindo por 24, teremos 2,13503982335*10^14 dias.
      Dividindo por 365, teremos 584 942 417 356 anos que é próximo de 600 bilhões.
      Assim, se a lenda for verdadeira, o "fim do mundo" está quase ali, se comparado aos 600 trilhões de anos...
      Muito boa tua postagem! Parabéns.
      Caren

      Excluir
  3. Diego essa função do amor é ótima cara! Parabéns! E essa lenda sobre a TORRE DE HANÓI é fantástica! Legal resolver isso por recorrência!

    Diego, existe algum local específico pra lançar desafios ou pedir pra você resolver alguma questão? Ou pode ser aqui mesmo? Tenho mais uma questão e sei que você é o cara!

    ResponderExcluir
  4. Olá, Diego!
    Já estava pensando de falar para você sobre a tal lenda hindu ( ou seria tibetana?), mas, vi que já era do seu conhecimento.
    Gostei como vc postou e demonstrou a solução através do uso de recorrência. Meus parabéns!
    Somente um aviso: " olhem o IV Carnaval da UBM... aí gente"!!!!!
    Um abraço!!!!!

    ResponderExcluir
  5. Olá sandro, você pode enviar perguntas ou fazer sugestões para meu email:

    diego.sousa.ismart@gmail.com

    Estou aguardando seu contato!

    ResponderExcluir
  6. Olá, Francisco Valdir!

    Obrigado pela visita, suas observações são sempre de grande valia, é bom ver que você está atento à leitura, espero que tenha entendido todos os passos e argumentos, eu também tomei conhecimento da lenda a pouco tempo, depois adicionei este fato à postagem.

    Obrigado e volte sempre!

    ResponderExcluir
  7. adorei esse site(blog) eu te ajudo a crescer o giga matematica eu trabalho na apple e posso publicar seu blog nos i phones.

    ResponderExcluir
  8. oi Diego, não consigo ver as imagens da matéria, acredito que são aquelas escritas em código latex, vc poderia me ajudar ?, obrigado

    ResponderExcluir

Você pode inserir suas fórmulas e equações no formato $\LaTeX$ nos comentários, basta escrevê-lo entre os símbolos $ \$ \ldots \$ $. Por exemplo, se você deseja escrever a seguinte fórmula:

$\lim_{x\to\infty}f(x)=0$

basta digitar a seguinte fórmula:

$ \$ $ \lim_{x\to\infty}f(x)=0 $ \$ $
(Um exemplo mais simples: $x^2=a$ é escrito como \$ x^2=a \$).

Agora é com você, comente à vontade, seu comentário é uma ferramenta fundamental para o crescimento do Giga Matemática!!!