Nim é um jogo em que se considera um conjunto de pilhas de objectos. Dois jogadores jogam de forma alternada e retiram um determinado número de objectos de uma das pilhas. Inclusivamente, é possível que todos os objectos de uma pilha sejam retirados. O último jogador a intervir, ganha.
Assim, a família de jogos Nim é vasta, uma vez que pode variar o número de pilhas e o número de objectos, mas claramente nenhum desses jogos pode terminar em empate. Então, existe um jogador que ganha. Será que podemos, a partir do número de pilhas e objectos iniciais, determinar uma estratégia que nos permita ganhar o jogo?
Vamos exemplificar um jogo de Nim simples, com 2 pilhas com 2 objectos cada. O jogador A, que começa e retira os dois objectos de uma das pilhas. De seguida o jogador B retira os dois objectos da restante e ganha o jogo. Começam outro jogo, o jogador A sabe que não pode retirar dois objectos de uma pilha, portanto retira apenas um; de seguida o jogador B retira um objecto da outra pilha, obriga o jogador A a limpar uma pilha e o jogador B volta a ganhar. O jogador B consegue sempre ganhar o jogo, independentemente do que o jogador A faça, dizemos que o jogador B tem uma estratégia ganhadora.
Naturalmente que em versões mais complexas do Nim somos obrigados a um trabalho muito mais exaustivo para determinar a estratégia ganhadora, e o jogador a que corresponde. Uma forma muito mais simples passa por analisar a decomposição binária do número de objectos em todas as pilhas, isto é, decompomos cada número de objectos numa soma de potências de 2. Por exemplo, assumimos um jogo com 3 pilhas, com 4, 5 e 8 objectos. Então representamos a situação inicial do jogo pelo seguinte quadro, dado que
$4=2^2, \ 5=2^2+2^0,\ e\ 8=2^3$
Dizemos que uma colecção de pilhas se encontra em equilíbrio se todas as potências de 2 ocorrem em número par (por convenção, 0 toma o significado de número par). Portanto a colecção de pilhas anterior encontra-se em desequilíbrio. Se o jogador A retirar 7 objectos da última (ordenação a partir da organização da tabela) pilha, esta passa a ter apenas um objecto, o que irá fazer com a colecção de pilhas passe a estar equilibrada:
De facto, conclui-se que a estratégia ganhadora consiste em transformar a colecção de pilhas de desequilibrada em equilibrada, sucessivamente, até que a posição de equilíbrio seja com apenas zeros na última linha, isto é, até à situação final de jogo. Se uma colecção de pilhas estiver em equilíbrio, o outro jogador é forçado a desequilibrar a colecção, dado que é impossível retirar objectos de uma pilha sem desequilibrar a colecção.
Podemos então concluir que se a colecção de pilhas inicial se encontrar em desequilíbrio o jogador A tem uma estratégia ganhadora, e portanto pode ganhar o jogo independentemente das jogadas do adversário. Caso contrário, será o jogador B a ter a estratégia ganhadora. Em ambos os casos as estratégias ganhadoras passam por equilibrar a colecção de pilhas, que se encontrava em desequilíbrio.
Sem comentários:
Enviar um comentário