Obtenha uma relação de recorrência para o problema das Torres de Hanói apresentado no Exercício 1.1.20.

Passo 1

Beleza, vamos lá! O exercício pede para a gente obter uma relação de recorrência para o problema das Torres de Hanói apresentado no Exercício 1.1.20. Isso significa que vamos criar uma fórmula que relaciona o número de movimentos necessários para resolver o quebra-cabeça com o número de discos envolvidos. Para isso, vamos precisar entender o que é uma relação de recorrência e como ela se aplica ao problema das Torres de Hanói.

Passo 2

Primeiro, vamos lembrar do que são as Torres de Hanói. É um jogo de quebra-cabeça que consiste em três hastes e um número de discos de tamanhos diferentes que podem deslizar sobre qualquer haste. O objetivo é mover toda a pilha de discos para outra haste, seguindo três regras:
  1. Apenas um disco pode ser movido por vez.
  2. Cada movimento consiste em pegar o disco mais no topo de uma das pilastras e deslizá-lo para outra pilastra.
  3. Nenhum disco pode ser colocado sobre um disco menor.

Passo 3

Agora, vamos falar sobre a relação de recorrência. É uma maneira de definir uma sequência baseada em termos anteriores da própria sequência. No contexto das Torres de Hanói, queremos expressar o número mínimo de movimentos necessários para resolver o quebra-cabeça com n discos em termos do número de movimentos para n-1 discos.

Passo 4

Para resolver as Torres de Hanói com n discos, a estratégia é a seguinte:
  1. Mover os n-1 discos superiores para uma haste auxiliar. Isso pode ser feito recursivamente.
  2. Mover o disco maior (o disco número n) para a haste de destino.
  3. Mover os n-1 discos da haste auxiliar para a haste de destino, sobre o disco maior. Isso também é feito recursivamente.

Passo 5

Vamos traduzir essa estratégia em uma relação de recorrência. Se denotarmos por T(n) o número mínimo de movimentos necessários para resolver o problema com n discos, então:
  • Mover os n-1 discos para a haste auxiliar requer T(n-1) movimentos.
  • Mover o disco maior requer 1 movimento.
  • Mover os n-1 discos para a haste de destino requer mais T(n-1) movimentos.
Então, a relação de recorrência fica:

Resposta

A relação de recorrência para o problema das Torres de Hanói é:

Exercícios relacionados

Seja o número de maneiras de se cobrir uma caixa com retângulos (você pode colocar cada dominó na horizontal ou vertical). Obtenha uma relação de recorrência para .
(a) Como visto na Proposição 3.1.7, os Números de Stirling de segunda ordem são definidos como o número de maneiras de distribuir bolas numeradas em urnas indistinguíveis, sem que nenhuma urna fique vazia. Sem utilizar a fórmula obtida na Proposição 3.1.7 ou seja, apresentando um argumento combinatório, mostre que os Números de Stirling de segunda ordem satisfazem a recorrência
Dica: considere bolas numeradas em urnas indistinguíveis. Há dois casos, ou a bola está sozinha em uma urna, ou não está.
(b) Uma permutação dos números pode ser representada por uma composição de ciclos. Por exemplo, para , a notação (142)(3)(576) representa a permutação tal que e , o que completa o primeiro ciclo. Depois, temos que , que é um ciclo de tamanho 1. Por fim, e . Os Números de Stirling de primeira ordem sem sinal, geralmente denotados por , são definidos como o número de permutações de elementos cuja decomposição em ciclos tem exatamente ciclos. Por exemplo, a permutação (142)(3)(576) anterior tem três ciclos. Mostre que os Números de Stirling de primeira ordem sem sinal satisfazem à recorrência
Dica: considere uma permutação de elementos com ciclos. Há dois casos, ou o -ésimo elemento está num ciclo de tamanho um, ou não.
Observação. A título de curiosidade, comentamos aqui que os Números de Stirling de primeira ordem com sinal (ou simplesmente Números de Stirling de primeira ordem) são definidos por . E os nomes de primeira
ordem e de segunda ordem se devem a uma conexão entre estes dois tipos de números, a chamada transformada de Stirling. A transformada de Stirling é a operação que leva uma sequência na sequência definida por
onde são os Números de Stirling de segunda ordem. Curiosamente, a inversa da transformada de Stirling é a operação que leva uma sequência na sequência definida por
onde são os Números de Stirling de primeira ordem (com sinal).
Reveja a definição de Números de Bell no Corolário 3.1.8. Mostre a seguinte recorrência:
Dica: note que o número de Bell é o número de possíveis relações de equivalência um conjunto , sendo . Fixe então um elemento de e denote por o número de elementos da classe de equivalência que contém esse elemento.
Um esporte pouco conhecido é o de subir escadas. Encontre uma relação de recorrência para o número de maneiras de se subir degraus de uma escada, se a cada passo pode-se escolher subir um ou dois degraus. Se considerarmos a questão de iniciar com o pé direito ou esquerdo, como ficará a recorrência?