- Jeu de Wythoff
-
Le jeu de Wythoff est une variante du jeu de Nim, inventée en 1907 par le mathématicien hollandais Willem A. 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
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.
Stratégie gagnante
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. Si le joueur dont c'est le tour peut gagner à partir d'une position donnée, on dit que cette position est chaude (hot en anglais), et froide (cold) sinon. En 1907, Wythoff a caractérisé numériquement les positions froides du jeu, en montrant qu'elles sont de la forme (nk, mk) avec :
avec k un entier quelconque, ϕ le nombre d'or, et
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 :
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
- Richard J. Nowakowski The History of Combinatorial Game Theory Jan. 2009, p.4
Wikimedia Foundation. 2010.
