Nimber

En mathématiques, dans la théorie des jeux combinatoires, les nimbers sont des jeux particuliers, définis comme des jeux de Nim à un tas avec un nombre éventuellement infini d'allumettes. Plus précisément, le nimber correspondant au nombre ordinal , souvent noté *, est défini comme le tas d'allumettes du jeu de Nim avec un nombre d'allumettes. Un nimber peut aussi désigner directement ce nombre d'allumettes. Les nimbers interviennent en particulier dans la théorie des jeux impartiaux : en effet, d'après le théorème de Sprague-Grundy, tout jeu impartial est équivalent à un certain nimber. Dans le cas d'un jeu de Nim fini où le perdant est celui qui ne peut plus jouer, on affecte à chaque position de ce jeu un nombre appelé nombre de Grundy ou nimber, défini récursivement comme suit : Le nimber de la position finale vaut 0. Le nimber d'une position donnée est le plus petit entier positif ou nul n'apparaissant pas dans la liste des nimbers des positions qui suivent immédiatement la position donnée. Dans le jeu de Nim trivial à un seul tas, le nimber d'un unique tas de n allumettes n'est autre que n lui-même. Les positions dont les nimbers valent 0 sont des positions gagnantes qu'il convient d'atteindre, les autres étant des positions perdantes. En effet, le joueur qui atteint une position ayant un nimber nul verra nécessairement son adversaire atteindre une position ayant un nimber non nul, quoi que ce dernier joue, et lui-même aura un coup à jouer qui pourra le ramener à une position ayant un nimber nul. Il pourra donc se déplacer d'un nimber nul à un autre jusqu'à ce que son adversaire soit bloqué. On généralise cette situation à des jeux infinis, à condition que, quelle que soit la position du jeu, il n'existe qu'un nombre fini de coups avant que la partie ne se termine. Cependant, chaque position peut avoir une infinité de successeurs immédiats. Dans ce cas, les nimbers peuvent prendre des valeurs infinies, qu'on dénote par des nombres ordinaux. Ces nimbers peuvent être dotés de propriétés intéressantes décrites ci-après.