Olimpíadas ⇒ Desafio: Torre de Hanói

[Auto Excluído (ID:17906)]

Dispõe-se de 3 pinos e n discos de vidro com num furo no meio, sendo que os discos tem pesos distintos dois a dois. Sabe-se que se um disco de peso maior é colocado sobre um disco de peso menor, então ele se quebra. É proposto então o seguinte jogo: "Todos os n discos estão encaixados no primeiro pino, de maneira que olhando de baixo para cima estão em ordem decrescente de peso. O movimento permitido é passar o disco que está na posição superior de um pino para outro pino." Qual é o menor número de movimentos necessários para se passar todos os discos para o terceiro pino, podendo usar o segundo pino (sem quebrar nenhum disco)?

[Tassandro]

Considere a sentença aberta
P(n) : O jogo com n discos tem solução.
Obviamente, P(1) é verdade. Suponha que P(n) seja verdadeiro,
para algum n; ou seja, que o jogo com n discos tem solução. Vamos
provar que o jogo com n + 1 discos tem solução.
Para ver isso, resolva inicialmente o problema para os n discos superiores da pilha, transferindo-os para uma das hastes livre (isso é
possível, pois estamos admitindo que o problema com n discos possua
solução):

20200416_193913.jpg (3.59 KiB) Exibido 704 vezes

Em seguida, transfira o disco que restou na pilha original (o maior
dos discos) para a haste vazia:

20200416_193937.jpg (3.71 KiB) Exibido 704 vezes

Feito isto, resolva novamente o problema para os n discos que
estão juntos, transferindo-os para a haste que contém o maior dos
discos.
Isso mostra que o problema com n + 1 discos também possui
solução, e, portanto, por Indução Matemática, que P(n) é verdadeira para todo n ∈ [tex3]\mathbb{N}[/tex3].
Para determinar uma fórmula para [tex3]j_n[/tex3], veja que, para resolver o
problema para n + 1 discos com o menor número de passos, temos,
necessariamente, que passar duas vezes pela solução mínima do problema com n discos. Temos, então, que
[tex3]j_{n+1} = 2j_n + 1,j_1=1[/tex3]
Obtemos, assim, uma progressão aritmético-geométrica.
Sabemos que o termo geral de uma PAG [tex3]a_{n+1}=qa_n+r[/tex3] é dado por [tex3]a_n=a_1q^{n-1}+r\frac{q^{n-1}-1}{q-1}[/tex3]
Assim, no caso dado, [tex3]q=2,r=1,j_1=1[/tex3]
Logo,
[tex3]j_n=2^{n-1}+\frac{2^{n-1}-1}{1}=\boxed{2^n-1}[/tex3]

Vale, bonam fortunam!