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 discos | Mínimo de movimentos |
|---|---|
| 1 disco | 1 |
| 2 discos | 3 |
| 3 discos | 7 |
| 4 discos | 15 |
| 5 discos | 31 |
| 6 discos | 63 |
| 7 discos | 127 |
| 8 discos | 255 |
| 9 discos | 511 |
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.
- Mover os n−1 discos de cima da esquerda para o meio.
- Mover o maior disco da esquerda para a direita, em 1 movimento.
- 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.
