Jeux de Nim

Le jeu de Nim (au singulier) est un jeu inventé (ou du moins décrit) par Charles Bouton au début du XX^e siècle, qui se joue avec des jetons disposés en tas :

Dans ce jeu, popularisé par le film l’année dernière à Marienbad, on retire autant de jetons que l’on veut d’un tas de jetons, mais d’un seul tas. D’autres jeux, similaires (par exemple celui joué à Fort-Boyard) sont également appelés jeux de Nim (au pluriel). Dans cet article, on explore divers jeux de ce type, où l’analogie avec le jeu de Nim est parfois bien cachée !

Jeux de Nim sur échiquier

On peut jouer à beaucoup de jeux de Nim (ou autres) sur un échiquier :

Avec des jetons

Outre le jeu de Nim (qui se joue traditionnellement avec des jetons), il y a le jeu Chomp, mais aussi celui de Grundy. dans ce jeu, on part d’un tas de jetons, et chaque tour de jeu consiste à choisir un tas de hauteur au moins 3 (au début du jeu, on n’a pas trop le choix) et le couper en deux parties de hauteurs différentes. Par exemple, à partir d’un tas de 10 jetons, si le premier joueur a enlevé un tas de 3 jetons pour avoir un tas de 7 et un tas de 3, et que le second joueur a commis l’imprudence de diviser le tas de 7 en un tas de 5 et un tas de 2, on obtient la situation montrée ci-dessus, où le premier joueur a pour coup gagnant de séparer le tas de 5 en un tas de 3 et un tas de 2.

Avec un pion

Aviezri Fraenkel a trouvé comment modéliser un jeu de Nim avec un graphe : le graphe représente les étapes possibles du jeu, et un un pion est posé sur l’état courant du jeu. Pour jouer, on déplace chacun son tour le pion le long d’une flèche et le dernier à pouvoir bouger le pion a gagné le jeu. Voici quelques exemples testés en école maternelle (GS) :

Et voici des jeux inventés par Aviezri Fraenkel, qui se jouent avec plusieurs pions :

Avec des dominos

Le jeu Cram se joue sur une grille (un échiquier par exemple) avec des dominos. Chaque domino couvre presque deux carrés de l’échiquier. Chaque joueur à son tour pose un domino sur deux cases vides de l’échiquier. Le premier qui ne peut plus poser de domino (parce que les cases vides sont isolées) perd le jeu.

Au tableau

Le jeu Sprouts se joue avec du papier et des crayons, ou au tableau avec des craies. Il consiste à dessiner incrémentalement un graphe, avec les contraintes suivantes :

• le degré d’un sommet (initialement nul) ne doit pas dépasser 3,
• deux arêtes ne doivent jamais se croiser,
• chaque fois que l’on trace une arête, on rajoute un sommet (de degré 2) au milieu de cette arête.

Comme dans n’importe quel jeu de Nim, le premier qui ne peut plus jouer a perdu.

Le jeu bénéficie d’un énorme succès dès le CP, d’autant que la caravane de l’IREM le faisait jouer au tableau, ce qui attire l’attention des non joueurs. Par exemple, en 2020 à l’école Aristide Briand du Tampon, un nuage de points est tracé en bleu par l’animateur IREM, puis les joueurs construisent le graphe avec une couleur par joueur.

Ici, le joueur Vert a joué trois coups, et le joueur Rouge joue son troisième coup (c’est donc Vert qui a commencé le jeu). Rouge dessine le nouveau sommet au milieu de l’arête qu’il vient de dessiner :

Le graphe possède maintenant 9 sommets dont 3 sont de degré 2 (le vert tout à gauche, le rouge nouvellement tracé, et le bleu en bas). Vert dispose dont de deux coups gagnants :

• joindre le sommet rouge nouvellement tracé au sommet bleu en bas (le nouveau sommet vert ne pourra pas être relié à celui à gauche sans traverser une arête),
• joindre le sommet vert à gauche, au sommet bleu en bas (le sommet vert que cela créera ne pourra être joint au dernier sommet rouge sans traverser une arête).

Mais en fait, il perd en jouant un coup interdit :

En effet, le sommet bleu en haut à gauche est maintenant de degré 4. De fait, dans le premier degré, les erreurs sont presque systématiquement des erreurs de dénombrement des degrés, traverser une arête ne se faisant guère.

Ici c’est à Rouge de jouer, sur un graphe ayant déjà 10 sommets :

Mais seuls deux sommets ont degré 2 (le bleu le plus senestre, et le vert le plus dextre), donc le seul coup jouable pour Rouge consiste à relier ces deux sommets par une arête. Or cela est impossible sans croiser une arête existante, ce que la règle du jeu interdit.

Un autre jeu de Nim peut être joué au tableau, mais en effaçant plutôt qu’en construisant. Green Hackenbush, lui aussi créé par John Conway, se joue sur un graphe connexe, dont un chemin est fixé, il s’appelle ligne de terre. Chaque joueur à son tour, efface un sommet qui n’est pas sur la ligne de terre, ainsi que toutes les arêtes qui émanaient de ce chemin, et toute partie du graphe qui n’est plus reliée à la terre. Lorsqu’il ne reste plus que la ligne de terre, le joueur qui vient de jouer a gagné le jeu.

En tournant des jetons

Hendrik Lenstra a montré dans les années 1970 que tout jeu de Nim peut être modélisé par des jeux où on retourne des pièces, selon un motif, certaines d’entre elles devant obligatoirement passer de pile à face. Deux de ces jeux sont praticables dès le CP :

• twins, où les pièces sont alignées,
• turning corners, où les pièces sont disposées en rectangle.

Avec des graines

Il existe deux jeux de semailles où les deux joueurs ont exactement les mêmes possibilités de jeu :

• Une variante de multitchouka (créé par Véronique Gautheron en 1977) appelée multitchoukatro,
• Le jeu impartial sowing, créé par John Conway en 1996.