More details on Grundy function and Grundy kernel.upload-20160321

1 files changed, 86 insertions, 37 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index a8df1eb..dc00f6f 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1673,7 +1673,7 @@ stratégie gagnante, $\tau$, dans $G_X^{\mathrm{a}}(A)$ (où il joue en
 second).
 \end{proof}
 
-\thingy En utilisant la
+\thingy\label{strategies-forall-exists-reformulation} En utilisant la
 terminologie \ref{gale-stewart-winning-positions}, la
 proposition \ref{strategies-forall-exists-lemma} peut se reformuler de
 la façon suivante :
@@ -1979,7 +1979,7 @@ jeux ouverts peut s'appliquer dans ce contexte :
 
 \begin{defn}\label{first-definition-impartial-combinatorial-game}
 Soit $G$ un graphe orienté (c'est-à-dire un ensemble $G$ muni d'une
-relation $E$ irreflexive dont les éléments sont appelés arêtes du
+relation $E$ irréflexive dont les éléments sont appelés arêtes du
 graphe, cf. \ref{definitions-graphs} ci-dessous pour les définitions
 générales) dont les sommets seront appelés \textbf{positions} de $G$,
 et soit $x_0$ un sommet de $G$ qu'on appellera \textbf{position
@@ -2121,7 +2121,7 @@ ne choisissent un coup qu'en fonction du sommet $x \in G$.  C'est ce
 qui va être démontré dans la section suivante.
 
 
-\subsection{Détermination pour les stratégies positionnelles}
+\subsection{Détermination pour les stratégies positionnelles}\label{subsection-positional-strategies-determinacy}
 
 \thingy Le but de la définition suivante est de formaliser, pour un
 jeu combinatoire comme
@@ -2335,7 +2335,7 @@ amènera à une position où on a une stratégie gagnante).
 Enfin, on note $D := G\setminus(N\cup P)$ l'ensemble des sommets
 restants.
 
-\begin{prop}
+\begin{prop}\label{positional-strategies-forall-exists-lemma}
 Avec les notations introduites en
 \ref{set-of-everywhere-winning-positional-strategies} et \ref{notation-n-and-p-sets-for-combinatorial-games},
 \begin{itemize}
