Em sua forma original, NIM é um jogo para dois participantes, que chamaremos de jogador A e jogador B. Colocamos sobre uma mesa 3 pilhas de objetos de qualquer tipo, ou então, usamos palitos de fósforo. Dispomos sobre a2 mesa 3 filas com um número arbitrário de palitos sendo que, no início, duas filas não podem ter o mesmo número de palitos.

Por exemplo:

Jogar NIM consiste em, após retiradas sucessivas dos palitos de cima da mesa, alternando de jogador para jogador, conseguir deixar o último palito para seu oponente retirar, pois a derrota se dá para aquele que retira o último palito. Estas retiradas só podem ser feitas em uma das filas a cada vez e o jogador precisa tirar pelo menos um palito. Também é permitido que o jogador retire todos os palitos de uma fila em sua vez de jogar.

O fato interessante é que se na sua vez de jogar você conseguir deixar uma certa configuração de palitos na mesa de modo que, se depois disso você jogar sem erro, seu oponente não possa ganhar, independentemente das jogadas que ele faça, esta configuração será chamada uma combinação segura.

Em linhas gerais, a demonstração deste fato consiste em mostrar que se o jogador A deixa uma “combinação segura” de palitos na mesa, então B, no seu próximo movimento, seja ele qual for, não poderá deixar uma combinação segura. Além do mais, após o movimento de B, o jogador A novamente poderá deixar uma nova combinação segura e continuar o jogo.
 

Suponha que a primeira fila tenha P palitos, a segunda S, e terceira, T palitos. Escreva estes números P, S e T em notação binária e disponha-os em 3 linhas horizontais de tal modo que as casas das unidades se correspondam.

Por exemplo:

P = 9 palitos, S = 5 palitos, T = 12 palitos

Teremos:

9 = 1.2³ + 0.2² + 0.2 +1.2⁰, isto é,

P = 1001 em notação binária.

Usando o mesmo raciocínio, temos, em notação binária, S = 101 e T = 1100.

Disposição:

Se a soma dos algarismo das casas correspondentes de P, S e T for igual a 0 ou 2 (i.e., congruente a 0 mod 2) então esta será uma combinação segura.

No caso:

Observe que, dados dois números em notação binária, podemos determinar um terceiro que dê uma combinação segura, e de maneira única. Basta escrevê-lo de tal forma que, ao somarmos as casas correspondentes, obtenhamos 0 ou 2.

Por exemplo: Dados, já em notação binária, P = 100 e S = 11; podemos determinar T da seguinte forma:

onde X, Y, Z só podem ser 0 ou 2. Neste caso, por uma fácil verificação, T = 111.

Não esqueça que T é dado em notação binária, logo, só pode ter os algarismos 0 ou 1.

Em outras palavras, se P, S e T formam uma combinação segura, então quaisquer dois deles determinam o terceiro.

Observações:

1)      Como toda regra tem sua exceção, também são combinações seguras:

a)      P = 1, S = T = 0

b)      P = S = T = 1

2)      Uma combinação segura particular é aquela em que duas filas têm o mesmo númro de palitos (P = S) e a terceira não tem nenhum (T = 0), com exceção de P = S = 1 e T = 0.

Enunciaremos agora os dois teoremas que ensinam você a ganhar.

Teorema 1: Se o jogador A deixa uma combinação segura na mesa, então B não conseguirá deixar outra combinação segura na sua vez de jogar.

A demonstração é fácil: basta ver que B pode mexer em apenas uma fila de palitos e tem que retirar pelo menos um. Sabendo-se que, dados os números de palitos de duas filas, determina-se unicamente o número de palitos da terceira e considerando-se a A deixou uma combinação segura, qualquer movimento que B faça desmanchará esta combinação segura. Logo, o jogador B não poderá deixar uma nova combinação segura.

Teorema 2: Se o jogador A deixa uma combinação segura na mesa e B retira palitos de uma certa fila, então A poderá recompor uma combinação segura retirando palitos de uma das filas restantes.

Antes da demonstração, veja um exemplo. Suponha que A deixou a seguinte combinação segura na mesa:

Suponha, também, que B retira 2 palitos da 1ª fila. Restam:

