TAREFA SOBRE A TORRE DE HANÓI
Andressa dos Santos Ferreira
2) O professor solicitará então aos alunos que construam uma torre com três discos na
posição C, “transpondo” os discos que estão em A, de acordo com as regras acima
mencionadas. Qual o número mínimo de movimentos? Qual a peça que mais se
movimenta? Qual a peça que menos se movimenta?
Número mínimo de movimentos: 7.
Peça que mais se movimenta: a menor (o disco 1).
Peça que menos se movimenta: a maior (o disco 3).
3) Toma-se então uma torre com 4 discos na posição A e pede-se aos alunos que formem
uma torre na posição C. Questionar os alunos se eles montaram a torre com o menor
número possível de movimentos. Questionar os alunos sobre como eles fizeram para
que encontrem a solução. Os alunos deverão relatar como eles formaram a torre com os
4 discos.
Como foi encontrada a solução: Tendo posse do valor mínimo de
movimentos, comecei a tentar obter esse valor. Após muitas jogadas fui percebendo
que o jogo consistia em montar e desmontar as “sub-torres” de 2 e de 3 discos.
Também percebi que se meu objetivo fosse mudar uma torre de 2 discos da
posição A para a posição C teria de começar colocando o disco 1 na posição B, se
fosse mudar uma torre de 3 discos, teria de começar colocando o disco 1 na posição
C. Generalizando, se eu tivesse um número par de discos começaria usando a
posição auxiliar (posição que não é nem a inicial e nem a final. Num jogo onde
queremos mudar as peças de A para C a posição auxiliar seria a B), caso contrário,
tendo um número ímpar de discos, começaria o jogo colocando o disco menor na
posição onde desejo montar novamente a torre (posição final).
A torre com quatro discos:
Disco 1 – Posição B
Disco 2 – Posição C
Disco 1 – Posição C
Disco 3 – Posição B
Disco 1 – Posição A
Disco 2 – Posição B
Disco 1 – Posição B
Disco 4 – Posição C
Disco 1 – Posição C
Disco 2 – Posição A
Disco 1 – Posição A
Disco 3 – Posição C
Disco 1 – Posição B
Disco 2 – Posição C
Disco 1 – Posição C
4) Questionar os alunos sobre as peças que mais se movimentam e as que menos se
movimentam para a construção da torre com 4 discos.
As que mais se movimentam, por ordem de quantidade, são: 1, 2, 3, 4. Pois,
para a construção da “sub-torre” de 3 discos, construímos duas vezes a “sub-torre”
de 2 discos. E para a construção da torre de 4 discos repetimos duas vezes a
construção da “sub-torre” de 3 discos (construindo, assim, 4 vezes a “sub-torre” de
2 discos).
5) Com 5 discos, qual a peça que mais se movimenta? E a que menos se movimenta? Qual
o número mínimo de movimentos para movimentar a torre de A para C?
A ideia do aluno relatar o que ocorreu ao transpor a torre de A para C, está relacionada
com o “tomar consciência” do movimento de cada disco, para que ele possa corrigir
eventuais erros e também possa descobrir as regularidades na montagem das torres,
descobrindo, conseqüentemente, o número mínimo de movimentos com 3, 4 discos ou
mais.
Com 5 discos, a peça que mais se movimenta é a menor, isto é, o disco 1. O
disco que menos se movimenta é o disco 5, o maior.
O número mínimo de movimentos para movimentar a torre de A para C é 31.
6) Sem jogar, qual o número mínimo de movimentos para 7 discos? E para 8 discos?
Para 7 discos, o número mínimo de movimentos é 127. E, para 8 discos, o
número mínimo de movimentos é 255.
7) Qual o segredo do jogo, que permite jogar bem, sem desperdiçar jogadas, independente
do número de discos?
Analisando quantos discos tem no jogo. Se tivermos n discos, n sendo um
número par, começamos utilizando a posição auxiliar, caso contrário, n sendo
ímpar, começamos colocando o disco 1 na posição de destino da torre.
Admitindo que temos um número de peças pares (pois, pro caso de termos
um número de peças ímpares, só ira mudar a posição pros primeiros movimentos) o
primeiro cenário seria montar a mini torre de 2 discos. Com o disco 1 na posição
auxiliar, ficamos com a posição final livre para colocarmos o disco 2 e, pondo por
cima deste o disco 1, completarmos a transferência dessa “sub-torre”. Agora
estamos com a posição auxiliar livre para colocar o disco 3 ali.
Para montar a torre de três peças basta procedermos da mesma maneira que
fizemos antes de movermos o disco 3 para a posição auxiliar, entendendo, agora,
que onde está o disco 3 é o nosso destino e que a nova posição auxiliar é a posição
inicial da torre. Procedendo sempre de maneira a subdividir a torre em pequenas
“sub-torres”, e sempre buscando diminuir até a “sub-torre” de 2 discos, que é a mais
fácil, não haverá desperdício de jogadas.
Claro, também, lembrando que se queremos o disco 2 em cima do 3, não
colocamos o disco 1, da jogada anterior, em cima do 3, pois isso irá aumentar o
nosso número de jogadas (generalizando, se quisermos colocar uma torre de n-1
discos sobre um disco n, analisamos se esse (n-1) é par ou ímpar. Se par, colocamos
o disco 1 na posição auxiliar; se ímpar, colocamos o disco 1 sobre o disco n).
8) Generalize uma função que descreve o número mínimo de movimentos associado ao
número de discos.
n
f(n) = 2  1 .