Nimber

Pour le verbe nimber (orner d'un nimbe), voir Nimbe.

En mathématiques, dans la théorie des jeux combinatoires, les nimbers sont des jeux particuliers, définis comme les tas du jeu de Nim avec un nombre éventuellement infini d'allumettes. Plus précisement, 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.

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.

Structure de corps

Il est possible de définir sur les nimbers des opérations d'addition et de multiplication, ce qui munit la classe des nimbers d'une structure de corps commutatif^[1]. Cette construction théorique a été décrite en 1976 dans On Numbers and Games, par John Horton Conway.

Il est à noter que l'on parle en général de structure algébrique pour des ensembles. Cependant, les nimbers, de la même façon que les nombres ordinaux, ne forment pas un ensemble, mais une classe propre. On considère donc la structure, non pas de l'ensemble des nimbers, ce qui serait une expression incorrecte, mais de la classe des nimbers.

Opérations d'addition et de multiplication

La définition des opérations d'addition et de multiplication nécessite au préalable la fonction mex, dite de Minimum EXclus. Le mex d'un ensemble d'ordinaux est défini comme le plus petit ordinal n'appartenant pas à cet ensemble. Par exemple :

Mex(1, 2) = 0
Mex(0, 1, 5, 6) = 2
Mex(0, 1, 2, 3, ..(tous les entiers).., $ω$ , $ω + 5$ ) = $ω + 1$ .

On utilise exactement la même définition du mex pour un ensemble de nimbers, à savoir que le mex d'un ensemble de nimbers est le plus petit nimber n'appartenant pas à cet ensemble.

Les opérations d'addition et de multiplication de deux nimbers $α$ et $β$ peuvent alors s'écrire :

$\alpha + \beta = \operatorname{mex}(\{\,\alpha' + \beta : \alpha' < \alpha\,\} \cup \{\, \alpha + \beta' : \beta' < \beta \,\}),$

$\alpha * \beta = \operatorname{mex}(\{\,\alpha' * \beta + \alpha * \beta' - \alpha' * \beta' : \alpha' < \alpha, \beta' < \beta\,\}),$

Structure de groupe abélien

L'opération d'addition définie sur les nimbers possède les propriétés remarquables suivantes :

le nimber 0 est un élément neutre : $α + 0 = α$
commutativité : $α + β = β + α$
associativté : $(α + β) + γ = α + (β + γ)$
Tout nimber possède un opposé (lui-même) : $α + α = 0$ et donc $- α = α$

Ces propriétés munissent la classe des nimbers d'une structure de groupe abélien.

Structure de corps commutatif

Par ailleurs, l'opération de multiplication possède les propriétés suivantes :

le nimber 1 est un élément neutre : $α * 1 = α$
commutativité : $α * β = β * α$
associativité : $(α * β) * γ = α * (β * γ)$
distributivité par rapport à l'addition : $(α + β) * γ = α * γ + β * γ$
Tout nimber non nul possède un inverse

Ces propriétés munissent en fait la classe des nimbers d'une structure de corps commutatif.

La propriété la plus surprenante est le fait que tout nimber possède un inverse. Cela se démontre grâce à une formule explicite qui permet de construire l'inverse de façon inductive. On définit un ensemble S par induction :

$0 \in S$
si $\beta' \in S$ alors pour tout $α' < α$ , on a : $\frac{1+(\alpha'-\alpha)*\beta'}{\alpha'} \in S$

On peut alors montrer que $\beta = \operatorname{mex}(S)$ vérifie $α * β = 1$ , c'est-à-dire $\beta = \frac 1\alpha$ .

Sous-corps remarquables

Certains sous-ensembles de nimbers sont stables pour les opérations d'addition et de multiplication. Pour n > 0 donné :

l'ensemble des nimbers de 0 à $2 n - 1$ est stable pour l'opération d'addition
l'ensemble des nimbers de 0 à $2^{2^n} - 1$ est stable pour l'opération de multiplication

Il s'ensuit que l'ensemble des nimbers de 0 à $2^{2^n} - 1$ est un corps fini à $2^{2^n}$ éléments distincts, donc isomorphe à $F_{2^{2^n}}$ .

Exemple du sous-corps fini F₁₆

Pour illustrer les opérations d'addition et de multiplication, on peut donner les tables suivantes, qui montrent le résultat de l'addition et de la multiplication des nimbers compris entre 0 et 15. L'ensemble des nimbers de 0 à 15 est clos pour ces opérations, c'est-à-dire que le résultat est lui-même un nimber entre 0 et 15. On obtient ainsi une structure isomorphe au corps fini F₁₆.

Table d'addition des Nimbers^[1]
+	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1	0	3	2	5	4	7	6	9	8	11	10	13	12	15	14
2	2	3	0	1	6	7	4	5	10	11	8	9	14	15	12	13
3	3	2	1	0	7	6	5	4	11	10	9	8	15	14	13	12
4	4	5	6	7	0	1	2	3	12	13	14	15	8	9	10	11
5	5	4	7	6	1	0	3	2	13	12	15	14	9	8	11	10
6	6	7	4	5	2	3	0	1	14	15	12	13	10	11	8	9
7	7	6	5	4	3	2	1	0	15	14	13	12	11	10	9	8
8	8	9	10	11	12	13	14	15	0	1	2	3	4	5	6	7
9	9	8	11	10	13	12	15	14	1	0	3	2	5	4	7	6
10	10	11	8	9	14	15	12	13	2	3	0	1	6	7	4	5
11	11	10	9	8	15	14	13	12	3	2	1	0	7	6	5	4
12	12	13	14	15	8	9	10	11	4	5	6	7	0	1	2	3
13	13	12	15	14	9	8	11	10	5	4	7	6	1	0	3	2
14	14	15	12	13	10	11	8	9	6	7	4	5	2	3	0	1
15	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0

Table de multiplication des Nimbers^[1]
×	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
2	2	3	1	8	10	11	9	12	14	15	13	4	6	7	5
3	3	1	2	12	15	13	14	4	7	5	6	8	11	9	10
4	4	8	12	6	2	14	10	11	15	3	7	13	9	5	1
5	5	10	15	2	7	8	13	3	6	9	12	1	4	11	14
6	6	11	13	14	8	5	3	7	1	12	10	9	15	2	4
7	7	9	14	10	13	3	4	15	8	6	1	5	2	12	11
8	8	12	4	11	3	7	15	13	5	1	9	6	14	10	2
9	9	14	7	15	6	1	8	5	12	11	2	10	3	4	13
10	10	15	5	3	9	12	6	1	11	14	4	2	8	13	7
11	11	13	6	7	12	10	1	9	2	4	15	14	5	3	8
12	12	4	8	13	1	9	5	6	10	2	14	11	7	15	3
13	13	6	11	9	4	15	2	14	3	8	5	7	10	1	12
14	14	7	9	5	11	2	12	10	4	13	3	15	1	8	6
15	15	5	10	1	14	4	11	2	13	7	8	3	12	6	9

Références

↑ ^{a, b et c} J. H. Conway On Numbers and Games 2nd edition, AK Peters (2000), p.50 à 63

(en) Elwyn Berlekamp, John Conway et Richard Guy, Winning Ways for your Mathematical Plays, A K Peters Ltd, 2001--2004, 2nd^e éd. (ISBN 1-56881-130-6, ISBN 1-56881-142-X, ISBN 1-56881-143-8, ISBN 1-56881-144-6)

Portail des mathématiques

Catégorie :

Théorie des jeux combinatoires

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

nimber — [ nɛ̃be ] v. tr. <conjug. : 1> • 1876; nimbé 1852; de nimbe 1 ♦ Pourvoir d un nimbe. ⇒ auréoler. 2 ♦ Entourer, auréoler. Apparition nimbée de lumière. Pronom. « de quel rayonnement se nimbait le beau visage de mon amie ! » (A. Gide). ●… … Encyclopédie Universelle
Nimber — In mathematics, the proper class of nimbers (occasionally called Grundy numbers) is introduced in combinatorial game theory, where they are defined as the values of nim heaps, but arise in a much larger class of games because of the… … Wikipedia
NIMBER — v. tr. Entourer d’un nimbe. Tête nimbée … Dictionnaire de l'Academie Francaise, 8eme edition (1935)
nimber — (entrée créée par le supplément) (nin bé) v. a. Pourvoir d un nimbe. • L auréole d or qui le nimbe fait ressortir la tête la plus idéalement candide qu on puisse rêver, E. BERGERAT Journ. offic. 14 mai 1876, p. 3263, 3e col … Dictionnaire de la Langue Française d'Émile Littré
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
Sprague–Grundy theorem — In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The Grundy value or nim value of an impartial game is then defined as the unique nimber that the … Wikipedia
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.… … Wikipédia en Français
Star (game) — In combinatorial game theory, star, written as * or *1, is the value given to the game where both players have only the option of moving to the zero game. Star may also be denoted as {0|0}. This game is an unconditional first player win.Star, as… … Wikipedia
Kayles — In combinatorial game theory, Kayles is a simple impartial game. In the notation of octal games, Kayles is denoted . 077. Rules Kayles is played with a row of tokens, which represent bowling pins. The row may be of any length. The two players… … Wikipedia
Marie-France Brière — est une artiste multidisciplinaire née à Montréal en 1957 explorant surtout la sculpture sur pierre. Elle a reçu le Prix Louis Comtois en 1996. Biographie Suite à ses études de premier cycle (1980) un séjour de plus d’un an en Italie marquait son … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Nimber

Sommaire

Structure de corps