número de movimentos necessários

Um quebra-cabeça, abaixo figurado, consiste em transferir os discos do 1 para o 3 pino sob as seguintes regras:
1) Somente um disco pode ser transferido de cada vez de um pino para qualquer outro.
2) Nunca se deve colocar um disco maior sobre um disco menor.



Na transferência de 7 discos, utilizando-se os 3 pinos, obtivemos a seguinte tabela:



Qual o número de movimentos necessários para transpor 10 discos do 1o para o 3o pino?
A) 511
B) 1023
C) 512
D) 1024
E) 1025

Suspeita:



É uma suspeita bem forte. Por ela, a resposta seria 2¹º - 1 = 1024 - 1 = 1023 (Letra b)

Se você não acredita em coincidência, marque b) e seja feliz. Se quiser provar, me acompanhe.

Demonstração da suspeita:

Vamos entender como se resolve o jogo com "N" discos.
Para isso, considere que, na seguinte sequência de procedimentos, cada número represente o tamanho do disco:

ETAPA 1:


ETAPA 2:


ETAPA 3:


ETAPA 4:


● Da etapa 1 para a etapa 2, eu passei N-1 peças de um pino para o outro. Isto é, eu resolvi o jogo para N-1 peças.
● Da etapa 2 para a etapa 3, eu troquei o pino remanescente de lugar, isto é, fiz um lance.
● Da etapa 3 para a etapa 4, eu passei N-1 peças de um pino para outro, isto é, resolvi novamente o jogo para N-1 peças.

Seja aN o nº de movimentos para resolver o jogo com N peças, aN-1 o nº de movimentos para resolver com N-1 peças.
Do raciocínio acima:



(Essa expressão já seria suficiente para, partindo de a1, calcular a10 na raça.)

Agora eu vou provar por indução a nossa suspeita. Sabemos que:



Suponha que de fato tenhamos:



Aplicando a lei deduzida:



A lei conjeturada é válida para a base de indução a1. Ademais, ela ser válida para aN-1 implica em sua veracidade para aN. Então, pelo princípio da indução finita, ela é valida para todo N natural.

CqD

Voce é mesmo um ferinha !
Valeww