vignette|Piles de pièces. Chacune des trois pile peut être divisée en deux autre piles de taille différente. Après avoir divisé la pile la plus à gauche sur la photo, les deux piles résultantes ne peuvent plus être divisées en piles de tailles différentes (une pile d'une pièce (indivisible) et une pile de deux pièces (ne peut être divisée en deux piles de tailles différentes)). Le jeu de Grundy est une variante du jeu de Nim. Il s'agit d'un jeu impartial à deux joueurs, inventé en 1939 par Patrick Grundy pour illustrer sa classification des jeux impartiauxP. M. Grundy Mathematics and Games Eureka, vol.27, octobre 1964, réimpression de l'article de Eureka, vol. 2, mai 1939, désormais connue sous le nom de théorème de Sprague-Grundy.
Règle du jeu
La position de départ consiste en un unique tas d'objets (des allumettes ou des pions, par exemple), et le seul coup disponible pour les joueurs consiste à séparer un tas d'objets en deux tas de tailles distinctes. Les joueurs jouent à tour de rôle, jusqu'à ce que l'un d'entre eux ne puisse plus jouer. Le jeu se joue habituellement en version normale, c'est-à-dire que le joueur qui ne peut plus jouer est le perdant.
Suite des nimbers D'après le théorème de Sprague-Grundy, un tas de n objets du jeu de Grundy est équivalent à un tas du jeu de Nim d'un certain nombre d'objets, appelé le nimber. L'étude du jeu de Grundy consiste alors à calculer pour chaque tas quel est son nimber équivalent.
taille du tas : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... nimber : 0 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0 ...
La suite des nimbers du jeu de Grundy est référencée sur l'Encyclopédie en ligne des suites de nombres entiers sous .
En 1982, Elwyn Berlekamp, John Horton Conway, et Richard Guy ont conjecturéE. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays Academic Press, 1982. que cette suite des nimbers est périodique, mais cette question n'est pas résolue, malgré le calcul par Achim Flammenkamp des 235 premières valeurs de la suite.
Références
Liens externes Jeu de Grundy sur MathWorld Séquence des nimbers du jeu de Grundy (A. Flammenkamp) Comptes rendus MATh.en.JEANS sur le jeu de Grundy
Grundy, Jeu de Grundy, Jeu de Catégorie:Théorie des jeux combinatoires Catégorie:Jeu de Nim