Estude! Com Prof. Caju

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:

Números de discos transferidos // Número de movimentos executados
1 2 3 4 5 6 7 ...... 10
1 3 7 15 31 63 127 ...... 10

Qual o número de movimentos necessários para transpor 10 discos do 1 para o 3 pino?

a) 511
b) 1023
c) 512
d) 1024
e) 1025

Disco [tex3]\rightarrow[/tex3] Movimento [tex3]1[tex3]\rightarrow[/tex3] 1 [tex3]\rightarrow[/tex3] 2-1=1
2 [tex3]\rightarrow[/tex3] 3 [tex3]\rightarrow[/tex3] 4-1=3
3 [tex3]\rightarrow[/tex3] 7 [tex3]\rightarrow[/tex3] 8-1=7
4 [tex3]\rightarrow[/tex3] 15 [tex3]\rightarrow[/tex3] 16-1=15
...
10 = [tex3]2^{n}-1[/tex3] [tex3]\rightarrow[/tex3] [tex3]2^{10}[/tex3]-1=1024-1=1023

Letra B

O problema da Torre de Hanoi pode ser resolvido por relação de recorrência.

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.

Seja [tex3]T_n[/tex3] = o menor número de movimentos para movimentar uma torre de n discos de um pino para outro.
Vamos chamar de pino 1, o pino inicial, onde se encontra a torre inicialmente; pino 2, o pino intermediário (auxiliar); e de pino 3, o pino final, para onde a torre de discos deve ser movida.

Se tivermos uma torre com 1 disco, será necessário, no mínimo, 1 movimento para mover a torre do pino 1 para o pino 3. Portanto, [tex3]T_1 =1[/tex3].
Se tivermos uma torre com 2 discos, moveremos o disco menor para o pino 2, depois moveremos o disco maior para o pino 3, e por fim, o disco menor para o pino 3. Portanto, [tex3]T_2 = 3[/tex3].
Se tivermos uma torre com 3 discos, (disco menor, disco médio, disco maior), movemos o disco menor para o pino 3, movemos o disco médio para o pino 2 e movemos o disco menor para o pino 2 (movendo para o disco auxiliar a sub-torre de 2 discos, ou seja, a sub-torre com n-1 discos). A seguir, movemos o disco maior para para o pino 3. Para movermos a torre de 2 discos formada para o pino 3, movemos o disco menor para o pino 1, movemos o disco médio para o pino 3, e por fim, movemos o disco menor para o pino 3. Portanto, [tex3]T_3 = 7[/tex3].

Para n discos, podemos observar que para a torre com n discos, moveremos a sub-torre com n-1 discos para o pino 2 (pino auxiliar), moveremos o disco grande para o pino 3, e por fim, moveremos a sub-torre de n-1 discos para o pino 3.
Portanto, os movimentos são: mover a sub-torre de n-1 discos, mover 1 disco, mover a torre de n-1 discos.
Logo, temos que: [tex3]T_n = T_{n-1} +1 + T_{n+1}[/tex3], ou seja:

[tex3]\begin{cases}
T_n = 2\cdot T_{n-1} +1 \;,\; n \geq 2\\
T_1 = 1
\end{cases}[/tex3]

Resolvendo a relação de recorrência, temos:

[tex3]T_n = 2 \cdot T_{n-1} + 1[/tex3]

Parte homogênea: [tex3]T_n = 2 \cdot T_{n-1} \;\; \rightarrow \;\; \alpha ^n = 2 \cdot \alpha^{n-1} \;\; \rightarrow \;\; \alpha = 2[/tex3]
Portanto, temos que: [tex3]h(n) = A \cdot 2^n[/tex3]

Parte particular: [tex3]p(n) = 1 = n^0 \;\; \rightarrow \;\; p(n) = B \;\; \rightarrow \;\; B = 2 B +1 \;\; \rightarrow \;\; B = -1[/tex3]
Portanto, temos que: [tex3]h(n) + p(n) = A \cdot 2^n - 1 \;\; \rightarrow \;\; T_1 = 1 \;\; \rightarrow \;\; 1 = A \cdot 2 - 1 \;\; \rightarrow \;\; A = 1[/tex3]

Logo, temos que: [tex3]\boxed{T_n = 2^n -1}[/tex3]

Para n = 10 discos, temos:
[tex3]T_n = 2^n -1 \;\; \rightarrow \;\; T_{10} = 2^{10} - 1 \;\; \rightarrow \;\; T_{10} = 1024 - 1 = 1023[/tex3] movimentos.