Quarta-feira, 11 de Fevereiro de 2009

O jogo do NIM - primeira versão

A revisão de um filme da década de 60 do século passado, do realizador francês Alain Resnais (o filme é "L`année dernière à Marienbad"), despertou-me para a importância dos jogos nas sociedades humanas. Um dos diálogos entre duas das personagens do filme referido (vou citar de memória) dizia o seguinte:

 

- Conheço um jogo em que eu ganho sempre.

- Se você ganha sempre não é um jogo.

- É um jogo mas eu ganho sempre.

 

Que jogo era este? É um jogo bastante antigo, possivelmente de origem chinesa. Para o jogar são precisos apenas dois jogadores. É bastante simples e tem variadas versões e poucas regras. Pode ser jogado com números, traços, fósforos, moedas, botões, sementes,... uma infinidade de objectos.

 

Vamos apresentar duas versões.

 

A primeira versão consta apenas de um conjunto com um número variado de objectos alinhados.

Regras: Ganha quem tirar o último objecto; cada jogador pode tirar até três objectos em cada jogada.

 

Vamos começar por considerar 20 objectos:

 

¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶    

1     2     3     4     5     6     7     8     9    10   11   12  13     

 ¶    ¶     ¶     ¶     ¶     ¶     ¶

14  15    16   17   18  19   20

 

Como ganha quem tirar o último objecto, vamos tentar descobrir como ganhar se for o nosso adversário a iniciar o jogo (jogador A). Que objectos devemos tirar para ganhar?

 

- 1ª jogada: o nosso adversário (jogador A) tira, por exemplo 3 objectos e nós 1. A situação fica do seguinte modo:

 

¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶     ¶    

5     6     7     8     9    10   11   12  13     
¶     ¶      ¶     ¶     ¶     ¶     ¶

14  15    16   17   18   19    20

 

- Na segunda jogada, o jogador A tira 2 objectos e nós também 2. A situação fica assim:

 

¶     ¶     ¶     ¶     ¶    ¶     ¶      ¶     ¶     ¶     ¶     ¶

9    10   11   12  13    14  15    16   17   18   19    20

 

- 3ª jogada: o jogador A tira 1 objecto, por exemplo, e nós tiramos 3. A situação fica como segue:

 

     

¶       ¶     ¶      ¶     ¶     ¶     ¶     ¶

13    14   15    16   17   18   19    20

 

- Na jogada seguinte, o nosso adversário tira, por exemplo, 3 objectos e nós 1. Neste momento já perdeu. A situação fica assim:

 

¶      ¶     ¶     ¶

17   18   19    20

 

- Na última jogada, cumprindo sempre as regras do jogo, sela qual for o número de objectos retirados pelo nosso jogador A, nós tiramos sempre o último e ganhamos.

 

Impõe-se uma pergunta: Qual é a estratégia ganhadora?

 

- Basta analisar as jogadas. Nós tiramos sempre os objectos que completam os múltiplos de 4: 4 - 8 - 12 - 16 - 20. Porquê? deixamos a interrogação.

 

Se formos nós a iniciar o jogo, como ganhar? É possível ganhar sempre?

 

Façamos uma experiência com 20 objectos. Vamos simular um conjunto de jogadas:

 

1ª jogada - Vamos tirar 3 objectos, por exemplo. Se o nosso adversário tirar igualmente 3 objectos, a situação o jogo fica com últimos 14.

Na 2ª jogada nós tiramos 2 objectos e a partir deste momento temos uma situação ganhadora.

Vamos tirar nas jogadas seguintes os objectos necessários para completar os múltiplos de 4, tal como no caso anterior.

 

As estratégias ganhadoras dependem do número de objectos com que estamos a jogar. Vamos utilizar, por exemplo, 37 objectos:

 

&      &     &     &      &     &     &     &     &     &     & 

1       2     3     4       5     6      7     8     9     10   11


&      &     &     &      &     &     &     &     &     &     &                   

12   13    14   15    16    17    18   19    20   21   22      


&      &     &     &      &     &     &     &     &     &     &      

23    24   25   26     27   28    29   30    31   32    33


&      &     &     &      

34    35   36    37

 

