Jeu de Grundy

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

  1. P. M. Grundy Mathematics and Games Eureka, vol.27, octobre 1964, réimpression de l'article de Eureka, vol. 2, mai 1939
  2. E. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays Academic Press, 1982.

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Jeu de Grundy de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Jeu impartial — Dans la théorie des jeux combinatoires, un jeu impartial est un jeu dans lequel les coups autorisés, ainsi que les gains obtenus, dépendent uniquement de la position, et pas du joueur dont c est le tour. Les jeux impartiaux incluent notamment le… …   Wikipédia en Français

  • Jeu de Cram — Pour les articles homonymes, voir CRAM. Le jeu de Cram est un jeu mathématique, étudié dans le cadre de la théorie des jeux combinatoires. Le jeu se joue sur un damier que l on remplit progressivement de Dominos. Il a été connu sous plusieurs… …   Wikipédia en Français

  • Jeu octal — Les jeux octaux, étudiés dans le cadre de la théorie des jeux combinatoires[1], sont une catégorie de jeux impartiaux, proches du jeu de Nim. Ils se jouent avec des tas d objets où les coups autorisés consistent à retirer des objets d un tas et… …   Wikipédia en Français

  • Jeu partisan — Dans la théorie des jeux combinatoires, un jeu partisan est un jeu qui n est pas impartial, c est à dire un jeu pour lequel les coups disponibles dépendent non seulement de la position, mais aussi du joueur dont c est le tour. Le concept de jeu… …   Wikipédia en Français

  • Théorème de Sprague-Grundy — Dans la théorie des jeux combinatoires, le théorème de Sprague Grundy indique que tout jeu impartial en version normale (c est à dire où le joueur qui ne peut plus jouer est le perdant), est équivalent à un certain tas du jeu de Nim, appelé… …   Wikipédia en Français

  • Superman: The Man of Steel (jeu vidéo, 1993) — Superman The Man of Steel Éditeur Virgin Interactive Développeur Virgin Interactive (MD) Graftgold (MS, GG) Date de sortie 1993 Genre Plates formes Mode de jeu …   Wikipédia en Français

  • Winning Ways for your Mathematical Plays — (Academic Press, 1982), est un livre écrit par Elwyn Berlekamp, John Conway, et Richard Guy, qui rassemble l ensemble de leurs résultats sur les jeux mathématiques. Avec On Numbers and Games, ce livre est considéré comme fondateur de la théorie… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Jeux de Nim — jeu de société Ce jeu appartient au domaine public Format divers Joueur(s) 2 Âge à partir de 5 ans Durée annoncée environ 10 minutes …   Wikipédia en Français

  • Going for Gold — Genre Jeu télévisé Réalisation Reg Grundy Organisation Présentation Henry Kelly (BBC1), John Suchet (Five) Pays  Royaume Uni Langue …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”