A Torre de Hanoi (torre do bramanismo ou quebra-cabeças
do fim do mundo) é um jogo, muito popular na Ásia, inspirado
em uma lenda hindú (outros afirmam que vem do Vietnam). A lenda diz
que em um templo (a Torre de Hanoi) havia 3 estacas e 64 discos de ouro,
de diâmetros diferentes. Esses discos estavam enfiados na primeira
estaca, em ordem crescente de diâmetros, de cima para baixo. Ocupavam-se
sacerdotes (para melhorar a disciplina mental) em transferí-los para
a terceira estaca, usando a segunda como estaca auxiliar. No processo de
transferência, jamais um disco poderia ser colocado sobre outro disco
menor. Quando todos estivessem na terceira estaca, o templo seria transformado
em pó e o mundo acabaria.
Na figura a seguir temos um jogo de Torre de Hanoi (uma base com 3 estacas)
com poucos discos. Vence o jogo aquele que coloca os discos na terceira estaca
com o menor número possível de transferências sem desobedecer
as regras.
Neste jogo, existe uma lei matemática, descoberta pelo matemático
francês Edouard Lucas (1842-1891), que relaciona o número de
discos com o menor número possível de transferências
de discos, de uma estaca para outra, feitas para colocá-las na terceira
estaca. Assim sendo, responda:
a) Se x é o número de discos e y é o número de
transferências (número mínimo de movimentos), qual a
expressão da função que relaciona x e y.
b) Se num jogo temos 10 discos, quantas transferências de discos, de
uma estaca para outra, devem ser feitas para colocá-los na terceira
estaca?
c) Num jogo completo com 64 discos, quantas transferências de discos,
de uma estaca para outra, devem ser feitas para colocá-los na terceira
estaca?
Solução: a) Este jogo exige um raciocínio recursivo
muito utilizado na ciência da computação, na
inteligência artificial etc.
Com 1 disco o número de transferência de disco é 1.
Com 2 disco, temos 1 transferência para deslocar o disco menor para
a estaca 2, mais 1 transferência para deslocar o disco maior para a
estaca 3 e novamente 1 transferência para deslocar o disco menor para
estaca 3 (total de 1+1+1 = 3 movimentos).
Com 3 discos, temos 3 transferência para deslocar os 2 primeiros discos
para a estaca 2, mais 1 transferência para deslocar o disco maior para
a estaca 3 e novamente 3 transferência para deslocar os 2 discos para
a estaca 3 (total de 3+1+3= 7 movimentos).
Com 4 discos, temos 7 transferência para deslocar os 3 primeiros discos
para a estaca 2, mais 1 transferência para deslocar o disco maior para
a estaca 3 e novamente 7 transferência para deslocar os 3 discos para
a estaca 3 (total de 7+1+7 = 15 movimentos). De modo análogo, com
5 discos teremos 15+1+15 = 31 transferências, e assim por diante.
Observando que o número de jogadas + 1 é uma potência
de base 2, segue que:
Com 1 disco temos: 1 = 21 - 1 transferências;
Com 2 discos temos: 3 = 22 - 1 transferências;
Com 3 discos temos: 7 = 23 - 1 transferências;
Com 4 discos temos: 15 = 24 - 1 transferências;
Com 5 discos temos: 31 = 25 - 1 transferências;
E assim sucessivamente. Logo, generalizando para x discos, teremos
y = 2x - 1 transferências.
b) Na
função exponencial y = 2x - 1 , se o
número de disco é x = 10, então o número de
movimentos é y = 210 - 1 = 1024 - 1 = 1023 movimentos.
c) Se o número de disco é x = 64 (como acontece na lenda),
então o número de movimentos é y = 264 -
1 = 18446744073709551616 - 1 = 18.446.744.073.709.551.615 movimentos.
Observe que, num jogo com 64 discos, se cada movimento fosse feito em 1 segundo,
o jogador levaria aproximadamente 5,9 bilhões de séculos para
terminar o jogo. (verifique!).
O tabuleiro do jogo de Xadrez é um quadriculado
que tem 64 casas. Diz a lenda, contada no livro "O Homem que Calculava", do matemático brasileiro
Malba Tahan, que o inventor deste jogo pediu ao Rei, como
recompensa, um grão de trigo pela primeira casa, dois grãos
pela segunda, quatro pela terceira e assim por diante, sempre dobrando a
quantidade a cada nova casa. O Rei, que não era bom em Matemática,
aceitou o pedido prontamente. Qual foi a quantidade de grãos pedida
pelo inventor do Xadrez?
Solução: A quantidade de grãos é
o resultado da soma S = 1 + 2 + 4 + 8 + 16 + ... , com 64 parcelas.
Trata-se da soma dos 64 termos de uma Progressão
Geométrica de razão q = 2 e primeiro termo a1
= 1.
Como a soma dos n termos de uma PG é S =
a1(qn - 1) / (q - 1) , segue que a soma procurada é:
S = 1(264 - 1) / (2 - 1) = 264 - 1 = 18446744073709551616
- 1 = 18.446.744.073.709.551.615 grãos.
NOTA: O número 18.446.744.073.709.551.615
(dezoito quintilhões, quatrocentos e quarenta e seis quatrilhões,
setecentos e quarenta e quatro trilhões, setenta e três
bilhões, setecentos e nove milhões, quinhentos e cinquenta
e um mil e, seiscentos e quinze) de grãos de trigo seria muito maior que
toda a safra do reino durante centenas de anos. Assim, o Rei teria que dar todo
o seu reino para o inventor do Xadrez.
(OBM) O dominó mais conhecido tem como maior
peça o duplo 6. Neste dominó são empregadas 28 peças
diferentes. Quantas peças tem o dominó cuja maior peça
é o duplo 8?
| (A) 34 |
(B) 36 |
(C) 42 |
(D) 55 |
(E) 45 |
Solução: Neste dominó cada peça
tem um par de números que podem ser distintos, ou podem ser iguais
(duplas). A ordem com que os números aparecem em cada peça
não faz diferença. Pela análise
combinatória, a quantidade de peças com números
diferentes é o número de combinações de 9 elementos
escolhidos 2 a 2, ou seja, é:
C9,2 = 9 × 8 / 2! = 9 × 8 / 2 = 72 / 2 = 36
peças.
As peças com números iguais (duplas) são: (0 , 0) ;
(1 , 1) ; (2 , 2) ; ... ; (7 , 7) ; (8 , 8). Portanto, existem 9 peças
com duplas.
Assim, o número total de peças neste dominó é
36 + 9 = 45 peças. Logo, (E) é a opção correta.
(PUC) Um torneio de xadrez no qual cada jogador joga
com todos os outros tem 351 partidas. O número de jogadores disputando
é...
Solução: Seja x o número
de jogadores. O número de partidas (jogos) é o número de
combinações de 2 elementos escolhidos
entre x jogadores, ou seja, Cx,2 = 351.
Então, x(x-1) /2!= 351. Segue que:
x2 - x = 702.
Portanto, temos a
equação do segundo grau:
x2 - x - 702 = 0 , que pode ser resolvida com a
"fórmula de Bhaskara".
Calculando o discriminante (delta),
encontramos: D = (1)2
- (4)×(1)×(702) = 1 - 2808 = 2809.
Sendo 3×3=9 e 7×7=49, segue que a raiz quadrada de 2809 termina
em 3, ou, em 7. Temos também que 50×50 = 2500 e 60×60 =
3600, portanto, a raiz quadrada de 2809 é 53, ou, é 57.
Como
53×53 = 2809 e 57×57 = 3249, então, a raiz quadrada de 2809
é 53.
Assim, x = (1+53) /
2 = 27 ou x = (1-53) / 2 = -26 (não convém).
Logo, o número de jogadores é 27.
Política de Privacidade Vídeos
Problemas resolvidos Bibliografia
