diff options
| -rw-r--r-- | controle-20170419.tex | 36 |
1 files changed, 18 insertions, 18 deletions
diff --git a/controle-20170419.tex b/controle-20170419.tex index 5453ec8..76b4af0 100644 --- a/controle-20170419.tex +++ b/controle-20170419.tex @@ -124,16 +124,16 @@ 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. + 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. \begin{center} \begin{tikzpicture}[baseline=0] @@ -187,7 +187,7 @@ devient \end{tikzpicture} \end{center} -(1) Expliquer pourquoi une position de ce jeu peut être représentée +(1) Expliquer pourquoi une position de ce jeu peut être considéré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 @@ -204,7 +204,7 @@ Qu'en déduit-on sur la valeur de Grundy de la position $T$ ? 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. +défini en ajoutant une unique position $0$ à $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 @@ -286,7 +286,7 @@ haut.) Quel coup préconiseriez-vous dans cette situation ? (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 +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$ @@ -319,15 +319,15 @@ car ces derniers ne sont définis que pour \emph{deux} joueurs.) \smallbreak -(1) Donner le tableau des gains du jeu considéré. (On choisira une +(1) Écrire le tableau des gains du jeu considéré. (On choisira une façon raisonnable de présenter un tableau à trois entrées, par exemple comme plusieurs tableaux à deux entrées mis côte à côte.) \smallbreak Si $p \in [0;1]$, on notera simplement $p$ la stratégie mixte d'un -joueur qui consiste à choisir $\mathtt{1}$ avec probabilité $p$ et -$\mathtt{0}$ avec probabilité $1-p$. +joueur qui consiste à choisir l'option $\mathtt{1}$ avec +probabilité $p$, et l'option $\mathtt{0}$ avec probabilité $1-p$. (2) Vérifier que l'espérance de gain d'Alice si elle joue selon la stratégie mixte $p$ tandis que Bob joue selon la stratégie mixte $q$ @@ -340,7 +340,7 @@ q -r$. (Ici, $p,q,r$ sont trois réels entre $0$ et $1$.) par Bob et la stratégie mixte $r$ jouée par Charlie les options $\mathtt{0}$ et $\mathtt{1}$ d'Alice sont indifférentes pour elle (c'est-à-dire, lui apportent la même espérance de gain). Montrer que -c'est le cas ssi $q + r = 1$. +c'est le cas si et seulement si $q + r = 1$. \smallbreak @@ -358,7 +358,7 @@ $q$ et $r$ ; la symétrie doit permettre de simplifier le travail). (6) Dans cette question, on modifie le jeu : plutôt que faire leurs choix indépendamment, les joueurs le font successivement (Alice, puis -Bob, puis Charlie). (a) Que vont faire Bob puis Charlie si Alice +Bob, puis Charlie). (a) Que va faire Bob si Alice choisit $\mathtt{0}$ ? (b) Informellement, expliquer qui est avantagé ou désavantagé par cette modification de la règle. |