Se o jogador A quer deixar uma combinação segura, é claro que ele terá que retirar palitos da 3ª fila, que contém 12 palitos. Vamos determinar o número de palitos que devem restar na 3ª fila (T’) para que A consiga uma combinação segura (observe que T’ tem que ser menor que T).

Dados:

Ora, para que PST seja uma combinação segura, temos as seguintes possibilidades para XYZ:

XYZ = 000 (incompatível com o problema)

XYZ = 202 (incompatível também)

XYZ = 220 (idem)

XYZ = 200 (idem)

e outras.

Prosseguindo neste raciocínio, concluímos que o único valor de XYZ compatível com o problema é 222; Portanto, T’ = 0010, ou seja, 2 palitos. Assim, o jogador A tem que retirar 10 palitos da 3ª fila para obter novamente uma combinação segura.

Agora, a demonstração do teorema 2.

Primeiramente, suponha que o jogador A deixou na mesa uma combinação segura. Daí, B escolhe uma das filas, por exemplo, a primeira, e retira um certo número de palitos dela. Observe que, quando um número diminui, a mudança que ocorre em sua representação binária, olhando da esquerda para a direita, é algum 1 que passa para 0 (caso contrário, o número estaria aumentando). Considere este primeiro algarismo no qual ocorre mudança de 1 para 0. Decorre do fato do jogador A ter deixado uma combinação segura que na casa correspondente ao algarismo que sofreu mudança, apenas um número dos dois restantes (P, S ou T) vai conter o algarismo 1 (nunca os dois ao mesmo tempo).

Agora, A escolhe este número e coloca zero na casa onde o algarismo 1 estiver, tomando o cuidado de alterar ou não os algarismos à direita desta casa neste mesmo número (de 0 para 1, ou de 1 para 0) de modo a obter novamente uma combinação segura.

Para ilustrar::

O que aconteceu na verdade foi que o jogador A deixou na mesa o número de palitos cuja representação binária é o número resultante das alterações feitas por ele ao armar uma nova combinação segura.

No caso:

Qualquer que seja a próxima jogada de B, por um raciocínio análogo, não impedirá A de fazer uma nova combinação segura, retirando os palitos de maneira conveniente. Deste modo, o jogador A fatalmente ganhará o jogo, observando as seguintes propriedades e estratégias.

I - Suponha que o jogador A, ao deixar uma combinação segura na mesa, retira todos os palitos de uma certa fila. Então, certamente as outras duas filas terão o mesmo número de palitos.

II - Suponha que o jogador B retira todos os palitos de uma das filas. Então, as duas outras terão números diferentes de palitos e, assim, o jogador A poderá igualá-las, deixando na mesa uma combinação segura.

III - Suponha que, anos após alguma das filas ter seu número de palitos reduzido a zero, o jogador B deixe uma das filas restantes com apenas 1 palito. Então, basta A tirar todos os palitos da outra fila, deixando que aquele último seja retirado por B e, conseqüentemente, fazendo com que B perca o jogo.

IV - Suponha que, uma das filas ter seu número de palitos reduzido a zero, o jogador B “zera” outra fila. Então, basta A deixar apenas um palito na fila restante, fazendo também com que B perca o jogo.

V - Suponha que o jogador A deixou alguma fila com apenas um palito. Então, ocorre uma das três possibilidades:

a)      as duas outras filas têm um palito cada uma;

b)      as duas filas não têm nenhum palito;

c)      as duas outras filas têm números diferentes de palitos uma da outra que, por sua vez, não serão 0 ou 1 simultaneamente.

Resumindo: O jogador que conseguir manter uma combinação segura na mesa ganha o jogo. Assim sendo, se a primeira disposição dos palitos na mesa formar uma combinação segura, a primeira pessoa a jogar vai desmanchar esta combinação segura. Logo, o segundo a jogar terá a sorte de poder recompor uma combinação segura e, se não errar, ganha o jogo. Da mesma forma, se a primeira disposição dos palitos na mesa não formar uma combinação segura, o primeiro a jogar poderá compor uma combinação segura e, novamente, se não errar, ganha o jogo.

Portanto, ganhar (ou não) depende da probabilidade de se ter uma combinação segura na primeira disposição dos palitos na mesa. E também, de entender este artigo.

Ref.:

