%% 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 \corrigefalse \def\seedval{test} % % % \begin{document} \ifcorrige \title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} \else \title{MITRO206\\Contrôle de connaissances\\{\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} 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 \leq \frac{1}{3}$, Alice gagne, tandis que si $x > \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 Alice a une stratégie gagnante \answer Bob 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} % % % \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} % % % \begin{question} C'est à votre tour de jouer au jeu de nim dans une configuration où il y a $1$, $4$, $10$ et $12$ bâtonnets sur les (quatre) lignes du jeu. Que faites-vous (pour suivre la stratégie gagnante) ? \rightanswer retirer $1$ bâtonnet de la ligne qui en a $10$ (qui passe donc à $9$) \answer retirer $3$ bâtonnets de la ligne qui en a $10$ (qui passe donc à $7$) \answer retirer le seul bâtonnet de la ligne qui en a $1$ (qui disparaît donc) \answer 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 y a $1$, $6$, $8$ et $12$ bâtonnets sur les (quatre) lignes du jeu. Que faites-vous (pour suivre la stratégie gagnante) ? \rightanswer retirer $1$ bâtonnet de la ligne qui en a $6$ (qui passe donc à $5$) \answer retirer $3$ bâtonnets de la ligne qui en a $6$ (qui passe donc à $3$) \answer retirer le seul bâtonnet de la ligne qui en a $1$ (qui disparaît donc) \answer retirer $3$ bâtonnets de la ligne qui en a $8$ (qui passe donc à $5$) \end{question} % % % \begin{question} Alice et Bob jouent au jeu suivant sur un échiquier $8\times 8$ sur lequel est positionné un unique pion (commun aux deux joueurs) : \begin{itemize} \item le pion démarre sur la case au coin sud-est de l'échiquier, et Alice joue en premier, \item chaque joueur, tour à tour, déplace le pion d'une seule case, soit vers le nord, soit vers l'ouest, soit (en diagonale) vers le nord-ouest, mais sans dépasser les limites de l'échiquier, \item celui qui atteint la case au coin nord-ouest de l'échiquier a \emph{gagné} (il revient au même de dire que le joueur qui ne peut plus jouer a perdu). \end{itemize} Que pensez-vous de ce jeu ? \rightanswer Alice a une stratégie gagnante, et (pour la suivre) doit commencer par déplacer le pion en diagonale (d'une case vers le nord-ouest) \answer Alice a une stratégie gagnante, et (pour la suivre) doit commencer par déplacer le pion d'une case vers le nord ou, indifféremment, vers l'ouest \answer Alice a une stratégie gagnante, et (pour la suivre) peut commencer par un coup quelconque \answer Bob a une stratégie gagnante \end{question} % % % \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} Auquel ordinaux suivants est égal $\omega + \omega^2 + \omega^\omega$ ? \rightanswer $\omega^\omega$ \answer $\omega^\omega + \omega^2 + \omega$ \answer $\omega$ \answer $\omega^{\omega+1}$ \answer $\omega^\omega\cdot 2$ \end{question} % % % \begin{question} Auquel ordinaux suivants est égal $2^{\omega\cdot 2}$ (lire : $2$ puissance $\omega\cdot 2$) ? \rightanswer $\omega^2$ \answer $\omega$ \answer $\omega^\omega$ \answer $\omega^{\omega^2}$ \answer $\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} % % % \end{document}