Pour les articles homonymes, voir Marienbad (homonymie).

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.

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.

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 x₁, ..., x_n les tailles de chaque pile avant un coup, et y₁, ..., y_n les tailles de ces mêmes piles après le coup. Soit s = x₁ ⊕ ... ⊕ x_n et t = y₁ ⊕ ... ⊕ y_n. Si le coup a été fait dans la pile k, nous avons: x_i = y_i pour tout i ≠ k, et x_k > y_k. 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 = x_k ⊕ y_k en appliquant (*). Ce nombre est différent de 0 car x_k ≠ y_k.

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 x_k est aussi différent de 0 (un tel k existe car sinon le d-ième bit de s serait 0). Posons y_k = s ⊕ x_k. Alors nous avons y_k < x_k. En effet tous les bits à gauche de d sont les mêmes dans x_k and y_k, le bit d passe de 1 à 0, faisant ainsi décroitre la valeur de 2^d. Quelles que soient les modifications sur les bits à droite de d, elles ne pourront pas générer une modification plus grande que 2^d−1. Le premier joueur peut donc prendre x_k − y_k objets de la pile k, et

t = s ⊕ xk ⊕ yk           (suivant (*))
  = s ⊕ xk ⊕ (s ⊕ xk)
  = 0.

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.

G.H. Hardy, E.M. Wright, An introduction to the theory of numbers, Clarendon Press, 5^e édition, (2005), 117-120

C. Berge, Théorie des graphes et ses applications, Collection universitaire de mathématiques, Dunod, (1958) ISSN 0530-9387.

• Jeux de Nim
• Théorie des graphes.

• Jeu de Marienbad en ligne
• Marienbad, le jeu et sa résolution

• Portail des jeux