NIM

NIM

O jogo de Nim parece ter origem na China, é jogado na Europa desde o século XVI. Joga-se com palitos, pedrinhas, favas, moedas ou quaisquer pequenos objetos bem distinguíveis. Um número arbitrário (normalmente de três a seis) de pilhas destes objetos, digamos palitos, é formado e alguém é escolhido para ser o primeiro a jogar. A jogada consiste de remover de uma das pilhas um número qualquer de palitos – mas obrigatoriamente pelo menos um. Quem ganha o Nim comum é quem remove o último palito da mesa. Nim é um jogo imparcial. Por este motivo os valores a serem calculados serão de um tipo novo: os números surreais.

Suponha que há n pilhas de palitos, com p1 palitos na primeira pilha, p2 palitos na segunda, ..., pn palitos na n-ésima. O valor da configuração mais simples – de mesa vazia – é zero, pois certamente quem precisa jogar terá perdido. Para entender o valor das configurações, vá a Jogos Matemáticos.

Considere uma situação muito simples: uma pilha de um palito. Por ser imparcial, A e B têm as mesmas opções – retirar o palito e produzir uma configuração de valor zero.

Valor { 0 | 0 } => igual a quê ?

Normalmente, o valor da configuração é o número “mais simples” menor que todos os termos à direita e maior de que todos os termos à esquerda. Neste caso, temos “o número com cota inferior zero e cota superior zero” - o que não é uma idéia muito simples! Este “número” é, portanto, fuzzy (confuso), ie. maior e menor que zero, ou seja, confundido com zero. Ele é denotado *1.

Uma pilha de dois palitos teria valor { 0, *1 | 0, *1 } que chamamos de *2. Em geral uma pilha de n palitos tem valor { 0, *1, *2, ..., *(n-1) | 0, *1, *2, ..., *(n-1) } = *n. Repare que realmente é fuzzy, já que o primeiro jogador a jogar ganha. Repare ainda que o valor da configuração é o menor número fuzzy que não aparece dentro das chaves. Pode parecer trivial, mas em geral esta regra é chamada de mex, a regra do mínimo excluído.

Duas pilhas não é muito mais difícil. Duas pilhas iguais dão vitória certa ao segundo a jogar: seja o que o primeiro faça, o segundo imita na outra pilha, mantendo após a sua jogada duas pilhas iguais. Se começar com duas pilhas desiguais, o primeiro torna-as iguais e garante vitória. O valor de uma configuração de duas pilhas é a soma dos valores de cada pilha. Repare que pelo quadro de valores isso implica que *k + *k = 0.

Figura 1

Veja na Figura 1 três pilhas, de um, dois e três palitos. Neste caso acontece também a perda de quem começar o jogo, pois seja o que o primeiro jogador faça, o segundo pode criar duas pilhas iguais (valor zero). Assim, *1 + *2 + *3 = 0, e portanto *1 + *2 = *3, *1 + *3 = *2 e *2 + *3 = *1, já que *n = - (*n).

Charles L. Bouton publicou um artigo em 1901 que esclareceu definitivamente o jogo Nim (aliás, foi Charles Bouton que deu para este jogo o nome Nim). Seu método envolve escrever o número de palitos em cada pilha em notação binária: todo número inteiro pode ser escrito em base 2 com algarismos 0 e 1, expressando um dado n como soma de potências de 2. Por exemplo, 13 na base dois é escrito 1101 = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20. Supomos que temos duas pilhas de n1 e n2 palitos. Escrevendo n1 e n2 na base dois, vemos que se são iguais os números terá um número par de ´1´ s em cada coluna da soma dos dois números, ou seja, terá ou nenhum ´1´ ou dois ´1´s.

Escrevemos as pilhas do exemplo de cima em base dois: 2 = 10, 3 = 11 e 1 = 1. A soma fica

10

11

1

e tem um número par de ´1´ s em cada coluna, isso é, tem dois. Consideramos a soma sem passagem de nada para a coluna à esquerda. Assim, 1 + 1 = 0 e 0 + 0 = 0. Fazendo soma assim, a soma de cima é igual a zero. Bouton provou que se a soma (no sentido indicado) é igual a zero então o segundo a jogar tem vitória garantida. Como? Isso decorre de três fatos

