Nim restreint et suites fractales
-
Maximum Nim & Minimum Nim

On considère un 1-graphe sans boucles dont l'ensemble des sommets est X.
Une fonction de Grundy, lorsqu'elle existe, fait correspondre à tout sommet x du graphe un entier naturel g(x) qui est le plus petit naturel ne figurant pas dans g(Y) où Y est l'ensemble des successeurs de x. (P. M. Grundy 1939).
La fonction de Grundy g(x) est souvent notée mex(x) (MEX : Minimum EXclu-ded-)

Il s'agit ici du jeu de Nim où les deux joueurs retirent tour à tour, à leur choix, 1, 2 ou trois allumettes du tas. Le gagnant est celui qui retire la dernière allumette.
Le graphe G associé à ce jeu a pour sommets l'ensemble X = {0, 1, 2, ..., 200} tel que chaque sommet x a pour successeurs x-1, x-2 et x-3 (lorsqu'ils existent dans X).
On obtient g(0) = 0 car 0 n'a pas de successeur.
g(1) = 1, g(2) = 2, g(3)=3, g(4) = 0 car les successeurs ont pour valeurs de Grundy g(1)=1, g(2)=2, g(3)=3 et que 0 est le plus petit naturel qui ne soit pas dans {1, 2, 3}.
g(n) = n%4 est le reste de la division euclidienne de n par 4. On obtient la suite ID Number: A010873 le N.J.A. Sloane

Un graphe n'admet pas toujours une fonction de Grundy.
Un graphe symétrique admet une fonction de Grundy. Idem pour un graphe transitif et pour un graphe sans circuit de longueur impaire.
Un graphe sans circuit admet une fonction de Grundy unique g et pour tout sommet x, g(x) est au plus égal à la longueur du plus long chemin issu de x.
L'ensemble N des sommets x tels que g(x) = 0 est un noyau du graphe. En effet, il est facile de montrer
x dans N n'a pas de successeur y dans N.
si x n'est pas dans N, alors il a un successeur dans N.
Diviser pour régner (important en particulier pour les jeux de Nim à plusieurs tas) : si un graphe G est une somme cartésienne de plusieurs graphes G_i admettant tous une fonction de Grundy g_i, alors G admet pour fonction de Grundy la somme digitale (le XOR noté ~ ) g = g_1 ~ g_2 ~ g_3 ...

Dans l'exemple décrit plus haut, le retrait effectué par un joueur est compris entre 1 et 3. On va généraliser ce jeu en définissant un retrait minimum min(n) et un retrait maximum max(n) dépendant uniquement du nombre n d'allumettes du tas. Suivant le type de jeu, retire min(n) allumettes ou plus pour un jeu minoré et retire entre 1 et max(n) allumettes pour un jeu majoré.
Remarque : Le jeu de Fibonacci-Nim n'entre pas dans cette catégorie de jeux car le retrait dépend du retrait précédent et non du nombre n d'allumettes.

Certaines propriétés sont démontrées dans les références. On pourra chercher à les découvrir sur les exemples proposés (cliquer sur le bouton [Exemples]).
On peut aussi fabriquer de nouveaux exemples.
Les suites calculées sont les valeurs g(i) des fonctions de Grundy pour i variant de 0 au nombre n

Retrait majoré par n/2
Retrait minoré par n/2
Retrait majoré périodique

Vous pouvez modifier ci-dessous les valeurs des deux tableaux this.min[i] ou this.max[i] en vous inspirant des exemples. Le code est du javascript et vous pouvez utiliser les fonctions mathématiques du javascript)
Certaines de ces suites sont référencées sur le site de N.J.A. Sloane, dans ce cas leur numéro d'identification est donné.
Le pur Nim classique est : Cliquer ICI.

Fonction de Grundy

Jusqu'à n =

fonction de Grundy g   lignes de termes   différence n- g(n) (g, f, g-f-1) lorsque f croît

for(var i=0; i<=n; i++) { this.min[i] = floor(1) this.max[i] = floor(i/2); }