Uma Torre de Hanoi dupla contém 2 n discos de n tamanhos diferentes, dois de cada tamanho. As regras de movimentação dos discos são as mesmas: um disco de cada vez e nunca colocar um disco sobre outro menor.
\theta
(a) Quantos movimentos são necessários para transferir a torre dupla de um eixo para outro, supondo que discos de mesmo tamanho sejam idênticos? Monte e resolva a relação de recorrência apropriada.
(b) Suponha agora que discos de mesmo tamanho são pintados com cores diferentes e o objetivo é transferir a torre mantendo a ordem de cores. (Dica: utilize os resultados do item anterior.)

Passo 1

Primeiro vou deixar bem claro o que o enunciado pede e quais informações estão dadas.
  • Temos uma “torre dupla” composta por 2n discos, com n tamanhos distintos e exatamente dois discos de cada tamanho empilhados em ordem decrescente (maiores embaixo).
  • As regras são as usuais da Torre de Hanoi: mover um disco por vez e nunca colocar um disco maior sobre um disco menor. Discos de mesmo tamanho podem ser colocados uns sobre os outros (já que não são menores).
  • O enunciado faz duas perguntas:
    (a) Supondo que discos de mesmo tamanho são idênticos (indistinguíveis), quantos movimentos mínimos são necessários para transferir toda a torre de um pino a outro? Pede montar e resolver a relação de recorrência apropriada.
    (b) Agora supondo que os dois discos de cada tamanho são pintados com cores diferentes (são distinguíveis) e que, além de transferir toda a torre, o objetivo é manter a ordem das cores (isto é, para cada par de mesmo tamanho a ordem relativa vertical entre as duas cores no final deve ser a mesma que havia no início). Usar o resultado do item (a).
Listei tudo o que está dado e o que é pedido. A partir do Passo 2 começo a resolver de fato.

Passo 2

Entendimento básico e ideia do método (sem ainda desenvolver contas). Vou trabalhar com uma abordagem recursiva, que é a maneira padrão de raciocinar nesses problemas:
  • Para esse tipo de problema a estratégia natural é: para mover todos os discos de tamanho \le n (isto é, todos os 2n discos) do pino origem A para o pino destino C usando B como auxiliar, a manobra costuma dividir-se em: mover os discos menores (todos os discos de tamanhos 1,\dots,n-1) para um pino auxiliar, depois mover os discos de maior tamanho, depois recolocar os menores sobre o destino. A diferença entre os dois itens do enunciado está em como tratamos o par de discos de cada tamanho: se são idênticos (item a) ou distinguíveis e com ordem a preservar (item b).
  • Vou formalizar essas ideias em uma relação de recorrência e resolver essa recorrência de maneira clara e didática.
Agora sim, começo o desenvolvimento e as contas explicadas passo a passo.

Passo 3

Resolução do item (a): montar a recorrência.
Observação sobre a configuração inicial e a operação necessária:
  • Para mover a torre inteira com os 2n discos (dois de cada tamanho 1,2,\dots,n) do pino A para o pino C, em todo o momento a regra vale: não se pode colocar um disco maior sobre um disco menor; porém discos de mesmo tamanho podem ser colocados sobre um igual (pois não são menores).
  • A estratégia recursiva natural é:
    1. Primeiro mover todos os discos de tamanhos 1,\dots,n-1 (ou seja, os 2(n-1) discos menores) do pino A para o pino B. Se chamarmos T(k) o número mínimo de movimentos para transferir a torre dupla de parâmetros k (isto é, 2k discos, dois de cada tamanho até k), esse passo toma T(n-1) movimentos.
    2. Depois, com os menores fora do caminho, os dois discos de tamanho n (os maiores) estão agora acessíveis no topo de A. Como os discos de mesmo tamanho são idênticos, posso movê-los para o destino C em dois movimentos consecutivos: mover o disco que está mais em cima (o de tamanho n) para C e depois o outro disco de tamanho n para C. Colocar um disco de tamanho n sobre outro do mesmo tamanho é permitido. Esse passo usa exatamente 2 movimentos.
    3. Finalmente, mover os 2(n-1) discos menores que estavam em B para C sobre os discos de tamanho n; isso custa novamente T(n-1) movimentos.
  • Portanto a relação de recorrência é
T(n)=2\,T(n-1)+2,
com condição inicial (caso base) quando n=1: há dois discos de mesmo tamanho, empilhados; para transferi-los, basta movê-los um a um para o destino, totalizando T(1)=2 movimentos.

Passo 4

