Para mover n discos primeiro você precisa afastar os n − 1 de cima, depois mover o disco maior uma vez, e em seguida recolocar esses n − 1 em cima. Assim M(n) = 2M(n − 1) + 1 com M(1) = 1, que se resolve como 2ⁿ − 1: oito discos precisam de 255 movimentos e três precisam de 7, nos dois primeiros links. 255 vai parecer familiar a quem lê tamanhos de memória: é o maior valor que cabe em um byte sem sinal, exatamente por esta razão.
A versão de Lucas vinha com sessenta e quatro discos de ouro e uma profecia de que o mundo acabaria quando a pilha tivesse sido movida. A um movimento por segundo isso são 2⁶⁴ − 1 = 1.844674407371⋅10+19 movimentos (terceiro link), uns 585 bilhões de anos, mais de quarenta vezes a idade do universo, e o quebra-cabeça de oito discos que você tem diante de si leva um minuto e meio. A mesma duplicação que torna trivial o caso pequeno torna geológico o grande, que é todo o sentido de uma exponencial: 255 e 1.844674407371⋅10+19 são a mesma regra a sessenta passos de distância.
Resposta
255
Como ler
2⁸ − 1 na área de trabalho. O segundo link são três discos; o terceiro é a contagem de sessenta e quatro discos que acaba com o mundo.
Fonte
Édouard Lucas marketed the Tower of Hanoi in 1883 as the towers of Brahma at Benares; the minimum for n disks is 2ⁿ − 1, forced by the recurrence M(n) = 2M(n − 1) + 1
Resolva na calculadora
Estes links abrem a calculadora adequada com os números deste problema já escritos. A linha de cima é o que a tela deveria mostrar: confira você mesmo.