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:
- Apenas um disco pode ser movido por vez.
- Cada movimento consiste em pegar o disco mais no topo de uma das pilastras e deslizá-lo para outra pilastra.
- 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:
- Mover os n-1 discos superiores para uma haste auxiliar. Isso pode ser feito recursivamente.
- Mover o disco maior (o disco número n) para a haste de destino.
- 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
(b) Uma permutação dos números
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
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
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
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?