Resolver a recorrência do item (a) e interpretar pedagogicamente.
Temos a recorrência linear de primeira ordem não-homogênea
T(n)=2\,T(n-1)+2,\qquad T(1)=2.
Vou resolver passo a passo:
  • Primeiro resolvo a parte homogênea T_h(n)=2\,T_h(n-1). Isso dá T_h(n)=C\cdot 2^{\,n-1} (constante C determinada por condição inicial).
  • Agora procuro uma solução particular constante T_p(n)=t. Substituindo em t=2t+2 obtém-se t=-2.
  • Assim a solução geral é
T(n)=C\cdot 2^{\,n-1}-2.
  • Uso T(1)=2 para achar C:
2 = C\cdot 2^{0}-2 \quad\Rightarrow\quad 2 = C-2 \quad\Rightarrow\quad C=4.
  • Portanto
T(n)=4\cdot 2^{\,n-1}-2 = 2^{\,n+1}-2.
Interpretação intuitiva rápida: cresce exponencialmente com n; para n=1 2, para n=2 6, para n=3 14 etc. A forma 2^{n+1}-2 é explícita e fácil de memorizar.

Passo 5

Resumo didático do item (a) (como você usaria na prova):
  • Monta-se a recursão pensando em “retirar” todos os discos menores para um pino auxiliar, mover os dois maiores (2 movimentos porque são iguais) e recolocar os menores. Isso motiva T(n)=2T(n-1)+2.
  • Resolve-se a recorrência (como fiz acima) e obtém-se T(n)=2^{\,n+1}-2.
  • Exemplo numérico: para n=2 (quatro discos no total) são T(2)=2^{3}-2=6 movimentos mínimos.
Agora vou ao item (b), explicando com calma a diferença conceitual e a solução.

Passo 6

Entendendo o item (b) e estratégia geral.
  • Agora os dois discos de cada tamanho são distinguíveis (por cores) e o enunciado exige que, além de transferir toda a torre, a ordem de cores de cada par seja preservada. Isso significa: se, no pino inicial A, para um determinado tamanho k o disco da cor X está acima do disco da cor Y, no pino final C o disco X deverá continuar acima de Y. Em outras palavras, não se pode trocar a ordem vertical dos dois discos de mesmo tamanho.
  • No item (a), quando os discos do mesmo tamanho são idênticos, mover os dois discos daquele nível para o destino em dois movimentos não impõe restrição de ordem; porém agora a ordem importa: mover o disco que estava por cima primeiro para o destino e em seguida mover o de baixo para o destino inverteria a ordem relativa desses dois discos (porque o segundo viria a ficar sobre o primeiro). Para preservar a ordem, é necessário um procedimento que coloque os dois discos no destino na mesma ordem relativa em que estavam no início.
  • Consequentemente, para cada par de discos de tamanho k que na origem está configurado (cima = cor A, baixo = cor B), a manobra que os coloca no destino na mesma ordem requer uma pequena sequência extra: é preciso retirar temporariamente o disco de cima para algum pino auxiliar, mover o disco de baixo para o destino e então recolocar o disco de cima sobre ele — essa sequência de recolocação do par (quando feita sem outros discos atrapalhando) leva 3 movimentos em vez de 2.
  • Porém, na presença de todos os outros discos (os menores), ganhar espaço e peões livres exige mover esses menores várias vezes. Por isso a conta global resulta numa recorrência diferente da do item (a) e que incorpora as operações de “criar espaço” e “recolocar” os menores várias vezes.
Vou agora montar a recorrência adequada aproveitando o raciocínio acima e o resultado do item (a).

Passo 7

Montagem da recorrência para o item (b) (passo a passo explicando cada termo).
Denoto por U(n) o número mínimo de movimentos necessários quando os discos de cada tamanho são distinguíveis e a ordem das cores deve ser preservada.
Raciocínio recursivo (idéia central):
  • Para lidar com o par de tamanho n (os dois maiores) mantendo a ordem, não basta simplesmente mover os dois discos em 2 movimentos como no item (a); é preciso, na prática, efetuar uma operação que equivale a “trocar” a ordem de colocação ou então usar um pino auxiliar para temporariamente armazenar um dos dois discos de tamanho n enquanto se posiciona o outro. Essa manobra, por si só, exige 3 movimentos diretos para os próprios dois discos de tamanho n (quando não há menores no meio): retirar o de cima para um pino auxiliar (1), mover o de baixo para o destino (1), recolocar o de cima sobre ele no destino (1) — total 3.
  • Porém, para poder armazenar temporariamente o disco superior de tamanho n num pino auxiliar, é necessário que esse pino auxiliar esteja livre de discos menores; por isso os 2(n-1) discos menores precisam ser deslocados várias vezes durante o processo de ordenação do par de tamanho n.
  • Um método eficiente (que se mostra ótimo por raciocínio recursivo) é o seguinte procedimento para mover todos os 2n discos preservando todas as ordens de cor:
    1. Mover os 2(n-1) discos menores de A para um pino (digamos B) obedecendo à regra de preservação de ordem — isso custa U(n-1).
    2. Mover o disco de cima do par de tamanho n para o pino destino auxiliar (uma operação que, devido à presença dos menores em B, exige que se libere espaço — a forma mais econômica de fazer isso, em recursão, equivale a movimentos adicionais de custo T(n-1) ou a mover os menores entre pinos; no efeito global isso equivale a incorrer em duas transferências dos menores).
    3. Executar os 3 movimentos que colocam os dois discos de tamanho n no pino destino na ordem correta.
    4. Recolocar os 2(n-1) discos sobre o destino preservando ordem — outro custo U(n-1).
  • Ao contabilizar as transferências necessárias dos menores para conseguir um pino temporário livre e depois recolocá-los, chega-se à recorrência (que é a forma “canônica” para este problema): cada nível exige basicamente três transferências completas da pilha menor (do tipo que custa U(n-1) em preservação de ordem), mais 3 movimentos para arrumar o par de tamanho n. Assim obtemos
