Um espaço lúdico da matemática e para a matemática mas onde o exercício livre da opinião e crítica é condição primordial. Aberto a ouvir, opinar, criticar e ser criticado...

Truques de matemática

terça-feira, 7 de abril de 2009

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.

Jogo do NIM (versão 1)

Um problema de divisão
Existe um jogo de palitos, tradicionalmente famoso proveniente da China e
chamado JOGO DO NIM.
O jogo, disputado por dois jogadores, é estabelecido da seguinte forma:
1. a quantidade de palitos deve ser um número ímpar;
2. cada jogador retira, por sua vez, uma determinada quantidade de palitos,
sendo que esta quantidade deve ter um limite mínimo e um máximo, previamente
fixados;
3. perde aquele que retirar o último palito.
Estratégia para vencer:
a) Determinada a quantidade de palitos que comporão a fileira e também
determinada a quantidade máxima para que o jogador possa retirar em uma
jogada, temos então um probleminha de divisão e resto.
Como fazer? Para ficar mais claro vamos exemplificar o problema:
Seja 33 a quantidade de palitos na fileira e 4 a quantidade máxima de palitos a
ser retirada:
Some 4 com 1 , isto dará 5, agora, veja o resto da divisão de 33 por 5, que é igual
a 3, ou seja, você tem seis grupos de 5 palitos e mais um grupo de 3, neste grupo
de três, retire um, que será o último palito.
Seu jogo terá o seguinte formato:
|| ||||| ||||| ||||| ||||| ||||| ||||| |
Quem iniciar o jogo, basta retirar os dois palitos iniciais, e depois retirar a
quantidade de palitos que faltam para se eliminar o outro grupo (isto é, retira a
quantidade que faltar para 5), assim, eliminará também o último grupo, restando 1
palito para a derrota de seu oponente.

Jogo do NIM (versão 2)

Nesta versão, este jogo consiste em colocarmos sobre uma mesa três fileiras
com quantidades diferentes de palitos. Este jogo é para dois participantes, sendo
assim, perde o que retirar o último palito. É necessário seguir as seguintes regras:
- Cada jogador, em cada jogada, deverá escolher uma fileira para retirar os palitos,
sem restrição de quantidade ( no mínimo um e no máximo toda fileira).
- Os jogadores alternam suas jogadas.
Exemplo:
Fileira 1: | | | | | | | | | (9 palitos)
Fileira 2: | | | | | | (6 palitos)
Fileira 3: | | | | (4 palitos)
Estratégia para vencer o jogo:
- No exemplo citado acima, converteremos as quantidades de palitos em cada fileira
por sua representação em binário:
Fileira 1: 1 0 0 1 (9 em binário)
Fileira 2: 1 1 0 (6 em binário)
Fileira 3: + 1 0 0 (4 em binário)
1 2 1 1
somando-se as colunas teremos um resultado com dígitos entre 0 e três, no caso,
obtivemos “1 2 1 1”.
Chamaremos de combinação segura, aquela que obtiver como resultado das somas
das colunas apenas os dígitos “2” e “0”.
Para vencer o jogo, basta o jogador transformar este resultado (1 2 1 1) numa
combinação segura, retirando palitos.
Observe que, como não se pode adicionar palitos, teremos que retirar palitos da
fileira 1, de modo que tenhamos uma combinação segura.
XXX
1 1 0
1 0 0
2 2 0
logo, na fileira 1 devemos ter “0 1 0”, que representa 2 palitos (verifique que
esta é a única solução possível). Para isso, basta retirarmos 7 palitos da fileira 1.
Após conseguir uma combinação segura, o próximo jogador não poderá
fazer uma nova combinação segura. Não é difícil observar isso, pense que em
binário, para diminuir um número somente podemos mudar de “0” para “1” e viceversa,
logo, pelo menos um “1” se tornaria “0”, e esta coluna, que antes tinha soma
“2” passa a Ter soma “1” que não é um dígito de combinação segura.
Até agora conseguimos observar que se um jogador fizer uma combinação
segura, poderá mantê-la, e por que então ele ganhará o jogo?
Adicionaremos algumas exceções de combinação segura: se a soma der 3,
isto é , linha1: 1 palito, linha 2: 1 palito e linha 3: 1 palito será uma combinação
segura, e a menor combinação segura será a de apenas um palito no total. Também,
como exceção, se a soma das linhas derem 2, não será uma combinação segura.
Vamos analisar a que ocorrerá: seja P uma combinação segura e I uma não
segura, A o jogador que deixa na mesa uma combinação segura e B o outro jogador,
teremos o seguinte:
P -> I -> P -> I ... como os palitos estão diminuindo, poderemos chegar as
seguintes combinações finais que garantirão o desfecho do jogo:
a) Se uma das linhas for eliminada pelo jogador B, como ele não consegue
deixar uma combinação segura, significa que nas linhas restantes existe um
número diferente de palitos, logo, basta o jogador A igualá-los, fazendo
assim, uma nova configuração segura (salvo a única exceção já citada).
b) Se o jogador A eliminar uma fila, significa que temos a configuração final do
item anterior, ou seja, ficamos com 2 filas com a quantidade igual de palitos.
Analisando os casos a) e b), a sequência vai convergir para os seguintes
resultados:
- O jogador A compõe a menor configuração segura do tipo soma = “dois” e “zero” ,
que é deixar dois palitos em cada fileira, nesta condição, o jogador B executará
mais uma jogada e permitirá ao jogador A compor a última e menor combinação
segura que é a de apenas um palito na mesa, e ganhará o jogo.
- O jogador B elimina uma fileira inteira, assim, restando palitos apenas numa fileira,
basta o jogador A deixar somente um palito nesta, e vencerá.
c) Se nenhuma fileira for eliminada, a menor configuração segura do tipo
soma=”0” ou “2”, será: as linhas com 1, 2 e 3 palitos, respectivamente, nesta
situação, o jogador B, se retirar uma linha inteira, recorre no caso a) e
perderá o jogo, se retirar um palito da linha que tem 3, deixará duas linhas
com 2 palitos, levando o jogador A ao procedimento do ítem b) ; finalizando,
se o jogador B retirar ou dois palitos da linha que tem três, ou um palito da
linha que tem dois, permitirá ao jogador A realizar a configuração segura de
soma=”3” (ou seja, um palito em cada linha), e vencerá o jogo em mais uma
jogada.
Conhecendo esta estratégia, basta conhecer os representantes “binários” ,
fazer algumas continhas de cabeça e vencer o jogo .

Bibliografia:
RPM – Revista do Professor de Matemática Vol 6.
Sociedade Brasileira de Matemática
1º semestre de 1985

3 comentários:

DD disse...

adoro este teu blog....

tem jogos de matemática. A melhor forma de aprender.

tinha sempre nega a matemática e 16,17 a fisica, porque?

porque a fisica se baseia na experiencia , nos problemas.

no nosso tempo a matemática era de arrancar os cabelos.

Carlos disse...

http://images.orkut.com/orkut/photos/OQAAAFvsHz6H1DnhlnUHki3jAIRuUbpFLnZ6QuU-i1wQYGzeptkyqY2RUlH1Qw1rFGBxy47AfW66PdLHz_2Or2GIJFsAm1T1UBRxMeU6YTjQLhuOA26VetEsJRpO.jpg


Bela resolução!

Carlos disse...

http://images.orkut.com/orkut/photos/OQAAAFvsHz6H1DnhlnUHki3jAIRuUbpFLnZ6QuU-