|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
Nim A matemática do NIM Há diversas variantes de jogos NIM. Descrevemos a variante clássica e damos um exemplo adaptado do livro de J. N. Silva e J. P. Neto, Jogos Matemáticos - Jogos Abstractos . Joga-se com pilhas de peças. Cada jogador, em cada jogada, escolhe uma pilha e retira dela o número de peças que desejar. Ganha o jogador que retirar a última peça. Com uma única pilha, o primeiro jogador retira todas as peças e ganha numa só jogada, pelo que o jogo é trivial. Com duas pilhas há uma estratégia óptima, que é retirar de uma delas o número de peças necessário para igualar as pilhas e, a partir daí, copiar a jogada do adversário, de forma a deixar sempre iguais as duas pilhas. A certa altura, o adversário terá de terminar completamente uma pilha. Nessa altura, esvazia-se a outra e ganha-se. Com três ou mais pilhas, a estratégia vencedora é mais difícil e pode ser formalizada introduzindo a soma NIM, operada sobre a representação dos números em expansão binária (a linguagem de zeros e uns dos computadores). A soma NIM adiciona um a um os dígitos, mas não procede ao «e vai um...». O clássico Teorema de Bouton assegura que se obtém uma posição vencedora quando se consegue que a soma NIM do número de peças das pilhas seja zero.
Torre de Hanoi Descrição Na criação, foi apresentado como se fosse trazido de um mosteiro vietnamita, onde os monges passassem o tempo todo movendo 40 discos gigantes de bronze. A lenda afirmava que o último movimento seria o sinal do fim do mundo (depois de ler essa ficha, você pode calcular quando este fim do mundo está programado !)... Nível Trata-se de um jogo que pode ser trabalhado em variados niveis.
É importante que os mais jovens jogadores começem com poucas peças (por exemplo, as 3 menores peças). A complexidade dos movimentos cresce rapidamente com o número de peças. Com as sete peças, é dificil de controlar a estratégia, e o sucesso só parece um efeito do acaso. Preparação do jogo Enfiar os três pinos no suporte de madeira, e pousar o número desejado de peças no primeiro pino. O jogo é normalmente solitário, mas melhor ainda jogado em equipes de 2, alternando os papeis : o primeiro jogador movimenta as peças, enquanto o segundo fiscaliza a boa aplicação das regras e verifica a contagem dos movimentos. Estratégia Para ajudar a construção de uma estratégia pode começar-se com um número reduzido de peças (3 ou 4). Juntando um novo disco aparece um princípio de recorrência que livra a estratégia: Se sei fazer a manipulação com 3 discos, por exemplo, e vi que precisava pelo menos de 7 movimentos, para passar quatro peças do pino 1 até o pino 3, tem que: • passar as três menores no pino 2 (7 movimentos), Vai precisar finalmente de 15 movimentos. De maneira geral, à cada nova etapa, você pode repetir a decomposição acima, isolando a maior peça: tem que dobrar o número de movimentos e adicionar um. E quem sabe fazer esse raciocínio, na prática ou de maneira explícita vai saber resolver o problema para qualquer número de discos (só precisará de paciência ...). Experimentando pouco a pouco, ou usando a lei acima achada, observamos os números mínimos de movimentos: 1 peça 1 movimento 2 peças 3 movimentos 3 peças 7 movimentos 4 peças 15 movimentos 5 peças 31 movimentos ... Observando também que, cada vez é quase o dobro de movimentos, podemos buscar a relação com as potências successivas de dois: 2, 4, 8, 16, 32 ... E constar no final que o número de movimentos para mover n peças é sempre 2 n – 1, o que pode se demostrar quando você conhece o princípio de recorrência, pois 2 x (2 n – 1) + 1 = 2 n+1 – 1. Complementos Para os que gostam da programação, o jogo de Hanói é um exemplo tradicional e muito fácil de programar do que as pessoas que trabalham com informática chamam de recursividade, o que significa um programa que se chama ele mesmo: Hanói (n) do pino 1 até pino 3,
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
