Jeu de Grundy : Aramis pouvait-il sauver ses six écus ?

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente.

Intervenant 20:02

Bonjour à tous !

Intervenant 10:05

C'est vraiment un immense plaisir de retrouver tous les auditeurs aujourd'hui pour une nouvelle exploration mathématique. Que ceux qui découvrent cette émission s'installent confortablement, parce que notre mission pour cette exploration approfondie, c'est de prendre une situation, une situation d'apparence banale, un simple jeu de comptoir en fait. Ouais, un truc tout pète. C'est ça. Et d'en extraire les rouages invisibles pour plonger la tête la première dans la théorie des graphes et les mathématiques pures.

Intervenant 20:30

Et c'est souvent dans ces petites récréations du quotidien que se cachent les structures les plus élégantes, tu sais. Le contraste entre un jeu de pièces sur une table en bois et la théorie des jeux combinatoires, c'est vertigineux. Mais bon, le chemin pour y parvenir est d'une logique implacable.

Intervenant 10:46

Du coup, je plante le décor. L'histoire veut que nos deux célèbres mousquetaires, Aramis et Athos, rentrent d'une longue mission exténuante. Ils font halte dans une taverne, ils commandent à boire, et au moment de régler l'addition, l'ambiance devient joueuse.

Intervenant 21:02

Comme d'habitude avec

Intervenant 11:03

eux. Voilà. Donc plutôt que de diviser la note, il décide que le perdant d'un petit jeu de réflexion payera pour les deux. Il rassemble six écus sur la table et il forme un seul tas initial.

Intervenant 21:14

Alors ça, en mathématiques, c'est ce qu'on appelle un jeu à information parfaite, fini et impartiel.

Intervenant 11:19

C'est-à-dire ?

Intervenant 21:21

Il n'y a pas de dés pour introduire de l'aléatoire. Il n'y a pas de carte cachée dans la manche. Tout est sur la table. Les deux joueurs ont exactement les mêmes options à tout moment. Et surtout, la partie doit obligatoirement se terminer.

Intervenant 11:33

D'accord. Alors, les règles qu'il se fixe sont hyper élémentaires. À tour de rôle, un joueur prend un tas présent sur la table et le sépare en deux tas, strictement inégaux. C'est la condition sine qua non de ce jeu, une séparation asymétrique.

Intervenant 21:47

C'est ça, inégaux. Donc 3 et 1 c'est bon, mais 2 et 2 c'est interdit.

Intervenant 11:52

Exactement. Et bien sûr, si un tas ne contient qu'une ou deux pièces, il est gelé. Impossible de diviser un tas de deux sans faire deux tas de un, ce qui serait égal et donc illégal selon leurs règles.

Intervenant 22:03

Logique.

Intervenant 12:03

Le perdant, c'est le joueur qui, lorsque son tour arrive, constate qu'il n'y a plus aucune division valide possible sur la table.

Intervenant 22:10

Et vu que chaque coup augmente le nombre de tas, tout en diminuant leur taille moyenne, la partie est vouée à s'achever assez rapidement en fait, sur une table remplie de petits tas de une ou deux pièces.

Intervenant 12:19

Mec, ça va très vite ! Aramis est le premier à jouer, il scrute les six pièces, il fait sa première division, Atos répond, Aramis rejoue, et après un total de seulement quatre tours de jeu depuis le début de la partie, Aramis reste pétrifié, il ne peut plus rien faire, la partie est finie, il doit payer.

Intervenant 22:37

Aïe.

Intervenant 12:38

Bon, décortiquons tout ça. Aramis a-t-il été victime de la malchance ? Ou bien Athos, en tant que deuxième joueur, disposait-il depuis le début d'une stratégie implacable, rendant la défaite d'Aramis inévitable ?

Intervenant 22:51

Bah, pour le savoir, il faut s'éloigner un instant de ces six pièces physiques, pour modaliser le problème. En maths, la meilleure approche face à un système complexe, c'est souvent de le réduire à sa version la plus triviale.

