Le jeu de Nim, dont il existe plusieurs variantes, est le plus connu des jeux de stratégie pure à deux joueurs où chacun joue alternativement, le perdant étant celui qui ne peut plus jouer. Les origines en sont probablement très anciennes. Il a été popularisé en 1961 par le film d’Alain Resnais et Alain Robbe-Grillet, L’Année dernière à Marienbad.
Le jeu des allumettes de Marienbad résolu !
Le principe : on dispose des allumettes sur plusieurs lignes, chacune contenant un certain nombre d’allumettes. À chaque tour, celui qui joue choisit une ligne et prend, sur cette ligne, le nombre d’allumettes qu’il veut (au moins une). Le dernier à pouvoir jouer a gagné.
Comme vu dans les précédents articles de ce dossier, dans ce type de jeux, chaque position (ou état) est de nature gagnante ou perdante pour celui qui en hérite. Cette connaissance pour chaque état entraîne la possibilité pour chacun des joueurs d’appliquer une stratégie optimale.
Commençons par évoquer une méthode de calcul de cette nature dans le jeu de Marienbad. Sa résolution, à la fois simple et spectaculaire, fait appel à la décomposition binaire et à la somme sans retenue, imaginée en 1901 par le mathématicien américain Charles Leonard Bouton (1869‒1922).
Soit a = (a1, ...
Lire la suite