diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 94 |
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 |