O JOGO DO NIM COM VELAS

Paulo Antonio Silvani Caetano e Angélica Pereira dos Santos

Como vencer o jogo do NIM ? 

(voltar para o jogo do Nim inicial)

   A idéia de poucas velas acesas está relacionada com a idéia de poucas velas acesas em duas fileiras apenas, já que com uma única jogada é possível apagar todas as velas da terceira fileira restante.

   Quando escrevemos poucas velas acesas estamos pensando em uma das três possibilidades seguintes:

• duas fileiras totalmente apagadas, não importando a quantidade de velas acesas na fileira restante; 
• duas fileiras com apenas uma vela acesa cada, não importando a quantidade de velas acesas na fileira restante;  
• uma fileira totalmente apagada e outra fileira com apenas uma vela acesa, não importando a quantidade de velas acesas na fileira restante;

    É muito fácil ganhar quando jogamos diante de uma configuração com poucas velas acesas. Experimente!!!

   Após aprender a ganhar com poucas velas acesas, o próximo passo é aprender a estratégia que reduz o número de velas acesas com segurança, isto é, que reduz o número de velas acesas possibilitando, em algum momento, jogarmos em vantagem diante de uma configuração com poucas velas acesas. 

   Tal estratégia passa pela representação binária dos números naturais e foi desenvolvida pelo matemático francês Charles Leonard Bouton, por volta de 1902, na Universidade de Havard.  Confira a bibliografia abaixo.

   A idéa consiste em organizar as velas de cada fila em grupos com uma, duas, quatro, oito velas, etc. Chamaremos de candelabro cada um desses grupos, que comportam uma quantidade de velas que é uma potência de 2. 

  Os agrupamentos devem ser tais que cada candelabro fique totalmente aceso ou totalmente apagado. Por exemplo, para agrupar 13 velas acesas em potência de dois precisamos de um candelabro com uma única vela e esta esteja acesa, um candelabro de duas velas, ambas apagadas, um candelabro de quatro velas totalmente aceso e um candelabro de oito velas totalmente aceso. De fato,

13 = 8 + 4 + 1 .

   É importante ressaltar que, independente da quantidade de velas acesas, sempre é possível agrupá-las em potência de dois. Na Matemática isto significa representar a quantidade de velas acesas na forma binária. Por exemplo, a representação binária do número 13 é 1101, isto é, 

13 = 1·8 + 1·4+ 0·2 + 1·1 .

    Confira abaixo como fazer agrupamentos de velas acesas em potência de dois numa fileira de 15 velas.

    A segurança na redução do número de velas consiste em agrupar as fileiras de velas acesas em potência de dois, mantendo sempre a paridade dos candelabros acesos, isto é, o número de candelabros acesos de cada tipo deve ser par (zero ou dois no caso de jogo com três fileiras).  

    A contribuição do francês Charles Leonard Bouton foi mostrar o seguinte:

• diante de uma configuração pareada de candelabros acesos é impossível apagar velas sem quebrar a paridade.

• diante de uma configuração não pareada de candelabros acesos sempre é possível apagar velas e tornar a configuração pareada. 

    Isto significa que se o jogo se inicia com uma combinação não pareada, o primeiro jogador pode pareá-la na primeira jogada. O segundo jogador necessariamente vai desmanchar a paridade, de modo que, se o primeiro jogador não errar, ele irá vencer o jogo. Mas se o jogo iniciar com uma combinação pareada e o segundo jogador souber jogar (como é o caso do nosso programa) então o primeiro jogador irá perder. Como nosso jogo se inicia com uma combinação aleatória, a probabilidade do primeiro jogador encontrar uma combinação pareada para sua primeira jogada é 1/16.

    Melhor que explicar como apagar velas mantendo a paridade dos candelabros acesos é ver como o computador usa esta tática  para ganhar o jogo. Abaixo, o Nim é jogado com as velas agrupadas em potência de dois. Confira !!! 

(voltar para o jogo do Nim inicial)

Curiosidades e sítios relacionados

• No filme L´Année dernière à Marienbad (1961) (O Ano Passado em Marienbad), de Alain Resnais, aparece várias vezes uma versão do jogo do Nim.
• As primeiras referências européias do jogo do Nim datam do Século I. 
• Algumas referências indicam que nos tempos antigos os marinheiros se distraiam com o jogo do Nim em suas longas viagens. 
• http://ciencia.eciencia.pe.gov.br/mat/conteudo/nim.htm
• http://www.darkfish.com/nimskulls/nimskulls.html
• http://www.cut-the-knot.com/ctk/May2001.shtml
• http://www.cut-the-knot.com/nim_st.shtml
• http://king.2020tech.com/cgi-bin/nim/nim
• http://www.angelfire.com/ab/jogos/nim.html

(voltar para o jogo do Nim inicial)

Referências

[1] Raguenet, I. F. e Barrêdo, M. K., A Teoria Matemática do Jogo do Nim. Revista do Professor de Matemática, n^o 6, 1^o semestre de 1985.
[2] Bouton, C. L., Nim, a Game With a Complete Mathematical Theory. Annals of Mathematics, ser. II, vol. 3, n^o 1, oct.1901, pág. 35.

início desta página
Esta matéria foi apresentada para publicação em 29/05/2002 por Paulo Antonio Silvani Caetano (orientador) e Angélica Pereira dos Santos (estudante), do DM-UFSCar. Foram utilizados arquivos fornecidos pelos autores.
Publicado em 26/08/2002. Atualizado em 26/08/2002.