Vamos simular o jogo, mantendo sempre as regras iniciais e com o nosso adversário a iniciar o jogo.

- Para iniciar o jogador A (nosso adversário) tira, por exemplo 2 objectos. Quantos objectos devemos tirar nós para construir ou iniciar uma estratégia ganhadora?

Se analisarmos a situação concluiremos que a nossa jogada deve ser tirar 3 objectos; portanto até ao 5º objecto.

A partir daqui as nossas jogadas devem orientar-se no sentido de tirarmos os objectos números 5 - 9 - 13 - 17 - 21 - 25 - 29 - 33 - 37, ou seja múltiplo de 4 mais 1.

Porquê? Mais uma vez deixamos a interrogação para os leitores.

E se formos nós a iniciar o jogo? Qual a estratégia ganhadora?

Mais uma vez vamos fazer uma simulação:

- Se tirarmos, por exemplo, três objectos (3) e o nosso adversário tirar também 3, que jogada devemos fazer a seguir para construir uma estratégia ganhadora?

É evidente que a nossa 2ª jogada deve ser 3 e ficamos na posição de controlar o evoluir do jogo, tal como na situação anterior.

Já dissemos que o número de objectos condiciona a estratégia.

Um pequeno desafio para os leitores:

 

- Que números devemos tirar para construir uma estratégia ganhadora, se o nosso adversário for o primeiro a tirar objectos e estivermos a jogar com 43 objectos? E se começarmos nós o jogo?

 

Nota: A 2ª versão será publicada no próximo artigo.

 

 

publicado por Frantuco às 23:15
link do post | comentar | favorito
|

.mais sobre mim

.pesquisar

 

.Janeiro 2010

Dom
Seg
Ter
Qua
Qui
Sex
Sab
1
2
3
4
5
6
7
8
9
10
12
13
14
15
17
18
19
20
21
22
23
25
26
27
28
29
30
31

.posts recentes

. O Ano 2010 e as potências...

. O Ano de 2010 e as potênc...

. O Ano de 2010 e as potênc...

. As cidades, as vilas, as ...

. O caderno de exercícios "...

. Os contos das noites de i...

. Mais uma vez o regresso à...

. Grandes Matemáticos - Pit...

. Cereais, legumes, medidas...

. Memórias I

. O Labirinto

. Sapos e rãs ou ovelhas e ...

. Rãs e Sapos ou Ovelhas e ...

. HIPÁTIA DE ALEXANDRIA

. A decomposição de números...

. Grandes Matemáticos - Leo...

. Os algoritmos - o número ...

. Os algoritmos - o código ...

. Os caminhos do João

. As probabilidades no dia ...

. As probabilidades no dia ...

. O tempo, os relógios e as...

. As probabilidades e os an...

. Vamos aos gambuzinos

. O jardim de pedra

. De novo as eleições - as ...

. Os frutos secos do Natal

. As caminhadas, as pesagen...

. O Método de Hondt

. O jogo do NIM - segunda v...

. O jogo do NIM - primeira ...

. A travessia da ponte - no...

. Algoritmos - A fórmula de...

. Algoritmos - O teorema de...

. Um problema de idades

. INVERSÕES

. A travessia da ponte

. O carteiro, as idades e o...

. A herança do lavrador

. O relógio, as horas e os ...

. A decomposição de números...

. O problema das idades

. CAPICUAS

. DINHEIRO FALSO

. O Pombal das cem pombas

. Números e cálculo mental

. Poesia Matemática

. Os algoritmos - raiz quad...

. Os algoritmos - raíz quad...

. Os algoritmos - algoritmo...

.arquivos

. Janeiro 2010

. Dezembro 2009

. Novembro 2009

. Outubro 2009

. Agosto 2009

. Julho 2009

. Junho 2009

. Maio 2009

. Abril 2009

. Março 2009

. Fevereiro 2009

. Janeiro 2009

. Dezembro 2008

. Novembro 2008

. Outubro 2008

. Setembro 2008

. Agosto 2008

. Julho 2008

.palavras-chave

. todas as tags

.links

.visitas

track web site traffic
Netflix Rental
blogs SAPO

.visitantes