Second exercise.

1 files changed, 225 insertions, 0 deletions

diff --git a/controle-20230417.tex b/controle-20230417.tex
index e7fcdcf..478c1eb 100644
--- a/controle-20230417.tex
+++ b/controle-20230417.tex
@@ -39,6 +39,7 @@
 \newcommand{\limp}{\Longrightarrow}
 \newcommand{\gr}{\operatorname{gr}}
 \newcommand{\rk}{\operatorname{rk}}
+\newcommand{\dur}{\operatorname{dur}}
 \newcommand{\fuzzy}{\mathrel{\|}}
 %
 \DeclareUnicodeCharacter{00A0}{~}
@@ -259,6 +260,230 @@ ou $(2,6,4)$ ou même $(1,6,7)$.
 \end{corrige}
 
 
+%
+%
+%
+
+\exercice
+
+Si $G$ est un graphe orienté bien-fondé (qu'on peut considérer comme
+l'ensemble des positions d'un jeu combinatoire auquel il ne manque que
+l'information, sans pertinence ici, de la position initiale), on
+rappelle qu'on a défini la fonction rang
+\[
+\rk(x) := \sup\nolimits^+\{\rk(y) : y\in\outnb(x)\} = \sup\,\{\rk(y)+1 :
+y\in\outnb(x)\}
+\]
+(en notant $\sup^+ S$ le plus petit ordinal strictement supérieur à
+tous les ordinaux de $S$ et $\sup S$ le plus petit ordinal supérieur
+ou égal à tous les ordinaux de $S$, et $\outnb(x)$ l'ensemble des
+voisins sortants de $x$), et la fonction de Grundy
+\[
+\gr(x) := \mex\,\{\gr(y) : y\in\outnb(x)\}
+\]
+(où $\mex S$ désigne le plus petit ordinal qui n'est pas dans $S$),
+— ces définitions ayant bien un sens par induction bien-fondée.  La
+première mesure en quelque sorte la durée du jeu si les deux joueurs
+coopèrent pour le faire durer aussi longtemps que possible, et la
+seconde nous donne notamment l'information de quel joueur a une
+stratégie gagnante.
+
+On va maintenant définir une fonction qui mesure en quelque sorte la
+durée du jeu si le joueur perdant cherche à perdre aussi lentement que
+possible tandis que le joueur gagnant cherche à gagner aussi vite que
+possible.  Précisément, on pose
+\[
+\left\{
+\begin{array}{ll}
+\dur(x) := \sup\,\{\dur(y)+1 : y\in\outnb(x)\}
+&\;\;\text{si $\gr(x) = 0$}\\
+\dur(x) := \min\,\{\dur(y)+1 : y\in\outnb(x)\text{~et~}\gr(y)=0\}
+&\;\;\text{si $\gr(x) \neq 0$}\\
+\end{array}
+\right.
+\]
+(où $\min S$ désigne le plus petit ordinal de $S$, si $S$ est un
+ensemble non-vide d'ordinaux).
+
+(1) Expliquer pourquoi cette définition a bien un sens (on
+prendra garde au fait que $\min\varnothing$ n'est pas défini).
+
+\begin{corrige}
+Lorsque $\gr(x) \neq 0$, il existe au moins un voisin sortant $y \in
+\outnb(x)$ tel que $\gr(y) = 0$ (car le $\mex$ est la plus petite
+valeur exclue: si un tel $y$ n'existait pas, le $\mex$ serait $0$) :
+ceci assure que le $\min$ dans la deuxième ligne de la définition
+porte toujours sur un ensemble non-vide.
+
+En-dehors de ce fait, la définition ne pose pas de problème : le
+$\sup$ d'un ensemble d'ordinaux existe toujours, et la récursivité de
+la définition est légitime par induction bien-fondée, c'est-à-dire que
+$\dur(x)$ peut faire appel aux valeurs de $\dur(y)$ pour des voisins
+sortants $y$ de $x$.  (Le fait de faire appel à $\gr(y)$ n'est pas un
+problème car on sait que $\gr$ est bien défini, et la distinction en
+cas est légitime de toute manière.)
+\end{corrige}
+
+(2) Expliquer rapidement et informellement pourquoi $\dur(x)$
+correspond bien à l'explication intuitive qu'on a donnée.
+
+\begin{corrige}
+Quand $x$ est une position avec $\gr(x) = 0$, c'est-à-dire une
+position P, le joueur qui doit jouer est le joueur perdant (n'ayant
+pas de stratégie gagnante) : il joue donc vers une position $y$ le
+faisant perdre le plus lentement possible, c'est-à-dire avec $\dur(y)$
+aussi grand que possible, d'où la définition $\dur(x) =
+\sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ dans ce cas (le $+1$ sert à
+compter le coup joué par ce joueur).
+
+Au contraire, lorsque $\gr(x) \neq 0$, c'est-à-dire que $x$ est une
+position N, le joueur qui doit jouer est le joueur gagnant : il joue
+donc vers une position $y$ le faisant gagner le plus rapidement
+possible, c'est-à-dire avec $\dur(y)$ aussi petit que possible parmi
+les coups $x\to y$ gagnants, autrement dit ceux pour lesquels $\gr(y)
+= 0$, d'où la définition $\dur(x) = \min\,\{\dur(y)+1 :
+y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\}$ dans ce cas (le $+1$ sert à
+compter le coup joué par ce joueur).
+\end{corrige}
+
+(3) Sur le graphe $G$ représenté ci-dessous, calculer chacune des
+fonctions $\rk$, $\gr$ et $\dur$ (les lettres servent simplement à
+étiqueter les sommets) :
+
+\begin{center}\footnotesize
+\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
+\node (nA) at (0bp,0bp) [draw,circle] {A};
+\node (nB) at (0bp,-40bp) [draw,circle] {B};
+\node (nC) at (40bp,0bp) [draw,circle] {C};
+\node (nD) at (40bp,-40bp) [draw,circle] {D};
+\node (nE) at (80bp,0bp) [draw,circle] {E};
+\node (nF) at (80bp,-40bp) [draw,circle] {F};
+\node (nG) at (120bp,-40bp) [draw,circle] {G};
+\draw[->] (nA) -- (nB);
+\draw[->] (nA) -- (nC);
+\draw[->] (nB) -- (nD);
+\draw[->] (nB) to[out=315,in=225] (nG);
+\draw[->] (nC) -- (nD);
+\draw[->] (nC) -- (nE);
+\draw[->] (nD) -- (nF);
+\draw[->] (nE) -- (nF);
+\draw[->] (nF) -- (nG);
+\draw[->] (nE) to[out=0,in=90] (nG);
+\end{tikzpicture}
+\end{center}
+
+Si on joue à partir du sommet A comme position initiale et que, comme
+suggéré dans la définition de $\dur$, le joueur perdant cherche à
+perdre aussi lentement que possible tandis que le joueur gagnant
+cherche à gagner aussi vite que possible, quelle sera le déroulement
+du jeu ?
+
+\begin{corrige}
+Les sommets ont été fort sympathiquement étiquetés dans un ordre
+compatible avec le rang (tri topologique), c'est-à-dire que chaque
+arête pointe vers un sommet situé strictement après dans l'ordre
+alphabétique.  On effectue donc les calculs dans l'ordre alphabétique
+inversé.  On trouve, pour le rang :
+
+\begin{center}\footnotesize
+\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
+\node (nA) at (0bp,0bp) [draw,circle] {$4$};
+\node (nB) at (0bp,-40bp) [draw,circle] {$3$};
+\node (nC) at (40bp,0bp) [draw,circle] {$3$};
+\node (nD) at (40bp,-40bp) [draw,circle] {$2$};
+\node (nE) at (80bp,0bp) [draw,circle] {$2$};
+\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
+\node (nG) at (120bp,-40bp) [draw,circle] {$0$};
+\draw[->] (nA) -- (nB);
+\draw[->] (nA) -- (nC);
+\draw[->] (nB) -- (nD);
+\draw[->] (nB) to[out=315,in=225] (nG);
+\draw[->] (nC) -- (nD);
+\draw[->] (nC) -- (nE);
+\draw[->] (nD) -- (nF);
+\draw[->] (nE) -- (nF);
+\draw[->] (nF) -- (nG);
+\draw[->] (nE) to[out=0,in=90] (nG);
+\end{tikzpicture}
+\end{center}
+
+Pour la valeur de Grundy :
+
+\begin{center}\footnotesize
+\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
+\node (nA) at (0bp,0bp) [draw,circle] {$0$};
+\node (nB) at (0bp,-40bp) [draw,circle] {$1$};
+\node (nC) at (40bp,0bp) [draw,circle] {$1$};
+\node (nD) at (40bp,-40bp) [draw,circle] {$0$};
+\node (nE) at (80bp,0bp) [draw,circle] {$2$};
+\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
+\node (nG) at (120bp,-40bp) [draw,circle] {$0$};
+\draw[->] (nA) -- (nB);
+\draw[->] (nA) -- (nC);
+\draw[->] (nB) -- (nD);
+\draw[->] (nB) to[out=315,in=225] (nG);
+\draw[->] (nC) -- (nD);
+\draw[->] (nC) -- (nE);
+\draw[->] (nD) -- (nF);
+\draw[->] (nE) -- (nF);
+\draw[->] (nF) -- (nG);
+\draw[->] (nE) to[out=0,in=90] (nG);
+\end{tikzpicture}
+\end{center}
+
+Et pour la fonction $\dur$ (afin de rendre le calcul plus facile à
+suivre, on a entouré en double les sommets de valeur de Grundy $0$) :
+
+\begin{center}\footnotesize
+\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
+\node (nA) at (0bp,0bp) [draw,double,circle] {$4$};
+\node (nB) at (0bp,-40bp) [draw,circle] {$1$};
+\node (nC) at (40bp,0bp) [draw,circle] {$3$};
+\node (nD) at (40bp,-40bp) [draw,double,circle] {$2$};
+\node (nE) at (80bp,0bp) [draw,circle] {$1$};
+\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
+\node (nG) at (120bp,-40bp) [draw,double,circle] {$0$};
+\draw[->] (nA) -- (nB);
+\draw[->] (nA) -- (nC);
+\draw[->] (nB) -- (nD);
+\draw[->] (nB) to[out=315,in=225] (nG);
+\draw[->] (nC) -- (nD);
+\draw[->] (nC) -- (nE);
+\draw[->] (nD) -- (nF);
+\draw[->] (nE) -- (nF);
+\draw[->] (nF) -- (nG);
+\draw[->] (nE) to[out=0,in=90] (nG);
+\end{tikzpicture}
+\end{center}
+
+Si on joue à partir de la position A, le premier joueur, appelons-la
+Alice, est en position perdante car la valeur de Grundy est nulle, et
+va jouer vers C car c'est ce qui maximise la fonction $\dur$ ; son
+adversaire, appelons-le Bob, joue alors vers D car c'est le seul coup
+gagnant, après quoi Alice joue vers F (seul coup possible) et Bob joue
+vers G.
+\end{corrige}
+
+(4) Montrer que, dans n'importe quel graphe $G$ bien-fondé, et pour
+n'importe quel sommet $x$ de $G$, on a $\dur(x) \leq \rk(x)$.
+
+\begin{corrige}
+On montre par induction bien-fondée que $\dur(x) \leq \rk(x)$.  On
+peut donc faire l'hypothèse qu'on sait que $\dur(y) \leq \rk(y)$ pour
+tout voisin sortant $y \in \outnb(x)$ (hypothèse d'induction).  Dans
+le cas où $\gr(x) = 0$, on a $\dur(x) = \sup\,\{\dur(y)+1 :
+y\in\outnb(x)\}$, qui est $\leq \sup\,\{\rk(y)+1 : y\in\outnb(x)\}$
+par hypothèse d'induction (il est clair qu'augmenter au sens large
+tous les éléments d'un ensemble d'ordinaux augmente son $\sup$ au sens
+large), et ceci vaut $\rk(x)$ par définition.  Dans le cas où $\gr(x)
+\neq 0$, on a $\dur(x) = \min\,\{\dur(y)+1 :
+y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \min\,\{\dur(y)+1 :
+y\in\outnb(x)\} \leq \sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ de façon
+évidente (en notant bien que les $\min$ portent sur des ensembles
+non-vides), et pour la même raison que précédemment, ceci est $\leq
+\sup\,\{\rk(y)+1 : y\in\outnb(x)\} = \rk(x)$.
+\end{corrige}
+
 
 
 %