U(n)=3\,U(n-1)+3,\qquad U(1)=3.
Explicação dos termos:
  • O termo 3\,U(n-1) representa: mover a pilha menor para liberar espaço, depois movê-la novamente para fazer a manobra intermediária e, por fim, recolocá-la sobre o destino (três transferências recursivas da pilha de tamanho n-1, cada uma custando U(n-1)).
  • O +3 cobre os três movimentos estritos necessários para colocar os dois discos de maior tamanho no destino mantendo a ordem (guardar o de cima em peg auxiliar, mover o de baixo para o destino, recolocar o de cima sobre ele).
Observação pedagógica: esta recorrência pode ser entendida como uma versão “triplicada” da recorrência do caso idêntico, porque para preservar a ordem precisa-se, em essência, deslocar a pilha menor mais vezes para criar espaço de armazenagem temporária.

Passo 8

Resolver a recorrência do item (b).
A recorrência é
U(n)=3\,U(n-1)+3,\qquad U(1)=3.
Resolver de forma direta:
  • Parte homogênea: U_h(n)=3\,U_h(n-1) tem solução U_h(n)=C\cdot 3^{\,n-1}.
  • Procuro solução particular constante U_p(n)=u. Substituindo: u=3u+3 u=-\tfrac{3}{2}. Para evitar frações podemos preferir outro método, mas continuarei algebraicamente.
  • Assim solução geral:
U(n)=C\cdot 3^{\,n-1}-\tfrac{3}{2}.
  • Use U(1)=3 para achar C:
3 = C\cdot 3^{0}-\tfrac{3}{2} \quad\Rightarrow\quad 3 = C - \tfrac{3}{2} \quad\Rightarrow\quad C = \tfrac{9}{2}.
  • Então
U(n)=\tfrac{9}{2}\,3^{\,n-1}-\tfrac{3}{2}=\tfrac{3}{2}\bigl(3^{\,n}-1\bigr).
  • Podemos reescrever de forma concreta:
U(n)=\tfrac{3}{2}\bigl(3^{\,n}-1\bigr).
  • Multiplicando por 2 e simplificando, outra forma útil é
U(n)=\frac{3^{\,n+1}-3}{2}.
Verificação rápida de pequenos n:
  • Para n=1: U(1)=\tfrac{3}{2}(3^{1}-1)=\tfrac{3}{2}\cdot 2=3, compatível com a observação direta (dois discos de mesmo tamanho, mas distinguíveis — para preservar a ordem é preciso 3 movimentos).
  • Para n=2: U(2)=\tfrac{3}{2}(9-1)=\tfrac{3}{2}\cdot 8=12. (Isso dá um valor plausível entre o caso idêntico T(2)=6 e o caso todos distintos 2^{4}-1=15.)

Passo 9

Interpretação e como usar isso na prova (dicas de memorização/checagem).
  • Item (a): a relação simples T(n)=2T(n-1)+2 resolve-se diretamente e dá T(n)=2^{\,n+1}-2. Lembre-se: “duas transferências dos menores + dois movimentos dos dois maiores”.
  • Item (b): a necessidade de preservar a ordem entre os dois discos de cada tamanho força repetir as transferências da pilha menor mais vezes para liberar e reutilizar um pino auxiliar; isso leva à recorrência U(n)=3U(n-1)+3 e à solução fechada U(n)=\tfrac{3}{2}(3^{n}-1)=\dfrac{3^{\,n+1}-3}{2}. Na prova, explique por que são três transferências da pilha menor (liberar, reorganizar, recolocar) e por que o par maior exige 3 movimentos, e então resolva a recorrência.

Resposta

(a) T(n)=2^{\,n+1}-2
(b) U(n)=\dfrac{3^{\,n+1}-3}{2}=\dfrac{3}{2}\bigl(3^{n}-1\bigr)

Exercícios relacionados