Sexta-feira, 20 de Fevereiro de 2009

O jogo do NIM - segunda versão

Tal como dissemos no artigo anterior, o jogo do NIM tem algumas versões. Esta segunda versão que vamos tratar é uma das mais conhecidas e é a que é referida no filme "L`année dernière à Marienbad".

 

 

Na primeira versão apresentámos o jogo com uma só linha.

Na segunda versão pode haver duas linhas ou dezenas delas.

As regras consistem em tirar tantos objectos quantos se quiser, mas de uma só linha e ganha o jogador que tirar o último objecto.

 

A versão mais simples poderá ser o jogo com duas linhas e apenas um objecto em cada uma:

 

 

Neste caso perde o jogador que começa o jogo. É fácil de ver porquê: o jogador A, que começa só pode tirar um objecto de uma linha. Logo, a seguir, o segundo jogador tira o segundo e último objecto  e ganha.

Vamos imaginar uma versão mais complicada: duas linhas com dois e sete objectos, respectivamente:

 

¶    ¶  

¶    ¶     ¶     ¶     ¶     ¶     ¶ 

 

Neste caso, só temos a certeza de ganhar se formos nós a começar o jogo. Como?

- 1ª jogada - tiramos cinco (5) objectos da segunda linha e fica assim:

 

¶    ¶

¶    ¶

 

- 2ª jogada - o nosso adversário tem duas hipóteses: ou tira 1 (um) objecto de uma linha e nós tiramos também 1 (um) objecto da outra linha e fica assim:


 

- A jogada a seguir corresponde à versão mais simples: o nosso adversário tira um objecto e nós tiramos o outro e ganhamos.

 

 - 2ª jogada- o nosso adversário tira 2 (dois) objectos de uma linha e nós tiramos os outros dois da outra linha e ganhamos.

 

Vamos imaginar que nos propunham um jogo com três (3) linhas, organizadas do seguinte modo:

 

¶     ¶     ¶

¶     ¶     ¶     ¶    ¶

¶     ¶     ¶     ¶    ¶     ¶     ¶

 

 

 Considerando que       101 = 10

                                     102 = 100

                                     103 = 1000

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

então

75 048 = 7 x 104 + 5 x 103+ 0 x 102+  4 x 101+ 8

 

Tal como escrevemos um número na base 10 podemos utilizar outras bases para escrever um número.

Consideremos a seguinte tabela:

 

Números base 2 base 5 base 8 base 10 base 12
7 111 12 7 7 7
14 1110 24 16 14 12
21 10101 41 25 21 19
36 100100 121 44 36 30
49 110001 144 61 49 41

 

Como se verifica escrevemos 5 números na base 10 em outras bases. Se observarmos bem verificamos que existe uma base que se destaca das outras todas pela sua simplicidade. É a base 2 que precisa apenas de dois (2) símbolos para escrever qualquer número.

Como passar um número da base 10 para qualquer base? Vamos fazer um exemplo para a base 2. Fazem-se divisões sucessivas por 2. Vamos passar o número 43, para a base 2:

  

O número 43 escreve-se na base 2 começando no último quociente como 101011, que também se pode escrever, tal como fizemos para o 75 048 na base 10:

 

101 011 = 1 x 25 + 0 x 24 + 1 x 23 + 0 x 22+ 1 x 21 + 1

 

Se fizermos os cálculos verificamos que o número 43 na base 10 se pode escrever do seguinte modo:

 

43 = 32 + 8 + 2 + 1 ou seja  25 = 32   //   23 = 8   //   21 = 2    //    20 = 1

Esta igualdade tem a ver com o teorema que afirma que "Um número inteiro é uma potência de dois (2) ou a soma de duas ou mais potências de dois (2)". A tabela que segue mostra isso mesmo:

 

 

Números              Potências de 2  Números na base 2
64 32 16 8 4 2 1
2           1 0               1  0
6         1 1 0               1  1  0
18     1    0 0 1 0               1   0  0  1  0
19     1 0 0 1 1               1  0  0  1  1
26     1 1 0 1 0               1  1  0  1  0
44   1 0 1 1 0 0               1  0  1  1  0  0

 

