Nim : Au pays des bâtonnets

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


Vous avez 17 bâtonnets et un adversaire en face de vous. A tour de rôle, vous allez devoir retirer 1, 2 ou 3  bâtonnets de la zone de jeu, jusqu’à ce qu’il n’en reste plus qu’un : celui qui est forcé de piocher le dernier bâtonnet perd la partie.

Ce jeu est une des nombreuses variantes du jeu de Nim, et les amateurs de Fort Boyard reconnaîtront sans doute cette fameuse épreuve qui voyaient les candidats affronter les maîtres du temps – même si, dans ce cas, il y a 20 bâtonnets, mais c’est un détail.

Jeu des bâtonnets

Vous pouvez vous entraîner à jouer contre l’ordinateur à cette adresse, mais autant vous prévenir tout de suite : il ne se laissera pas faire ! A la moindre de vos erreurs, il sautera sur l’occasion pour vous infliger une cuisante défaite : n’hésitez pas à analyser son comportement pour comprendre comment il procède.

Existe-t-il une stratégie qui permettrait de gagner à tous les coups ? Ou bien tout ceci n’est-il que pur hasard ?

Les premières analyses

C’est la question que j’ai posée à mes deux classes de 4ème lors de séances d’accompagnement personnalisé : après une brève projection de la vidéo, les élèves étaient amenés à s’affronter à ce jeu. De temps en temps, lorsque l’un d’eux se sentait suffisamment confiant, il venait me défier au tableau : quelle belle occasion de mettre la pâtée à son prof de maths !

Fort heureusement pour mon orgueil, la défaite promise n’est pas venue, mais les premières analyses ont émergé. Ainsi, lorsqu’il reste 5 bâtonnets sur la table ou le tableau, le joueur sait qu’il est condamné. S’il prend 1 bâtonnet, son adversaire en retirera 3 ; s’il en prend 2, l’adversaire en prendra aussi 2. Enfin, si le joueur retire 3 bâtonnets, alors son opposant en prendra 1. Dans tous les cas, il ne restera plus qu’un seul bâtonnet, que le joueur sera obligé de prendre, perdant ainsi la partie.

On en vient à la conclusion que 5 bâtonnets représentent une position perdante. Pour gagner, il suffit de faire en sorte que notre adversaire se trouve face à ces cinq bâtonnets.

Et le même raisonnement vient alors lorsqu’il en reste 9 sur la table. Si c’est à mon adversaire de jouer, il me suffit d’employer la même tactique qu’au-dessus, à savoir compléter son coup pour qu’au total, ce soient 4 bâtonnets qui aient été retirés.

Et ainsi de suite, si l’adversaire se retrouve avec 13, 17, 21, 25 bâtonnets et ainsi de suite, je suis sûr de remporter la manche, pourvu que je ne fasse pas d’erreur.

Ces nombres ont un point commun : si je fais le maximum de paquets de 4 bâtonnets, alors il m’en restera 1 et 1 seul à la fin. On dit que le reste de la division euclidienne de ces nombres par 4 vaut 1, ou que ces nombres sont égaux à 1 modulo 4.

Ainsi, lorsque l’on me présente le tapis de jeu, j’ai tout intérêt à compter les bâtonnets avant de prendre une décision. S’il y a 5, 9, 13, 17, ou tout autre nombre égal à 1 modulo 4 d’allumettes, je laisse mon adversaire jouer le premier coup, et je joue les miens pour me ramener à chaque fois à l’un de ces nombres.

Dans le cas contraire, je dois jouer en premier et me ramener à cette situation, perdante pour mon adversaire. Si par exemple, il y a 22 bâtonnets, en prendre 1 ramènera notre jeu au cas de 21 bâtonnets, et je peux reprendre la stratégie expliquée plus haut.

Des prises variables

Résoudre un jeu, c’est bien. En résoudre toute une catégorie, c’est encore mieux !

