Figura 17.3
Números ímpares (preto) e pares (branco) no triângulo de Pascal.Ao que parece, Lucas era assombrado — ainda que sem sabê-lo — pelo triângulo de
Sierpinski. Em 1883, ele comercializou, sob o pseudônimo N. Claus (o sobrenome é um
anagrama do seu), o famoso quebra-cabeça conhecido como Torre de Hanói. O jogo consiste
em oito (ou menos) discos montados sobre três pinos — o caso com 3 discos é mostrado na
Figura 17.4 —, sendo um velho companheiro dos matemáticos recreativos e dos cientistas da
computação. Os discos são montados em um dos pinos por ordem de tamanho, como ilustrado,
e deve-se mover um de cada vez, de modo que nenhum disco fique em cima de um disco
menor, até que todos terminem numa única pilha, mas num pino diferente do inicial.
Figura 17.4
Posição típica na Torre de Hanói com três discos, e seus movimentos permitidos.Sabemos muito bem que a solução tem uma estrutura recursiva. Isto é, podemos deduzir a
solução para o jogo com (n + 1) discos a partir do jogo com n discos. Por exemplo, suponha
que você saiba como resolver o jogo com 3 discos e seja então apresentado à versão com 4
discos. A princípio, ignore o disco de baixo e use seu conhecimento do jogo com 3 discos para
transferir os primeiros três discos para um pino vazio. Agora, temporariamente, observe o
quarto disco, apoiado completamente só no pino original, e mova-o para o outro pino vazio.
Volte então a ignorá-lo, mas lembre-se do pino em que está, e use o seu conhecimento sobre o
jogo com 3 pinos para transferir os três primeiros discos para esse pino — em cima do quarto
disco, o que resolve a charada. Dessa maneira, podemos resolver um jogo com 100 discos se
soubermos como resolver o jogo com 99 discos, e pelo mesmo motivo podemos resolver o
jogo com 99 discos se soubermos como resolver o jogo com 98 discos, e assim por diante... O
que, afinal, nos leva ao jogo com 1 só disco. Mas esse é fácil de resolver: basta pegarmos o
único disco e movê-lo para qualquer outro pino.
Podemos interpretar geometricamente essa estrutura recursiva, e é aí que surge a conexão
com o triângulo de Sierpinski. Qualquer quebra-cabeça desse tipo geral (mover objetos,
número finito de posições) pode ser associado a um grafo Hn cujos vértices sejam as posições
permitidas dos discos e cujas arestas representem os movimentos permitidos entre as
posições. Qual é a aparência de Hn? Por exemplo, considere H 3 , que descreve as posições e
movimentos de um jogo com 3 discos. Para representar uma posição, numere os três discos
como 1, 2, 3 — 1 é o menor, 3 é o maior. Numere os pinos como 1, 2, 3 da esquerda para a
direita. Suponha, por exemplo, que o disco 1 esteja no pino 2, o disco 2 esteja no pino 1 e o
disco 3 esteja no pino 2. Dessa forma definimos perfeitamente a posição do jogo, porque as
regras determinam que o disco 3 deve estar embaixo do disco 1. Assim, podemos codificar