Torre de Hanói

Diz a lenda que um templo em Benares, na Índia, tem três pinos onde monges movem 64 discos de ouro de um pino para outro, dia e noite. No dia em que terminarem, o mundo acaba. Assustador? Quando você vir como a contagem de movimentos cresce, saberá quão distante esse "fim do mundo" realmente está.

Apenas três regras

O objetivo: levar uma pilha inteira de discos do pino da esquerda para o pino da direita.

1. Mova um disco de cada vez, e somente o disco de cima de um pino;
2. Um disco só pode ficar sobre um pino;
3. Um disco maior nunca pode ficar sobre um menor.

As regras são simples, mas a terceira é uma armadilha: coloque um disco grande sobre um pequeno e a tentativa acaba arruinada na hora. Aliás, o disco menor é o mais livre — ele pode ficar sobre qualquer coisa e nunca quebra uma regra.

Desvendando três discos

Pensar nos três discos de uma vez fica confuso. O truque: domine dois discos, e três discos virão em seguida.

Para mover 3 discos para o pino de destino:

1. Primeiro mova os 2 discos de cima para o pino auxiliar do meio (3 movimentos);
2. Mova o disco maior diretamente para o pino de destino (1 movimento);
3. Mova os 2 discos do pino auxiliar de volta para cima dele (3 movimentos).

$3 + 1 + 3 = 7$ movimentos, pronto. Percebeu algo? "Mover 2 discos" aconteceu duas vezes — o trabalho grande se dividiu em dois trabalhos menores mais um movimento próprio.

Quatro discos funcionam do mesmo jeito: mova 3 discos para o pino auxiliar (7 movimentos), transfira o disco maior (1 movimento), mova os 3 discos de volta para cima (7 movimentos) — 15 no total. Se você consegue mover n−1 discos, consegue mover n. Essa estrada não tem fim, e sempre funciona.

Como usar

Discos

3456

Movimentos: 0Mínimo: 7

Mova um disco por vez; nunca coloque um disco maior sobre um menor

A contagem de movimentos: 1, 3, 7, 15, 31…

Conte os movimentos mínimos:

Discos	1	2	3	4	5
Movimentos mínimos	1	3	7	15	31

O padrão é dobrar e depois somar 1: $3 = 1 \times 2 + 1$, $7 = 3 \times 2 + 1$, $15 = 7 \times 2 + 1$… escrito como uma fórmula:

$2^n - 1$

Para n discos, o mínimo é $2^n - 1$ movimentos. Isso combina exatamente com a estratégia: mover n discos = mover n−1 discos duas vezes + mover o disco grande uma vez.

Por que 64 discos nunca terminam

Esse é o lado assustador do crescimento exponencial: adicionar um disco é um passo pequeno, mas a contagem de movimentos quase dobra. Ir de 5 discos para 10 aumenta o mínimo de 31 para 1023 — ainda apenas cerca de 17 minutos a um movimento por segundo, sem problema algum; com 20 discos, passa de um milhão de movimentos. Qualquer coisa que dobra a cada passo logo se torna inimaginável.

Confira você mesmo

Questionário rápido

Tentar de novo

0 / 3 corretas0 / 3 corretas

1. 1. Qual é o número mínimo de movimentos para 3 discos?

   679

2. 2. Ao passar de 3 discos para 4, o mínimo sobe de 7 para quanto?

   81415

3. 3. Por que a lenda dos 64 discos nunca será concluída?

   Os discos se desgastamCada disco extra quase dobra os movimentos, então o total é absurdoOs monges se cansam