Nim restreint et suites fractales
-
Maximum Nim & Minimum Nim

Jeux de Nim

Fonctions de Grundy

Définition

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-)

Exemple

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

Propriétés

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 ...

Nim à retraits minorés ou majorés

Jeux concernés

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.

Propriétés

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

Exemples

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

Calcul des fonctions de Grundy

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




         



Autres pages du site

Jeu de Wythoff Fonction de Grundy - Périodicité
Jeux de Nim
Page de liens sur les jeux de Nim

Références, documents, liens

Fractal Sequences and Restricted Nim   Lionel Levine University of California Berkeley «... We introduce a new variant of Nim, Restricted Nim, which restricts the number of stones a player may re- move from a heap in terms of the size of the heap. Certain classes of Restricted Nim are found to produce sequences of Grundy numbers with a self-similar fractal structure...»
Diviser pour régner   une stratégie fondamentale de l'algorithmique. Philippe Dumas INRIA Rocquencourt
The On-Line Encyclopedia of Integer Sequences   
Jeux et Stratégies   Dominique Perrin
Elwyn Berlekamp   
Combinatorial Game Theory   David Eppstein
Combinatorial Game Suite   is an open-source program to aid research in combinatorial game theory.

















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014