Comptes Rendus MATh.en.JEANS 04-05

 

Jeu de NIM

par

    Mickaël Carbonnier, Lucas Dufour, Geoffrey Kozak,
    Mélania Ricard, Adrien Santamaria et Violaine Solé
    du collége de Nézant à Saint-Brice sous forêt (Val d'Oise)
    &
    Anne Cassier, Sylvain Cassier et Madeleine Moscatelli
    du collège Charles Lebrun à Montmorency (Val d'Oise)

 

 

Enseignants : Yann BOURIT, Eric MARTINOD (Clg. Nézant) & Frédéric ALBERTINI, Christian GEORGES (Clg. Lebrun).

Chercheur : François PARREAU (Inst. Galilée, Univ. Paris 13, 93-Villetaneuse).

Jumelage MATh.en.JEANS entre les collèges L'Ardillière de Nézant à Saint-Brice sous forêt (95) et Charles Lebrun à Montmorency (95). Option 4ème scientifiqu et Atelier de Pratique Scientifique, année scolaire 2004-2005.

[Article vérifié et annoté : les passages entre crochets sont des éditeurs]
[ L'icone renvoie au Glossaire MATh.en.JEANS , à un document ]
[Article en cours d'analyse et de vérification : les passages entre crochets sont des éditeurs]

[Résumé (par les éditeurs). ]

Plan

  1. Les régles du jeu. Quelques parties en exemple. Qu'est ce qu'une position perdante ?
  2. Début de la construction de la table de stella. La position (1; 2 ; 3)
  3. Explication du jeu de nim a deux tas , continuation de la construction de la table de Stella.
  4. Régles de remplissage de la table de Stella.
  5. Les propriétes de la table.
  6. Décomposition des nombres en puissances de deux, plusieurs techniques...
  7. Le jeu de nim a quatre tas : des situations symétriques. Le jeu de nim à cinq tas.

[Le sujet]

[Ce texte reprend l'exposé présenté au congrès 2005].

1. Les règles du jeu

-Le jeu de Nim est un jeu qui se joue a deux joueurs.

-On place un certain nombre de tas (au choix) avec un certain nombre d'allumettes dans chaque tas (au choix) !

-Alternativement, chaque joueur enleve un certain nombre d'allumettes (une au minimum ou n'importe quel nombre même le tas complet, peut importe) mais dans un seul tas !!!!!!!!!

-Le jeu s'arrête lorsqu'il n'y a plus d'allumettes. Le gagnant est celui qui prend la dernière allumette.

Nous parlerons d'une situation perdante lorsque le premier joueur perd à tous les coups [quoiqu'il fasse] et donc le second gagne.

Exemple :  on part de la situation 1-2-3      

1er cas : [...]

1

2

3

  • le premier joueur prend l' allumette dans le tas de 1. Il reste 2-3 .

0

2

3

Le second prend une allumette dans le tas de 3, il reste donc 2-2

0

2

2

Puis le premier en prend 2 ou 1 allumette
(dans n'importe quel tas vu qu'il sont égaux)

0

0

2

le deuxième joueur n'a plus qu'à imiter le premier.

0

0

0

2ème cas : [...]

1

2

3

  • le premier joueur prend deux allumettes dans le tas de 2, il reste donc 3.

1

0

3

Le second prend 2 allumettes dans le tas de 3. Donc il reste 1-1.

1

0

1

Le premier joueur n'a plus le choix quoi qu'il fasse, il perd !

1

0

0

Le second prend la derniére allumette!

0

0

0

3ème cas [...]

1

2

3

  • le premier joueur prend qu'une seule allumette dans le tas de 2, il reste 1-1-3.

1

1

3

Le second n'a plus qu'a retirer les trois allumettes du tas de 3, il reste 1-1.

1

1

0

Et comme le 2éme cas, le premier joueur n'a plus le choix quoi qu'il fasse, il perd !

1

0

0

Le second prend la derniére allumette!

0

0

0

4ème cas [...]

1

2

3

  • le premier joueur prend les trois allumettes du tas de 3, Il reste 1-2.

1

2

0

Le second retire une allumette du tas de deux. Il reste 1-1.

1

1

0

Et comme dans les cas 2 et 3. Le premier joueur perd automatiquement!

1

0

0

Le second prend la derniére allumette!

0

0

0

5ème cas [...]

1

2

3

  • le premier joueur ne prend que deux allumettes dans le tas de 3, il reste 1-2-1.

1

2

1

Le second retire les allumettes du tas de 2, et laisse donc au premier la situation 1-1.

1

0

1

Et comme dans les 3 cas précédents, on n'a aucune possibilité de gagner.

1

0

0

Le second prend la derniére allumette!

0

0

0

6ème cas [...] 6ème cas

1

2

3

  • le premier joueur ne prend qu'une seule allumette dans le tas de 3, il reste 1-2-2.

1

2

2

Le second retire l'allumette du tas de 1, il reste donc 2-2.(vu dans le 1er cas).

0

2

2

Et comme dans le cas 1, le second joueur n'à plus qu'a imiter le premier, donc le 1er perd encore une fois!

0

0

2

Le second prend les derniéres allumettes !

0

0

0

Conclusion :
Le deuxiéme joueur prend toujours la dernière allumette, quelque soit ce que joue le premier.
On dira que la situation ( 1 ; 2 ; 3 ) est une situation perdante.

2. L'opération « stella »

1.    Définition de Stella :

Stella est le nom donné à l'opération, notée « * », où l'on voit les solutions perdantes.

Par exemple, jouer avec un tas de 1 allumette, un tas de 2 et un tas de 3 est une solution perdante, on écrit 1 * 2 = 3.

2.    La table de Stella :

a.     Définition :

On range tous les résultats dans un tableau appelé table de Stella. Elle se lit de la ligne horizontale qui a le nombre d'allumettes du premier tas, vers la ligne verticale qui a celui du deuxième tas. A l'intersection de ces lignes, on voit le nombre d'allumettes qu'il doit y avoir dans le troisième tas pour avoir une solution perdante (voir en bas de partie).

b.     Premières propriétés :

Il existe une diagonale de zéros qui forme un axe de symétrie de la table  car les positions 1 * 1 ; 2 * 2 ; 3 * 3 ; donnent la diagonale et pour chacune d'elles on revient à un jeu à deux tas identiques (solution perdante) entraînant donc 1 * 1 = 0 ; 2 * 2 = 0 ; 3 * 3 = 0 ; formant ainsi la diagonale de zéros.

Pour vérifier que c'est un axe de symétrie prenons une position perdante, par exemple la position 1 * 2 = 3. La position 2 * 1 = 3 est aussi une position perdante car lorsqu'on joue l'ordre des tas nest pas important, en effet le fait d'avoir le tas d'allumettes à droite, au milieu ou à gauche ne change pas le jeu.

De plus on peut déduire de ce qui précède qu'il y a plusieurs façons d'écrire la position 1 * 2 = 3 qui restera toujours perdante : 2 * 1 = 3 (pour l'axe de symétrie), mais aussi 1 * 3 = 2 ; 2 * 3 = 1 ; 3 * 1 = 2 ou 3 * 2 = 1.

c.     La table de Stella :

*

0

1

2

3

4


Voici le début de la table de Stella où sont notées :

Ø     la diagonale de zéros (en rouge) ;

Ø     les positions qui s’en déduisent (en vert) ;

Ø    la position perdante 1 * 2 = 3 avec toutes celles qui s’en déduisent (en bleu).

0

0

1

2

3

...

1

1

0

3

2

...

2

2

3

0

1

...

3

3

2

1

0

...

4

...

...

...

...

0

La même chose vue par le professeur :

si on a trois tas d'allumettes, avec :

  1.  1 allumette dans le premier tas,
  2.  2 allumettes dans le deuxième tas,
  3.  3 allumettes dans le troisième tas,

le premier joueur perd toujours car il ne peut pas ramasser la dernière allumette (à condition que le deuxième joueur joue bien).

On dira donc que la position (1 ; 2 ; 3) est une position perdante.

On a décidé de faire comme si c'était une opération et d'appeler cette opération « stella ». On la note *.

On a commencé par dire que, comme la position (1 ; 2 ; 3) est une position perdante, on dira que 1 * 2 = 3 (ou 1 « stella » 2 = 3).

Evidemment, pour pouvoir parler d'opération, il faudrait vérifier qu'il n'y a pas d'autre position perdante à trois tas avec 1 allumette dans le premier tas et 2 allumettes dans le deuxième. C'est ce qu'on a essayé de faire à la partie 4.

D'autre part, l'ordre des tas dans le jeu de Nim n'a aucune importance.

Donc, si la position (1 ; 2 ; 3) est perdante, les positions suivantes seront aussi perdantes :

( 1 ; 3 ; 2) est perdante donc 1 * 3 = 2

( 2 ; 1 ; 3) est perdante donc 2 * 1 = 3

( 2 ; 3 ; 1) est perdante donc 2 * 3 = 1

( 3 ; 1 ; 2) est perdante donc 3 * 1 = 2

( 3 ; 2 ; 1) est perdante donc 3 * 2 = 1

Puis nous avons décidé de mettre tous ces résultats dans une table, comme la table de Pythagore pour les multiplications.

* (stella)

0

1

2

3

0

1

3

2

2

3

1

3

2

1

Définition

D'une façon plus générale, on dira que n * p = q (ou n stella p = q) si la position ( n ; p ; q ) est perdante.

C'est à dire que si on a n allumettes dans le premier tas, p allumettes dans le deuxiéme tas et q allumettes dans le troisième tas alors le premier qui joue ne peut pas prendre la derniére allumette (à condition que le deuxiéme joueur joue comme il faut).

Le jeu de nim à deux tas.

Avant de s'intéresser au jeu de Nim à trois tas, nous avons d'abord joué avec deux tas.

Avec deux tas, c'est comme s'il y avait un troisième tas sans allumettes dedans, il compte comme zéro.

On a trois allumettes dans chaque tas

3

3

Le joueur A enlève une allumette dans le premier tas

2

3

Le joueur B l'imite avec l'autre tas

2

2

Le joueur A continue a prendre dans le premier tas

1

2

Le joueur B imite toujours l'autre joueur

1

1

Le joueur A prend une allumette

0

1

Le joueur B prend la dernière allumette

0

0

LE JOUEUR B GAGNE !!!!!

On a remarqué que si il y avait le même nombre d'allumette par tas, le second joueur n'a qu'a imiter l'adversaire pour gagner

1*1=0; 2*2=0; 3*3=0 etc...

n*0=0; 0*n=0

Par contre si il n'y a pas le même nombre, il suffit au premier joueur de ramener le jeu à deux tas égaux et ensuite imiter son adversaire pour gagner.

Nous avons donc pu continuer la table de stella(*).

Table de Stella(*)

*

0

1

2

3

4

5

6

7

8

9

10

0

0

1

2

3

4

5

6

7

8

9

10

1

1

0

3

2

2

2

3

0

1

3

3

2

1

0

4

4

0

5

5

0

6

6

0

7

7

0

8

8

0

9

9

0

10

10

0

Sommaire

partie suivante

Comment remplir la table de Stella ?

Aprés avoir rempli les 6 premières lignes et colonnes de la table en jouant toutes les parties possibles, il nous a semblé qu'on pouvait continuer à remplir la table à l'aide de deux règles :

Conséquence de ces règles : si on a un nombre n dans une case, on aura tous les nombres inférieurs à n dans les cases situées avant ou au-dessus de cette case.

Existence d’une solution perdante :

  1.  Exemple : On cherche 5 * 3 .

    D'aprés les régles définies ci-dessus, on trouve que 5 * 3 = 6.

    C'est à dire que ( 5 ; 3 ; 6 ) doit être une position perdante.

    Supposons que le premier joueur pioche dans le tas de 5 allumettes (s'il piochait dans un autre tas, on utiliserait un procédé similaire à celui qu'on va vous montrer).

    On va regarder les nombres contenus dans les cases au-dessus du 6 dans la colonne 3.

    Deux cas sont à envisager selon que ces nombres soient inférieurs ou supérieurs à 6.

    Autrement dit par le professeur

    Soit a, b et c trois nombres entiers naturels tel que c = a * b (c est obtenu avec les règles 1 et 2).

    On a vu à la partie 2 que si l’une des égalités a * b = c, b * c = a ou c * a = b est une solution perdante alors les deux autres le sont aussi car l’ordre des trois tas a, b, et c n’a pas d’importance.

Le premier joueur peut donc choisir n’importe quel tas pour enlever des allumettes, par exemple il retire x allumettes dans le tas a.

  1.  Théorème :

Le nombre entier naturel c tel que a * b = c (où c est obtenu avec les règles 1 et 2)

donne bien une solution perdante (pour trois tas a, b et c)

(1) signifie que dans le tableau le rectangle obtenu avec les cases des a premières lignes et b premières colonnes à l’exception de la dernière case ( a * b ), toutes les solutions obtenues à l’aide des règles 1 et 2 sont perdantes. Cette supposition permet de vérifier que le tableau ne contient que des solutions perdantes colonne par colonne.

Le principe est se reporter au tableau en consultant la ligne a – x et la colonne b :

En effet, d’une part, si tel n’était pas le cas alors la case (a – x) * b du tableau aurait comme particularité de contenir un nombre supérieur à c, bien que c ne serait apparu précédemment ni dans la ligne a – x ni dans la colonne b ce qui contredit la règle 2 du remplissage du tableau, d’autre part le nombre c ne peut pas figurer deux fois dans la colonne b d’après la règle 1.

Donc il faut jouer en laissant m allumettes dans le tas b et cette solution est perdante d’après (1).

sommaire

partie suivante

Les propriétés de la table de Stella

Nous avons remarqué que la table de Stella est symétrique par rapport à sa diagonale.

Ce qui est évident, car si ( n ; p ; q ) est une position perdante, ( p ; n ; q ) le sera aussi.

Nous les avons représentées de différentes couleurs sur la table. Les carrés sont de différentes grandeurs. Par exemple les carrés de côté 2 sont représentés en jaune.Les carrés de côté 4 en violet clair ou foncé, les carrés de côté 8 en noir ou bleu clair et nous n'avons que commencé les carrés de côté 16 en rose ou blanc.

De plus, les carrés de même taille situés sur la diagonale sont identiques :

le carré de côté 4 en violet est identique au carré de côté 4 en jaune-vert situé en haut à gauche.

le carré de côté 8 en bleu clair est identique au carré de côté 8 en jaune-vert-violet situé en haut à gauche.

*

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

0

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

1

0

3

2

5

4

7

6

9

8

11

10

13

12

15

14

17

2

2

3

0

1

6

7

4

5

10

11

8

9

14

15

12

13

18

3

3

2

1

0

7

6

5

4

11

10

9

8

15

14

13

12

19

4

4

5

6

7

0

1

2

3

12

13

14

15

8

9

10

11

20

5

5

4

7

6

1

0

3

2

13

12

15

14

9

8

11

10

21

6

6

7

4

5

2

3

0

1

14

15

12

13

10

11

8

9

22

7

7

6

5

4

3

2

1

0

15

14

13

12

11

10

9

8

23

8

8

9

10

11

12

13

14

15

0

1

2

3

4

5

6

7

24

9

9

8

11

10

13

12

15

14

1

0

3

2

5

4

7

6

25

10

10

11

8

9

14

15

12

13

2

3

0

1

6

7

4

5

26

11

11

10

9

8

15

14

13

12

3

2

1

0

7

6

5

4

27

12

12

13

14

15

8

9

10

11

4

5

6

7

0

1

2

3

28

13

13

12

15

14

9

8

11

10

5

4

7

6

1

0

3

2

29

14

14

15

12

13

10

11

8

9

6

7

4

5

2

3

0

1

30

15

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

31

16

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

0

Nous avons également remarqué qu'il y a une espèce de translation.

Par exemple, dans le tableau ci-dessous, pour obtenir toutes les cases d'un des carrés verts, il suffit d'ajouter 2 à la case qui se trouve deux cases avant ou deux cases plus haut: 0+2=2 ; 1+2=3 etc.

*

0

1

2

3

0

0

1

2

3

1

1

0

3

2

2

2

3

0

1

3

3

2

1

0


De même, si on passe aux carrés de côté 4, pour passer d'une case violette à la case bleue située 4 cases plus loin ou 4 cases plus bas, on ajoute 4.

*

0

1

2

3

4

5

6

7

0

0

1

2

3

4

5

6

7

1

1

0

3

2

5

4

7

6

2

2

3

0

1

6

7

4

5

3

3

2

1

0

7

6

5

4

4

4

5

6

7

0

1

2

3

5

5

4

7

6

1

0

3

2

6

6

7

4

5

2

3

0

1

7

7

6

5

4

3

2

1

0

sommaire

partie suivante

[Une technique de calcul]

Comme c'était trop long de jouer toutes les parties pour trouver les positions perdantes dans notre table de stella, surtout pour des grands nombres, nous avons cherché une technique pour calculer n'importe quelle « opération » dans la table.

Nous allons chercher combien vaut 85 * 97

1ère Technique :1ère phase : il faut tout d'abord trouver entre quelles puissances de 2 se trouvent les deux nombres de l'opération.
64 < 85 < 128 et 64 < 97 < 128.
Ce qui veut dire que 85 * 97 se trouve dans le carré de côté 64 rose du tableau ci-dessous [...]. Donc il suffit de revenir dans l'autre carré (rose en haut à gauche sur le tableau ci-dessous) comme nous l'avons vu dans la partie 5.

*

 0  

...

 33

...

 63

 64

 97

127

127

0

  

...

21

x

...

63

64

...

85

x

...
                  

127


Ensuite il faut soustraire la puissance de 2 inférieure aux nombres (ici 64). Donc 85*97 = (85-64)*(97-64) = 21 * 33 on obtient alors une opération plus petite donc un peu plus simple.

2éme phase : Mais là, il y a une complication, dans la phase précédente, les deux nombres étaient encadrés par les mêmes puissances de 2. Mais cette fois , on remarque que c'est différent : 16 < 21 < 32 alors que 32 < 33 < 64 !!!

*

 0

  1

...

16

 ...

31

32

33

63

0

 

 

...

 

 

16

 

 

...

 

 

21

x-32

  

 

x

...

 

 

31

 

 

32

 

 


Donc nous faisons l'étape suivante : nous avons vu à la partie 5 que, pour obtenir le carré vert, il faut ajouter 32 à chaque case du carré jaune. En particulier, pour obtenir le nombre situé dans la case 21 * 33, il faut faire la somme du nombre situé dans la case 21 * 1 (situé 32 cases avant) et de 32 (car on a changé de couleur).

Ou 21*33 = (21* (33-32)) +32 = (21*1) +32.

En procédant de la même façon, nous avons trouvé que :

21*1 = ((21-16)*1) + 16 = (5*1) + 16Puis 5*1 = ((5-4)*1) + 4 = 1*1 + 4

Or nous savons que 1*1 = 0 car c'est une position symétrique. En remontant toutes ces opérations, nous trouvons que :

85 * 97 = 0 + 4 + 16 + 32 = 52

Simplification de cette technique

On voit bien avec la méthode ci-dessus qu'il suffit de décomposer les nombres de l'opération en puissances de 2 et de supprimer les puissances de 2 qui apparaissent dans les deux nombres car cela revient à remonter d'un carré de même couleur sur la diagonale.

Ainsi :

85 = 64 + 21

85 = 64 + 16 + 5

85 = 64 + 16 + 4 +1

Et 97 = 64 + 33

97 = 64 + 32 + 1

Ensuite il suffit de retirer les puissances de 2 qui sont les mêmes dans les 2 décompositions ( 64 et 1 ) et d'ajouter les restes.

Donc nous avons

85 * 97 = 16 + 32 + 4 = 52

sommaire

partie suivante

Le jeu de nim à quatre tas

Nous avons essayé de compliquer le problème, en ajoutant un tas.

Une situation symétrique : On a d'abord cherché lorsqu'on avait quatre fois le même nombre dans chaque tas. Et nous avons remarqué, que c'était une solution perdante. On a essayé de mettre deux tas identiques, suivit de deux tas identiques différents du premier, pas exemple, 2 2 3 3 : c'est aussi une solution perdante.

Pour une position symétrique comme 2 2 3 3, on a d'abord utilisé la même technique que pour un tas de 2 c'est à dire imiter l'adversaire.

5 tas, une situation non symétrique : On en a déduit l'hypothèse que deux solutions perdantes superposées forment une solution perdante.

Donc 1 2 3 2 2 est une solution perdante, et on a trouvé une stratégie qui consiste d'abord à séparer la solution par exemple 1 2 3 2 2 --> 1 2 3 / 2 2.

Ensuite on joue chaque solution séparément (selon ce que joue l'adversaire)

Le Calcul :

On s'est servit du système de la table de stella [...] pour trouver le quatrième tas lorsqu'on n'en avait que trois.

Exemple: 3*2*7= ?

On fait d'abord 3*2=1 et ensuite on fait 1*7=6 c'est comme si on avait mis des parenthèses à 3*2. Donc (3*2)*7=6

Mais on peut aussi faire le calcul dans l'autre sens.

3*2*7=? On fait d'abord 2*7=5 et ensuite 3*5 =6 c'est comme si on avait mis des parenthèses à 2*7. Donc 3*(2*7) = aussi 6.

on peut supposer que la position (3 ; 2 ; 7 ; 6) est perdante d'habitude le jeu de marienbad est posé avec le position (1 ; 3 ; 5 ; 7)

1*3=2

2*5=7

Donc on suppose que la position (1 ; 3 ; 5 ; 7) est perdante.

En jouant toutes les possibilités on s'est aperçu que c'était bien une position perdante.

MOTS CLEFS

JEU DE NIM, STRATÉGIE, NIM-ADDITION, STELLA, TAS

Comptes Rendus MATh.en.JEANS 
05-06

© MATh.en.JEANS 2009. Tous droits réservés.

Retour au début d'article

Retour aux Comptes Rendus MATh.en.JEANS