Back to the hydra game.upload-20160323

1 files changed, 86 insertions, 8 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 9e1373d..6281638 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -566,7 +566,7 @@ possible à partir de cette position consiste à aller vers l'état
 $(n'_1,\ldots,n'_r)$ où $n'_i = n_i$ pour tout $i$ sauf exactement un
 pour lequel $n'_i < n_i$.  Il s'agit ici d'un jeu à deux joueurs
 impartial à connaissance parfaite (un cas particulier du jeu général
-défini en \ref{introduction-graph-game}).  On verra que la théorie de
+défini en \ref{introduction-graph-game}).  On verra en \ref{subsection-nim-sum} que la théorie de
 Grundy permet de décrire exactement la stratégie gagnante : en
 anticipant sur la suite, il s'agit de calculer le XOR (= « ou
   exclusif », appelé aussi \index{nim (somme de)}\index{somme de nim}\textit{somme de nim} dans ce contexte des
@@ -780,7 +780,8 @@ stratégie gagnante soit pour Alice, soit pour Bob, soit pour le
 premier joueur, soit pour le second (l'ensemble du dessin ci-dessus,
 par exemple, est gagnable par Alice).
 
-\thingy Le \defin[hydre (jeu de l')]{jeu de l'hydre} : Hercule essaie de terrasser
+\thingy\label{introduction-hydra-game}
+Le \defin[hydre (jeu de l')]{jeu de l'hydre} : Hercule essaie de terrasser
 l'hydre.  Le joueur qui joue l'hydre commence par dessiner (i.e.,
 choisir) un arbre (fini, enraciné), la forme initiale de l'hydre.
 Puis Hercule choisit une \emph{tête} de l'hydre, c'est-à-dire une
@@ -858,9 +859,10 @@ devient
 
 Ce jeu est particulier en ce que, mathématiquement, non seulement
 Hercule possède une stratégie gagnante, mais en fait Hercule gagne
-\emph{toujours}, quoi qu'il fasse et quoi que fasse l'hydre.
-Pourtant, en pratique, l'hydre peut facilement s'arranger pour
-survivre un temps inimaginablement long.
+\emph{toujours}, quoi qu'il fasse et quoi que fasse l'hydre
+(cf. \ref{subsection-hydra-game-again}).  Pourtant, en pratique,
+l'hydre peut facilement s'arranger pour survivre un temps
+inimaginablement long.
 
 \thingy Le \defin[Choquet (jeu topologique de)]{jeu topologique de Choquet} : soit $X$ un espace
 métrique (ou topologique) fixé à l'avance.  Uriel et Vania choisissent
@@ -1103,7 +1105,7 @@ Ceci conduit à faire la définition suivante :
 Donné un jeu en forme normale comme
 en \ref{definition-game-in-normal-form}, si $s := (s_1,\ldots,s_N) \in
 S_1 \times \cdots \times S_N$ est un profil de stratégies mixtes, on
-appelle \defin{gain [espéré]} du joueur $i$ selon ce profil la
+appelle \defin[gain espéré]{gain [espéré]} du joueur $i$ selon ce profil la
 quantité
 \[
 u_i(s) := \sum_{a\in A} s_1(a_1)\cdots s_N(a_N)\,u_i(a)
@@ -3774,7 +3776,7 @@ Un ensemble partiellement ordonné est dit \defin[totalement ordonné]{totalemen
 lorsque pour tous $x\neq y$ on a soit $x>y$ soit $y>x$.
 
 Un ensemble totalement ordonné bien-fondé $W$ est dit
-\defin{bien-ordonné}.  D'après \ref{well-founded-induction}, ceci
+\defin[bien-ordonné (ensemble)]{bien-ordonné}.  D'après \ref{well-founded-induction}, ceci
 peut se reformuler de différentes façons :
 \begin{itemize}
 \item[(*)]$W$ est un ensemble totalement ordonné dans lequel il
@@ -4489,6 +4491,82 @@ de $2^c$ pour des entiers naturels $c$ distincts).  À titre d'exemple,
 \end{array}
 \]
 
+\subsection{Retour sur le jeu de l'hydre}\label{subsection-hydra-game-again}
+
+\thingy À tout arbre fini enraciné $T$ on peut associer un
+ordinal $o(T) <\varepsilon_0$ par récurrence sur la profondeur de
+l'arbre, de la façon suivante : si $T_1,\ldots,T_r$ sont les
+sous-arbres ayant pour racine les fils de la racine, triés de façon
+que $o(T_1) \geq \cdots \geq o(T_r)$, alors on pose $o(T) =
+\omega^{o(T_1)} + \cdots + \omega^{o(T_r)}$ (autrement dit, quitte à
+regrouper les puissances identiques, ceci donne la forme normale de
+Cantor de $o(T)$).
+
+À titre d'exemple, dans le dessin
+\begin{center}
+\begin{tikzpicture}[baseline=0]
+\draw[very thin] (-1.5,0) -- (1.5,0);
+\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
+\node (P0) at (0,0) {};
+\node (P1) at (0,1) {};
+\node (P2) at (-1,2) {};
+\node (P3) at (0,2) {};
+\node (P4) at (1,2) {};
+\node (P5) at (0.5,3) {};
+\node (P6) at (1.5,3) {};
+\end{scope}
+\begin{scope}[line width=1.5pt]
+\draw (P0) -- (P1);
+\draw (P1) -- (P2);
+\draw (P1) -- (P3);
+\draw (P1) -- (P4);
+\draw (P4) -- (P5);
+\draw (P4) -- (P6);
+\end{scope}
+\node[anchor=west] at (P6) {$x$};
+\node[anchor=west] at (P4) {$y$};
+\node[anchor=west] at (P1) {$z$};
+\end{tikzpicture}
+\end{center}
+le sous-arbre partant de $x$ a pour valeur $0$ (il n'a aucun fils),
+celui partant de $y$ a pour valeur $\omega^0 + \omega^0 = 2$, celui
+partant de $z$ a pour valeur $\omega^2 + 2$, et l'arbre tout entier a
+pour valeur $\omega^{\omega^2 + 2}$.
+
+Il est facile de se convaincre que si on remplace un $T_i$ par un
+autre arbre $T'_i$ avec $o(T'_i) < o(T_i)$ alors l'arbre $T'$
+résultant vérifie $o(T') < o(T)$.  Ceci marche donc à n'importe quel
+niveau de remplacement.
+
+\thingy Rappelons maintenant les règles du \index{hydre (jeu de
+  l')}jeu de l'hydre qui ont été données
+en \ref{introduction-hydra-game} : Hercule choisit une \emph{tête} de
+l'hydre, c'est-à-dire une feuille $x$ de l'arbre, et la décapite en la
+supprimant de l'arbre.  L'hydre se reproduit alors de la façon
+suivante : soit $y$ le nœud parent de $x$ dans l'arbre, et $z$ le nœud
+parent de $y$ (grand-parent de $x$, donc) : si l'un ou l'autre
+n'existe pas, rien ne se passe (l'hydre passe son tour) ; sinon,
+l'hydre choisit un entier naturel $n$ (aussi grand qu'elle veut) et
+attache à $z$ autant de nouvelles copies de $y$ (mais sans la tête $x$
+qui a été décapitée) qu'elle le souhaite.  Si on appelle $T_y$ le
+sous-arbre de l'hydre partant du nœud $y$ avant décapitation et $T'_y$
+le même après décapitation, on a $o(T'_y) < o(T_y)$ (puisqu'on a
+décapité une tête), donc $\omega^{o(T'_y)}\cdot n < \omega^{o(T_y)}$
+\emph{quel que soit $n$} entier naturel.  Ainsi, si on appelle $T_z$
+et $T'_z$ les sous-arbres partant de $z$ avant et après décapitation +
+reproduction, on voit que $T'_z$ est obtenu en remplaçant
+$\omega^{o(T_y)}$ dans son écriture en forme normale de Cantor par un
+terme $\omega^{o(T'_y)}\cdot n$ strictement plus petit.  On a donc
+$o(T_z') < o(T_z)$, et cette inégalité stricte vaut encore pour
+l'arbre tout entier.
+
+On voit donc que si on considère la suite des ordinaux associés aux
+différentes formes de l'hydre au cours d'une partie du jeu de l'hydre,
+cette suite est \emph{strictement décroissante}, et d'après
+\ref{decreasing-sequences-of-ordinals-terminate}
+ou \ref{sets-of-ordinals-are-well-ordered}, le jeu termine donc
+toujours en temps fini.
+
 
 
 %
@@ -4606,7 +4684,7 @@ pour $\beta<\alpha$, c'est donc exactement $\alpha$.
 \end{proof}
 
 
-\subsection{Somme de nim}
+\subsection{Somme de nim}\label{subsection-nim-sum}
 
 \begin{defn}\label{definition-nim-sum-of-games}
 Soient $G_1,G_2$ deux jeux combinatoires impartiaux dont on note