From 2fa6f9fd3c20a3d7f107c3479f5e4553659c5201 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 23 Jun 2020 18:05:15 +0200 Subject: Write a file with sample questions (and remove them from the main bank). --- sample-2020qcm.tex | 334 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 334 insertions(+) create mode 100644 sample-2020qcm.tex (limited to 'sample-2020qcm.tex') 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} -- cgit v1.2.3