diff options
| -rw-r--r-- | controle-2020qcm.tex | 404 |
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} + % % |