Plenty of new questions (including various normal form games), and mark some as variants.

1 files changed, 385 insertions, 19 deletions

diff --git a/controle-2020qcm.tex b/controle-2020qcm.tex
index e4eba2b..ea5bf29 100644
--- a/controle-2020qcm.tex
+++ b/controle-2020qcm.tex
@@ -114,6 +114,237 @@ Git: \input{vcline.tex}
 %
 %
 
+\begin{qvar}
+
+\begin{question}
+
+Considérons le jeu à somme nulle, symétrique, entre Alice et Bob, dont
+la matrice des gains est donnée par le tableau suivant (Alice choisit
+la ligne, Bob choisit la colonne, le tableau donne le gain d'Alice et
+le gain de Bob est l'opposé de la valeur indiquée) :
+
+\begin{center}
+\begin{tabular}{r|rrrrr}
+$\downarrow$Alice, Bob$\rightarrow$&U&V&W&X&Y\\\hline
+U&$0$&$0$&$+1$&$+1$&$-1$\\
+V&$0$&$0$&$-1$&$-1$&$+1$\\
+W&$-1$&$+1$&$0$&$0$&$+2$\\
+X&$-1$&$+1$&$0$&$0$&$-1$\\
+Y&$+1$&$-1$&$-2$&$+1$&$0$\\
+%% m = Matrix(QQ, 5, 5, [[0, 0, 1, 1, -1], [0, 0, -1, -1, 1], [-1, 1, 0, 0, 2], [-1, 1, 0, 0, -1], [1, -1, -2, 1, 0]])
+\end{tabular}
+\end{center}
+
+Laquelle des réponses suivantes est une stratégie optimale à ce jeu ?
+(Chaque réponse proposée est la liste des probabilités de jouer les
+options U,V,W,X,Y dans cet ordre.)
+
+\rightanswer
+$(\frac{1}{2}, 0, \frac{1}{4}, 0, \frac{1}{4})$
+
+\answer
+$(1, 0, 0, 0, 0)$
+
+\answer
+$(0, \frac{1}{3}, 0, \frac{1}{3}, \frac{1}{3})$
+
+\answer
+$(0, 0, 0, 0, 1)$
+
+\end{question}
+
+\begin{question}
+
+Considérons le jeu à somme nulle, symétrique, entre Alice et Bob, dont
+la matrice des gains est donnée par le tableau suivant (Alice choisit
+la ligne, Bob choisit la colonne, le tableau donne le gain d'Alice et
+le gain de Bob est l'opposé de la valeur indiquée) :
+
+\begin{center}
+\begin{tabular}{r|rrrrr}
+$\downarrow$Alice, Bob$\rightarrow$&U&V&W&X&Y\\\hline
+U&$0$&$+2$&$0$&$-2$&$+1$\\
+V&$-2$&$0$&$+1$&$+1$&$+2$\\
+W&$0$&$-1$&$0$&$+1$&$+1$\\
+X&$+2$&$-1$&$-1$&$0$&$+2$\\
+Y&$-1$&$-2$&$-1$&$-2$&$0$\\
+%% m = Matrix(QQ, 5, 5, [[0, 2, 0, -2, 1], [-2, 0, 1, 1, 2], [0, -1, 0, 1, 1], [2, -1, -1, 0, 2], [-1, -2, -1, -2, 0]])
+\end{tabular}
+\end{center}
+
+Laquelle des réponses suivantes est une stratégie optimale à ce jeu ?
+(Chaque réponse proposée est la liste des probabilités de jouer les
+options U,V,W,X,Y dans cet ordre.)
+
+\rightanswer
+$(\frac{1}{5}, \frac{2}{5}, 0, \frac{2}{5}, 0)$
+
+\answer
+$(0, \frac{1}{2}, 0, \frac{1}{2}, 0)$
+
+\answer
+$(0, 0, 0, 0, 1)$
+
+\answer
+$(\frac{1}{3}, \frac{1}{3}, 0, \frac{1}{3}, 0)$
+
+\end{question}
+
+\begin{question}
+
+Considérons le jeu à somme nulle, symétrique, entre Alice et Bob, dont
+la matrice des gains est donnée par le tableau suivant (Alice choisit
+la ligne, Bob choisit la colonne, le tableau donne le gain d'Alice et
+le gain de Bob est l'opposé de la valeur indiquée) :
+
+\begin{center}
+\begin{tabular}{r|rrrrr}
+$\downarrow$Alice, Bob$\rightarrow$&U&V&W&X&Y\\\hline
+U&$0$&$+1$&$-1$&$0$&$-1$\\
+V&$-1$&$0$&$+2$&$-1$&$-1$\\
+W&$+1$&$-2$&$0$&$+1$&$+2$\\
+X&$0$&$+1$&$-1$&$0$&$0$\\
+Y&$+1$&$+1$&$-2$&$0$&$0$\\
+%% m = Matrix(QQ, 5, 5, [[0, 1, -1, 0, -1], [-1, 0, 2, -1, -1], [1, -2, 0, 1, 2], [0, 1, -1, 0, 0], [1, 1, -2, 0, 0]])
+\end{tabular}
+\end{center}
+
+Laquelle des réponses suivantes est une stratégie optimale à ce jeu ?
+(Chaque réponse proposée est la liste des probabilités de jouer les
+options U,V,W,X,Y dans cet ordre.)
+
+\rightanswer
+$(\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, 0)$
+
+\answer
+$(\frac{1}{5}, \frac{1}{5}, \frac{1}{5}, \frac{1}{5}, \frac{1}{5})$
+
+\answer
+$(0, 0, 0, 0, 1)$
+
+\answer
+$(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}, 0, 0)$
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+Considérons le jeu à somme nulle, entre Alice et Bob, dont la matrice
+des gains est donnée par le tableau suivant (Alice choisit la ligne,
+Bob choisit la colonne, le tableau donne le gain d'Alice et le gain de
+Bob est l'opposé de la valeur indiquée) :
+
+\begin{center}
+\begin{tabular}{r|rrr}
+$\downarrow$Alice, Bob$\rightarrow$&X&Y&Z\\\hline
+U&$-3$&$0$&$+3$\\
+V&$0$&$-1$&$-3$\\
+W&$-2$&$+2$&$-1$\\
+%% m = Matrix(QQ, 3, 3, [[-3, 0, 3], [0, -1, -3], [-2, 2, -1]])
+\end{tabular}
+\end{center}
+
+Quelle est la stratégie optimale de chacun des deux joueurs à ce jeu ?
+(Chaque réponse proposée est la liste des probabilités pour Alice de
+jouer les options U,V,W dans cet ordre puis pour Bob de jouer X,Y,Z.)
+
+\rightanswer
+$(\frac{1}{3}, \frac{2}{3}, 0)$ pour Alice, et $(\frac{2}{3}, 0,
+\frac{1}{3})$ pour Bob
+
+\answer
+$(\frac{1}{4}, \frac{3}{4}, 0)$ pour Alice, et $(\frac{1}{4},
+\frac{3}{4}, 0)$ pour Bob
+
+\answer
+$(0,1,0)$ pour Alice, et $(1,0,0)$ pour Bob
+
+\end{question}
+
+\begin{question}
+
+Considérons le jeu à somme nulle, entre Alice et Bob, dont la matrice
+des gains est donnée par le tableau suivant (Alice choisit la ligne,
+Bob choisit la colonne, le tableau donne le gain d'Alice et le gain de
+Bob est l'opposé de la valeur indiquée) :
+
+\begin{center}
+\begin{tabular}{r|rrr}
+$\downarrow$Alice, Bob$\rightarrow$&X&Y&Z\\\hline
+U&$-3$&$-2$&$+2$\\
+V&$+1$&$+2$&$0$\\
+W&$0$&$-2$&$-3$\\
+%% m = Matrix(QQ, 3, 3, [[-3, -2, 2], [1, 2, 0], [0, -2, -3]])
+\end{tabular}
+\end{center}
+
+Quelle est la stratégie optimale de chacun des deux joueurs à ce jeu ?
+(Chaque réponse proposée est la liste des probabilités pour Alice de
+jouer les options U,V,W dans cet ordre puis pour Bob de jouer X,Y,Z.)
+
+\rightanswer
+$(\frac{1}{6}, \frac{5}{6}, 0)$ pour Alice, et $(\frac{1}{3}, 0,
+\frac{2}{3})$ pour Bob
+
+\answer
+$(\frac{3}{8}, 0, \frac{5}{8})$ pour Alice, et $(\frac{5}{8}, 0,
+\frac{3}{8})$ pour Bob
+
+\answer
+$(0,1,0)$ pour Alice, et $(0,0,1)$ pour Bob
+
+\end{question}
+
+\begin{question}
+
+Considérons le jeu à somme nulle, entre Alice et Bob, dont la matrice
+des gains est donnée par le tableau suivant (Alice choisit la ligne,
+Bob choisit la colonne, le tableau donne le gain d'Alice et le gain de
+Bob est l'opposé de la valeur indiquée) :
+
+\begin{center}
+\begin{tabular}{r|rrr}
+$\downarrow$Alice, Bob$\rightarrow$&X&Y&Z\\\hline
+U&$-3$&$-2$&$+2$\\
+V&$+3$&$+1$&$0$\\
+W&$+1$&$+1$&$-1$\\
+%% m = Matrix(QQ, 3, 3, [[-3, -2, 2], [3, 1, 0], [1, 1, -1]])
+\end{tabular}
+\end{center}
+
+Quelle est la stratégie optimale de chacun des deux joueurs à ce jeu ?
+(Chaque réponse proposée est la liste des probabilités pour Alice de
+jouer les options U,V,W dans cet ordre puis pour Bob de jouer X,Y,Z.)
+
+\rightanswer
+$(\frac{1}{5}, \frac{4}{5}, 0)$ pour Alice, et $(0, \frac{2}{5},
+\frac{3}{5})$ pour Bob
+
+\answer
+$(\frac{1}{3}, 0, \frac{2}{3})$ pour Alice, et $(0, \frac{1}{2},
+\frac{1}{2})$ pour Bob
+
+\answer
+$(0,1,0)$ pour Alice, et $(0,0,1)$ pour Bob
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
 \begin{question}
 
 Considérons le jeu analogue à pierre-papier-ciseaux, sauf que les deux
@@ -157,6 +388,8 @@ ni (x) ni (y) n'est un équilibre de Nash
 %
 %
 
+\begin{qvar}
+
 \begin{question}
 
 Douze joueurs jouent au jeu suivant : chacun choisit une option parmi
@@ -192,11 +425,6 @@ ni (x) ni (y) ni (z) n'est un équilibre de Nash
 
 \end{question}
 
-
-%
-%
-%
-
 \begin{question}
 
 Douze joueurs jouent au jeu suivant : chacun choisit une option parmi
@@ -233,6 +461,8 @@ ni (x) ni (y) ni (z) n'est un équilibre de Nash
 
 \end{question}
 
+\end{qvar}
+
 
 %
 %
@@ -288,6 +518,8 @@ jouer chacune des cinq options avec probabilité $\frac{1}{5}$
 %
 %
 
+\begin{qvar}
+
 \begin{question}
 
 Alice et Bob jouent au jeu de type Gale-Stewart suivant : chacun à son
@@ -316,11 +548,6 @@ lequel
 
 \end{question}
 
-
-%
-%
-%
-
 \begin{question}
 
 Alice et Bob jouent au jeu de type Gale-Stewart suivant : chacun à son
@@ -349,11 +576,15 @@ lequel
 
 \end{question}
 
+\end{qvar}
+
 
 %
 %
 %
 
+\begin{qvar}
+
 \begin{question}
 
 C'est à votre tour de jouer au jeu de nim dans une configuration où il
@@ -374,11 +605,6 @@ retirer $3$ bâtonnets de la ligne qui en a $12$ (qui passe donc à $9$)
 
 \end{question}
 
-
-%
-%
-%
-
 \begin{question}
 
 C'est à votre tour de jouer au jeu de nim dans une configuration où il
@@ -399,6 +625,111 @@ retirer $3$ bâtonnets de la ligne qui en a $8$ (qui passe donc à $5$)
 
 \end{question}
 
+\end{qvar}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+On considère le jeu combinatoire (impartial, à information parfaite)
+associé au graphe orienté acyclique représenté ci-dessous, la position
+de départ étant notée $s$ :
+
+\begin{center}
+\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
+\node (n00) at (0bp,0bp) [draw,circle] {};
+\node (n01) at (40bp,0bp) [draw,circle] {};
+\node (n02) at (80bp,0bp) [draw,circle] {};
+\node (n10) at (0bp,-40bp) [draw,circle] {};
+\node (n11) at (40bp,-40bp) [draw,circle] {};
+\node (n12) at (80bp,-40bp) [draw,circle] {};
+\node (n20) at (0bp,-80bp) [draw,circle] {};
+\node (n21) at (40bp,-80bp) [draw,circle] {};
+\node (n22) at (80bp,-80bp) [draw,circle] {$s$};
+\draw[->] (n01) -- (n00);  \draw[->] (n02) -- (n01);
+\draw[->] (n11) -- (n10);  \draw[->] (n12) -- (n11);
+\draw[->] (n21) -- (n20);  \draw[->] (n22) -- (n21);
+\draw[->] (n10) -- (n00);  \draw[->] (n20) -- (n10);
+\draw[->] (n11) -- (n01);  \draw[->] (n21) -- (n11);
+\draw[->] (n12) -- (n02);  \draw[->] (n22) -- (n12);
+\end{tikzpicture}
+\end{center}
+
+Quelle est la valeur de Grundy du jeu (i.e., celle de la
+position $s$) ?
+
+\rightanswer
+$0$
+
+\answer
+$1$
+
+\answer
+$2$
+
+\answer
+$3$
+
+\answer
+$4$
+
+\end{question}
+
+\begin{question}
+
+On considère le jeu combinatoire (impartial, à information parfaite)
+associé au graphe orienté acyclique représenté ci-dessous, la position
+de départ étant notée $s$ :
+
+\begin{center}
+\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
+\node (n00) at (0bp,0bp) [draw,circle] {};
+\node (n01) at (40bp,0bp) [draw,circle] {};
+\node (n02) at (80bp,0bp) [draw,circle] {};
+\node (n10) at (0bp,-40bp) [draw,circle] {};
+\node (n11) at (40bp,-40bp) [draw,circle] {};
+\node (n12) at (80bp,-40bp) [draw,circle] {};
+\node (n20) at (0bp,-80bp) [draw,circle] {};
+\node (n21) at (40bp,-80bp) [draw,circle] {};
+\node (n22) at (80bp,-80bp) [draw,circle] {$s$};
+\draw[->] (n01) -- (n00);  \draw[->] (n02) -- (n01);
+\draw[->] (n11) -- (n10);  \draw[->] (n12) -- (n11);
+\draw[->] (n21) -- (n20);  \draw[->] (n22) -- (n21);
+\draw[->] (n11) -- (n00);  \draw[->] (n12) -- (n01);
+\draw[->] (n21) -- (n10);  \draw[->] (n22) -- (n11);
+\draw[->] (n10) -- (n00);  \draw[->] (n20) -- (n10);
+\draw[->] (n11) -- (n01);  \draw[->] (n21) -- (n11);
+\draw[->] (n12) -- (n02);  \draw[->] (n22) -- (n12);
+\end{tikzpicture}
+\end{center}
+
+Quelle est la valeur de Grundy du jeu (i.e., celle de la
+position $s$) ?
+
+\rightanswer
+$0$
+
+\answer
+$1$
+
+\answer
+$2$
+
+\answer
+$3$
+
+\answer
+$4$
+
+\end{question}
+
+\end{qvar}
+
 
 %
 %
@@ -530,16 +861,32 @@ $0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1\ldots$
 
 \begin{question}
 
-Lequel des ordinaux suivants est le plus grand ?
+On considère le jeu suivant (inspiré du jeu de nim) : l'état du jeu
+est formé d'un certain nombre de tas de pierres, chaque tas comportant
+$\geq 1$ pierre.  Chaque joueur, quand vient son tour, choisit un tas
+ayant $\geq 2$ pierres et le scinde en deux tas ayant chacun $\geq 1$
+pierres (autrement dit, il remplace un tas de $n \geq 2$ pierres par
+deux tas ayant $n_1$ et $n_2$ pierres, avec $n = n_1 + n_2$ et
+$n_1\geq 1$ et $n_2 \geq 1$).  En particulier, le nombre total de
+pierres ne change jamais.  Comme d'habitude, le jeu se termine quand
+un joueur ne peut plus jouer (c'est-à-dire quand il n'y a plus que des
+tas de $1$ pierre), et le joueur qui devait jouer a alors perdu.
+
+Quelle formule de récurrence permet de calculer la fonction de Grundy
+$f(n) := \gr(H_n)$ de l'état $H_n$ du jeu ayant un unique tas de $n$
+pierres ?
 
 \rightanswer
-$(\omega^{(\omega^{(\omega\cdot 4)})\cdot 2})\cdot 3$
+$f(1) = 0$ et $f(n) = \mex\{f(k)\oplus f(n-k) : 1\leq k\leq n-1\}$
 
 \answer
-$(\omega^{(\omega^{(\omega\cdot 3)})\cdot 4})\cdot 2$
+$f(1) = 0$ et $f(n) = \mex\{f(k) : 1\leq k\leq n-1\}$
 
 \answer
-$(\omega^{(\omega^{(\omega\cdot 2)})\cdot 3})\cdot 4$
+$f(1) = 0$ et $f(n) = \mex\{f(k) + f(n-k) : 1\leq k\leq n-1\}$
+
+\answer
+$f(1) = 0$ et $f(n) = \mex\{f(k_1) \oplus \cdots \oplus f(k_r) : k_1,\ldots,k_r \geq 1 \ \text{et}\ k_1+\cdots+k_r = n\}$
 
 \end{question}
 
@@ -548,6 +895,23 @@ $(\omega^{(\omega^{(\omega\cdot 2)})\cdot 3})\cdot 4$
 %
 %
 
+\begin{qvar}
+
+\begin{question}
+
+Lequel des ordinaux suivants est le plus grand ?
+
+\rightanswer
+$(\omega^{(\omega^{(\omega\cdot 4)})\cdot 2})\cdot 3$
+
+\answer
+$(\omega^{(\omega^{(\omega\cdot 3)})\cdot 4})\cdot 2$
+
+\answer
+$(\omega^{(\omega^{(\omega\cdot 2)})\cdot 3})\cdot 4$
+
+\end{question}
+
 \begin{question}
 
 Lequel des ordinaux suivants est le plus grand ?
@@ -563,6 +927,8 @@ $(\omega^{(\omega^{(\omega+ 2)})\cdot 2})\cdot 2$
 
 \end{question}
 
+\end{qvar}
+
 
 %
 %