Pour simplifier un peu la chose, nous n’allons pas jouer à la version « misère » comme dans le film d’Alain Resnais, mais à la version « normale » (ie que le joueur prenant la dernière allumette a gagné).

Etape 1 : Trouver les nimbers

La notion de nimber, juste contraction des mots ‘Nim’ et ‘number’, est un pilier de la théorie des jeux combinatoire. Un nimber désigne un ‘jeu de Nim à un seul tas’ (par opposition au 4 tas d’allumettes décrits plus haut) mais par extension on appelle également nimber, un nombre entier caractéristique d’une position donnée pour un ‘jeu de Nim à un tas’. [Remarque; le nimber est aussi parfois appelé ‘nombre de Grundy’ ou ‘nimbre’ pour les anglophobes].
Dans le cas du jeu de Marienbad du film de Resnais, il y a quatre tas d’allumettes donc quatre nimbers. Reste à voir comment calculer ces nimbers.
Le nimber d’un tas se définit alors comme ce qui suit:

• Le nimber de la position finale vaut 0
• Le nimber d’une position donnée est définit comme le plus petit entier naturel (ie positif ou nul) n’apparaissant pas dans la liste des nimbers des positions pouvant suivre immédiatement cette position.

Alors comme ça… ça peut sonner un peu cabalistique mais avec des exemples tout est plus clair:
Pour un tas de 0 allumette: le nimber est 0 (cf définition).
Pour un tas de 1 allumette: le nimber est 1. Lorsqu’il ne reste qu’une allumette, je n’ai pas le choix : je vais enlever une allumette et la position suivante sera un tas de 0 allumette. La liste des nimbers des positions suivantes est donc {0}.
Le plus petit entier positif n’appartenant pas à la liste {0}, c’est bien 1.
Pour un tas de 2 allumettes: le nimber est 2. Lorsqu’il reste deux allumettes, je peux soit choisir d’en retirer une, soit deux : la positions suivantes possibles sont « un tas de 0 allumette » ou « un tas de 1 allumette ». La liste des nimbers des positions suivantes possibles est donc {0,1}.
Le plus petit entier positif n’appartenant pas à la liste {0,1}, c’est bien 2.
Dans le cas du jeu de Marienbad, les nimbers correspondent donc aux nombres d’allumettes de chaque tas (facile!)

Remarque: Imaginons que nous soyons dans une émission de télévision grand publique et que je porte un masque à tête de tigre (grrrr). J’aurais alors pu rajouter la règle « chaque joueur ne peut enlever que 1,2 ou 3 allumettes » dans ce cas:
Pour les tas de 0,1,2 et 3 allumettes, tout marche pareil, mais c’est après que les nimbers changent un peu.
Pour un tas de 4 allumettes, la position 0 allumette ne peut pas être atteinte (je ne peux retirer que 3 allumettes au maximum). La liste des nimbers des positions suivantes sera donc {1,2,3} et le plus petit entier naturel n’appartenant pas à cette liste c’est 0.
Pour un tas de 5 allumettes, le nimber est  1
6 allumettes: le nimber est 2 …
et ainsi de suite.
Pour un tas de n allumettes, le nimber est donc définit comme le reste de la division euclidienne du nombre d’allumettes du tas par 4.

Etape 2 : Chercher à annuler la somme de Nim des nimbers

Et maintenant on fait quoi avec nos nimbers?
Et c’est là que Sprague et Grundy interviennent. En effet, le théorème de Sprague-Grundy nous explique que tout jeu impartial peut être transformé en un « jeu de Nim à un tas » équivalent possédant un nimber propre à chacune de ses positions. Pour le cas du jeu de Marienbad (Bouton l’avait déjà démontré), le nimber global du jeu peut s’obtenir en faisant la somme de Nim des différents nimbers.
Une fois cet unique nimber obtenu et propre à chaque position du jeu.

La stratégie gagnante (pour la version ‘normale’) consistera toujours à agir sur le jeu de manière à annuler ce nimber global.

Donc comme nous l’avons dit, pour le jeu de Marienbad, ce nimber s’obtient en faisant la somme de Nim des nimbers des différents tas.
Pour effectuer cette opération un peu spéciale, il faut commencer par passer tous nos nimbers en binaire.
Alors, pour rappel, écrire un nombre en binaire c’est décomposer ce nombre en une somme de puissances de 2.
L’astuce pour convertir facilement un nombre décimale en binaire consiste à le diviser plusieurs fois par 2 et regarder le reste Euclidien de chacune de ces divisions (cf figure 3, ci-contre).
Une fois nos quatre nimbers passés en binaire, il faut les sommer un à un avec les règles suivantes (les informaticiens reconnaîtront une somme XOR):

• 0+0=0
• 1+1=0
• 1+0=0+1=1

Dans notre cas précis, notre somme est égale à 000

Et comme l’objectif poursuivit par une stratégie gagnante est de toujours faire passer cette somme de Nim à 000, on constate donc que la position initiale est une position perdante. En effet, puisque la somme de Nim est déjà égale à 0, toute action de jeu la fera varier vers un résultat différent de 000 (c’est pas moi qui le dit, c’est Bouton!).

 

Mise en application:

Imaginons que votre adversaire joue en premier, vous êtes donc dans une position gagnante…

Si vous vous appliquez, votre adversaire n’a aucune chance de gagner. Votre adversaire prend deux allumettes dans la pile de 7  allumettes. La nouvelle configuration est donc : 4 rangées de 1,2,5 et 5 allumettes.
La somme de Nim est alors de 010.
Il vous faut donc refaire passer cette somme à 000. Pour cela vous pouvez retirez deux allumettes au tas de 3 allumettes.