Le jeu de Nim

Des tas d'objets ; chacun en retire autant qu'il veut dans un seul tas, et qui prend le dernier gagne. On joue contre la page, ou à deux sur le même écran. Le jeu est résolu depuis 1901 par une addition en base $2$ sans retenue, et la démonstration est donnée en entier.

De $2$ à $6$ tas d'objets ; à tour de rôle, chaque joueur retire autant d'objets qu'il veut d'un seul tas, et celui qui prend le dernier gagne. On affronte la page, qui joue parfaitement ou se trompe parfois, ou un ami sur le même écran, la page servant d'arbitre. Elle peut afficher les tas en base $2$ et leur somme de Nim, et indiquer un coup gagnant.

Ce que cela signifie : la somme de Nim $a_1 \oplus \dots \oplus a_k$ est l'addition en base $2$ sans retenue. Le théorème de Bouton (1901), démontré dans la page, dit que le joueur au trait gagne si et seulement si cette somme n'est pas nulle, en la rendant nulle à chaque coup. Avec les tas $3$, $4$, $5$, la somme vaut $2$ et le seul coup gagnant ramène le tas de $3$ à $1$. Avec $1$, $3$, $5$, $7$, la somme est nulle : celui qui commence perd. La page a vérifié le théorème par recherche exhaustive sur $3\,072$ positions.

Le piège le plus courant est de chercher une règle simple (prendre beaucoup, égaliser les tas, laisser un nombre pair) : seule l'égalisation est juste, et seulement pour deux tas.