i) vitória corresponde à soma zero;

ii) se a soma é zero, a próxima jogada com certeza resultará em soma não-zero;

iii) se a soma não é zero, a próxima jogada sempre pode torná-la igual a zero.

Para entender os fatos ii) e iii), considere uma situação de soma zero. Sejam pilhas de 5, 2, 10 e 13 palitos. Escritos na base binária são 101, 10, 1010, 1101. A soma é zero:

101

10

1010

1101

0000

Seja qual for a próxima jogada, alterará uma das ´1´s e/ou ´0´s numa das colunas e portanto a nova soma não será zero. Finalmente, considere uma situação de soma não-zero, com pilhas de 6, 3, 8 e 9 palitos:

110

11

1000

1001

0100

Quem joga agora pode com certeza converter a soma em zero se quiser. Neste caso, retirando quatro palitos da primeira pilha leva a 2, 3, 8 e 9 palitos:

10

11

1000

1001

0000

ou seja, cada valor de pilha, *k, é escrito como soma binária, e *2s + *2s = 0. O importante desta idéia é que ela se aplica a muitos outros jogos além de Nim, e que é de fato um método infalível para o próprio jogo de Nim. Mas como é que fica o uso prático desta análise ao jogar, em particular, em jogo com alunos de 6º ano de ensino básico ao 3º ano do ensino médio?

Para isso temos um método prático, não-infalível mas freqüentemente muito útil. Suponha por exemplo o desafio de jogar contra outra pessoa com o mesmo nível de preparo uma partida de três pilhas – uma de 4, uma de 7 e uma de 13 palitos. Dispensamos o cálculo da soma binária; vemos que apenas uma das pilhas tem mais de que 23 = 8 palitos. Logo a soma não pode ser zero. Para conseguir isso reduzimos a pilha de 13 a uma pilha entre 4 e 7 palitos, mas sem produzir duas pilhas iguais, pois isso daria ao adversário uma estratégia infalível (eliminação da pilha desigual). Assim, reduzimos a pilha de 13 a uma de 5 ou 6 palitos. Suponha que seja 5 e passamos a pensar no lugar do segundo jogador.

Assim, este enfrenta três pilhas, de 7, 5 e 4 palitos. Não tem nenhuma pilha única maior de que alguma potência de dois. Logo, a lógica mais simples diz: não produza uma situação destas, de uma pilha bem maior de que as outras, nem produza duas pilhas iguais. Há várias alternativas abertas ao jogador. Uma delas de fato garantiria vitória a B: retirar dois palitos da pilha de 4 – mas isso comumente não vai ser de imediata percepção por parte do jogador.

Em 1910 o matemático Moore propôs um jogo alternativo a Nim, chamado de Nimk, e publicou um artigo mostrando as estratégias para este jogo. Nimk é como Nim, mas ao invés de poder retirar palitos de uma única pilha, qualquer número de palitos pode ser retirado de uma a k pilhas. Consideremos Nim2 como exemplo: pode-se retirar qualquer número de palitos de uma ou duas pilhas.

Como é o Nimk no caso de haver somente duas pilhas?

Figura 2

Na Figura 2 a vitória é do segundo a jogar, ou seja, o valor da configuração é zero. Em geral a análise é semelhante à de nim comum. Expresse o tamanho de cada pilha como número binário e soma estes números sem passagem para outra coluna, mas some-os módulo k + 1 e não módulo 2 como é o caso de Nim clássico. Se a soma é zero é vitória ao segundo jogador; caso contrário quem ganha é o primeiro a jogar, que fará uma redução de uma ou duas pilhas de modo que a soma passa a ser zero.

Por exemplo, suponha inicialmente quatro pilhas de 3, 6, 7 e 10 palitos numa partida de Nim2. Escrevendo-os em notação binária e efetuando a soma (mod 3) temos

11

110

111

1010

1212

E portanto o primeiro a jogar garante vitória. Deixamos ao leitor apontar sua jogada vitoriosa.