Jeu de Wythoff
Fonction de Grundy - Périodicité

Les deux joueurs déplacent à tour de rôle un pion sur se quadrillage. le gagnant est le premier à atteindre l'origine : la case (0, 0).
Les déplacements permis à partir de la case (x, y) sont vers l'ensemble Im(x, y) des cases (x-a, y), (x, y-b) ou (x-c, y-c) avec les conditions 0<a<x, 0<b<y et 0<c<x et c<y.

(Page du jeu de Wythoff)

Le graphe correspondant est sans circuit et il existe une fonction de Grundy g unique.
g(0, 0) = 0 et pour x et y non tous les deux nuls, g(x, y) est le plus petit entier qui n'est pas dans g(Im(x, y)).

Les valeurs nulles g(x, y) = 0 correspondent aux positions gagnantes du jeu, c'est-à-dire les cases où placer le pion chaque fois que l'on joue, pour gagner, (du moins lorsque l'adversaire n'a pu nous en empêcher, s'il en a eu la possibilité en début de partie).

Grundy g(x,y)	g(x,y)-x+2y	x+y-g(x,y)

Sauf pour certains couples particuliers comme (0, y),(x, 0) ou encore pour ceux où la fonction de Grundy s'annule, on ne connaît pas de formule permettant un calcul direct. La seule possibilité est donc le calcul par récurrence de la fonction de Grundy, ici un programme en javascript se charge des calculs.

Tant que x et y restent petits, g(x, y) se calcule aisément. Le programme de cette page a pu effectuer les calculs pour x et y inférieurs à N=200, mais évitez de lui en demander trop !

Le programme permet d'obtenir les valeurs g(x, y) modulo un entier m supérieur ou égal à 2. Il permet aussi de mettre en évidence, en les écrivant en rouge, les valeurs supérieures à un entier K donné.
Indiquez les valeurs de m et de K avant de lancer le calcul ou au contraire laissez les cases vides, ci-dessous.
Pour obtenir la table de g(x,y)-s+2*y ou de x+y-g(x,y) au lieu de g(x,y), cocher la case correspondante.

Valeurs maximales de x et de y, X Y =
g(x, y) est calculé modulo m =
Valeur coloriée à partir de K =
Grundy g(x)
Périodique g(x,y)-x+2y
Périodique x+y-g(x,y)

Symétrie g(x, y) = g(y, x).
Alignements des positions gagnantes sur deux droites.
Chaque ligne ou colonne du tableau est une permutation de N. En particulier, pour x=0 on a g(0, y) = y et pour y=0, g(x, 0)=x.
g(x, y) est compris (au sens large) entre x-2y et x+y. (Howard Landman)
Pour y fixé et x variable, la suite des g(x,y) -x + 2*y est périodique après un certain rang. Les périodes sont successivement, pour y = 0 : [0], pour y = 1 : [3, 3, 0], pour y = 2 : [6, 3, 3], pour y = 3 : [8, 9, 4, 2, 9, 4] ...
De même sont périodiques,lorsque x est variable et y constant, les suites de la forme a.(g(x,y)-x+b).
Les suites périodiques sans doute les plus naturelles sont sans doute g(x,y) -x + 2*y et x+y-g(x,y).