A Torre de Hanói aparece muito em livros didáticos e provas de vestibular como tema de recorrência e de indução matemática no ensino médio (no Japão, na matemática B). Neste artigo, praticamos a forma de pensar resolvendo exemplos. Os discos são numerados 1, 2, 3… do menor para o maior, e o mínimo de movimentos para mover uma torre de n discos se escreve aₙ.

Exemplo 1 Montar a recorrência

Problema: Há 3 hastes, A, B e C, e em A estão empilhados n discos de tamanhos diferentes, do maior para o menor. Movendo 1 disco por vez e sem pôr um disco grande sobre um menor, levam-se todos os discos para C. Sendo aₙ o mínimo de movimentos, escreva aₙ₊₁ em função de aₙ.

Resolução: Olhe o maior disco (o de número n+1). Para movê-lo para C, no momento do movimento os n discos de cima precisam estar todos empilhados em B.

  1. Mover os n discos de cima de A para B … no mínimo aₙ movimentos
  2. Mover o disco n+1 de A para C … 1 movimento
  3. Mover os n discos de B para C … no mínimo aₙ movimentos

Com essa sequência dá para mover n+1 discos, então aₙ₊₁ ≦ 2aₙ + 1. Por outro lado, em qualquer sequência os movimentos de 1 a 3 são necessários, então aₙ₊₁ ≧ 2aₙ + 1. Portanto,

aₙ₊₁ = 2aₙ + 1 (a₁ = 1)

Em vestibulares, às vezes se pede mostrar ”≦” e ”≧” para afirmar a igualdade. Uma explicação detalhada está na fórmula do mínimo de movimentos.

Exemplo 2 Achar o termo geral

Problema: Ache o termo geral da sequência definida por a₁ = 1 e aₙ₊₁ = 2aₙ + 1.

Resolução: Uma recorrência da forma aₙ₊₁ = paₙ + q se transforma usando o α que satisfaz α = 2α + 1. Como α = −1, somando 1 aos dois lados,

aₙ₊₁ + 1 = 2(aₙ + 1)

A sequência aₙ + 1 é uma progressão geométrica de primeiro termo a₁ + 1 = 2 e razão 2. Logo, aₙ + 1 = 2 · 2ⁿ⁻¹ = 2ⁿ, e

aₙ = 2ⁿ − 1

Para conferir, verifique que a₁ = 1, a₂ = 3 e a₃ = 7 combinam com a recorrência.

Exemplo 3 Provar por indução matemática

Problema: Prove por indução matemática que o mínimo de movimentos para mover n discos é 2ⁿ − 1.

Resolução:

  1. Para n = 1, 1 disco se move em 1 movimento e não dá para menos, então o mínimo é 1 = 2¹ − 1, e vale.
  2. Suponha que, para n = k, o mínimo de movimentos seja 2ᵏ − 1. Para n = k+1, pela ideia do Exemplo 1, o mínimo é 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1, e vale também para n = k+1.
  3. Por 1 e 2, vale para todos os números naturais n.

O ponto é que o ”≦ e ≧ juntos” do Exemplo 1 é usado na etapa 2 da indução.

Exemplo 4 Quando só se pode mover para a haste vizinha

Problema: As hastes A, B e C estão em fila, e os discos só se movem entre A e B e entre B e C (não dá para ir direto de A para C). Ache o mínimo de movimentos bₙ para mover n discos de A para C.

Resolução: O maior disco, o n, precisa se mover 2 vezes: A → B → C.

  1. Mover os n−1 discos de cima de A para C … bₙ₋₁ movimentos (para mover o n para B, é preciso deixar B vazia)
  2. Mover o disco n de A para B … 1 movimento
  3. Mover os n−1 discos de C para A … bₙ₋₁ movimentos (para mover o n para C, é preciso deixar C vazia)
  4. Mover o disco n de B para C … 1 movimento
  5. Mover os n−1 discos de A para C … bₙ₋₁ movimentos

Portanto bₙ = 3bₙ₋₁ + 2 (b₁ = 2). De α = 3α + 2, temos α = −1, então bₙ + 1 = 3(bₙ₋₁ + 1). A sequência bₙ + 1 é uma progressão geométrica de primeiro termo 3 e razão 3, logo

bₙ = 3ⁿ − 1

Para 1 a 6 discos, também confirmamos por um cálculo que examina todas as disposições que esse é o mínimo de movimentos. O curioso é que, nesses 3ⁿ − 1 movimentos, passa-se uma vez por cada uma das 3ⁿ disposições (o número de disposições está no artigo sobre regularidades).

Exemplo 5 Exercícios

Por fim, resolva você mesmo. As respostas estão abaixo.

  1. Ache o mínimo de movimentos com 10 discos.
  2. A partir de quantos discos o mínimo de movimentos passa de 1000?
  3. Ao mover n discos com a sequência mínima, quantas vezes o menor disco se move?

Respostas: 1. 2¹⁰ − 1 = 1023 movimentos. 2. De 2ⁿ − 1 > 1000, temos 2ⁿ > 1001; como 2⁹ = 512 e 2¹⁰ = 1024, são 10 discos ou mais. 3. 2ⁿ⁻¹ vezes (a razão está em “Quantas vezes cada disco se move”, no artigo sobre regularidades).