Jeu de Wythoff

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le jeu de Wythoff est une variante du jeu de Nim, inventée en 1907 par le mathématicien hollandais Willem Abraham Wythoff. Il s'agit d'un jeu impartial à deux joueurs, qui est historiquement le deuxième jeu mathématique, après le jeu de Nim, à avoir été résolu de façon exacte[1].

Règle du jeu[modifier | modifier le code]

La position de départ consiste en deux tas d'objets (des allumettes ou des pions), et les coups disponibles pour les joueurs consistent à retirer un nombre quelconque d'objets de l'un des tas, ou bien le même nombre d'objets de chacun des tas. Les joueurs jouent à tour de rôle, jusqu'à ce que l'un d'entre eux ne puisse plus jouer, et celui qui ne peut plus jouer est le perdant.

Une variante équivalente de ce jeu consiste à déplacer un jeton à tour de rôle sur un damier, soit en se déplaçant vers la gauche, soit en se déplaçant vers le bas, soit en se déplaçant le long d'une diagonale vers la gauche et le bas, le joueur atteignant la case inférieure gauche ayant gagné.

Stratégie gagnante[modifier | modifier le code]

Indication en bleu des positions gagnantes à atteindre dans la version damier du jeu de Wythoff. La case inférieure gauche correspond à la position (0,0) du jeu de Wythoff à deux tas.

La position du jeu (c'est-à-dire l'état du jeu) à un moment donné de la partie est notée par un couple (n, m) qui représente le nombre d'objets dans chacun des tas. Une position est dite gagnante si le joueur qui y parvient peut gagner (la position finale (0,0) est gagnante). Une position est dite perdante dans le cas contraire. Un joueur qui arrive à une position perdante pourra voir son adversaire atteindre une position gagnante au coup suivant, et un joueur parvenu à une position gagnante verra son adversaire, quoique ce dernier joue, atteindre une position perdante. La stratégie gagnante consiste donc à se déplacer d'une position gagnante à une autre jusqu'à avoir pris le dernier objet.

En 1907, Wythoff a caractérisé numériquement les positions gagnantes du jeu, en montrant qu'elles sont de la forme (nk, mk) ou (mk, nk) avec :

n_k = \lfloor k \phi \rfloor
m_k = \lfloor k \phi^2 \rfloor = n_k + k

avec k un entier quelconque, \phi le nombre d'or, et \lfloor ... \rfloor la fonction partie entière. Les suites nk et mk sont référencées sur l'Encyclopédie en ligne des suites de nombres entiers sous A000201 et A001950.

Les deux suites nk et mk sont les suites de Beatty associées à l'équation :

\frac{1}{\phi} + \frac{1}{\phi^2} = 1 \,.

Le théorème de Beatty permet alors d'affirmer que ces deux suites sont disjointes et complémentaires : tout entier positif apparaît exactement une et une seule fois soit dans nk soit dans mk.

Références[modifier | modifier le code]

  1. (en) Richard J. Nowakowski, The History of Combinatorial Game Theory, janvier 2009, p.4