@@ -2469,11 +2469,11 @@ $D\supseteq D^*$.
 En particulier, si on utilise le
 théorème \ref{non-well-founded-definition} ci-dessous pour définir la
 \emph{plus petite} (pour l'inclusion) fonction partielle $f\colon G
-\dasharrow Z := \{\mathrm{P}, \mathrm{N}\}$ telle que $f(x)$ vaille
-$\mathrm{P}$ ssi $x$ a au moins un voisin sortant $y$ pour lequel
-$f(y) = \mathrm{N}$, et que $f(x)$ vaille $\mathrm{N}$ ssi pour tout
-voisin sortant $y$ de $x$ on a $f(y) = \mathrm{P}$, alors $f(x)$ vaut
-$\mathrm{P}$ ou bien $\mathrm{N}$ ou bien est indéfinie lorsque
+\dasharrow Z := \{\mathtt{P}, \mathtt{N}\}$ telle que $f(x)$ vaille
+$\mathtt{P}$ ssi $x$ a au moins un voisin sortant $y$ pour lequel
+$f(y) = \mathtt{N}$, et que $f(x)$ vaille $\mathtt{N}$ ssi pour tout
+voisin sortant $y$ de $x$ on a $f(y) = \mathtt{P}$, alors $f(x)$ vaut
+$\mathtt{P}$ ou bien $\mathtt{N}$ ou bien est indéfinie lorsque
 respectivement le premier joueur a une stratégie gagnante, le second
 joueur en a une, ou les deux ont une stratégie survivante.
 \end{prop}
@@ -2491,15 +2491,15 @@ $P^*$ ou $D^*$ il ne peut pas perdre non plus : donc $P^* \cup D^*
 \subseteq P \cup D$, ce qui signifie exactement $N^* \supseteq N$.
 
 Le deuxième paragraphe est une reformulation de la même affirmation :
-la fonction $f \colon G \dasharrow Z := \{\mathrm{P}, \mathrm{N}\}$
-définie par $f(x) = \mathrm{P}$ lorsque $x \in P$ et $f(x) =
-\mathrm{N}$ lorsque $x \in N$ est la plus petite fonction partielle
+la fonction $f \colon G \dasharrow Z := \{\mathtt{P}, \mathtt{N}\}$
+définie par $f(x) = \mathtt{P}$ lorsque $x \in P$ et $f(x) =
+\mathtt{N}$ lorsque $x \in N$ est la plus petite fonction partielle
 vérifiant les propriétés qu'on a dites, i.e., la plus petite telle que
 $f(x) = \Phi(x, f|_{\outnb(x)})$ avec les notations du
 théorème \ref{non-well-founded-definition} et $\Phi(x, g)$ valant
-$\mathrm{N}$ si $g(y)$ est défini et vaut $\mathrm{N}$ pour au moins
-un $y \in \outnb(x)$ et $\mathrm{P}$ si $g(y)$ est défini et vaut
-$\mathrm{P}$ pour tout $y \in \outnb(x)$ (comme $\Phi$ est cohérente
+$\mathtt{N}$ si $g(y)$ est défini et vaut $\mathtt{N}$ pour au moins
+un $y \in \outnb(x)$ et $\mathtt{P}$ si $g(y)$ est défini et vaut
+$\mathtt{P}$ pour tout $y \in \outnb(x)$ (comme $\Phi$ est cohérente
 en la seconde variable, on est bien dans le cas d'application
 duthéorème \ref{non-well-founded-definition}, même si ici on a déjà
 démontré l'existence d'une plus petite $f$).
@@ -2526,7 +2526,7 @@ et \ref{scholion-well-founded-definition}).
 Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et
 d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un
 ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit
-d'un ensemble $G$ muni d'une relation $E$ irreflexive.  Les éléments
+d'un ensemble $G$ muni d'une relation $E$ irréflexive.  Les éléments
 de $G$ s'appellent \textbf{sommets} et les éléments de $E$
 \textbf{arêtes} de $G$, et si $(x,y) \in E$, on dit qu'il y a une
 arête allant du sommet $x$ au sommet $y$, ou arête de source $x$ et de
@@ -2821,26 +2821,63 @@ Soit $G$ un graphe orienté bien-fondé.  En utilisant le
 théorème \ref{well-founded-definition}, on définit alors une partie $P
 \subseteq G$ telle que $x \in P$ ssi $\outnb(x) \cap P =
 \varnothing$ ; formellement, c'est-à-dire que pour $f\colon \outnb(x)
-\to \{0,1\}$ on définit $\Phi(x, f)$ comme valant $1$ si $f$ prend la
-valeur $0$ et $0$ si $f$ vaut constamment $1$, et qu'on appelle $f$ la
-fonction telle que $f(x) = \Phi(x, f|_{\outnb(x)})$ dont l'existence
-et l'unicité sont garanties par le théorème, et enfin on pose $P = \{x
-\in G : f(x) = 0\}$.
-
-Les éléments de $P$ seront appelés les \textbf{P-sommets} (ou
-P-positions) de $G$, tandis que les éléments du complémentaire
-$G\setminus P$ seront appelés \textbf{N-sommets} (ou N-positions)
-de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous les voisins
-  sortants sont des N-sommets, et un N-sommet est un sommet qui a au
-  moins un P-sommet pour voisin sortant}.
+\to \{\mathtt{P},\mathtt{N}\}$ on définit $\Phi(x, g)$ comme valant
+$\mathtt{N}$ si $g$ prend la valeur $\mathtt{P}$ et $\mathtt{N}$ si
+$g$ vaut constamment $\mathtt{P}$ (y compris si $g$ est la fonction
+vide), et qu'on appelle $f$ la fonction telle que $f(x) = \Phi(x,
+f|_{\outnb(x)})$ dont l'existence et l'unicité sont garanties par le
+théorème, et enfin on pose $P = \{x \in G : f(x) = \mathtt{P}\}$.
+
+Les éléments de $P$ (i.e., les $x$ tels que $f(x) = \mathtt{P}$)
+seront appelés les \textbf{P-sommets} (ou P-positions) de $G$, tandis
+que les éléments du complémentaire $G\setminus P$ (i.e., les $x$ tels
+que $f(x) = \mathtt{N}$) seront appelés \textbf{N-sommets} (ou
+N-positions) de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous
+  les voisins sortants sont des N-sommets, et un N-sommet est un
+  sommet qui a au moins un P-sommet pour voisin sortant}.
 \end{defn}
 
