Variantes da Torre de Hanói
Tássio Naia dos Santos∗ e
José Augusto Ramos Soares (orientador)
para a terceira, sem se descuidar das regras
xas que acabamos de indicar, e que foram
impostas por Brahma. Quando tudo esti-
Universidade de São Paulo (USP), Brasil
ver terminado, a torre e os brâmanes cairão,
[email protected]
e será o m dos mundos!
1. Introdução
Os enunciados acima são do conhecido quebracabeça Torre de Hanói [15], proposto comercialmente
Le mandarin N. Claus (de Siam) nous
pelo matemático francês Édouard Lucas em 1983. O
raconte qu'il a vu, dans ses voyages pour
problema consiste em determinar a menor seqüência
la publication des écrits de l'illustre Fer-
de movimentos que perfazem a tarefa dos monges.
Fer-Tam-Tam,
dans le grand temple de
Um
Bénarès, au-dessous du dôme qui marque
le centre du monde, trois aiguilles de di-
já
de
si
interessante,
utilizado
truturas recursivas e indução, a Torre de Hanói rende
amant, plantées dans une dalle d'airain,
material para estudo há mais de um século, e suas
hautes d'une coudée et grosses comme le
variantes ainda apresentam questões em aberto.
corps d'une abeille. Sur une de ces aiguilles
Numerosos foram os estudos sobre sua estrutura
Dieu enla, au commencement des siècles,
matemática, e foram observadas relações entre o
soixante-quatre disques d'or pur, le plus
quebra-cabeça e objetos matemáticos conhecidos,
large reposant sur l'airain, et les autres,
como os triângulos de Sierpi«ski e de Pascal,
de plus en plus étroits, superposés jusqu'au
sommet.
problema
freqüentemente como exemplo em introduções a es-
a
seqüência diatômica de Stern [4] e os números de
C'est la tour sacrée de Brahma.
Stirling de segundo tipo [2].
Nuit et jour, les prêtes se succèdent sur les
Uma extensa referên-
cia bibliográca (com mais de 350 entradas), sobre
marches de l'autel, occupés à transporter
diversos aspectos do problema e suas variantes, foi
la tour de la première aiguille de diamant
compilada por Stockmeyer [11].
sur la troisième, sans s'écarter des règles -
Mesmo exibindo diversas propriedades interessan-
xes que nous venons d'indiquer, et qui on
tes, a solução do quebra-cabeça original é atualmente
été imposées par Brahma. Quand tout sera
já bem conhecida. Por outro lado a investigação de
ni, la tour et les brahmes tomberont, et ce
suas diversas variantes tem descortinado uma imen-
sera la n des mondes!
sidão de questões complexas, que desaam pesquisadores há décadas.
O mandarim N. Claus (de Sião) nos
conta que viu, em suas viagens para a publi-
De longe, a variante mais conhecida, mais antiga
cação dos escritos do ilustre Fer-Fer-Tam-
e estudada da Torre de Hanói advém do incremento
Tam, no grande templo de Bénarès, sob o
do número de pinos disponíveis para empilhar os dis-
domo que marca o centro do mundo, três
cos. Essa variante data de 1904 [1], quando que são
agulhas de diamante, assentadas sobre uma
considerados 4 pinos.
sas como o corpo de uma abelha.
Sobre
imposição de restrições a movimentos de discos en-
uma dessas agulhas, Deus empilhou, no co-
tre certos pinos. Abordamos aqui três delas. Chama
meço dos séculos, sessenta e quatro discos
a atenção o fato de que, nessa família de variantes,
de ouro puro, o maior repousando sobre a
a quantidade de pinos se apresentar como um fator
laje, e os outros, cada vez menores, sobre-
determinante da complexidade da análise: as vari-
postos até o pico. Esta é a torre sagrada de
antes generalizáveis para um número arbitrário de
Brahma. Dia e noite, os monges se sucedem
pinos são questões em aberto se o número de pinos
nos afazeres do altar, ocupados a transpor-
for maior ou igual a quatro.
1
laje de latão, altas de um côvado e gros-
Afora essa, diversas outras variantes nasceram da
tar a torre da primeira agulha de diamante
Nas seções 3, 4 e 5, apresentamos resultados conhecidos da Torre de Hanói e de algumas variantes
∗ [email protected]
1 Côvado:
bem conhecidas, a
medida correspondente à distância entre o cotovelo e as pontas dos dedos, aproximadamente equivalente a
45 cm.
variante estendida,
proposta em
sua forma generalizada para um número qualquer de
pinos em [13], as variantes
linha
107
[5].
circular
[5],
estelar
[12] e
2. Notação e denições
Discos e pinos.
A
0
1
(n − 1) discos →
1 disco →
O número de discos e de pinos envol-
1
0
0
1
0
1
0
1
0
1
0
1
0
1
vidos nos problemas a serem discutidos serão denotados, respectivamente, por
n e p.
Os discos
1, 2, . . . , n
Figura 1.
são numerados em ordem crescente de tamanho, e os
pinos são numerados de 1 a
Congurações.
conguração
tamanho do topo para a base. Muitas vezes, a uma
dada conguração faremos corresponder uma
n-upla
1 ≤ i ≤ n e 1 ≤ ai ≤ p, que representa que
o disco i repousa no pino ai .
Uma conguração a = (an , an−1 , . . . , a1 ) é dita
simples se ai = k para todo i, 1 ≤ i ≤ n. Denotarek
mos tais congurações Sn .
com
Indicaremos ainda a passagem de uma congura-
c1
a outra,
c2 ,
por
c1 → c2 .
Quando tratarmos
da tarefa de mover uma pilha de discos de um pino
a
a outro, (Sn
de
origem
Grafos.
um grafo
e
G
→ Snb , a, b pinos) chamaremos
o pino b de destino.
o pino
a
Denotaremos o conjunto de vértices de
por
V (G),
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
(b)
Recursão na Torre de Hanói
uma dis-
buição dos discos em pilhas em ordem crescente de
ção
(a)
C
1
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
p.
Chamamos
posição válida de discos nos pinos, i.e.: uma distri-
(ai ),
B
e seu conjunto de arestas por
E(G). Quando tratarmos de um grafo
A(G) denotará o conjunto de seus arcos.
orientado,
uma estratégia recursiva para a resolução do problema, já que, para que se chegue ao dito estado, é
necessário mover uma pilha menor para o pino auxiliar. Em outras palavras, o problema reduz-se a uma
instância menor do problema inicial.
Denotemos por
o número mínimo de movi-
n
dis-
cos de um pino a outro. Então, no momento representado pela gura 1 (b), já terão sido efetuados, no
mínimo,
f (n − 1)
movimentos. Pode-se agora mover
o maior disco para o pino de destino.
Mas a situ-
ação após esse movimento é a mesma de antes, se
trocarmos os rótulos dos pinos A e C. Por simetria,
a seqüência que demanda o menor número de movimentos possível já está neste ponto determinada, e
basta perfazer mais
f (n − 1)
movimentos.
Outro esquema possível de movimentação dos discos seria fazer com que o maior disco (n) fosse de A
para B antes de chegar a C. Ora, essa opção implica
3. A Torre de Hanói
necessariamente a passagem por três congurações
Dispõe-se de três pinos, em um dos quais há discos
empilhados em ordem crescente de tamanho do topo
intermediárias antes que seja possível nalmente mover o maior disco para C:
•
para a base. Deseja-se transportar a pilha para um
dos outros pinos, de modo que:
o disco maior está em A, e todos os demais discos estão em C;
1. somente seja movido um disco por vez;
•
da pilha em que está; e
•
o disco maior está em B e os demais estão em
A;
3. jamais um disco repouse sobre outro de menor
tamanho.
o disco maior está em B e todos os demais estão
em C; e
2. o disco a ser movido a cada passo seja o menor
e, ao menos,
Se a pilha consistir de apenas um disco, basta um
movimento para resolver o problema. Consideremos,
sem perda de generalidade, que o pino de origem
seja denotado por A, e o de destino seja o C (vide
gura 1 (a)). Quando a quantidade de discos,
f (n)
mentos em que é possível mover uma pilha de
n,
for
igual a 2, faz-se necessário liberar o maior deles já
que em algum momento ele terá que ser movido colocando o menor em um pino auxiliar (pino B) e,
2f (n−1)+1 movimentos são necessários
nesse caso.
Conseqüentemente, a seqüência de movimentos em
que o maior disco é movido duas vezes para alcançar o pino C tem tamanho
traste com
2f (n − 1) + 1
3f (n − 1) + 2,
em con-
do outro esquema de mo-
vimentação, e, portanto, não faz parte da solução
2
procurada . Assim, a relação que expressa o número
procurado é
a seguir, mover, primeiro o maior e depois o menor,
f (n) = 2f (n − 1) + 1.
para o pino de destino, num total de 3 movimentos.
(1)
As restrições do quebra-cabeça condicionam o movimento do maior dos discos de A para C a uma
única disposição dos demais discos: devem estar todos em B. Essa característica sugere o emprego de
2 Isso
ca claro quando se considera que f (1) = 1 para
ambas as estratégias de movimentação, e que 3f (n − 1) + 2 >
2f (n − 1) + 1, se n ≥ 0.
108
f (n) + 1 = 2(f (n) + 1), com f (1) = 1,
f (n) + 1 = g(n),
g(n) = 2g(n − 1),
⇒ g(n) = 2n .
g(1) = 2
Donde
fazendo
e,
Por construção,
Hn
possui
n-upla (an , an−1 , . . . , a1 ) reprei está no pino
de Hn , cada um de seus vértices
Lembramos que a
senta a conguração tal que o disco
ai .
Pela denição
corresponde naturalmente à uma conguração.
A
conexão entre as congurações do quebra-cabeça e o
f (n) = 2n − 1.
(2)
O algoritmo 1 (recursivo) obtém os movimentos
necessários para resolver o problema com o mínimo
possível de movimentos.
Algoritmo 1 mover (n,origem, destino, auxiliar)
Requer: n ≥ 1, {origem, destino, auxiliar} = {A, B, C}
Garante: Gera uma seqüência de movimentos para a
transferência de uma pilha de n discos em origem para
destino, de tamanho 2n − 1.
= 1
{i, j, k} = {1, 2, 3}.
a estrutura exibida na gura 3.
Finalmente, obtemos
se n
onde
então
mova o disco no topo do pino origem para destino
grafo de congurações
Prova.
1.
Claramente, a proposição é válida para
n=
Suponhamos, por indução, que a proposição seja
válida para todo número de discos menor que um
n > 1.
Hn .
certo
Consideremos dois vértices distintos
Sabemos que
mover (n - 1, origem, auxiliar, destino)
é estabelecida pela propo-
Proposição 3.1. Para quaisquer vértices u e v em
V (Hn ), se cu e cv são as congurações correspondentes, então {u, v} ∈ E(Hn ) se, e somente se, existir
um movimento (válido) que leve cu a cv .
em
senão
Hn
sição a seguir.
i
Hn−1
é obtido de
Hn−1
pela adi-
ção do maior disco à base da pilha sobre o pino
mova o disco no topo do pino origem para destino
i.
mover (n - 1, auxiliar, destino, origem)
Conseqüentemente, se as congurações diferirem
pela posição de algum dos
m se
n − 1 menores discos, pela
hipótese de indução a proposição será válida.
Por
outro lado, se as congurações diferirem pela posição do maior disco, estarão ligadas se, e somente se,
3.1 Resultados
os
Essa seção aborda o problema tradicional da Torre
de Hanói, para
3 pinos e n discos.
Wood [8] discute o
caso em que as congurações inicial e nal são quaisquer. Xuemiao [9] introduz (em 1986) o termo
fos de Hanói,
gra-
formalizando a abordagem de Scorer,
Grundy e Smith [5] (1944), e demonstra que há no
máximo duas seqüências distintas de comprimento
mínimo entre duas congurações.
Uma expressão
para a determinação da quantidade de tais seqüências para um dado par de congurações expressa
em termos da seqüência diatômica de Stern é obtida por Hinz e outros [4]. A seguir, listamos alguns
resultados desses artigos. Para isso serão necessárias
algumas denições.
Começamos pela denição dos grafos de Hanói
Hn ,
n−1
menores discos estiverem no mesmo pino
em ambas as congurações, o que é garantido por
construção.
É importante notar que uma condição necessária
(mas não suciente) para que duas congurações tenham respectivos vértices
vizinhos em Hn é que estes
diram em apenas uma coordenada. Em outras palavras, deve-se ter apenas um disco em uma posição
diferente, restando os demais na mesma posição em
ambas as congurações.
Um
caminho do nó s ao nó t em Hn é uma seqüên-
(v0 , v1 , . . . , vm ), com v0 = s e vm = t,
{vi , vi+1 } ∈ E(Hn ), 0 ≤ i < m. Um caminho de s a t é dito mínimo se não houver outro
caminho (w0 , w1 , . . . , wl ) de s a t com l < m. Neste
caso, dizemos que a distância entre s e t, denotada
cia de vértices
tal que
que se tornaram uma ferramenta muito popular no
estudo da Torre de Hanói e suas variantes.
(1)
Os grafos de Hanói são denidos por Xuemiao,
recursivamente, da seguinte forma:
H1
(gura 2) é
(1),
(3).
1
Para n > 1, Hn consiste de três subgrafos, Hn ,
2
3
i
Hn , e Hn . Cada Hn é obtido de Hn−1 pela adição
do prexo i aos rótulos de seus vértices, e de três
o grafo completo com três vértices, com rótulos
(2),
e
arestas conectando os pares de vértices
(i, k, . . . , k)
e
(3)
Figura 2.
(j, k, . . . , k),
109
(2)
Grafo de congurações H1
Lema
Sn1
3.5 (Xuemiao)
arbitrários
u
v
e
.
em
Para todo
dist(u, v) ≤ 2n − 1.
Hn1
Prova.
Provamos o resultado por indução em
dist(u, v) = 1 = 21 − 1
Hn3
Hn2
Suponha agora que
Sn3
Sn2
dist(u, v),
é
cu e cv correspondentes
u e v . Vamos considerar dois casos.
Se o disco n está no mesmo pino em cu e em cv ,
digamos, pino j , então temos que u e v estão no
j
subgrafo Hn que é isomorfo a Hn−1 . Portanto
m.
de distância:
dist(u, v) = dist(u, v),
a
Lema
respondentes a
A distância
dist entre vértices em Hn , sa-
(i)
indicam, respectivamente, os vértices cor-
u, v, w ∈ V (Hn ):
u
e
v
em
Hn−1 .
dist(u, v) ≤ 2n−1 − 1,
dist(u, v) ≥ 0 sendo
u = v,
que
dist(u, v) = 0
se e
somente se
(ii)
uev
Pela hipótese de indução, isso implica
tisfaz as seguintes propriedades, para quaisquer vértices
n. Vamos mosn discos.
Considere as congurações
onde
.
e que o lema é válido
aos vértices
função é realmente uma métrica.
3.2
n > 1
trar que o lema é válido também para
O lema a seguir, bem conhecido em teoria dos gra-
dist
n.
∀u 6= v ∈ V (H1 ).
para número de discos menor do que
Estrutura recursiva de Hn
fos, justica chamar a função
(4)
n = 1,
Para
Figura 3.
n > 0 e dois vértices
Hn
o que prova o lema para este caso.
Suponha agora que o disco
rentes em
dist(u, v) = dist(v, u),
cu
e
cv .
n
está em torres dife-
Sem perda de generalidade, pode-
n está no pino 1 em cu e no
2 em cv . Considere um caminho de u a v usando
a aresta e = {w1 , w2 }, onde w1 = (1, 3, 3, . . . , 3) e
w2 = (2, 3, 3, . . . , 3). Note que o disco n está no
mesmo pino em cu e na conguração correspondente
a w1 e que também o disco n está no mesmo pino
em cv e na conguração correspondente ao vértice
w2 . Usando o argumento do caso anterior obtemos
mos assumir que o disco
(iii)
dist(u, v) ≤ dist(u, w) + dist(w, v).
pino
Segue um resultado básico da Torre de Hanói
(equação (2)), reescrito em termos dos vértices de
Hn .
Lema
.
3.3
Para todo
n > 0,
e
i 6= j, (1 ≤ i, j ≤ 3),
dist(Sni , Snj ) = 2n − 1.
(3)
que
i
i
Denotemos H n o grafo obtido de Hn quando apagamos o prexo i de cada um de seus vértices, e, se
u é um vértice em Hni , então u será usado para dei
notar o vértice em H n obtido de u pela exclusão do
i
prexo. Então H n é Hn−1 . E temos
Lema
3.4 (Xuemiao)
cem a
então
1.
Hni ,
.
Se dois vértices
u
e
v
u a v pode ser obtido
u a v adicionando-se
u
a
v
pode ser obtido
de um caminho mínimo de
u
a
v
i
A propriedade seguinte é bem conhecida para gra3.6. Seja G um grafo. Para quaisquer vértices
u, w e v em V (G), w está em um caminho mínimo
de u para v se e só se
i a cada um dos vértices que o compõe;
3. todo caminho mínimo de
2n−1 − 1 + 1 + 2n−1 − 1
2n − 1.
Lema
e
prexo
≤
=
fos.
de um caminho mínimo de
o prexo
dist(u, w1 ) + dist(w1 , w2 )
+dist(w2 , v)
perten-
dist(u, v) = dist(u, v);
2. todo caminho mínimo de
dist(u, v) ≤
retirando-se o
a cada um dos vértices que o compõe.
dist(u, v) = dist(u, w) + dist(w, v).
Lema
3.7 (Xuemiao)
n > 0.
Então, para qualquer nó
.
(5)
{i, j, k} = {1, 2, 3} e
u em Hnj , cada camii
nho mínimo de Sn a u contém os vértices (i, k, . . . , k)
e (j, k, . . . , k).
110
Sejam
o caminho de
Prova.
Por simetria, basta provar o lema para i = 1
j = 3. Isto é, qualquer caminho mínimo de Sn1
a u precisa conter os vértices v1 = (1, 2, 2, . . . , 2)
e v2 = (3, 2, 2, . . . , 2). Ou seja, o disco n é movimento somente uma vez (do pino 1 para o pino 3).
e
Por contradição, suponha que não.
Então, para o
n terminar no pino 3, ele precisa passar pelo
2. Isso corresponde ao caminho mínimo conter
os vértices w1 = (1, 3, 3, . . . , 3) e w2 = (2, 3, 3, . . . , 3)
para mover o disco n do pino 1 ao pino 2 e
w3 = (2, 1, 1, . . . , 1) e w4 = (3, 1, 1, . . . , 1) para
mover o disco n do pino 2 ao pino 3.
disco
pino
Assim, pelo lema 3.6
dist(Sn1 , u)
≥
+ dist(w1 , w2 )
+dist(w2 , w3 ) + dist(w3 , w4 )
+dist(w4 , u)
≥ dist(Sn1 , w1 ) + 1 + dist(w2 , w3 ) + 1
= 2n−1 + 2n−1 pelo lema 3.3
= 2n ,
Temos agora condição de demonstrar um dos teoremas centrais de [9].
Teorema
em
Hn .
3.8 (Xuemiao)
.
Sejam
Então, para todo
(i) o caminho mínimo de
(ii)
dist(Sni , u) pode
paço O(n).
Prova.
para
n > 0 e u um vértice
i
Sni
a
u
é único; e
ser calculada em tempo e es-
vale a recorrência:
dist(Sn1 , u)
/ V (Hn1 )
2n−1 + dist(w2 , u), se u ∈
1
dist(Sn−1 , u), se u ∈ V (Hn1 ).
=
Aplicando a recorrência acima
n−1
vezes, e usando
diretamente a distância entre vértices de
tância entre
Sn1
e
u
H1 ,
a dis-
é determinada. Note que a com-
putação denida pela recorrência pode ser feita em
tempo e espaço
1.
O(n),
o que conrma (ii).
3.9 (Xuemiao)
quer vértices
u
e
v
.
Para todo
n ≥ 0,
e quais-
Hn
em
dist(u, v) pode ser calculada em espaço e tempo
O(n), e
2. há, no máximo, dois caminhos de comprimento
mínimo entre
u
v.
e
V (Hnj ) para algum j , então
o problema pode ser estudado em Hn−1 . Portanto,
j
i
vamos supor que u ∈ V (Hn ) e v ∈ V (Hn ) para i 6= j .
Novamente por simetria, pode-se supor que u está
1
3
em V (Hn ) e v em V (Hn ). Note que num caminho
mínimo o disco n é movido diretamente do pino 1
ao pino 3, ou pe movido do pino 1 ao pino 2 e
do pino 2 ao pino 3. No primeiro caso, os vértices v1 = (1, 2, 2, . . . , 2) e v2 = (3, 2, 2, . . . , 2) estão
Se
uev
estão em
no caminho, e a distância percorrida é
d1
Por simetria, basta provarmos o teorema
Vamos mostrar, por indução em
(i).
A propriedade vale para o grafo
Agora, para um
(i)
dist(Sn1 , w1 ) = 2n−1 − 1,
1
n−1
então dist(Sn , w2 ) = 2
. Usando a argumentação
dos parágrafos anteriores, temos que, para n > 1,
i = 1.
priedade
Com isso, a propriedade
Como, pelo lema 3.3,
Prova.
o que contradiz o lema 3.5.
u.
a
está provada.
Teorema
dist(Sn1 , w1 )
Sn1
n > 1,
n, que vale a proH1 .
vamos assumir que a pro-
priedade vale para valores menores que
n
e conside-
rar dois casos.
1
1
O vértice u está em Hn . Como S n =
1
Sn−1
, pela hipótese de indução o caminho mínimo de
1
Sn−1
a u é único, o mesmo valendo para o caminho
1
de Sn a u.
j
O vértice u está em algum Hn (j 6= 1).
Pelo lema 3.7, todo caminho mínimo de
Sn
a
u
e
k 6= j.
con-
tém os vértices
dist(u, v1) + dist(v1 , v2 ) + dist(v2 , v)
=
dist(u, v1) + 1 + dist(v2 , v).
w1 = (1, 3, 3, . . . , 3),
w2 = (2, 3, 3, . . . , 3), w3 = (2, 1, 1, . . . , 1) e (w4 =
(3, 1, 1, . . . , 1) estão no caminho e a distância per-
No segundo caso, os vértices
corrida, usando lema 3.3, é
d2
=
Caso 1.
Caso 2.
=
dist(u, w1) + dist(w1 , w2 ) + dist(w2 , w3 )
+dist(w3 , w4 ) + dist(w4 , v)
=
dist(u, w1) + 1 + 2n−1 − 1 + 1 + dist(w4 , v)
=
dist(u, w1) + dist(w4 , v) + 2n−1 + 1.
d1 e d2 .
dist(u, v) basta calcular dist(u, v1 ), dist(v2 , v), dist(u, w1 ) e dist(w4 , v),
A distância entre
u
e
v
será o mínimo entre
Isso signica que para calcular
o que pode, segundo o teorema 3.8, ser feito em
w1 = (1, k, . . . , k)
e
w2 = (j, k, . . . , k), k 6= 1
tempo e espaço
O(n),
o que prova (1).
Note que, também pelo teorema 3.8, cada um dos
Então ele pode ser dividido em duas partes: a primeira é um caminho mínimo de
um caminho mínimo de
w2
a
u.
Sn1
a
w1
e a segunda
Pelo mesmo raciocí-
nio do Caso 1 ambos são únicos e o mesmo vale para
4 distâncias mend1 e d2 denem ca-
caminhos mínimos que denem as
cionadas são únicos e, portanto,
minhos únicos. Portanto, ou o caminho de comprimento mínimo entre
111
uev
é único quando
d1 6= d2
Figura 5.
Figura 4.
ou
d1 = d2
Variante cíclica: n = 1, p = 6
Grafo de congurações H4
e existem dois caminhos de compri-
mento mínimo entre
u
e
v,
o que prova (2).
Figura 6.
4. Grafos de Hanói
Variante linha com n = 1, p = 6
Como já foi mencionado, as variantes abordadas
neste artigo derivam da mudança de dois parâmetros
da Hanói original,
1. número de pinos; e
2. restrições ao movimento entre certos pares de
pinos.
Dito isto, ao empregarmos no que segue estaremos
sempre nos referindo a variantes dessa forma.
Em
geral, para o estudo dessas variantes são considerados com freqüencia dois grafos,
G e H , assunto dessa
Figura 7.
Variante estrela: n = 1, p = 6
seção.
O
H,
grafo das congurações,
que denotaremos por
é tal que seus vértices correspondem a congu-
u, v con{u, v} ∈ E(H) se, e somente se, é possível,
de u chegar a v com um movimento legal.
rações da variante em questão, e, dadas
gurações
a partir
Quando as regras de movimentação não permitem
simetria de movimentos, os grafos considerados são
grafos
orientados, com arcos no lugar de arestas.
As
guras 2 e 4 exemplicam esse conceito.
Outro grafo comumente utilizado para descrever
uma variante com essas características consiste em
um mapa dos possíveis movimentos de discos entre
G. Cada vértice em G corresponde a um pino, e (a, b) ∈ E(G) se, e só se, existir
a possibilidade de mover um disco do topo do pino a
para o topo do pino b. As guras 5 a 8 exibem esse
pinos. Denotá-lo-emos
tipo de grafos.
112
Figura 8.
Variante estendida: n = 1, p = 6
Lema
.
4.1
Sejam
discussão acima, e
G um
Hn o
grafo denido conforme a
2. pelas arestas
grafo das congurações de
uma certa variante para uma quantidade
{(i, c1 , c2 , . . . , cn ) , (j, c1 , c2 , . . . , cn ))}
n de discos,
então
tais que
G = H1 .
Prova.
(6)
Basta observar que a única restrição do mo-
vimento do disco 1 entre dois pinos
(a, b) ∈ G,
a
e
donde cada vértice e aresta de
b é que
H1 pos-
sui um correspondente vértice ou aresta, respectivamente, em
G.
Uma pergunta que surge naturalmente da observação dos grafos
G é sob que condições pode-se garantir
que o problema terá solução?
Mais especicamente,
ci 6= i, ci 6= j
e
{i, j} ∈ E(G).
Ressaltamos que, para o caso de uma variante orientada, substitui-se a noção de aresta por arco. Por
brevidade, no restante da seção trataremos apenas
de variantes não-orientadas, mas a abordagem para
o caso orientado é a mesma (no âmbito da contagem), substituindo-se apenas
Lema
.
4.2
Seja
Hn
E(G)
A(G).
o grafo de congurações de uma
variante da Torre de Hanói. Se
an
por
an = |E(Hn )|,
então
satisfaz a recursão
an = pan−1 + a1 (p − 2)n−1
dado um grafo que mapeia as movimentações possí-
(8)
veis para o menor disco, quais as constrições necessárias para que seja possível, partindo de qualquer
conguração válida com
tado qualquer?
n
discos, chegar a outro es-
Prova.
Uma condição suciente para que
isso seja possível é
G
Desenvolvendo a expressão, obtemos
ser fortemente conexo e pos-
an
3 vértices (pode possuir 2 vértices caso
máximo 1 disco envolvido no problema).
suir ao menos
haja no
=
=
=
4.1 Contagem de vértices
Outra característica comum aos grafos
H
dessas va-
riantes é o fato de seu número de vértices
|H|,
|H| = pn .
=
ser
p
=
possíveis esco-
lhas de pinos em que colocar cada um dos discos, e
=
de, uma vez determinado um conjunto de discos, haver exatamente uma maneira de empilhá-los em um
dado pino, já que todos os os discos têm tamanhos
pan−1 + a1 (p − 2)n−1 n−2
p pan−2 + a1 (p − 2)
+ a1 (p − 2)n−1
n−3
p2 pan−3 + a1 (p − 2)
+
n−1
n−2
+ a1 (p − 2)
+ p (p − 2)
n−1
p3 an−3 + a1 (p − 2)
+
n−2
n−3
2
+ p (p − 2)
+ p (p − 2)
···
(7)
O que decorre do fato de haver
Essa recursão deriva diretamente da constru-
ção acima descrita.
n−1
n−2
pn−1 a1 + a1 (p − 2)
+ p (p − 2)
+ · · · + pn−2 (p − 2)
Pn−1
a1 i=0 pi (p − 2)n−1−i .
Resolvendo o somatório, chegamos a uma expressão concisa para o número de arestas em
distintos.
an = a1
4.2 Contagem de arestas
A denição dos grafos de Hanói sugere uma abordagem recursiva para a contagem das arestas de uma
variante. Consideremos o grafo de congurações de
n discos e p pinos, deEsse grafo (Hn ) pode ser
uma determinada variante com
notado
Hn , e seja G = H1 .
construído recursivamente, por meio de uma generalização da construção do grafo de Hanói proposto
Hn
é gerado recursivamente a partir de
da seguinte forma:
pn − (p − 2)n
2
(9)
5. Variantes
Nesta seção apresentamos a denição de algumas variantes conhecidas da Torre de Hanói.
5.1 Variante estendida
Uma das primeiras variantes do quebra-cabeça, uma
por Xuemiao [9].
O grafo
Hn .
H1
é (isomorfo a)
vértices numerados de 1 a
p;
e
Hn
G,
G
e possui os
é o grafo formado
extensão para quatro pinos conhecida como
Puzzle
Reeve's
foi proposta por Henry Dudeney em [1]. O
problema da obtenção de um algorimo que realize a
tarefa ótimamente, isto é, com o menor número de
p
1
2
Hn−1
, Hn−1
, . . . , Hn−1
,
i
cada Hn−1 é obtido a partir de Hn−1
ção do prexo i a seus vértices, e
1. pelos
grafos
em
que
pela adi-
movimentos possível, está em aberto, embora haja
uma
solução presumidamente ótima
comprovada
ótima para até 20 discos (conforme [6]).
113
5.2 Variante circular
de
A variante circular foi proposta por Scorer, Grundy
e Smith em [5]. Consiste em dispor os pinos em um
ciclo e permitir apenas movimentos em um sentido
digamos, horário. Uma análise do que ocorre para
um número arbitrário de pinos e discos é feita por
Berend e Sapir [3, 7], que obtêm uma série de resultados interessantes. O problema também foi alvo de
estudos em [10, 12, 14] entre outros, sem que tenha
sido obtida a resposta para o problema com mais de
três pinos.
Nesta versão, os vértices
vi , 1 ≤ i ≤ p
são dispostos
em uma la, e somente são permitidos movimentos
vj
mente se
H1
i
Hn−1
é conexo se e so-
o for, haverá um caminho entre qual-
Hn , quer estejam ou não no
i
Hn−1
, se e somente se H(1, p) for fortemente
quer par de vértices em
mesmo
conexo.
7. Agradecimentos
Este trabalho teve apoio nanceiro da FAPESP
(Fundação de Amparo à Pesquisa do Estado de São
Referências
[1] H. E. Dudeney,
vj+1 , 1 ≤ j < p.
e
Na variante estrela, São dados
[2] S. Klavºar and U. Milutinovi¢ and C. Petr, Combinatorics
of topmost discs of multi-peg Tower of Hanoi problem,
2001.
p pinos, numerados de
1 a p, dispostos em um círculo, e ainda outro no centro deste, denotado C. Nenhum disco pode jamais
ser movido diretamente entre os pinos numerados,
isto é, podem apenas partir de C para algum outro
pino qualquer ou de um destes para C.
Stockmeyer
[12]
estudou-a no caso
introduziu
p = 3.
The Canterbury Puzzles (and Other Cu-
, E.P. Dutton, 1908.
rious Problems)
5.4 Variante estrela
essa
Quando
variante,
p = 2,
e
a vari-
ante é idêntica à variante linha (subseção 5.3) com
p = 3,
se, e só se,H1 for fortemente conexo. Como,
Paulo), no processo de referência 2007/05285-2.
5.3 Variante linha
entre
Hn
or indução, cada um dos
e foi estudada em [14].
6. Condições de solubilidade
É interessante considerar os fatores que determinam
[3] D. Berend and A. Sapir, The cyclic multi-peg Tower
Hanoi, ACM Trans. Algorithms 2 (2006), 297317.
of
[4] A. M. Hinz and S. Klavºar and U. Milutinovi¢ and D. Parisse and C. Petr, Metric properties of the Tower of Hanoi
graphs and Stern's diatomic sequence, 2005.
[5] R. S. Scorer and P. M. Grundy and C. A. B. Smith,
binary games, MG 28 (1944), 96-103.
[6] B. Houston and H. Masun, Explorations in 4-peg
of Hanoi, Technical Report TR-04-10 (2004).
Some
Tower
[7] D. Berend and A. Sapir, The diameter of Hanoi
graphs, Inf. Process. Lett. 98 (2006), no. 2, 7985, DOI
http://dx.doi.org/10.1016/j.ipl.2005.12.004.
[8] D. Wood, Adjudicating a towers of hanoi contest, International Journal of Computer Mathematics 14 (1983), 199
207.
a existência de uma solução para o quebra-cabeça.
[9] L. Xuemiao, Towers of hanoi graphs, International Journal of Computer Mathematics 19 (1986), 2338.
Apesar de, originalmente, serem apenas considera-
[10] P. K. Stockmeyer,
das as seqüências de movimentos de mínimo comprimento entre congurações simples, o problema (por
[11]
vezes chamado de
[12]
problema geral
da Torre de Hanói)
em que as congurações inicial e nal são quaisquer
também foi alvo de considerável atenção [8, 9].
Avaliamos a seguir as condições de existência de
soluções para o problema geral das variantes.
Denição 1. Diremos que um problema é geralmente
solúvel se, para qualquer par ordenado (a, b) de congurações existir uma seqüência de movimentos válidos que leve
Lema
H(n, p)
.
6.1
a
a
b.
Uma
variante
com
grafo
ções
, 2005".
four-post Tower of Hanoi
Forbidden Moves
,
[15] É. Lucas, Récréations Mathématiques, Vol. III, GauthierVillars et Fils (Paris), 1893.
[16] D. G. Poole,
H(1, p)
(subseção 4.2) que existe um ca-
minho entre cada par de subgrafos
, Variations on the
, CN 102 (1994), 3-12.
[14] A. Sapir, The Tower of Hanoi with
Comput. J. 47 (2004), no. 1, 20-24.
Decorre da construção do grafo de congura-
H(n, p) = Hn
.
The Tower of Hanoi: A Bibliography
[13] J. S. Frame, Solution to Advanced Problem 3918, American Mathematical Monthly 48 (1941), no. 3, 216219.
for fortemente conexo.
Prova.
,
puzzle
associado
é geralmente solúvel se e somente se
The Average Distance between Nodes
in the Cyclic Tower of Hanoi Digraph
i
Hn−1
,1≤i≤p
114
The Towers and Triangles of Professor
Claus (or, Pascal Knows Hanoi)
67 (1994), no. 5, 323-344.
, Mathematics Magazine