Write answers to first exercise.

1 files changed, 128 insertions, 0 deletions

diff --git a/controle-20170419.tex b/controle-20170419.tex
index b4a9f19..bafc332 100644
--- a/controle-20170419.tex
+++ b/controle-20170419.tex
@@ -223,6 +223,20 @@ l'arbre $T$ est la somme de nim de celles représentées par
 $T'_1,\ldots,T'_r$.  Qu'en déduit-on sur la valeur de Grundy de la
 position $T$ ?
 
+\begin{corrige}
+Il s'agit simplement d'observer que les différentes branches de
+l'arbre n'interagissent pas du tout.  Jouer à la somme de nim des jeux
+de Hackenbush représentés par les arbres $T'_1,\ldots,T'_r$ revient,
+si on veut, à jouer à Hackenbush sur la réunion disjointe de ces
+arbres, et comme la racine n'intervient pas, cela ne change rien au
+jeu de réunir leurs racines en une seule, ce qui donne l'arbre $T$.
+
+On en déduit que $\gr(T) = \gr(T'_1) \oplus \cdots \gr(T'_r)$ où
+$\gr(T)$ désigne, par abus de notation, la valeur de Grundy de la
+position de Hackenbush représentée par l'arbre $T$, et où $\oplus$
+désigne la somme de nim des entiers naturels.
+\end{corrige}
+
 \smallbreak
 
 \centerline{* * *}