-On va voir que dans le jeu exposé en \ref{introduction-graph-game}, si
-le graphe est bien-fondé, les P-sommets sont les positions du jeu à
-partir desquelles le joueur précédent a une stratégie gagnante, tandis
-que les N-sommets sont celles à partir desquelles le joueur suivant
-(`N' comme « Next ») a une stratégie gagnante (consistant, justement,
-à jouer vers un P-sommet).
+\thingy Dans un jeu combinatoire comme exposé en
+\ref{introduction-graph-game} et/ou
+\ref{first-definition-impartial-combinatorial-game}, si le graphe est
+bien-fondé, les P-sommets sont les positions du jeu à partir
+desquelles le joueur Précédent (=second joueur) a une stratégie
+gagnante, tandis que les N-sommets sont celles à partir desquelles le
+joueur suivant (`N' comme « Next », =premier joueur) a une stratégie
+gagnante (consistant, justement, à jouer vers un P-sommet) : ceci
+résulte de \ref{strategies-forall-exists-lemma}
+ou \ref{strategies-forall-exists-reformulation} (ou encore
+de \ref{positional-strategies-forall-exists-lemma} dans le cadre plus
+général de la
+section \ref{subsection-positional-strategies-determinacy}).
+
+On peut donc résumer ainsi la stratégie gagnante « universelle » pour
+n'importe quel jeu combinatoire impartial à connaissance parfaite dont
+le graphe est bien-fondé : \emph{jouer vers un P-sommet}, après quoi
+l'adversaire sera obligé de jouer vers un N-sommet (si tant est qu'il
+peut jouer), et on pourra de nouveau jouer vers un P-sommet, et ainsi
+de suite (et comme le graphe est bien-fondé, le jeu termine forcément
+en temps fini, et celui qui a joué pour aller vers les P-sommets aura
+gagné puisqu'il peut toujours jouer).
+
+\thingy Pour illustrer la technique de démonstration par induction
+bien-fondée, montrons que si $\gamma$ est la fonction de Grundy
+introduite en \ref{definition-grundy-function} et si $P$ est la partie
+introduite en \ref{definition-grundy-kernel}, alors on a $x \in P$ si
+et seulement si $\gamma(x) = 0$, i.e., les P-sommets sont ceux pour
+lesquels la fonction de Grundy est nulle.
+
+Par induction bien-fondé (cf. \ref{scholion-well-founded-induction}),
+on peut supposer la propriété (« $x \in P$ si et seulement si
+  $\gamma(x) = 0$ ») déjà connue pour tous les voisins sortants $y$ du
+sommet $x$ où on cherche à la vérifier.  Si $x \in P$, cela signifie
+par définition de $P$ que tous ses voisins sortants $y$ de $x$ sont
+dans $G \setminus P$, et d'après l'hypothèse d'induction cela signifie
+$\gamma(y) \neq 0$ pour tout $y \in \outnb(x)$, c'est-à-dire
+$\mex\{\gamma(y) : y\in\outnb(x)\} = 0$ (puisque $\mex S = 0$ si et
+seulement si $0 \not\in S$), ce qui signifie $\gamma(x) = 0$.  Toutes
+ces reformulations étaient des équivalences : on a bien montré que $x
+\in P$ équivaut à $\gamma(x) = 0$, ce qui conclut l'induction.
 
 \thingy\label{ordinal-valued-rank-and-grundy-function} En anticipant
 sur la notion d'ordinaux introduite dans la
@@ -2856,14 +2893,26 @@ $y\in\outnb(x)$.
 De même, la fonction de Grundy peut se généraliser à n'importe quel
 graphe bien-fondé en définissant $\gamma(x) = \mex\{\gamma(y) :
 y\in\outnb(x)\}$ où $\mex S$ désigne le plus petit ordinal
-\emph{n'appartenant pas} à $S$.  Il reste vrai que $\gamma(x)$ est nul
-si et seulement si $x$ est un N-sommet.
+\emph{n'appartenant pas} à $S$.  Il reste vrai (avec la même
+démonstration) que $\gamma(x)$ est nul si et seulement si $x$ est un
+P-sommet.
+
+On peut donc résumer ainsi la stratégie gagnante « universelle » pour
+n'importe quel jeu combinatoire impartial à connaissance parfaite dont
+le graphe est bien-fondé : \emph{jouer de façon à annuler la fonction
+  de Grundy} (c'est-à-dire, jouer vers un P-sommet), après quoi
+l'adversaire sera obligé de jouer vers un sommet dont la valeur de
+Grundy est non-nulle, et on pourra de nouveau jouer vers zéro, et
+ainsi de suite (et comme le graphe est bien-fondé, le jeu termine
+forcément en temps fini, et celui qui a joué pour annuler la fonction
+de Grundy aura gagné puisqu'il peut toujours jouer).
 
 \thingy\label{well-founded-induction-algorithm} Lorsque $G$ est
 \emph{fini} et bien-fondé, i.e., est un graphe fini acyclique
 (cf. \ref{finite-graph-is-well-founded-iff-acyclic}), la fonction $f$
 définie par le théorème \ref{well-founded-definition} peut se calculer
-algorithmiquement de la façon suivante :
+algorithmiquement de la façon suivante (si tant est que $\Phi$
+elle-même est calculable) :
 \begin{itemize}
 \item utiliser un algorithme de \textbf{tri topologique} (en ayant
   inversé le sens des arêtes pour se ramener à la convention usuelle)