Discuss Conway equivalence of impartial games (equality of Grundy) a bit more.

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$,