diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 31 |
1 files changed, 30 insertions, 1 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 5de1ca7..6559c17 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -5400,6 +5400,35 @@ faculté la consomme pour tout le monde, et le jeu n'est fini qu'une fois ce tour consommé) : en effet, c'est simplement une reformulation du jeu $G \oplus *1$. +\thingy On peut définir une relation d'équivalence $\doteq$ entre jeux +combinatoires impartiaux bien-fondés par : $G \doteq H$ lorsque le +second joueur possède une stratégie gagnante au jeu $G\oplus H$ +(c'est-à-dire que [la position initiale de] $G\oplus H$ est une +P-position, ou encore que sa valeur de Grundy est nulle). + +Selon le modèle de \ref{conway-equivalence-on-partizan-games} plus +bas, on peut montrer que $\doteq$ est une relation d'équivalence et +qu'elle est compatible avec la somme de nim (c'est-à-dire que si +$G\doteq G'$ et $H\doteq H'$ alorsq $G\oplus H \doteq G'\oplus H'$) : +le point crucial est que si le second joueur possède une stratégie +gagnante à un jeu $G_0$ alors le joueur qui a une stratégie gagnante à +$G\oplus G_0$ est le même qu'à $G$ (comparer +avec \ref{basic-facts-on-sum-of-partizan-games} ci-dessous). + +Cette relation $\doteq$ sera particulièrement pertinente pour les jeux +partisans (dont la théorie est esquissée dans la +section \ref{section-combinatorial-partizan-games} ci-dessous), mais +dans le cas des jeux impartiaux considérés ici, elle est complètement +contenue dans la valeur de Grundy : on a $G\doteq H$ si et seulement +si $\gr(G) = \gr(H)$ (en effet, $G\doteq H$ équivaut par définition au +fait que le second joueur ait une stratégie gagnante à $G\oplus H$, +c'est-à-dire $\gr(G\oplus H) = 0$, ce qui +d'après \ref{nim-sum-for-games-versus-ordinals} signifie $\gr(G) +\oplus \gr(H) = 0$, autrement dit, +cf. \ref{nim-sum-has-characteristic-two}, que $\gr(G) = \gr(H)$). +Bref, les « classes d'équivalence » pour la relation $\doteq$ sont +précisément données par les ordinaux à travers la valeur de Grundy. + \thingy À côté de la somme de nim définie en \ref{definition-nim-sum-of-ordinals}, il existe aussi une opération de \index{nim (produit de)|see{produit de nim}}\defin{produit de nim} @@ -5618,7 +5647,7 @@ strictement plus favorable à Blaise que $H$). Sous ces conditions : -\begin{prop} +\begin{prop}\label{conway-equivalence-on-partizan-games} La relation $\doteq$ est une relation d'équivalence. Elle est compatible à la somme (c'est-à-dire que si $G \doteq G'$ et $H \doteq H'$ alors $G + H \doteq G' + H'$) ainsi qu'aux relations $>$, $\geq$, |