1.8 Este é um jogo antigo chamado Torre de Hanoi. Dispõe-se de
discos perfurados de diâmetros decrescentes enfiados numa haste
, 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)
é o menor número de jogadas que resolve o jogo com
discos, mostre que
e se
, então
;
b) Mostre, por indução sobre
, que se
, então
.
a)
b) Mostre, por indução sobre
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
. 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
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
jogadas). Assim
[
a_n = a_{n-1} + 1 + a_{n-1}
]
ou seja .
[
a_n = a_{n-1} + 1 + a_{n-1}
]
ou seja
Passo 3
Para (b), usamos indução em n. Base: para n=1 temos
e
, ok. Hipótese: suponha que para algum k≥1 valha
. 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, para todo n≥1.
[
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,