summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-04-17 21:24:53 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-04-17 21:24:53 (GMT)
commit020e328071cb71895fa8177ff23054c0d645d408 (patch)
tree82d589f97dc94e8bac4255961418591faaa965e1
parent797618753f8d4a8560402a8b3555252e015e2a8d (diff)
downloadmitro206-020e328071cb71895fa8177ff23054c0d645d408.zip
mitro206-020e328071cb71895fa8177ff23054c0d645d408.tar.gz
mitro206-020e328071cb71895fa8177ff23054c0d645d408.tar.bz2
Re-read exam question.
-rw-r--r--controle-20170419.tex36
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.