Comentários

As torres de Hanói

As torres de Hanói

Diz a lenda que no grande templo de Varanasi, abaixo da cúpula que marca o centro do mundo, está uma base de bronze sobre a qual são fixadas três agulhas de diamante de um cotovelo alto e a espessura do corpo de uma abelha. .

Em uma dessas agulhas, Deus, no início dos séculos, colocou sessenta e quatro discos de ouro puro, o maior na base de bronze, e os outros, em ordem decrescente de largura, sobrepostos ao topo. Esta é a torre Brahma.

Dia e noite, os padres se revezam na ocupação de transportar a torre da primeira agulha de diamante para a terceira, sem se desviar das regras fixas e imutáveis ​​impostas por Brahma: O padre não deve mover mais de um disco por vez e você não deve colocar um disco que não seja uma agulha livre ou um disco maior. Ao seguir estritamente essas recomendações, os sessenta e quatro discos foram transferidos da agulha na qual Deus os colocou no terceiro, a torre e os brâmanes se tornarão poeira e serão o fim do mundo.

Supondo que os padres pudessem fazer uma jogada a cada segundo,

Quanto tempo levará para chegar ao fim do mundo?

Solução

O número mínimo de movimentos para resolver o problema é 2n - 1, sendo n o número de discos, neste caso 64. Se fizermos o cálculo, obtemos que 18.446.744.073.709.551.615 movimentos de um segundo cada são necessários, representando aproximadamente 585.000.000.000 de anos.

Você pode encontrar mais informações sobre a abordagem e a resolução desse problema nesta página e na wikipedia.