Para escrever qualquer número inteiro na base dois (2) basta descobrir quais as potências de 2 que somadas dão o número escolhido. Vejamos o 44.

 

            44 = 32 + 8 + 4, mas não tem o 16, nem o 2, nem o 1. Por isso, colocando por ordem as potências de 2, na posição do 32, do 8 e do 4 aparece 1 e na posição do 16, do 2 e do 1 aparece 0.

Assim 44 na base 2 escreve-se 1 0 1 1 0 0.

 

O sistema binário ou de base 2 tem variadissimas aplicações especialmente em computação. A sua utilização no jogo do NIM permite-nos encontrar uma estratégia ganhadora, utilizando a lógica do sistema binário. Vamos voltar à proposta das três linhas de objectos. Se ainda se lembram tínhamos três linhas com 3, 5 e 7 objectos. Qual a estratégia ganhadora?

Vamos construir uma tabela com estes números:

 

Números Base 2
quatro - 4 dois - 2 um - 1
3 0 1 1
5 1 0 1
7 1 1 1
  0 0 1

 

Para que serve esta tabela?

Temos os números de objectos escritos na base 2. Temos as colunas somadas, cujos resultados são da esquerda para a direita 0, 0, 1. O que significam estes valores? Se a soma é par colocamos 0, se for impar colocamos 1.

No jogo do NIM a estratégia ganhadora implica que todas as "somas" sejam 0 (pares). O que temos não é uma situação ganhadora.

O que devemos fazer se formos nós a jogar?

Temos duas jogadas possíveis. Tirar um objecto da 1ª linha, onde ficariam dois objectos. A situação ficaria:

Números Base 2
quatro - 4 dois - 2 um - 1
2 0 1 0
5 1 0 1
7 1 1 1
  0 0 0

 

Poderíamos ter feito outra jogada. Qual? Deixo ao leitor a sua descoberta.

Vamos fazer as jogadas possíveis utilizando os objectos:

                                                    

¶    ¶    ¶

¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶    ¶    ¶

 

- A primeira jogada é tirar um objecto da primeira linha para obtermos uma posição ganhadora. A situação fica assim:

 

¶    ¶

¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶    ¶    ¶

 

- Agora é o nosso adversário a jogar. Imaginemos que ele tira 3 objectos da 3ª fila.

Que jogada devemos fazer?

Podemos tirar, por exemplo, os dois objectos da 1ª linha e a posição fica assim:

 

¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶ 

 

-.Agora é novamente o nosso adversário a jogar. Se estivesse no lugar dele que jogada faria? Vamos imaginar que tira três objectos da 1ª fila. O que fazemos nós? Para continuarmos a manter a posição vencedora temos de tirar dois objectos na 2ª fila e a posição fica como segue:

 

¶    ¶

¶    ¶

 

- Agora é novamente o nosso adversário a jogar. E já perdeu. Se tirar dois objectos de uma das filas, nós tiramos os outros dois da outra fila e ganhamos.

Se tirar um objecto de uma fila, nós tiramos um objecto da outra e fica um objecto em cada fila. Como a seguir joga ele e tem de tirar um objecto de uma fila, nós tiramos o outro e ganhamos.

 

Para terminar, vamos deixar um desafio aos leitores. Não se devem esquecer de organizar uma tabela para encontrar a estratégia ganhadora.

- Somos nós a jogar e temos esta posição, que queremos transformar em posição ganhadora. Que jogada fazer? E como desenvolver o jogo perante o nosso adversário?

 

¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶

¶    ¶    ¶    ¶    ¶

 

E se a situação fosse a seguinte, um pouco mais complicada?

 

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

¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶    ¶

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

¶    ¶    ¶    ¶    ¶

 

Fico à espera das vossas soluções.

 

publicado por Frantuco às 11:35
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

blogs SAPO