Un jeu si simple qu'on peut l'expliquer en dix secondes — et pourtant entièrement résolu, par une opération que personne n'attendait là : l'addition en base deux sans retenue.
Des tas d'allumettes. Chacun son tour, on en retire autant qu'on veut, mais dans un seul tas et au moins une. Celui qui prend la dernière allumette gagne. Rien de plus. En 1901, Charles Bouton donna la stratégie complète ; en 1935, Sprague et Grundy montrèrent que ce petit jeu contient tous les jeux de ce type. Les cinq planches qui suivent refont le chemin, et chaque affirmation y est vérifiée par calcul exhaustif sur la page elle-même.
Cliquez sur une allumette : elle disparaît, ainsi que toutes celles qui sont à sa droite dans la même rangée. La machine répond aussitôt. Essayez de gagner — puis regardez combien de fois vous y arrivez.
Ce qu'il faut remarquer. Contre la machine parfaite, la position de départ 1·3·5·7 — celle du film L'Année dernière à Marienbad — est perdue d'avance pour celui qui commence. Vous ne gagnerez que si la machine se trompe, et elle ne se trompe jamais. En revanche, sur 3·4·5, c'est vous qui avez la partie gagnante : il existe dès le premier coup une réponse qui vous assure la victoire quoi que fasse la machine. En mode misère, la règle s'inverse : celui qui prend la dernière allumette perd. Comment la machine sait-elle, sans jamais explorer l'arbre des parties, quel coup jouer ? Les planches 2 à 4 démontent le mécanisme.
Commençons par une version bridée : un seul tas de n allumettes, et l'on ne peut en retirer qu'entre 1 et k. Le ruban ci-dessous colorie chaque position selon son sort, calculé de proche en proche à partir de 0 — sans aucune formule. Une régularité saute aux yeux.
Ce qu'il faut remarquer. Les positions perdantes sont exactement les multiples de k+1, et rien d'autre — le calcul brut le confirme sur 201 positions sans une seule exception. La raison est limpide : depuis un multiple de k+1, tout retrait de 1 à k en sort ; depuis une position qui n'en est pas un, on peut toujours y revenir en retirant le reste. La stratégie tient en une phrase : ramenez toujours l'adversaire sur un multiple de k+1. Retenez la structure : on ne cherche pas « le bon coup », on cherche l'ensemble des positions perdantes, et la stratégie en découle toute seule.
Deux tas, retrait libre. La carte ci-dessous donne le sort de chaque position (a, b), là encore calculé de proche en proche. Cliquez sur une case pour voir le coup gagnant ; le bouton déroule une partie entière.
Ce qu'il faut remarquer. Toutes les positions perdantes sont sur la diagonale, et aucune ailleurs. La stratégie est celle du miroir : égalisez les deux tas, puis copiez votre adversaire. S'il prend trois allumettes à gauche, prenez-en trois à droite. L'égalité étant rétablie après chacune de vos réponses, c'est forcément lui qui se retrouvera devant deux tas vides. Notez que la diagonale a = b s'écrit aussi a ⊕ b = 0, où ⊕ est l'opération de la planche suivante : le miroir est un cas particulier déguisé.
Trois tas ou plus : le miroir ne suffit plus. Écrivons chaque tas en base deux, l'un sous l'autre, et comptons la parité de chaque colonne. Une colonne impaire est un déséquilibre. La position est perdante si et seulement si toutes les colonnes sont paires.
Ce qu'il faut remarquer. Le nim-somme ⊕ est l'addition en base deux sans retenue : colonne par colonne, 0⊕0 = 0, 1⊕1 = 0, 0⊕1 = 1. Le théorème de Bouton dit que la position est perdante exactement quand ce nim-somme vaut zéro. Le bouton de vérification calcule le sort réel des 65 536 positions à quatre tas de 0 à 15, par récurrence pure, sans jamais utiliser la formule ; puis il compte les désaccords avec elle. Il en trouve zéro, et 4 096 positions perdantes, soit exactement une sur seize — car les trois premiers tas étant libres, le quatrième est imposé. En mode misère, une seule exception : tant qu'il reste un tas d'au moins deux allumettes, on joue comme en normal ; dès que tous les tas valent 0 ou 1, il faut en laisser un nombre impair. Une seule ligne change, et le théorème redevient exact.
Voici le résultat qui change de niveau. Prenez n'importe quel jeu à deux joueurs, à information complète, sans hasard, où les deux joueurs disposent des mêmes coups et où celui qui ne peut plus jouer perd. Sprague et Grundy affirment qu'il est équivalent à un simple tas de Nim — et que plusieurs tels jeux joués en parallèle s'additionnent par le nim-somme. Trois volets pour le voir, puis une épreuve sur 29 952 positions.
Un jeu de soustraction : un tas, et l'on ne peut retirer que les quantités cochées. À chaque taille de tas on attribue le plus petit entier positif ou nul qui n'apparaît chez aucun de ses successeurs — le mex. Cet entier est la taille du tas de Nim équivalent.
Un jeton sur un damier, en bas à gauche l'arrivée. On le déplace vers la gauche, vers le bas, ou en diagonale vers le bas-gauche, d'autant de cases qu'on veut. Chaque case reçoit sa valeur de Grundy. Les cases de valeur 0 — les positions perdantes — ne suivent aucune diagonale simple : elles s'alignent sur deux droites de pentes irrationnelles.
On empile maintenant trois jeux qui n'ont rien en commun : le jeton de Wythoff sur un damier 12×12, un tas de Nim ordinaire de 0 à 12, et le jeu de soustraction {1, 3, 4} de 0 à 15. À son tour, un joueur joue dans le jeu de son choix. Le calcul brut détermine le sort réel de chacune des 29 952 positions du produit. La prédiction de Sprague-Grundy, elle, ne regarde que le nim-somme des trois valeurs de Grundy.
Ce qu'il faut remarquer. Aucun des trois jeux ne ressemble à Nim : l'un se joue sur un damier avec un nombre d'or dans ses positions perdantes, l'autre a une suite périodique de période 7, le troisième seul est un vrai tas. Pourtant il suffit de remplacer chacun par le tas de Nim de sa valeur de Grundy, puis d'appliquer le théorème de Bouton, pour prédire le sort exact des 29 952 positions — zéro désaccord. C'est la portée réelle du jeu de Nim : il n'est pas un jeu parmi d'autres, il est la forme normale de toute cette famille. La contrepartie est honnête : calculer une valeur de Grundy peut être aussi coûteux que résoudre le jeu ; le théorème ne promet pas que ce sera facile, seulement que Nim est au bout du chemin.