Charles L. Bouton – Annals of Mathematics, ser. II, vol. 3, Nº 1, Oct. 1901, p. 35 (Nim, a game with a Complete Mathematical Theory).

Resta-um, Resta-zero e a operação Nim

Carlos Augusto Isnard Instituto de Matemática Pura e Aplicada Rio de Janeiro – RJ

Uma variante do jogo do NIM é praticada nas praias brasileiras, com os palitos substituídos por pontos marcados na areia que vão sendo apagados pelos jogadores. O jogo se inicia com seis filas horizontais que têm respectivamente 6, 5, 4, 3, 2 e 1 pontos.

. . . . . .
. . . . .
. . . .
. . .
. .
.

  Este jogo é, às vezes, chamado o Resta-um.

Os praticantes do jogo conhecem de memória as “combinações seguras” como P, S, T iguais, 1, 2, 3 ou 1, 4, 5 ou 3, 5, 6 ou n, n, 0 (n 2), etc. O artigo anterior apresenta uma interessante caracterização matemática dessas combinações seguras, através da representação dos números na base 2.

Mesmo havendo uma quantidade arbitrária de filas, a disposição na base 2, descrita pelos autores, serve ainda para caracterizar as combinações seguras: a combinação será segura quando a soma dos algarismos de cada casa for par, isto é, quando cada coluna vertical tiver uma quantidade par de algarismos 1. Existe uma exceção a esta regra que ocorre quando nenhuma fila horizontal tiver mais do que um ponto: uma quantidade ímpar de filas com um só ponto é obviamente uma combinação segura para o Resta-um.

O Resta-zero é outro jogo, cujas regras são as mesmas do Resta-um, exceto pela definição do vencedor: na regra do Resta-zero o vencedor é quem conseguir apagar o último ponto. As combinações seguras do Resta-zero têm uma caracterização simples: são as mesmas do Resta-um sem a exceção desagradável no caso em que nenhuma fila tem mais do que  um ponto. É óbvio que uma quantidade par de filas de um só ponto é uma combinação segura para o Resta-zero.

Existe uma interessante operação comutativa e associativa relacionada a esses jogos, a operação Nim, definida no conjunto Z⁺ = {0, 1, 2, ...} por P  S = T P, S, T é combinação segura para o Resta-zero (o que significa que é também combinação segura para o Resta-um, se P 2 ou S 2).

Temos: n  0 = n = 0 n e n n = 0, para qualquer n Z⁺, de maneira que na operação , Z⁺ é um grupo comutativo com identidade 0 e tal que o inverso de cada n é o próprio n (o grupo Nim).

Havendo m filas com p₁, p₂,  ..., p_m pontos, então essa combinação é segura para o Resta-zero se e somente se :

ou seja, se e somente se .

Por exemplo 2, 3, 4, 5 é combinação segura (para o Resta-zero, logo também para o Resta-um), porque 2  3  4 = 5 (cálculo: 2  3 = 1 e 1  4 = 5, pois 1, 2, 3 e 1, 4, 5 são combinações seguras conhecidas).

Da mesma maneira 1, 5, 4, 3, 2, 1 é combinação segura para ambos os jogos porque 1  5  4 = 0 e 1 3  2 = 0 (pois 1, 4, 5 e 1, 2, 3 são combinações seguras).

A seguinte regra é útil quando os números são muito grandes: Se P < 2^k, então 2^k + P = 2^k  P (P, k  Z⁺). Em conseqüência, se P < 2^k e S < 2^k então 2^k + P, 2^k +S, T é combinação segura, se e somente se P, S, T é combinação segura (P, S, T, k  Z⁺).

Como aplicação, algumas computações Nim:

19, 21, 6 é combinação segura porque 19  21 = (16  3)  (16  5) = 3  5 = 6; podemos calcular 3 5 = (2  1)  (4  1) = 2  4 = 6 (usamos várias vezes 2^k  P =  2^k + P se P <  2^k, P, k  Z⁺).

No filme “O ano passado em Marienbad” o jogo aparece várias vezes com cartas de baralho no lugar de pontos ou palitos, iniciando-se com a combinação 7, 5, 3, 1 que é uma combinação segura porque 1  3  5  7 = 2  5  7 = 2  (4  1)  (4  3) = 2  1  3 = 0 ou porque na base 2 temos

Referências: