A Torre de Hanói e o Princípio da Indução
Matemática
I.
O jogo
A Torre de Hanói consiste de uma base com três pinos e um certo número n de discos de
diâmetros diferentes, colocados um sobre o outro em um dos pinos, em ordem
decrescente de seus diâmetros, de baixo para cima, como na figura abaixo, em que n=6.
laetitiasilva.blogspot.com
O jogo consiste em transferir a torre de discos para um dos outros dois pinos,
movimentando um disco de cada vez, utilizando-se um dos pinos livres como auxiliar e
nunca colocando um disco sobre outro de diâmetro menor.
A ilustração abaixo apresenta uma possibilidade para os 7 movimentos necessários para
resolver o jogo para n=3:
evelinedocinho.blogspot.com
Se o número de discos fosse n=2, claramente seriam necessários 3 movimentos. Verifique!
Dá para perceber isso na figura acima ao movermos os discos vermelho e preto para a
haste do meio.
II.
Observações sobre alguns casos particulares
E se n=4? Vejamos: para mover esses 4 discos - que estão no pino que chamaremos de
pino 1 -para outro pino, precisamos liberar o disco maior, de baixo. Para tanto, precisamos
mover os 3 discos acima dele para um outro pino, que chamaremos de pino 2, o que se faz
com 7 movimentos, como na figura acima e, claro, usando também os pinos 1 e 3 quando
necessário. Uma vez instalados os 3 discos menores no pino 2, movemos o disco grande,
solitário no pino 1, para o pino solitário que chamaremos de pino 3, com apenas 1
movimento! Finalmente, com novos 7 movimentos, movemos os 3 discos do pino 2 para o
pino 3, encima do disco grande, como no exemplo anterior e o problema está resolvido: os
discos foram transferidos do pino 1 para o pino 3. Assim, o total de movimentos para
resolver o problema de 4 discos é 7+1+7=15. Observe que não sabemos exatamente quais
são esses 15 movimentos, mas sabemos que, se são necessários 7 movimentos para
moverem 3 discos, então serão necessários 15 movimentos para mover 4 discos.
E se n=5? Raciocinamos exatamente como no caso anterior: movemos os 4 discos que
estão encima do maior para o pino 2, com 15 movimentos, depois movemos o disco grande
para o pino 3 com 1 movimento e, finalmente, movemos os 4 discos do pino 2 para o pino
3, encima do disco grande, com 15 movimentos. Está resolvido o jogo da Torre com
15+1+15=31 movimentos. Novamente, observamos que não sabemos exatamente quais
são esses 31 movimentos, mas sabemos que, se são necessários 15 movimentos para
moverem 4 discos, então serão necessários 31 movimentos para mover 5 discos.
E se n=6? Deixo para você concluir que o número de movimentos necessários para se
resolver o jogo da Torre de Hanói com 6 discos será 31+1+31=63.
Esses exemplos particulares permitem concluir que se o problema com n discos se resolve
com N movimentos, então o problema com n+1 discos se resolve com N+1+N = 2N+1
movimentos, pois é necessário liberar o disco maior, de baixo, sempre, com o
deslocamento dos n discos acima dele através de N movimentos. Depois, colocamos esse
disco grande no pino vazio com 1 movimento e, finalmente, movemos os n discos para
cima desse grande com mais N movimentos.
Esses casos particulares e essa conclusão geral, permitem que montemos a seguinte tabela
e façamos a conjectura que dela segue:
n = número de discos
1
2
3
4
5
6
N= número de movimentos necessários
para resolver o problema da torre de Hanói
1
3
7
15
31
63
7
8
127
255
Bem, para encontrarmos a próxima linha da tabela, é fácil: quando n=9, então N será
255.2+1=511. Mas se quisermos N quando n for 26? Chegaríamos à resposta apenas
depois de termos passado por n=10, 11, 12, ... , 23, 24 e 25, um trabalho considerável.
III.
A indução empírica
Seria, portanto, interessante que obtivéssemos uma fórmula para N em função de n, que
nos permitisse encontrar diretamente N quando n fosse 26 ou qualquer outro número
natural. Como obter uma tal fórmula, se é que ela existe?
Comecemos analisando novamente os casos particulares acima. Observe que se somarmos
1 aos números da segunda coluna, obteríamos as potências sucessivas de 2: 2, 4, 8, 16, 32,
64, 128 e 256. Será que isso aconteceria para n=9? E para um outro n qualquer? Aí, os
casos particulares não são conclusivos, seu poder é, no máximo, o de sugerir.
Vamos reescrever a tabela com as observações que fizemos:
n = número de discos
1
2
3
4
5
6
7
8
N= número de movimentos necessários
para resolver o problema da torre de Hanói
1=
3=
7=
15=
31=
63=
127=
255=
O que, então, a tabela acima sugere?
Esses casos particulares sugerem que
, para n sendo um número natural
qualquer. Se essa fórmula for verdadeira, podemos calcular qualquer N em função de um
dado n, por exemplo, se n=12, então
, sem passar pelo n=9, 10 e 11.
Neste ponto, vamos parar para refletir: mesmo que a tabela acima tivesse mil linhas e essa
fórmula fosse verificada nesses mil casos, não poderíamos garantir que a fórmula valeria
para qualquer número natural n.
Anteriormente havíamos concluído de observações particulares que se o problema com n
discos se resolve com N movimentos, então o problema com n+1 discos se resolve com
N+1+N = 2N+1 movimentos, pois é necessário liberar o disco maior, de baixo, sempre,
qualquer que seja o número de discos! Mas agora a situação é outra: não há um argumento
definitivo válido para concluirmos a fórmula acima para qualquer número n de discos.
Essa é a diferença entre o método científico em matemática e em ciências experimentais:
nas ciências experimentais, as conclusões são alcançadas a partir de um número
considerado suficiente de observações particulares, isto é, induz-se uma conclusão a
partir de casos particulares, trata-se da indução empírica. Essa conclusão é mantida até
que outras situações experimentais levem a outras conclusões. Na matemática, as
conclusões são obtidas através de argumentos gerais apoiados num jogo lógico de
verdades pré-estabelecidas e, uma vez deduzida uma conclusão, ela será verdadeira
sempre.
IV.
A Indução Matemática
Vamos então usar o Princípio da Indução Matemática (PIM) para provar que a fórmula
acima vale, para todo número natural n. Vamos considerar que o conjunto dos números
naturais, representado pelo símbolo IN é {1, 2,3, 4, ...}.
A versão que utilizaremos do PIM, abordada aqui de forma intuitiva, afirma o seguinte:
Se A é um subconjunto de IN que satisfaz as duas condições (a) e (b) abaixo, então
A=IN:
(a) 1 é um elemento de A;
(b) Se A contém um número qualquer x, então ele contém também o número x+1.
Pense um pouco sobre a afirmação acima e tente convencer-se de que ela deve ser mesmo
verdadeira. Vou tentar ajudar: primeiro, entenda bem que o conjunto A foi dado como
satisfazendo as duas condições (a) e (b). Assim, pela condição (a), o conjunto A contém o
número 1. Mas, pela condição (b), A deverá, então, conter o número 2 (já que contém o 1 e
2=1+1). Como ele contém o 2, pela condição (b), A deverá conter também o número
3=2+1. Mas a condição (b), poderosíssima, vai então fazer com que A contenha também o
número 4, daí o 5, portanto o 6 e, dessa forma, fará com que A contenha todos os números
naturais, logo, como também A é um subconjunto de IN, então ele deve ser igual a IN.
Perceba ainda que o poder da condição (b) de nada serviria se a condição (a) não estivesse
a permitir a presença do 1 no conjunto A.
V.
De volta à Torre
Voltemos agora para a Torre de Hanói e vamos provar que
.
Para tanto, utilizaremos o PIM e, para isso, precisamos adequar a situação às condições
presentes no enunciado do PIM.
Consideremos a torre com n discos assentados em um dos pinos em ordem decrescente
de tamanho, de baixo para cima, como sempre.
Vamos considerar o conjunto A como sendo o subconjunto de IN constituído dos números
n para os quais o número de movimentos necessários para se resolver o jogo da Torre de
Hanói com n discos é
.
Se mostrarmos que A satisfaz as condições (a) e (b) do PIM, a conclusão será que A=IN, o
que quer dizer
, para todo n natural.
A condição (a) é satisfeita pelo conjunto A, porque 1 ser elemento de A, nesse caso,
significa que o jogo da torre com apenas um disco pode ser resolvido com
movimentos, isto é, com apenas 1 movimento, o que é óbvio: basta transferir esse disco
para um dos outros dois pinos e pronto.
A condição (b), nesse caso, significa que, se para um jogo com x discos forem necessários
movimentos (que significa x ser elemento de A), então um jogo de x+1 discos
exigirá
movimentos (que significa x+1 ser elemento de A).
Para ver que isso ocorre, lembremos que se são necessários X movimentos para resolver o
jogo com imagine x discos, então serão necessários 2X+1 movimentos para resolver o jogo
com x+1 discos. Basta, então, substituirmos X por
e obteremos que 2X+1
movimentos. Assim, a condição (b) do PIM
também é satisfeita pelo conjunto A.
Portanto, pelo PIM, A=IN, isto é, a Torre de Hanói com n discos necessita de
movimentos para ser resolvida, qualquer que seja o número natural n de discos.
VI.
A lenda da Torre de Hanói
O problema da Torre de Hanói foi publicado em 1883 pelo matemático francês
Edouard Lucas, inspirado numa lenda hindu segundo a qual, no início dos tempos
foi dada aos monges de um templo a tarefa de resolver o jogo da torre para 64
discos e que, ao final da resolução, o mundo acabaria. Se realmente isso fosse
ocorrer, seriam necessários
movimentos. Em quanto tempo, então, o
mundo acabaria? Se supusermos que cada um desses movimentos dura 1 segundo,
então o mundo acabaria depois de
= 18.446.744.073.709.551.615 segundos, ou
seja, aproximadamente 585 bilhões de anos! Como já se passaram perto de 6 bilhões de
anos desde o início do universo, ainda nos resta um tempinho de aproximadamente 580
bilhões de anos pra curtir o planeta, desde que cuidemos dele!