Três discos:
Para três discos, a transferência se dá com 7 movimentos: m3 = 7
Experimentos com três discos mostram que a idéia é transferir os dois discos de
cima para o pino do meio, depois mover o terceiro e, finalmente, transferir os
outros dois para cima deste. Isto nos dá uma pista para transferência de n discos
em geral: primeiro transferimos os n-1 discos menores para um pino intermediário
( o que requer mn-1 movimentos), depois movemos o maior disco (o que requer um
movimento) e, finalmente, empilhamos os n -1 discos menores em cima do maior
(o que requer mn-1 movimentos). Portanto podemos transferir n discos (para n>0)
em no máximo 2 mn-1 +1 movimentos.
mn £ 2 mn-1 +1 , para n > 0
Esta fórmula usa “£” no lugar de “=” porque nossa construção mostra apenas que
2 mn-1 +1 movimentos são suficientes: não mostramos que 2 mn-1 +1 movimentos
são necessários. Uma pessoa esperta poderia ser capaz de encontrar um atalho.
Mas existe um modo melhor? De fato não. Alguma hora vamos ter que mover o
maior disco. Quando fizermos, os n-1 discos menores tem que estar, todos, em
algum pino e foram precisos pelo menos mn-1 movimentos para colocá-los lá. Se
não estivermos bem atentos, corremos o risco de mover o maior disco mais de
uma vez. Mas depois de mover o maior disco pela última vez, precisamos
transferir os n-1 discos menores (que, de novo, tem que estar em um único pino)
para cima do maior; para isto também são necessários mn-1 movimentos. Logo
mn ³ 2 mn-1 +1 , para n > 0
Estas duas inequações, junto com a solução trivial para n = 0, fornecem
m0 =0
mn = 2 mn-1 +1 , para n > 0
Assim, podemos montar a tabela, sendo n o número de discos e mn o número de
movimentos:
n 1 2 3 4 5 6 ¼
mn 1 3 7 15 31 63 ¼
Observando a segunda linha da tabela vemos que os seus números são:
1= 2 - 1
3 = 22 – 1
7 = 23 – 1
15 = 24 – 1
O que nos leva a fazer a seguinte conjectura: mn = 2n – 1
Esta sentença é verdadeira para n = 1, 2, 3, 4, 5 ,6, mas será verdadeira para
sempre?
Tentemos demostrá-la por indução:
Seja S o conjunto dos números naturais n tais que n discos são movidos com 2n-1
movimentos.
i) 1 Î S, pois para 1 disco necessitamos de 1 = 21 – 1 movimento.
ii) Vamos supor que k Î S, isto é, k discos são removidos com 2k –1
movimentos.
Vamos provar que k + 1 Î S, isto é, que mk +1 = 2k + 1 – 1.
Para remover k + 1 discos passamos, inicialmente, k discos para o bastão
de trás com mk movimentos;
Em seguida, com 1 movimento, o (k + 1) – ésimo disco vai para o outro
bastão da frente;
Com mais mk movimentos, os k discos de trás passam para o bastão da
frente. Isto é:
mk+1 = mk + 1 + mk
mk+1 = 2k – 1 + 1 + 2k – 1
mk+1 = 2 . 2k – 1
mk+1 = 2k+1 – 1
E isto mostra que k + 1 Î S.
O princípio da indução nos garante que n discos podem sempre ser removidos
com 2n – 1 movimentos e, em particular, m64 = 264 – 1.
Para três discos, a transferência se dá com 7 movimentos: m3 = 7
Experimentos com três discos mostram que a idéia é transferir os dois discos de
cima para o pino do meio, depois mover o terceiro e, finalmente, transferir os
outros dois para cima deste. Isto nos dá uma pista para transferência de n discos
em geral: primeiro transferimos os n-1 discos menores para um pino intermediário
( o que requer mn-1 movimentos), depois movemos o maior disco (o que requer um
movimento) e, finalmente, empilhamos os n -1 discos menores em cima do maior
(o que requer mn-1 movimentos). Portanto podemos transferir n discos (para n>0)
em no máximo 2 mn-1 +1 movimentos.
mn £ 2 mn-1 +1 , para n > 0
Esta fórmula usa “£” no lugar de “=” porque nossa construção mostra apenas que
2 mn-1 +1 movimentos são suficientes: não mostramos que 2 mn-1 +1 movimentos
são necessários. Uma pessoa esperta poderia ser capaz de encontrar um atalho.
Mas existe um modo melhor? De fato não. Alguma hora vamos ter que mover o
maior disco. Quando fizermos, os n-1 discos menores tem que estar, todos, em
algum pino e foram precisos pelo menos mn-1 movimentos para colocá-los lá. Se
não estivermos bem atentos, corremos o risco de mover o maior disco mais de
uma vez. Mas depois de mover o maior disco pela última vez, precisamos
transferir os n-1 discos menores (que, de novo, tem que estar em um único pino)
para cima do maior; para isto também são necessários mn-1 movimentos. Logo
mn ³ 2 mn-1 +1 , para n > 0
Estas duas inequações, junto com a solução trivial para n = 0, fornecem
m0 =0
mn = 2 mn-1 +1 , para n > 0
Assim, podemos montar a tabela, sendo n o número de discos e mn o número de
movimentos:
n 1 2 3 4 5 6 ¼
mn 1 3 7 15 31 63 ¼
Observando a segunda linha da tabela vemos que os seus números são:
1= 2 - 1
3 = 22 – 1
7 = 23 – 1
15 = 24 – 1
O que nos leva a fazer a seguinte conjectura: mn = 2n – 1
Esta sentença é verdadeira para n = 1, 2, 3, 4, 5 ,6, mas será verdadeira para
sempre?
Tentemos demostrá-la por indução:
Seja S o conjunto dos números naturais n tais que n discos são movidos com 2n-1
movimentos.
i) 1 Î S, pois para 1 disco necessitamos de 1 = 21 – 1 movimento.
ii) Vamos supor que k Î S, isto é, k discos são removidos com 2k –1
movimentos.
Vamos provar que k + 1 Î S, isto é, que mk +1 = 2k + 1 – 1.
Para remover k + 1 discos passamos, inicialmente, k discos para o bastão
de trás com mk movimentos;
Em seguida, com 1 movimento, o (k + 1) – ésimo disco vai para o outro
bastão da frente;
Com mais mk movimentos, os k discos de trás passam para o bastão da
frente. Isto é:
mk+1 = mk + 1 + mk
mk+1 = 2k – 1 + 1 + 2k – 1
mk+1 = 2 . 2k – 1
mk+1 = 2k+1 – 1
E isto mostra que k + 1 Î S.
O princípio da indução nos garante que n discos podem sempre ser removidos
com 2n – 1 movimentos e, em particular, m64 = 264 – 1.
Nenhum comentário:
Postar um comentário