An exercise on tree Hackenbush.

1 files changed, 172 insertions, 0 deletions

diff --git a/controle-20170419.tex b/controle-20170419.tex
index fe2c1b5..4ded72a 100644
--- a/controle-20170419.tex
+++ b/controle-20170419.tex
@@ -121,6 +121,178 @@ Git: \input{vcline.tex}
 %
 %
 
+\exercice
+
+On s'intéresse dans cet exercice au jeu de \emph{Hackenbush impartial
+  en arbre}, défini comme suit.  L'état du jeu est un arbre (fini,
+enraciné\footnote{C'est-à-dire que la racine fait partie de la donnée
+  de l'arbre, ce qui est la convention la plus courante.}).  Deux
+joueurs alternent, et chacun, quand vient son tour, choisit une arête
+de l'arbre et l'efface, ce qui fait automatiquement disparaître du
+même coup tout le sous-arbre qui descendait de cette arête (voir
+figure).  Le jeu se termine lorsque plus aucun coup n'est possible
+(c'est-à-dire que l'arbre est réduit à sa seule racine), auquel cas,
+selon la convention habituelle, le joueur qui ne peut plus jouer a
+perdu.
+
+\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}
+\begin{scope}[line width=3pt,red]
+\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,-0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,0.2)$);
+\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,-0.2)$);
+\end{scope}
+\end{tikzpicture}
+devient
+\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 (P9) at (1.75,1) {};
+\end{scope}
+\begin{scope}[line width=1.5pt]
+\draw (P0) -- (P1);
+\draw (P1) -- (P2);
+\draw (P2) -- (P3);
+\draw (P2) -- (P4);
+\draw (P0) -- (P9);
+\end{scope}
+\end{tikzpicture}
+\end{center}
+
+(1) Expliquer pourquoi une position de ce jeu peut être représentée
+comme une somme de nim de différents jeux du même type.  Plus
+exactement, soit $T$ un arbre de racine $x$, soient $y_1,\ldots,y_r$
+les fils de $x$, soient $T_1,\ldots,T_r$ les sous-arbres ayant pour
+racines $y_1,\ldots,y_r$ et soient $T'_1,\ldots,T'_r$ les arbres de
+racine $x$ où $T'_i$ est formé de $x$ et de $T_i$ (avec une arête
+entre $x$ et $y_i$) : expliquer pourquoi la position (représentée par
+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$ ?
+
+\smallbreak
+
+Indépendamment de ce qui précède, on va considérer une nouvelle
+opération sur les jeux : si $G$ est un jeu combinatoire impartial, vu
+comme un graphe orienté (bien-fondé), on définit un jeu noté $*{:}G$
+défini en ajoutant une unique position à $G$ comme on va l'expliquer.
+Pour chaque position $z$ de $G$ il y a une position notée $*{:}z$ de
+$*{:}G$, et il y a une unique autre position, notée $0$,
+dans $*{:}G$ ; pour chaque arête $z \to z'$ de $G$, il y a une arête
+$*{:}z\, \to \, *{:}z'$ dans $*{:}G$, et il y a de plus une arête
+$*{:}z\, \to 0$ dans $*{:}G$ pour chaque $z$ (en revanche, $0$ est un
+puits, c'est-à-dire qu'aucune arête n'en part) ; la position initiale
+de $*{:}G$ est $*{:}z_0$ où $z_0$ est celle de $G$.  De façon plus
+informelle, pour jouer au jeu $*{:}G$, chaque joueur peut soit faire
+un coup normal ($*{:}z\, \to \, *{:}z'$) dans $G$, soit appliquer un
+coup « destruction totale » $*{:}z\, \to 0$ qui fait terminer
+immédiatement le jeu (et celui qui l'applique a gagné\footnote{Ce jeu
+  considéré tout seul n'est donc pas très amusant puisqu'on a toujours
+  la possibilité de gagner instantanément.}).
+
+\smallbreak
+
+(2) Montrer par induction bien-fondée que si $G$ est un jeu
+combinatoire impartial (bien-fondé) de valeur de Grundy $\alpha$,
+alors $*{:}G$ a pour valeur de Grundy $1+\alpha$.
+
+\smallbreak
+
+(3) On revient au jeu de Hackenbush impartial en arbre.  Soit $T$ un
+arbre de racine $y$ et $T'$ l'arbre obtenu en ajoutant une nouvelle
+racine $x$ à $T$, c'est-à-dire que les sommets de $T'$ sont ceux de
+$T$ plus $x$, qui en est la racine, avec une arête entre $x$ et $y$.
+Expliquer pourquoi le jeu de Hackenbush représenté par $T'$ s'obtient
+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$ ?
+
+\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.
+
+\smallbreak
+
+(5) Quelle est la valeur de Grundy de la position représentée
+ci-dessous ?  (Il s'agit de la position utilisée en exemple plus
+haut.)  Quel coup préconiseriez-vous dans cette situation ?
+
+\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}
+\end{tikzpicture}
+\end{center}
+
+\smallbreak
+
+(La question qui suit est indépendante des questions précédentes.)
+
+(6) On remarque que la construction $*{:}G$ définie avant la
+question (2) peut se définir de façon identique lorsque $G$ est un jeu
+partisan, en donnant à une arête $*{:}z\, \to \, *{:}z'$ la même
+couleur que $z\to z'$ et à une arête $*{:}z\, \to 0$ la couleur verte
+(ce qui signifie : à la fois bleue et rouge).  En décrivant une
+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).
+
+
 
 
 %