diff options
| -rw-r--r-- | controle-2020qcm.tex | 138 | ||||
| -rw-r--r-- | sample-2020qcm.tex | 334 |
2 files changed, 334 insertions, 138 deletions
diff --git a/controle-2020qcm.tex b/controle-2020qcm.tex index ea5bf29..dd4a76d 100644 --- a/controle-2020qcm.tex +++ b/controle-2020qcm.tex @@ -163,43 +163,6 @@ 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$\\ @@ -548,34 +511,6 @@ lequel \end{question} -\begin{question} - -Alice et Bob jouent au jeu de type Gale-Stewart suivant : chacun à son -tour choisit un chiffre binaire (soit $0$ soit $1$ : Alice choisit -$a_1$ puis Bob choisit $a_2$ puis Alice choisit $a_3$ et ainsi de -suite). Au bout d'un nombre infini de tours, on considère le nombre -réel $x$ entre $0$ et $1$ dont l'écriture binaire fractionnaire est -formée de ces chiffres (c'est-à-dire $x = \sum_{i=1}^{+\infty} -a_i\,2^{-i}$, ou $0{.}a_1a_2a_3\ldots$ en écriture binaire) : si $x < -\frac{1}{3}$, Alice gagne, tandis que si $x \geq \frac{1}{3}$, Bob -gagne. (À toutes fins utiles, on rappelle que $\frac{1}{3}$ s'écrit -$0{.}01010101\ldots$ en binaire.) Que pensez-vous de ce jeu ? - -\rightanswer -Bob a une stratégie gagnante - -\answer -Alice a une stratégie gagnante - -\answer -aucun joueur n'a de stratégie gagnante - -\answer -un joueur a une stratégie gagnante, mais il est impossible de savoir -lequel - -\end{question} - \end{qvar} @@ -654,52 +589,6 @@ de départ étant notée $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); @@ -1012,33 +901,6 @@ $\omega^{\omega^\omega}$ \end{question} -% -% -% - -\begin{question} - -Auquel ordinaux suivants est égal $2^{\omega^2}$ (lire : $2$ puissance -$\omega^2$) ? - -\rightanswer -$\omega^\omega$ - -\answer -$\omega$ - -\answer -$\omega^2$ - -\answer -$\omega^{\omega^2}$ - -\answer -$\omega^{\omega^\omega}$ - -\end{question} - - \end{qcm} % % diff --git a/sample-2020qcm.tex b/sample-2020qcm.tex new file mode 100644 index 0000000..3ac1545 --- /dev/null +++ b/sample-2020qcm.tex @@ -0,0 +1,334 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{matrix,calc} +\usepackage{hyperref} +% +%\externaldocument{notes-mitro206}[notes-mitro206.pdf] +% +\newenvironment{qcm}{\relax}{\relax} +\newenvironment{qvar}{\relax}{\relax} +\newcounter{quescnt} +\newenvironment{question}% +{\stepcounter{quescnt}\bigskip\noindent\textbf{Question~\arabic{quescnt}.}\par\nobreak} +{\relax} +\newcounter{answcnt}[quescnt] +\newcommand\answer{% +\stepcounter{answcnt}\smallskip\textbf{(\Alph{answcnt})}~} +\let\rightanswer=\answer +% +\newcommand{\outnb}{\operatorname{outnb}} +\newcommand{\downstr}{\operatorname{downstr}} +\newcommand{\precs}{\operatorname{precs}} +\newcommand{\mex}{\operatorname{mex}} +\newcommand{\id}{\operatorname{id}} +\newcommand{\limp}{\Longrightarrow} +\newcommand{\gr}{\operatorname{gr}} +\newcommand{\rk}{\operatorname{rk}} +\newcommand{\fuzzy}{\mathrel{\|}} +% +\DeclareUnicodeCharacter{00A0}{~} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% +\begin{document} +\ifcorrige +\title{MITRO206\\Échantillon de questions — Corrigé\\{\normalsize Théories des jeux}} +\else +\title{MITRO206\\Échantillon de questions\\{\normalsize Théories des jeux}} +\fi +\author{} +\date{26 juin 2020} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Ce contrôle de connaissances est un QCM (questionnaire à choix +multiples). Chaque question admet une unique réponse correcte. Les +questions sont totalement indépendantes les unes des autres. La +sélection des questions et l'ordre ont été tirés aléatoirement et +n'obéissent donc à aucune logique particulière. + +La réponse est attendue sous forme d'une liste de numéros de question +suivie de la réponse proposée : par exemple, « \verb=1A 2B 4D= » pour +signifier que la réponse proposée à la question 1 est (A), la réponse +proposée à la question 2 est (B), et la réponse proposée à la +question 4 est (D). + +Une réponse incorrecte sera (deux fois) plus fortement pénalisée +qu'une absence de réponse : il est donc préférable de ne pas répondre +à une question que de répondre aléatoirement. + +\medbreak + +Durée : 1h de 17h30 à 18h30 + +\vfill + +%% \noindent +%% Sujet généré pour : \texttt{\seedval} + +\medskip + +{\tiny\noindent +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + +\begin{qcm} + +\begin{question} + +Auquel ordinaux suivants est égal $2^{\omega^2}$ (lire : $2$ puissance +$\omega^2$) ? + +\answer +$\omega^{\omega^\omega}$ + +\rightanswer +$\omega^\omega$ + +\answer +$\omega^{\omega^2}$ + +\answer +$\omega^2$ + +\answer +$\omega$ + +\end{question} + +\begin{corrige} +On a $2^{\omega^2} = 2^{\omega\times\omega} = (2^\omega)^\omega = +\omega^\omega$, donc réponse \textbf{(B)}. +\end{corrige} + + +% +% +% + +\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.) + +\answer +$(\frac{1}{3}, \frac{1}{3}, 0, \frac{1}{3}, 0)$ + +\answer +$(0, \frac{1}{2}, 0, \frac{1}{2}, 0)$ + +\answer +$(0, 0, 0, 0, 1)$ + +\rightanswer +$(\frac{1}{5}, \frac{2}{5}, 0, \frac{2}{5}, 0)$ + +\end{question} + +\begin{corrige} +Dans un jeu à somme nulle, les équilibres de Nash sont exactement les +paires de stratégies optimales. Ici le jeu est symétrique, donc les +stratégies optimales seront les mêmes pour les deux joueurs et la +valeur $v$ du jeu sera $0$. Pour vérifier qu'une stratégie est +optimale, il s'agit donc de vérifier que si les deux joueurs la joue, +aucun ne peut faire mieux en jouant une stratégie pure différente. On +calcule donc les combinaisons des lignes du tableau dont les +coefficients sont donnés par les probabilités dans les différentes +réponses, et la seule dont toutes les valeurs sont $\geq v$ est +$(\frac{1}{5}, \frac{2}{5}, 0, \frac{2}{5}, 0)$. +Réponse \textbf{(D)}. +\end{corrige} + + +% +% +% + +\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$) ? + +\answer +$4$ + +\answer +$2$ + +\rightanswer +$0$ + +\answer +$1$ + +\answer +$3$ + +\end{question} + +\begin{corrige} +On calcule les valeurs de Grundy de proche en proche (c'est-à-dire par +induction bien-fondée), la valeur de Grundy d'une position étant le +mex (= plus petite valeur exclue) des valeurs de Grundy de ses voisins +sortants. On trouve + +\begin{center} +\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] +\node (n00) at (0bp,0bp) [draw,circle] {$0$}; +\node (n01) at (40bp,0bp) [draw,circle] {$1$}; +\node (n02) at (80bp,0bp) [draw,circle] {$0$}; +\node (n10) at (0bp,-40bp) [draw,circle] {$1$}; +\node (n11) at (40bp,-40bp) [draw,circle] {$0$}; +\node (n12) at (80bp,-40bp) [draw,circle] {$1$}; +\node (n20) at (0bp,-80bp) [draw,circle] {$0$}; +\node (n21) at (40bp,-80bp) [draw,circle] {$1$}; +\node (n22) at (80bp,-80bp) [draw,circle] {$0$}; +\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} + +La réponse correcte est donc \textbf{(C)}. +\end{corrige} + + +% +% +% + +\begin{question} + +Alice et Bob jouent au jeu de type Gale-Stewart suivant : chacun à son +tour choisit un chiffre binaire (soit $0$ soit $1$ : Alice choisit +$a_1$ puis Bob choisit $a_2$ puis Alice choisit $a_3$ et ainsi de +suite). Au bout d'un nombre infini de tours, on considère le nombre +réel $x$ entre $0$ et $1$ dont l'écriture binaire fractionnaire est +formée de ces chiffres (c'est-à-dire $x = \sum_{i=1}^{+\infty} +a_i\,2^{-i}$, ou $0{.}a_1a_2a_3\ldots$ en écriture binaire) : si $x < +\frac{1}{3}$, Alice gagne, tandis que si $x \geq \frac{1}{3}$, Bob +gagne. (À toutes fins utiles, on rappelle que $\frac{1}{3}$ s'écrit +$0{.}01010101\ldots$ en binaire.) Que pensez-vous de ce jeu ? + +\answer +un joueur a une stratégie gagnante, mais il est impossible de savoir +lequel + +\rightanswer +Bob a une stratégie gagnante + +\answer +Alice a une stratégie gagnante + +\answer +aucun joueur n'a de stratégie gagnante + +\end{question} + +\begin{corrige} +On peut faire remarquer que $[\frac{1}{3};1]$ est fermé (ou plus +correctement, que l'ensemble des représentations binaires des réels +de $[\frac{1}{3};1]$ est fermé pour la topologie produit) pour se +convaincre qu'il existe forcément une stratégie gagnante pour au moins +un joueur, mais en fait peu importe : Alice va manifestement jouer $0$ +à tous les coups et Bob jouer $1$ à tous les coups (on peut tracer le +début de l'arbre binaire infini des possibilités pour y voir plus +clair), si bien qu'on va tomber sur $\frac{1}{3}$ et Bob a une +stratégie gagnante. Réponse \textbf{(B)}. +\end{corrige} + + +% +% +% + +\end{qcm} + +% +% +% +\end{document} |