Jeu de Marienbad
Le jeu de Marienbad a été popularisé par le film d'Alain Resnais et d'Alain Robbe-Grillet, L'Année dernière à Marienbad, en 1961.
Ce jeu de société combinatoire abstrait, dont il existe plusieurs variantes, se joue avec des graines, des dominos, des jetons, des cartes, des allumettes, ... Son origine est probablement très ancienne. Il appartient à la famille plus large des jeux de Nim.
Cette variante a été rendue célèbre par le film d'Alain Resnais au point d'en prendre le nom. Dans ce film, l'un des protagonistes gagne parties sur parties. Il prononce cette phrase à la portée symbolique : Je peux perdre, mais je gagne toujours...
Dans la version du film, il y a quatre rangées, avec respectivement 1, 3, 5, 7 allumettes et celui qui prend la dernière allumette perd. À chaque tour, le joueur prend le nombre d'allumettes qu'il veut, au moins une et dans une même rangée. Dans une autre variante, le gagnant est celui qui prend la dernière allumette.
Stratégie gagnante
La méthode repose sur le système binaire. La position de départ, précisée par le dessin ci-contre, s'analyse à l'aide des calculs suivants :
1 = 0 0 1 en binaire 3 = 0 1 1 " 5 = 1 0 1 " 7 = 1 1 1 "
Si on effectue les sommes des chiffres du binaire colonne par colonne en base dix, on trouve :
S = 2 2 4
Considérons d'abord la variante où le gagnant est celui qui prend la dernière allumette. Selon le théorème de Sprague-Grundy, une position est gagnante pour le joueur qui l'atteint si et seulement si tous les chiffres de S sont pairs. Une telle position sera perdante pour le joueur qui part d'une telle position. Ainsi, dans l'exemple donné, la position initiale est perdante pour le premier joueur, son adversaire ayant la possibilité de conserver cette propriété de S tout le long de la partie jusqu'à ce qu'il ne reste plus d'allumette. Une démonstration directe de ce résultat est donnée ci-dessous.
Dans le cas où celui qui prend la dernière allumette est le perdant, la stratégie est la même jusqu'à ce qu'il ne reste plus que des lignes ayant une allumette, situation à partir de laquelle il convient de laisser à son adversaire un nombre impair de telles lignes.
Démonstration
La démonstration de la stratégie optimale a été faite par Charles Bouton[1] dans les annales de mathématiques en 1901.
Théorème. Dans un jeu de Nim, le joueur jouant en premier a une stratégie gagnante si et seulement si la somme nim des piles est différente de zéro. Sinon, le second joueur a une stratégie gagnante.
Démonstration: La loi de composition XOR [2] (⊕) est associative et commutative, et vérifie également: x ⊕ x = 0 (en termes mathématiques l'ensemble des nombres naturels munis de ⊕ est un groupe abélien dont chaque élément non nul est d'ordre 2).
Soit x1, ..., xn les tailles de chaque pile avant un coup, et y1, ..., yn les tailles de ces mêmes piles après le coup. Soit s = x1 ⊕ ... ⊕ xn et t = y1 ⊕ ... ⊕ yn. Si le coup a été fait dans la pile k, nous avons: xi = yi pour tout i ≠k, et xk > yk. En appliquant les propriétés de ⊕ il vient:
t = 0 ⊕ t
= s ⊕ s ⊕ t
= s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn)
= s ⊕ (x1 ⊕ y1) ⊕ ... ⊕ (xn ⊕ yn)
= s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xk ⊕ yk) ⊕ 0 ⊕ ... ⊕ 0
= s ⊕ xk ⊕ yk
(*) t = s ⊕ xk ⊕ yk.
La démonstration se fait par récurrence à partir des deux lemmes suivants.
Lemme 1. Si s = 0, alors t ≠0 quel que soit le coup choisi.
Démonstration: S'il n'y a aucun coup possible alors le lemme est trivialement vrai. Sinon, un coup quelconque dans la pile k génèrera t = xk ⊕ yk en appliquant (*). Ce nombre est différent de 0 car xk ≠yk.
Lemme 2. Si s ≠0, alors il est possible de jouer un coup tel que t = 0.
Démonstration: Soit d la position du premier bit différent de 0 en partant de la gauche dans la représentation binaire de s. Choisissons k tel que le d-ième bit de xk est aussi différent de 0 (un tel k existe car sinon le d-ième bit de s serait 0). Posons yk = s ⊕ xk. Alors nous avons yk < xk. En effet tous les bits à gauche de d sont les mêmes dans xk and yk, le bit d passe de 1 à 0, faisant ainsi décroitre la valeur de 2d. Quelles que soient les modifications sur les bits à droite de d, elles ne pourront pas générer une modification plus grande que 2d−1. Le premier joueur peut donc prendre xk − yk objets de la pile k, et
t = s ⊕ xk ⊕ yk (suivant (*)) = s ⊕ xk ⊕ (s ⊕ xk) = 0.
Jeu par arrangement
Un jeu par arrangement est un jeu dans lequel on pose des pièces sans jamais en retirer. Malgré les apparences, le Jeu de Marienbad appartient bien à cette catégorie. En effet, on pourrait créer un tableau comportant 4 rangées de 1, 3, 5 et 7 cases et dire que la règle consiste à poser tour à tour autant de pions que souhaité dans une rangée, jusqu'à ce que le tableau soit entièrement rempli.
Bibliographie
G.H. Hardy, E.M. Wright, An introduction to the theory of numbers, Clarendon Press, 5e édition, (2005), 117-120
C. Berge, Théorie des graphes et ses applications, Collection universitaire de mathématiques, Dunod, (1958) ISSN 0530-9387.