=?WINDOWS-1252?Q?Re:_[obm-l]_A_torre_de_han=F3i?=

[=?WINDOWS-1252?Q?Bruno_Fran=E7a_dos_Reis?= <bfreis@xxxxxxxxx>]

Se n = 1, vale a propriedade. Supondo v�lida para n, provemos a validade para n+1.
Para transferir n+1 discos para o suporte B usando C de auxiliar,
transfira n discos para o suporte C usando B como auxiliar, depois
transfira 1 disco (o ultimo) de A para B, e ent�o transfira n discos de
C para B, usando A como auxiliar. Isso nos d�:
n, A->C: 2^n - 1
1, A->B: 1
n, C->B: 2^n - 1
total: 2^n - 1 + 1 + 2^n - 1 = 2^n + 2^n - 1 = 2*2^n - 1 = 2^(n+1) - 1, q.e.d.

Abra�o!
Bruno

On 4/9/05, Fernando <goianinho_@terra.com.br> wrote:

S�o dados tr�s suportes

A, B e C. No suporte A est�o encaixados n

discos cujos di�metros, de baixo para cima, est�o em ordem estritamente decrescente.

Mostre que � poss�vel, com 2^n

  � 1 movimentos, transferir todos os discos para o suporte

B

, usando o suporte C como auxiliar, de modo que jamais, durante a opera��o, um disco

maior fique sobre um disco menor.

Desde jah grato, []'s

-- 
Bruno Fran�a dos Reis
email: bfreis - gmail.com
gpg-key: http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
icq: 12626000

e^(pi*i)+1=0