Jeu de Wythoff : de quoi s’agit-il ?
Le jeu de Wythoff se joue avec deux piles. À votre tour, soit vous prenez autant d’objets que vous voulez dans une pile, comme au Nim, soit vous prenez le même nombre dans les deux piles à la fois. Le joueur qui prend le dernier objet gagne : ce jeu se joue toujours dans le sens normal, l’option misère et l’option des piles de départ du jeu classique ne s’appliquent donc pas.
La taille des piles vient de l’option de taille de la configuration de la table : 5 et 7 (petit), 9 et 12 (moyen, par défaut) ou 14 et 20 (grand). Une façon connue de se représenter le jeu est une dame d’échecs qui ne peut aller que vers la gauche, vers le bas ou en diagonale vers le bas à gauche : les deux piles sont ses distances aux deux bords de l’échiquier, et celui qui l’amène dans le coin gagne.
Changements de règles
| Règle | Nim standard | Jeu de Wythoff |
|---|---|---|
| Piles | Nim standardPlusieurs piles : 1, 3, 5 et 7 objets par défaut, ou un autre ensemble choisi dans la configuration de la table. | Jeu de WythoffDeux piles : 5 et 7, 9 et 12 (par défaut) ou 14 et 20, choisies comme taille dans la configuration de la table. |
| Coups | Nim standardPrenez un objet ou plus dans une pile. | Jeu de WythoffSoit prenez un objet ou plus dans une pile, soit prenez le même nombre dans les deux piles. |
| Objectif | Nim standardJeu misère par défaut : celui qui prend le dernier objet perd. La configuration permet de passer au jeu normal, où prendre le dernier objet fait gagner. | Jeu de WythoffToujours en jeu normal : celui qui prend le dernier objet gagne. |
| Jeu gagnant | Nim standardLaissez les piles avec une somme de Nim (le XOR bit à bit de leurs tailles) nulle, avec une subtilité en fin de partie misère. | Jeu de WythoffLes positions perdantes pour le joueur au trait sont les paires 1 et 2, 3 et 5, 4 et 7, 6 et 10, 8 et 13, et ainsi de suite : la k-ième paire est formée des parties entières de k × φ et k × φ², où φ est le nombre d’or. Aucune position de départ proposée ici n’est une telle paire, le premier joueur peut donc gagner. |
Histoire
Le mathématicien néerlandais Willem Abraham Wythoff a publié le jeu et sa solution en 1907, dans l’article « A modification of the game of nim » paru dans Nieuw Archief voor Wiskunde. Il a montré que les positions perdantes suivent le nombre d’or. Les plus petits et les plus grands nombres des paires perdantes forment deux suites de Beatty qui, à elles deux, contiennent chaque entier positif exactement une fois, ce qui explique que le jeu apparaisse dans les écrits de théorie des nombres autant que dans ceux sur les jeux.
Martin Gardner a parlé du jeu dans sa rubrique de magazine Mathematical Games en mars 1977, en affirmant qu’on y jouait en Chine sous le nom de jiǎn shízǐ, « ramasser des pierres ». Nous ne connaissons aucune autre source pour cette affirmation.