diff options
| -rw-r--r-- | controle-20170419.tex | 172 |
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). + + % |