summaryrefslogtreecommitdiffstats
path: root/controle-20170419.tex
diff options
context:
space:
mode:
Diffstat (limited to 'controle-20170419.tex')
-rw-r--r--controle-20170419.tex23
1 files changed, 12 insertions, 11 deletions
diff --git a/controle-20170419.tex b/controle-20170419.tex
index 76b4af0..8529436 100644
--- a/controle-20170419.tex
+++ b/controle-20170419.tex
@@ -127,13 +127,13 @@ On s'intéresse dans cet exercice au jeu de \emph{Hackenbush impartial
en arbre}, défini comme suit. L'état du jeu est représenté par 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.
+ courante.}). Deux joueurs alternent et chacun à 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]
@@ -195,12 +195,13 @@ 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$ ?
+$T'_1,\ldots,T'_r$. Qu'en déduit-on sur la valeur de Grundy de la
+position $T$ ?
\smallbreak
+\centerline{* * *}
+
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$
@@ -313,7 +314,7 @@ uns des autres un élément de l'ensemble $\{\mathtt{0},\mathtt{1}\}$ :
Il sera utile de remarquer que les joueurs ont des rôles complètement
symétriques, et que les options sont également symétriques.
-(Attention, même si la somme des gans des trois joueurs vaut
+(Attention, même si la somme des gains des trois joueurs vaut
toujours $0$, ce n'est pas un « jeu à somme nulle » au sens classique,
car ces derniers ne sont définis que pour \emph{deux} joueurs.)