Intervenant 13:03

D'accord, on simplifie.

Intervenant 23:04

Voilà. Imaginons un instant que nos mousquetaires n'aient joué qu'avec trois pièces au

Intervenant 13:08

départ. Avec trois pièces, le premier joueur sépare forcément le tas en un tas de deux et un tas de un. Fin de l'histoire.

Intervenant 23:17

Exactement.

Intervenant 13:17

La victoire est immédiate pour le premier joueur, puisqu'aucune autre action n'est permise.

Intervenant 23:22

C'est ça. Maintenant, passons à quatre pièces. La seule division asymétrique autorisée, c'est de créer un tas de 3 et un tas de 1. Le tas de 1 est définitivement bloqué, reste que le tas de 3. Et ça, ça laisse le deuxième joueur face à la situation qu'on vient tout juste de résoudre.

Intervenant 13:40

Ah bah oui, ce deuxième joueur sépare le 3 en 2 et 1 et c'est lui qui remporte la partie. Tu

Intervenant 23:45

vois l'idée.

Intervenant 13:46

En fait, pour se représenter mentalement la dynamique, c'est un peu comme si on demandait de casser une tablette de chocolat

Intervenant 23:51

asymétriquement.

Intervenant 13:54

Si on force des parts inégales à chaque cassure, on va inévitablement se retrouver très vite avec des carrés individuels ou des duos inséparables. La contrainte d'asymétrie, c'est vraiment un accélérateur d'épuisement des possibles.

Intervenant 24:06

C'est une super bonne façon de le visualiser. Alors, à cinq pièces, l'arbre des possibilités s'ouvre légèrement. Le premier joueur peut séparer en quatre et un, ce qui ramène au cas des quatre

Intervenant 14:17

pièces.

Intervenant 24:19

Ou alors en trois et deux, ce qui ramène au cas des trois pièces. Et c'est en connectant toutes ces situations les unes aux autres que la modélisation prend tout son sens. Si on traduit ça dans le langage de la théorie des graphes, chaque configuration sur la table devient un sommet et chaque coup joué devient un arc dirigé vers une nouvelle configuration.

Intervenant 14:40

D'accord, donc si on s'attaque au problème des six pièces d'Aramis, on dessine un sommet de départ numéro T6.

Intervenant 24:45

Voilà.

Intervenant 14:46

Si il choisit de faire un tas de 5 et un tas de 1, on trace une flèche vers un sommet étiqueté 5 et 1. Le graphe entier cartographie l'absolue totalité des destins possibles de cette partie.

Intervenant 24:58

Tout à fait. Et là, ma analyse du chemin spécifique emprunté par Aramis, jusqu'à sa défaite, révèle une donnée super intéressante. Sa configuration finale, celle où il était bloqué, elle était composée de tas de 2, 1, 1, 1 et 1.

Intervenant 15:13

Ok. Cinq tas au

Intervenant 25:15

total. C'est ça. Pour attendre ce sommet final, depuis le sommet de départ de 6, le parcours comportait un nombre pair d'arcs. Puisque les joueurs alternent scrupuleusement un nombre pair d'étapes signifie obligatoirement que c'est le deuxième joueur, Athos, qui a posé le dernier acte valide. Aramis s'est de facto précipité dans une impasse.

Intervenant 15:35

Mais attends. Est-ce que ce chemin empoisonné était le seul disponible ou est-ce qu'Aramis a activement pris le mauvaise décision en cours ? Parce qu'une fois que ce graphe est dessiné, on doit pouvoir colorier les sommets en deux catégories, non ? Genre ceux qui garantissent la victoire et ceux qui mènent à la ruine ?

Intervenant 25:52

C'est l'essence même de l'analyse rétrograde. On peut effectivement remonter le graphe depuis la fin pour identifier les positions gagnantes et perdantes. Ce qui est fascinant ici, c'est qu'on peut classer toutes les situations.