Le principe du « jeu de Marienbad »1 est simple : quatre rangées contenant respectivement 1, 3, 5 et 7 allumettes (ou des cartes), sont disposées sur une table, comme sur le schéma ci-dessous.

À tour de rôle chaque joueur doit en prélever au moins une, dans une seule rangée. Perd celui qui doit prendre la dernière. Il s'agit là d'une variante de ce qu'on connaît aussi, depuis un article de Charles Leonard Bouton paru en 1901 dans les prestigieuses Annals of Mathematics de Princeton1 sous le nom de Jeu de Nim (peut-être à cause de l'allemand nimm !, prends !), dont les règles sont identiques, avec un nombre quelconque de rangées et d'allumettes (ou de jetons) dans chacune d'entre elles. L'article de Bouton, un Américain originaire de Saint Louis et professeur, entre autres, à Harvard, peut être considéré comme l'acte de naissance de la théorie des jeux. Il explicite une stratégie gagnante, que nous résumons ici. 

Cas où celui qui prend la dernière allumette gagne

Il est plus simple, pour commencer, d'étudier le cas où celui qui prend la dernière allumette gagne. On dira qu'une distribution est gagnante (du point de vue d'un joueur donné, mettons Pitoëff dans le film) s'il existe pour lui, lorsqu'il doit jouer à partir de celle-ci, une stratégie lui permettant de gagner (et donc de prendre la dernière allumette), quels que soient les choix de l'adversaire. À l'inverse, une distribution perdante est celle qui laisse, quoi qu'on fasse, la possibilité à l'adversaire, s'il joue bien, de gagner. Il est évident qu'une disposition est gagnante si et seulement si on peut, en un coup, atteindre une disposition perdante (c'est-à-dire placer l'adversaire en difficulté). Considérons dans la suite une distribution à $n$ rangées, contenant des nombres d'allumettes notés $x_{1},...,x_{n}$.

L'idée de Bouton est alors — et nous la justifierons plus loin — d'exprimer le nombre d'allumettes dans chaque rangée en écriture binaire. Disposons alors les uns en dessous des autres les nombres ainsi obtenus, en les alignant à droite comme pour poser une addition. Prenons un exemple avec quatre rangées de 33, 59, 25 et 3 allumettes, ce qui donne:

$1$ $0$ $0$ $0$ $0$ $1$       33  allumettes
$1$ $1$ $1$ $0$ $1$ $1$       59 allumettes
  $1$ $1$ $0$ $0$ $1$       25 allumettes
        $1$ $1$        3 allumettes
$2$ $2$ $2$ $0$ $2$ $4$  

  

Dans la suite, on dira qu'une distribution vérifie la propriété $P$ lorsque la somme des chiffres contenus dans chaque colonne est paire. Celle donnée en exemple vérifie bien cette propriété.

  • Prouvons tout d'abord que, à partir d'une distribution ne vérifiant pas $P$, on peut se ramener en un coup à une distribution vérifiant $P$. Il suffit en effet de repérer la colonne avec un total impair située le plus à gauche : celle-ci contient au moins un $1$, mettons dans la ligne $i$ portant le nombre $x_{i}$. Il peut alors modifier dans $x_{i}$ tous les chiffres nécessaires pour obtenir dans chaque colonne la parité. C'est possible, car le $1$ évoqué doit être changé en $0$, sans que les chiffres situés plus à gauche dans $x_{i}$ soient affectés (ils sont en effet situés dans des colonnes où le total est déjà pair) : on crée ainsi un nombre plus petit (ce qui revient bien à enlever des allumettes). 

 

  • Remarquons aussi que, lorsqu'on joue à partir d'une distribution vérifiant $P$, on obtient nécessairement une distribution vérifiant non $P$. En effet, en prenant des allumettes dans une rangée, on modifie un et un seul des nombres considérés (ce qui revient à changer certains $0$ en $1$ et inversement). Il est impossible, ce faisant, de conserver la parité de chaque colonne (puisque, étant donné les $n-1$ autres nombres, il n'existe qu'une seule manière d'en choisir un dernier pour qu'ensemble ils vérifient la propriété $P$). Dans notre exemple, qui vérifie la propriété $P$, supposons qu'Albertazzi ait pris 5 allumettes de la première rangée, n'en laissant donc que 28 ($11100$ en système binaire). Pitoëff joue donc à partir d'une distribution ne vérifiant pas $P$ :
  $1$ $1$ $1$ $0$ $0$       28  allumettes
$1$ $1$ $1$ $0$ $1$ $1$       59 allumettes
  $1$ $1$ $0$ $0$ $1$       25 allumettes
        $1$ $1$        3 allumettes
$1$ $3$ $3$ $0$ $2$ $3$  

La dernière colonne au total impair, en l'espèce, est celle située le plus à gauche : c'est donc dans $111011$ (59) qu'il faut modifier tous les chiffres sauf le pénultième et l'antépénultième, ce qui donne $000010$, soit $2$. Ainsi faut-il prendre 57 allumettes de la deuxième rangée, pour rétablir la propriété $P$, et renvoyer à Albertazzi une distribution vérifiant encore la propriété $P$ :

  $1$ $1$ $1$ $0$ $0$       28  allumettes
        $1$ $0$        2 allumettes
  $1$ $1$ $0$ $0$ $1$       25 allumettes
        $1$ $1$        3 allumettes
  $2$ $2$ $0$ $2$ $2$  
  • Montrons maintenant qu'une distribution vérifiant la propriété $P$ est perdante. En effet, si l'adversaire (Pitoëff) applique la stratégie indiquée à partir d'une distribution ne vérifiant pas la propriété $P$, on obtient une série de distributions vérifiant alternativement $P$ (dans notre exemple, lorsque Albertazzi doit jouer la distribution renvoyée par Pitoëff) et non $P$ (lorsque c'est au tour de Pitoëff de jouer ce qu'Albertazzi lui renvoie nécessairement), et où le nombre d'allumettes diminue strictement, ce qui assure de finir. Pour gagner, il faut renvoyer à son adversaire la distribution ne contenant aucune allumette, et cela n'est possible qu'à partir d'une distribution ne contenant qu'une seule rangée (avec éventuellement plusieurs allumettes), et vérifiant donc la propriété non $P$. Seul, donc, celui qui joue toujours à partir de distributions vérifiant non $P$ est en pouvoir de gagner. À l'inverse, celui qui a joué une fois une distribution vérifiant $P$ est amené, si son adversaire connaît la stratégie, à ne plus jamais avoir à jouer que des distributions $P$. 
  • Ce jeu est donc dépourvu de hasard. Si celui qui commence (Albertazzi dans le film) part d'une distribution vérifiant $P$, il faudra une erreur de son adversaire pour qu'il puisse gagner. Autrement, il renvoie au coup suivant à son adversaire une distribution vérifiant $P$ (perdante) et il est sûr de gagner. 
  • La force de Bouton est d'avoir mis en évidence une propriété $P$ que seul l'un des deux joueurs a le pouvoir de conserver, ce qui lui donne la maîtrise complète de la partie. L'expression du nombre d'allumettes en écriture binaire permet justement de construire, en alternant les $0$ et les $1$, l'alternance régulière entre $P$ et non $P$.

Cas de Marienbad : celui qui prend la dernière perd

Désormais, pour gagner, il faut contraindre l'adversaire à jouer la distribution ne contenant qu'une seule allumette — dans tous les autres cas, il peut évidemment éviter de prendre la dernière. Cette distribution ne vérifie pas $P$. Est-ce à dire qu'il suffit d'inverser les rôles par rapport au cas précédent, et de renvoyer pendant toute la partie du non $P$ à l'adversaire pour gagner ? Cette stratégie est inapplicable car seul celui qui renvoie $P$ est en mesure de garder la main pendant tout le jeu : il contraint l'adversaire à rendre non $P$ (théorème B), et renvoie à son tour $P$ (théorème A). À l'inverse, qui renvoie non $P$ laisse l'adversaire libre de renvoyer $P$ ou non $P$. On doit donc renvoyer $P$ le plus longtemps possible, et ne changer qu'à la fin. Il s'agit de savoir quand. 

Une difficulté vient s'ajouter: il peut arriver qu'en renvoyant $P$ on se condamne à perdre. C'est le cas si l'on donne à l'adversaire la distribution à deux rangées d'une allumette ($1$-$1$), et, plus généralement, pour toute distribution avec un nombre pair de rangées à une allumette. À l'inverse, quand on envoie un nombre impair de rangées à une allumette (distribution ne vérifiant par $P$), on condamne l'adversaire à prendre la dernière. 

La stratégie à suivre est donc la suivante, pour le joueur capable de renvoyer $P$ :

— envoyer $P$ aussi longtemps que, dans les distributions données à l'adversaire, il subsiste au moins une rangée contenant plus de deux allumettes ;
— si l'on doit jouer à partir d'une distribution du type $1$-$1$-$1$-$\dots$-$n$, on doit éviter de rendre $1$-$1$-$\dots$-$1$, avec un nombre pair de $1$. Il faut prendre les $n$ allumettes si le nombre initial de rangées est pair, ou seulement $n-1$, si ce nombre est impair. 

Exactement comme dans le premier cas, tout joueur en mesure de renvoyer une distribution vérifiant $P$ est assuré de gagner, et celui recevant une telle distribution perdra.

Retour à Marienbad

Pour revenir à nos deux protagonistes, il faut remarquer que, à chaque fois que la scène du jeu se répète (et le film est fondé sur la répétition et l'absence de cadres temporels ordinaires), Pitoëff laisse son adversaire commencer, avec une distribution (1-3-5-7) vérifiant la propriété $P$ : le sort d'Albertazzi est entièrement entre ses mains. « Je gagne toujours... ». Singulier exemple, et l'un des rares, en théorie des jeux, pour lequel on possède une stratégie certaine.