O Quebra-cabeças designado por Torres de Hanói
(ou Torres de Brama) é constituído por três colunas (dispostas em linha ou como
vértices de um triângulo) e por um número variável de discos (cujos diâmetros
são sucessivamente maiores) que podem ser encaixados nas colunas.
As Torres de Hanói que se
encontram na exposição Matemática Viva, situada no Pavilhão do
Conhecimento (Lisboa), têm o seguinte aspecto (dispõem de apenas 4 discos):
(fotografia minha)
Há uma única regra para a colocação dos discos nas colunas: quando se
encaixa um disco, ele não pode ser colocado sobre outro disco com diâmetro
inferior.
E o objectivo do Quebra-cabeças é: estando N discos encaixados numa
das colunas (a figura seguinte exemplifica-o para N = 3 discos) …
… pretende-se encaixá-los numa
segunda coluna, com o apoio da terceira.
Para N = 1 basta um único
movimento.
Para N = 2 são necessários … 3
movimentos.
Para N = 3, a dificuldade aumenta
um pouco …
Para N = 4 já é necessária alguma
organização …
Número de discos (N):
|
1
|
2
|
3
|
4
|
5
|
6
|
Nº mínimo de
movimentos (MN):
|
1
|
3
|
Depois de algumas experiências
percebemos que o raciocínio mais simples é: se sabemos resolver para N discos,
então sabemos resolvê-lo para N + 1 discos. Chama-se a isto, raciocínio por
recorrência.
De que forma expressar matematicamente
o número mínimo de movimentos (MN) em função do número de discos
(N)?