@@ -251,6 +265,29 @@ immédiatement le jeu (et celui qui l'applique a gagné\footnote{Ce jeu
 combinatoire impartial (bien-fondé) de valeur de Grundy $\alpha$,
 alors $*{:}G$ a pour valeur de Grundy $1+\alpha$.
 
+\begin{corrige}
+Observons tout d'abord que la valeur de Grundy de la position $0$
+de $*{:}G$ vaut $0$ puisque c'est un puits.  Montrons par induction
+bien-fondée sur les sommets de $*{:}G$ que la valeur de Grundy de la
+position $*{:}z$ vaut $1+\gr(z)$ où $\gr(z)$ désigne la valeur de
+Grundy de la position $z$ dans $G$.  Les voisins sortants de $*{:}z$
+sont $0$ et les $*{:}z'$ pour $z'$ voisin sortant de $z$ (dans $G$) ;
+la définition de la valeur de Grundy assure donc que $\gr(*{:}z) =
+\mex(\{0\} \cup \{\gr(*{:}z') : z'\in\outnb(z)\})$, c'est-à-dire que
+la valeur de Grundy de $*{:}z$ est le plus petit ordinal qui n'est
+ni $0$ ni un $\gr(*{:}z')$ pour $z'$ voisin sortant de $z$ ; mais par
+hypothèse d'induction, on peut remplacer $\gr(*{:}z')$ par
+$1+\gr(z')$, ce qui donne $\gr(*{:}z) = \mex(\{0\} \cup \{1+\gr(z') :
+z'\in\outnb(z)\})$.  Montrons que ce $\mex$ vaut $1+\gr(z)$ : pour
+cela, il suffit d'observer que (A) $1+\gr(z)$ ne vaut ni $0$ ni
+$1+\gr(z')$, et (B) tout ordinal $<1+\gr(z)$ vaut soit $0$ soit
+$1+\gr(z')$.  Or le (A) est clair car $1+\gr(z) > 0$ et que $\gr(z')
+\neq \gr(z)$ assure $1+\gr(z') \neq 1+\gr(z)$, et le (B) est clair car
+si $\beta < 1+\gr(z)$, alors soit $\beta=0$ soit $\beta = 1+\beta'$ où
+$\beta' < \gr(z)$, auquel cas la définition de $\gr$ assure qu'il
+existe $z'$ voisin sortant de $z$ tel que $\beta' = \gr(z')$.
+\end{corrige}
+
 \smallbreak
 
 (3) On revient au jeu de Hackenbush impartial en arbre.  Soit $T$ un
@@ -262,12 +299,39 @@ par la construction « $*{:}$ » considérée en (2) à partir de celui
 représenté par $T$.  Qu'en déduit-on sur la valeur de Grundy de la
 position $T'$ par rapport à celle de $T$ ?
 
+\begin{corrige}
+Un coup dans le jeu de Hackenbush représenté par l'arbre $T'$ peut
+consister soit à couper l'arbre à sa racine, c'est-à-dire couper
+l'arête reliant $x$ et $y$, ce qui met fin au jeu immédiatement, soit
+à jouer dans $T$ (i.e., couper une arête de celui-ci) ; c'est
+précisément la définition qu'on a donnée de la
+construction « $*{:}$ ».
+
+On en déduit que $\gr(T') = 1 + \gr(T)$ (comme par ailleurs on a ici
+affaire à des entiers naturels, le $+$ est commutatif, donc dans cette
+question on peut aussi l'écrire $\gr(T') = \gr(T) + 1$).
+\end{corrige}
+
 \smallbreak
 
 (4) Déduire des questions précédentes une méthode pour calculer la
 valeur de Grundy d'une position quelconque au Hackenbush impartial en
 arbre.
 
+\begin{corrige}
+Des questions précédentes, on déduit que la valeur de Grundy d'un
+arbre $T$ au Hackenbush impartial se calcule comme la somme de nim des
+$\gr(T'_i) = 1+\gr(T_i)$ où les $T_i$ sont les sous-arbres partant des
+fils de la racine de $T$.
+
+On peut donc calculer la valeur de Grundy d'un arbre en calculant
+celle de ses sous-arbres enracinés aux différents nœuds, des feuilles
+vers la racine : dès qu'on a calculé la valeur de Grundy de tous les
+sous-arbres enracinés aux fils $y_1,\ldots,y_r$ d'un nœud $x$, on en
+déduit celle du sous-arbre enraciné en leur père $x$ comme la somme de
+nim des valeurs en question incrémentées de $1$.
+\end{corrige}
+
 \smallbreak
 
 (5) Quelle est la valeur de Grundy de la position représentée
@@ -303,6 +367,49 @@ haut.)  Quel coup préconiseriez-vous dans cette situation ?
 \end{tikzpicture}
 \end{center}
 
+\begin{corrige}
+On trouve les valeurs de Grundy suivantes en notant à côté de chaque
+nœud la valeur du sous-arbre enraciné en ce nœud :
+\begin{center}
+\begin{tikzpicture}[baseline=0]
+\fill [gray!50!white] (-1.5,0) rectangle (1.5,-0.2);
+\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.5,2) {};
+\node (P3) at (-2.0,3) {};
+\node (P4) at (-1.0,3) {};
+\node (P5) at (1.5,2) {};
+\node (P6) at (0.75,3) {};
+\node (P7) at (1.5,3) {};
+\node (P8) at (2.25,3) {};
+\node (P9) at (1.75,1) {};
+\end{scope}
+\begin{scope}[line width=1.5pt]
+\draw (P0) -- (P1);
+\draw (P1) -- (P2);
+\draw (P1) -- (P5);
+\draw (P2) -- (P3);
+\draw (P2) -- (P4);
+\draw (P5) -- (P6);
+\draw (P5) -- (P7);
+\draw (P5) -- (P8);
+\draw (P0) -- (P9);
+\end{scope}
+\node[anchor=east] at (P2) {$0$};
+\node[anchor=west] at (P5) {$1$};
+\node[anchor=east] at (P1) {$3$};
+\node[anchor=east] at (P0) {$5$};
+\end{tikzpicture}
+\end{center}
+
+La valeur de Grundy recherchée est donc $5$.  En étudiant les
+différentes possibilités, on trouve qu'un coup gagnant possible
+consiste à retirer n'importe laquelle des arêtes les plus en haut sur
+le dessin (dans tous les cas, le sommet étiqueté $3$ sur la figure
+ci-dessus passe à $0$ et la racine de même).
+\end{corrige}
+
 \smallbreak
 
 (La question qui suit est indépendante des questions précédentes.)
@@ -316,6 +423,27 @@ stratégie, montrer que si $G \geq H$ on a aussi $*{:}G \geq *{:}H$, et
 en déduire que si $G\doteq H$ alors $*{:}G \doteq *{:}H$ (où $\doteq$
 désigne l'égalité au sens de Conway des jeux partisans).
 
+\begin{corrige}
+Tout d'abord, observons que $-(*{:}G) = *{:}(-G)$ puisque la
+construction « $*{:}$ » est symétrique entre bleu et rouge.
+
+La condition $G\geq H$ signifie que le joueur bleu (Blaise) possède
+une stratégie gagnante au jeu $G-H = G+(-H)$ s'il joue en second.
+Montrons qu'il en possède encore une à $(*{:}G) - (*{:}H) = (*{:}G) +
+(*{:}(-H))$ en considérant comment il répond à un coup de son
+adversaire (Roxane).  Si Roxane joue un coup de « destruction totale »
+sur l'une des composantes $(*{:}G)$ ou $(*{:}(-H))$, Blaise réplique
+sur l'autre et gagne.  Si Roxane joue un coup dans une des deux
+composantes $G$ ou $-H$, Blaise répond selon la stratégie qu'il est
+supposé posséder.  Dans tous les cas, Blaise peut répondre à tout coup
+de Roxane, donc il gagne.  Ceci montre $*{:}G \geq *{:}H$.
+
+Comme $G\doteq H$ signifie $G\geq H$ et $G\leq H$, on a bien $*{:}G
+\geq *{:}H$ et $*{:}G \leq *{:}H$ d'après ce qu'on vient d evoir,
+c'est-à-dire $*{:}G \doteq *{:}H$.  (La valeur d'un jeu partisan
+$*{:}G$ est donc déterminée par la valeur de $G$.)
+\end{corrige}
+
 
 %
 %