Jeu de Wythoff

Le jeu de Wythoff est une variante du jeu de Nim, inventée en 1907 par le mathématicien néerlandais 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.

Règle du jeu

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

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, quoi que 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 (n_k, m_k) ou (m_k, n_k) avec :

$n_{k}=\lfloor k\phi \rfloor$

$m_{k}=\lfloor k\phi ^{2}\rfloor =n_{k}+k$

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

Les deux suites n_k et m_k 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 n_k soit dans m_k.