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). --- controle-2020qcm.tex | 138 --------------------- sample-2020qcm.tex | 334 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 334 insertions(+), 138 deletions(-) create mode 100644 sample-2020qcm.tex diff --git a/controle-2020qcm.tex b/controle-2020qcm.tex index ea5bf29..dd4a76d 100644 --- a/controle-2020qcm.tex +++ b/controle-2020qcm.tex @@ -160,43 +160,6 @@ 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 @@ -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} @@ -640,52 +575,6 @@ 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] {}; @@ -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} -- cgit v1.2.3