diff options
Diffstat (limited to 'controle-20170419.tex')
| -rw-r--r-- | controle-20170419.tex | 23 |
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.) |