- Jeu de Grundy
-
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 impartiaux[1], désormais connue sous le nom de théorème de Sprague-Grundy.
Sommaire
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 taille distincte. 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 A002188.
En 1982, Elwyn Berlekamp, John Horton Conway, et Richard Guy ont conjecturé[2] 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
- P. M. Grundy Mathematics and Games Eureka, vol.27, octobre 1964, réimpression de l'article de Eureka, vol. 2, mai 1939
- E. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays Academic Press, 1982.
Liens externes
- Jeu de Grundy sur MathWorld
- Séquence des nimbers du jeu de Grundy (A. Flammenkamp)
Wikimedia Foundation. 2010.
