summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20160421.tex92
1 files changed, 77 insertions, 15 deletions
diff --git a/controle-20160421.tex b/controle-20160421.tex
index 9c09891..1e2a140 100644
--- a/controle-20160421.tex
+++ b/controle-20160421.tex
@@ -218,9 +218,9 @@ d'Alice (i.e., il n'est plus son adversaire comme dans les questions
(1), (2) et (3), mais son allié). On cherche à déterminer quels sont
les équilibres de Nash possibles. On notera $(p_U,p_V, q_X,q_Y)$ un
profil de stratégies mixtes général, où $p_U,p_V$ (positifs de
-somme $1$) sont les poids des trois options d'Alice (=probabilités
+somme $1$) sont les poids des deux options d'Alice (=probabilités
qu'elle les joue), et $q_X,q_Y$ (positifs, également de somme $1$) les
-poids des trois options de Bob. On va discuter selon le support des
+poids des deux options de Bob. On va discuter selon le support des
stratégies (i.e., selon les ensembles d'options qui ont un poids
strictement positif).\spaceout (a) Pour commencer, quels sont les
équilibres de Nash évidents en stratégies pures ? Expliquer pourquoi
@@ -240,8 +240,8 @@ du jeu considéré.
est maximum sur la ligne et sur la colonne ; si Alice joue
(purement) V et Bob joue (purement) Y, aucun n'a intérêt à changer
puisque $4$ est maximum sur la ligne et sur la colonne. Les gains
- d'Alice (et de Bob) dans chacun de ces trois cas sont donc $3$
- et $4$ respectivement.
+ d'Alice (et de Bob) dans chacun de ces cas sont donc $3$ et $4$
+ respectivement.
Il s'agit là de l'ensemble des équilibres de Nash où l'un des deux
joueurs a une stratégie pure : par exemple, si Alice joue purement U,
@@ -313,6 +313,24 @@ coup valable consiste à le remplacer par trois jetons, sur les cases
$(18,7)$, $(42,5)$ et $(18,5)$.) Le nombre de jetons présents
augmente donc de $2$ à chaque coup joué.
+\begin{center}
+\vskip-\baselineskip
+\begin{tikzpicture}
+\draw[step=.5cm,help lines] (0,-2) grid (3.5,0);
+\begin{scope}[every node/.style={circle,fill,inner sep=1.2mm}]
+\node at (1.25,-0.75) {};
+\node at (1.25,-1.75) {};
+\node at (2.75,-0.75) {};
+\node[fill=gray] at (2.75,-1.75) {};
+\end{scope}
+\node[anchor=east] at (0,-0.75) {$\alpha'$};
+\node[anchor=east] at (0,-1.75) {$\alpha$};
+\node[anchor=south] at (1.25,0) {$\beta'$};
+\node[anchor=south] at (2.75,0) {$\beta$};
+\end{tikzpicture}
+\\{\footnotesize (Le jeton en gris est remplacé par les trois noirs.)}
+\end{center}
+
On remarquera que les jetons sur la ligne ou la colonne $0$ ne peuvent
plus être retirés ou servir de quelque manière que ce soit : on pourra
dire que cette ligne et cette colonne $0$ sont la « défausse » des
@@ -480,7 +498,9 @@ inductive), et on a montré ce qui était demandé.
5$ et $0\leq\beta\leq 5$. Pour accélérer les calculs ou bien pour les
vérifier, on pourra utiliser les résultats de
l'exercice \ref{inductions-on-nim-product} (il n'est pas nécessaire
-d'avoir traité l'exercice en question).
+d'avoir traité l'exercice en question). On ne demande pas de
+justifier les calculs, mais on recommande de les vérifier
+soigneusement.
\begin{corrige}
En calculant un peu plus loin que ce qui était demandé, on trouve :
@@ -503,6 +523,49 @@ commutativité, et le fait que $\alpha\otimes 3 = \alpha\otimes(2\oplus
\alpha\otimes(4\oplus 1) = (\alpha\otimes 4) \oplus \alpha$).
\end{corrige}
+\smallbreak
+
+(5) Si vous devez jouer dans la position suivante (les lignes et
+colonnes sont numérotées à partir de $1$, c'est-à-dire que la défausse
+n'est pas figurée), quel coup feriez-vous ?
+
+\begin{center}
+\vskip-\baselineskip
+\begin{tikzpicture}
+\draw[step=.5cm,help lines] (0,-2.5) grid (2.5,0);
+\begin{scope}[every node/.style={circle,fill,inner sep=1.2mm}]
+\node at (0.25,-0.25) {};
+\node at (0.75,-0.75) {};
+\node at (1.25,-1.25) {};
+\node at (1.75,-1.75) {};
+\node at (2.25,-2.25) {};
+\end{scope}
+\node[anchor=east] at (0,-0.25) {$1$};
+\node[anchor=east] at (0,-0.75) {$2$};
+\node[anchor=east] at (0,-1.25) {$3$};
+\node[anchor=east] at (0,-1.75) {$4$};
+\node[anchor=east] at (0,-2.25) {$5$};
+\node[anchor=south] at (0.25,0) {$1$};
+\node[anchor=south] at (0.75,0) {$2$};
+\node[anchor=south] at (1.25,0) {$3$};
+\node[anchor=south] at (1.75,0) {$4$};
+\node[anchor=south] at (2.25,0) {$5$};
+\end{tikzpicture}
+\end{center}
+
+\begin{corrige}
+La valeur de Grundy est $(1\otimes 1) \oplus (2\otimes 2) \oplus
+(3\otimes 3) \oplus (4\otimes 4) \oplus (5\otimes 5) = 1 \oplus 3
+\oplus 2 \oplus 6 \oplus 7 = 1$, et on veut l'annuler. Plusieurs
+coups gagnants sont possibles, par exemple : retirer le jeton en
+$(1,1)$ (c'est-à-dire jouer $(\alpha,\beta,\alpha',\beta') =
+(1,1,0,0)$) ; ou bien, remonter le jeton $(3,3)$ en $(1,3)$
+(c'est-à-dire jouer $(\alpha,\beta,\alpha',\beta') = (3,3,1,0)$) ; ou
+encore, remplacer le jeton $(5,5)$ par trois jetons en $(4,5)$,
+$(5,4)$ et $(4,4)$ (c'est-à-dire jouer $(\alpha,\beta,\alpha',\beta')
+= (5,5,4,4)$).
+\end{corrige}
+
%
%
@@ -511,16 +574,15 @@ commutativité, et le fait que $\alpha\otimes 3 = \alpha\otimes(2\oplus
\exercice\label{inductions-on-nim-product}
On définit inductivement une opération $\alpha\otimes\beta$
-(\emph{produit de nim}) de deux ordinaux $\alpha,\beta$ par la
-formule (*) de l'exercice \ref{game-for-nim-product} (il n'est pas
-nécessaire d'avoir traité l'exercice en question, même s'il est permis
-de s'en servir), autrement dit $\alpha\otimes\beta :=
-\mex\{(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
-(\alpha'\otimes\beta') : \alpha'<\alpha, \beta'<\beta\}$ où la
-notation $\oplus$ désigne la somme de nim.
-
-(On rappelle que $\gamma = \mex S$ signifie que $\gamma\not\in S$ et
-que tout ordinal $\gamma'<\gamma$ appartient à $S$.)
+(\emph{produit de nim}) de deux ordinaux $\alpha,\beta$ par
+$\alpha\otimes\beta := \mex\{(\alpha'\otimes\beta) \oplus
+(\alpha\otimes\beta') \oplus (\alpha'\otimes\beta') : \alpha'<\alpha,
+\beta'<\beta\}$ (autrement dit, par la formule (*) de
+l'exercice \ref{game-for-nim-product} ; il n'est pas nécessaire
+d'avoir traité l'exercice en question, même s'il est permis de s'en
+servir). La notation $\oplus$ désigne la somme de nim. On rappelle
+par ailleurs que $\gamma = \mex S$ signifie que $\gamma\not\in S$ et
+que tout ordinal $\gamma'<\gamma$ appartient à $S$.
(1) Montrer que $\otimes$ est commutative, c'est-à-dire que
$\beta\otimes\alpha = \alpha\otimes\beta$ quels que soient les