summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-02-14 19:02:12 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-02-14 19:02:12 (GMT)
commit15f3fb9dc4eda564dafa9b2db3f998e20a69bade (patch)
tree01671f21408fc345208140fb8aa147b6cec4cfd3 /notes-mitro206.tex
parentafa40cb18857930ab6ef1811b2609c9556ba6a5e (diff)
downloadmitro206-15f3fb9dc4eda564dafa9b2db3f998e20a69bade.zip
mitro206-15f3fb9dc4eda564dafa9b2db3f998e20a69bade.tar.gz
mitro206-15f3fb9dc4eda564dafa9b2db3f998e20a69bade.tar.bz2
Hercules vs the Hydra.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex49
1 files changed, 35 insertions, 14 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index d37e8a3..fce6917 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -449,20 +449,6 @@ Cet exemple sert à illustrer le fait que dans l'étude des jeux sous
forme normale, l'hypothèse de finitude des choix sera généralement
essentielle.
-\thingy Le \textbf{jeu topologique de Choquet} : soit $X$ un espace
-métrique (ou topologique) fixé à l'avance. Uriel et Vania choisissent
-tour à tour un ouvert non vide de ($X$ contenu dans) l'ouvert
-précédemment choisi : i.e., Uriel choisit $\varnothing \neq U_0
-\subseteq X$, puis Vania choisit $\varnothing \neq V_0 \subseteq U_0$,
-puis Uriel choisit $\varnothing \neq U_1 \subseteq V_0$ et ainsi de
-suite. Le jeu continue pendant un nombre infini de tours indicés par
-les entiers naturels. À la fin, on a bien sûr $\bigcap_{n=0}^{\infty}
-U_n = \bigcap_{n=0}^{\infty} V_n$ : on dit qu'Uriel gagne le jeu si
-cette intersection est vide, Vania le gagne si elle est non-vide. On
-peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une
-stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en
-a une.
-
\thingy\label{introduction-graph-game} Le jeu d'un graphe : soit $G$
un graphe orienté (cf. \ref{definitions-graphs} ci-dessous pour la
définition) et $x_0$ un sommet de $G$. Partant de $x_0$, Alice et Bob
@@ -492,6 +478,41 @@ défini en \ref{introduction-graph-game}) : on verra que la théorie de
Grundy permet de décrire exactement la stratégie gagnante (et pour
qui).
+\thingy Le \textbf{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
+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'exite 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. Hercule gagne s'il réussit à décapiter le dernier nœud de
+l'hydre ; l'hydre gagnerait si elle réussissait à survivre
+indéfiniment.
+
+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.
+
+\thingy Le \textbf{jeu topologique de Choquet} : soit $X$ un espace
+métrique (ou topologique) fixé à l'avance. Uriel et Vania choisissent
+tour à tour un ouvert non vide de ($X$ contenu dans) l'ouvert
+précédemment choisi : i.e., Uriel choisit $\varnothing \neq U_0
+\subseteq X$, puis Vania choisit $\varnothing \neq V_0 \subseteq U_0$,
+puis Uriel choisit $\varnothing \neq U_1 \subseteq V_0$ et ainsi de
+suite. Le jeu continue pendant un nombre infini de tours indicés par
+les entiers naturels. À la fin, on a bien sûr $\bigcap_{n=0}^{\infty}
+U_n = \bigcap_{n=0}^{\infty} V_n$ : on dit qu'Uriel gagne le jeu si
+cette intersection est vide, Vania le gagne si elle est non-vide. On
+peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une
+stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en
+a une.
+
\subsection{Remarques}