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