1.8 Este é um jogo antigo chamado Torre de Hanoi. Dispõe-se de n discos perfurados de diâmetros decrescentes enfiados numa haste A, e de duas outras hastes B e C.
O problema consiste em transferir toda a pilha de discos para a haste C, deslocando um disco de cada vez para qualquer haste, de modo que nenhum disco seja colocado sobre um outro de diâmetro menor
a) S e an é o menor número de jogadas que resolve o jogo com n discos, mostre que a1=1 e se n >= 2, então an=2 an-1+1;
b) Mostre, por indução sobre n, que se n >= 1, então an=2^n-1.

Passo 1

O enunciado descreve o clássico Jogo da Torre de Hanoi com n discos em A, e pede em (a) derivar recorrentemente o menor número de jogadas a_n e em (b) demonstrar por indução que a_n=2^n−1. Vamos usar teoria de recorrência e princípio de indução.

Passo 2

Para (a), com apenas 1 disco o único lance é levá-lo de A para C, logo a1=1. Para n≥2, para mover n discos de A para C sem violar a regra basta: primeiro mover os n−1 discos menores de A para a haste auxiliar B (requere an-1 jogadas), depois mover o maior disco de A para C (1 jogada), e por fim mover os n−1 discos de B para C (novamente an-1 jogadas). Assim
[
a_n = a_{n-1} + 1 + a_{n-1}
]
ou seja an = 2an-1 + 1.

Passo 3

Para (b), usamos indução em n. Base: para n=1 temos a1=1 e 2^1-1=1, ok. Hipótese: suponha que para algum k≥1 valha ak = 2^k -1. Passo indutivo:
[
a_{k+1} = 2a_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1
]
Logo vale para k+1. Pelo princípio de indução, an = 2^n - 1 para todo n≥1.

Resposta

an = 2^n - 1

Exercícios de Livros Relacionados