Na Torre de Hanói com n discos, o menor número de movimentos para mover a torre para outra haste é 2ⁿ−1. É o resultado de multiplicar 2 por si mesmo tantas vezes quanto o número de discos e subtrair 1.

Número de discosMínimo de movimentos
1 disco1
2 discos3
3 discos7
4 discos15
5 discos31
6 discos63
7 discos127
8 discos255
9 discos511

A cada disco a mais, o número de movimentos quase dobra. Vamos ver, passo a passo, por que isso acontece.

Olhe para o maior disco

Pense em mover uma torre de n discos da esquerda para a direita. O maior disco está embaixo dos outros, então não dá para movê-lo assim. Para levá-lo para a direita, no momento do movimento é preciso que:

  • não haja nada sobre o maior disco;
  • a haste da direita esteja vazia (porque não se pode pôr nenhum disco menor embaixo do maior).

Ou seja, os outros n−1 discos precisam estar todos empilhados na haste do meio.

Dividindo os movimentos em 3 partes

Daqui, a sequência para mover n discos se divide em 3 partes.

  1. Mover os n−1 discos de cima da esquerda para o meio.
  2. Mover o maior disco da esquerda para a direita, em 1 movimento.
  3. Mover os n−1 discos do meio para cima do maior disco.

Os passos 1 e 3 são exatamente o problema de “mover uma torre de n−1 discos”. Escrevendo T(n) para o mínimo de movimentos com n discos, temos a relação

T(n) = T(n−1) + 1 + T(n−1) = 2 × T(n−1) + 1

Com 1 disco é 1 movimento, então T(1) = 1. Daí saem em ordem 3, 7, 15, 31…

Por que a fórmula é 2ⁿ−1

Somando 1 aos dois lados dessa relação, temos

T(n) + 1 = 2 × (T(n−1) + 1)

Isso quer dizer que “o número de movimentos mais 1” dobra exatamente a cada disco a mais. Com 1 disco, T(1) + 1 = 2, então com n discos é 2 multiplicado n vezes, ou seja, 2ⁿ. Subtraindo 1, chega-se a T(n) = 2ⁿ−1.

Por que não dá para fazer com menos

Vimos que a sequência acima move em 2ⁿ−1 movimentos. Mas não existiria um jeito de mover com menos?

Como vimos, no primeiro momento em que o maior disco se move, os outros n−1 discos precisam estar todos empilhados em outra haste. Até ali, gastam-se pelo menos os movimentos de mover uma torre de n−1 discos. Do mesmo modo, depois que o maior disco é posto pela última vez na direita, reempilhar os n−1 discos restantes sobre ele também exige pelo menos os movimentos de mover uma torre de n−1 discos. E o próprio maior disco se move pelo menos 1 vez.

Qualquer sequência precisa desses 3 trechos de movimentos. Por isso não dá para fazer com menos que 2 × T(n−1) + 1. Sabe-se também que a sequência mínima, na verdade, é uma só.

O “Clássico” do app tem 127 movimentos

O modo “Clássico” do app Torre de Hanói tem 7 discos, então o mínimo é 2⁷−1 = 127 movimentos. Se o número de movimentos chegar a 127, você resolveu com a sequência mínima. Movendo “o disco pequeno sempre no mesmo sentido”, como no artigo sobre como jogar, você completa em exatamente 127 movimentos.