summaryrefslogtreecommitdiffstats
path: root/sample-2020qcm.tex
blob: 4cf4b0258948b26556dc5b1041b2307defebedaf (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
%% 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 (mais
certaines peuvent se ressembler).  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 (possiblement jusqu'à 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}