disco maior se move apenas uma vez”.
Figura 17.6
Grafo H 5 da Torre de Hanói com 5 discos.Passemos agora a um caso pessoal, que ilustra o modo como as ideias podem passar da
matemática recreativa para uma linha central de pesquisa. Em 1989, escrevi sobre o grafo da
Torre de Hanói em Pour la Science, a revista-irmã da Scientific American, publicada na
França. Não muito depois, participei do Congresso Internacional de Matemáticos em Kyoto,
onde conheci um matemático alemão chamado Andreas Hinz. Ele vinha tentando calcular a
distância média entre dois pontos de um triângulo de Sierpinski, teve dificuldades e pediu
ajuda a dois especialistas. Um deles disse “É muito difícil”, e o outro disse “É trivial, e a
resposta é 8/15”. No fim das contas, viu-se que a prova do segundo especialista era falaciosa
e que o primeiro estava certo. O equívoco equivalia a presumirmos que, na Torre de Hanói, o
famoso teorema segundo o qual “o disco maior se move apenas uma vez”, aplicado às
posições inicial e final habituais, também fosse válido quando quiséssemos nos mover entre
quaisquer duas posições pelo caminho mais eficiente. Isso nem sempre é verdade, sendo um
erro comum na literatura.
Infelizmente, apreender a natureza da falácia não nos ajuda a encontrar a resposta correta.
Mas Hinz já havia provado uma fórmula para o número médio de movimentos entre as
posições da Torre de Hanói e, usando essa prova, pôde provar que, no jogo com n discos, o
número médio de movimentos que ligam duas posições é assintótico a (466/885)2n — isto é, a
fórmula representa uma boa aproximação para algum n de número elevado. Ao ler o meu
artigo, ele percebeu que seu resultado para o jogo com n discos determina imediatamente que a
distância média entre dois pontos num triângulo de Sierpinski é precisamente 466/885. (Basta
dividirmos sua fórmula por 2n – 1, a extensão do “lado” de Hn, e escolhermos um n muito
elevado. As unidades de medida devem ser escolhidas de modo que o lado do triângulo tenha
extensão 1.) O resultado é cerca de 2% menor que o valor de 8/15 sugerido pelo segundo
especialista.
Até o momento, essa abordagem pela Torre de Hanói é o único método conhecido para
encontrarmos a resposta. Para os que adotam o pensamento estatístico, Hinz também provou