Une version plus compliquée mais encore simple de ce jeu consiste à augmenter le nombre de bâtonnets que l’on peut prendre : si, au lieu d’en prendre entre 1 et 3, on pouvait en prendre entre 1 et 4, existerait-il toujours une stratégie gagnante ? Avec ces nouvelles règles, il est possible, quoi que fasse l’adversaire, de compléter son coup pour retirer un total de 5 allumettes (4+1, 3+2, 2+3, 1+4)… Autrement dit, plutôt que de s’intéresser aux nombres égaux à 1 modulo 4, on regarde plutôt ici les nombres égaux à 1 modulo 5 : ceux-ci représentent des positions perdantes.

Mais si la règle de tirage se révèle plus compliquée, qu’en est-il ? Par exemple, tirer 1, 2 ou 4 bâtonnets, tirer 2,3 ou 5 bâtonnets, ne pas avoir le droit de prendre le même nombre de bâtonnets que l’adversaire…

Pour résoudre ces problèmes, on peut regarder toutes les configurations, en distinguant celles qui sont gagnantes de celles qui sont perdantes. Prenons par exemple le cas où le jeu démarre avec 13 bâtonnets, et où nous avons le droit d’en prendre 2, 3 ou 5 à la fois. On suppose que c’est à notre tour de jouer.

  • S’il reste 1 ou 2 bâtonnets, nous avons perdu, puisque nous sommes obligés d’en prendre 2. Ces positions sont perdantes.
  • Si, au contraire, il en reste 3, nous avons gagné : il suffit de prendre 2 bâtonnets et ainsi n’en laisser qu’un, pour amener notre adversaire dans un position perdante.
  • Le même raisonnement tient pour 4 : en prendre 2 ou 3 mène notre adversaire à une situation perdante. Pour 5, il suffit d’en prendre 3, et ainsi de suite…

Il est possible de représenter toutes ces configurations sur un graphe : les nombres de bâtonnets sont représentés par les sommets du graphe, et on place une flèche d’un sommet à un autre s’il est possible de passer du premier nombre de bâtonnets au second en un seul coup (par exemple, on peut passer de 7 à 2 en retirant 5 bâtonnets).

On colorie alors les positions gagnantes d’une couleur, et les positions perdantes d’une autre : au départ, on sait seulement que les positions 1 et 2 sont perdantes. Puis on remonte dans le graphe en procédant ainsi :

  • Si un sommet pointe sur une position perdante, alors ce sommet représente une position gagnante : il suffit de jouer le coup correspondant à la flèche.
  • Si un sommet ne pointe QUE sur des positions gagnantes, alors ce sommet représente une position perdante. Quoi que l’on fasse, on se retrouve dans une situation désavantageuse.

Voici par exemple le graphe du jeu présenté un peu plus haut

Graphe du jeu à 13 bâtonnets

On voit que si l’on commence avec 13 bâtonnets, alors il suffit d’en prendre 5. Notre adversaire, qui sera alors face à 8 bâtonnets, ne pourra alors se rendre que sur les sommets 6, 5, ou 3, qui sont tous trois gagnants (il suffit en effet de prendre respectivement 5, 3 ou 2 bâtonnets pour gagner).

Naturellement, de tels graphes sont parfois compliqués à mettre en place, alors si vous souhaitez impressionner vos proches avec vos compétences bâtonnetières, restez à des cas simples, c’est plus prudent.

Pour compléter

  • Micmaths, Gagner au jeu des bâtonnets de Fort Boyard. Une vidéo pour mieux visualiser le problème.
  • Une série de trois articles d’Eljj, sur le jeu des bâtonnets d’abord, sur le jeu de Nim « classique » ensuite, qui revient à avoir plusieurs tas de bâtonnets et à piocher dans l’un d’eux. Sur le théorème de Sprague-Grundy enfin, qui résoudra tous vos problèmes (à ces jeux du moins)
  • Les articles de Jean-Paul Delahaye dans la revue Pour la Science, n°377 (Stratégies magiques au pays de Nim)
  • (Anglais) La vidéo sur le jeu Dr Nim par standupmaths, ou comment un jeu des années 60 vous battra à tous les coups !

 

Cet article, publié dans Curiosités et récréation, est tagué , , , , , . Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s