summaryrefslogtreecommitdiffstats
path: root/controle-2020qcm.tex
blob: 7fc66ff88c9d8895e4472d6f33542e4b8b204ce3 (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
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
%% 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}

Considérons le jeu analogue à pierre-papier-ciseaux, sauf que les deux
joueurs \emph{détestent} choisir tous les deux la même option, si bien
que la matrice des gains est la suivante (ce n'est plus un jeu à somme
nulle !) :

\begin{center}
\begin{tabular}{r|ccc}
$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux\\\hline
Pierre&$-100,-100$&$-1,+1$&$+1,-1$\\
Papier&$+1,-1$&$-100,-100$&$-1,+1$\\
Ciseaux&$-1,+1$&$+1,-1$&$-100,-100$\\
\end{tabular}
\end{center}

On considère deux profils de stratégies mixtes : (x) Alice et Bob
jouent tous les deux une option entre pierre, papier ou ciseaux
choisie aléatoirement avec probabilité $\frac{1}{3}$ (comme la
stratégie optimale dans le cas du jeu à somme nulle) ; et : (y) Alice
et Bob jouent tous les deux : papier avec probabilité $\frac{101}{200}
= 0.505$, pierre avec probabilité $\frac{99}{200} = 0.495$ et jamais
ciseaux.  Que pensez-vous de ces deux profils ?

\rightanswer
(x) est un équilibre de Nash, mais (y) n'en est pas un

\answer
(x) n'est pas un équilibre de Nash, mais (y) en est un

\answer
(x) et (y) sont tous les deux des équilibres de Nash

\answer
ni (x) ni (y) n'est un équilibre de Nash

\end{question}


%
%
%

\begin{question}

Ambre et Bastien ($8$ ans) jouent à
pierre-papier-ciseaux-éléphant-souris, dont les règles sont les
suivantes : chacun choisit une des cinq options (pierre, papier,
ciseau, éléphant ou souris) indépendamment de l'autre, et
\begin{itemize}
\item si les deux joueurs ont choisi la même option, le jeu est nul,
  sinon :
\item si les deux joueurs ont choisi parmi pierre, papier ou ciseaux,
  le gagnant est déterminé comme à pierre-papier-ciseaux (i.e., le
  papier gagne sur la pierre, les ciseaux gagnent sur le papier et la
  pierre gagne sur les ciseaux),
\item l'éléphant gagne sur tout sauf la souris,
\item la souris gagne sur l'éléphant et perd contre tout le reste.
\end{itemize}
(On accordera la valeur $+1$ au fait de gagner, $-1$ au fait de
perdre, et $0$ à un match nul.)

Quelle est la stratégie optimale à ce jeu ?

\rightanswer
jouer chacun de pierre, papier et ciseaux avec probabilité
$\frac{1}{9}$, éléphant avec probabilité $\frac{1}{3}$ et souris avec
probabilité $\frac{1}{3}$

\answer
jouer chacun de pierre, papier et ciseaux avec probabilité
$\frac{1}{3}$, et jamais éléphant ni souris

\answer
jouer chacun de pierre, papier, ciseaux avec probabilité
$\frac{1}{6}$, éléphant avec probabilité $\frac{1}{2}$ et jamais
souris

\answer
jouer chacun de pierre, papier et ciseaux avec probabilité
$\frac{1}{4}$, éléphant avec probabilité $\frac{1}{8}$ et souris avec
probabilité $\frac{1}{8}$

\answer
jouer chacune des cinq options avec probabilité $\frac{1}{5}$

\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
\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}

On considère une variante du jeu de nim, mais avec la différence qu'on
peut retirer \emph{un ou deux} bâtonnets d'une seule ligne (et dans la
limite du nombre effectivement présent sur cette ligne !).  Par
exemple, à partir de la position $(1,2,3)$ (c'est-à-dire la position
dans laquelle il y $1$ bâtonnet sur une ligne, $2$ sur une autre, et
$3$ sur la troisième), on pourrait aller en $(0,2,3)$ ou $(1,1,3)$ ou
$(1,0,3)$ ou $(1,2,2)$ ou $(1,2,1)$ mais pas en $(1,2,0)$.

Laquelle des descriptions suivantes définit la stratégie gagnante de
ce jeu ?  (On pourra commencer par la valeur de Grundy de la position
où il y a une unique ligne avec $n$ bâtonnets, et se rappeler que la
valeur de Grundy de la somme de nim de deux jeux est la somme de nim
des valeurs de Grundy.)

\rightanswer
jouer de manière à ce qu'il y ait un nombre pair de lignes ayant un
nombre de bâtonnets congru à $1$ modulo $3$ et aussi un nombre pair de
lignes ayant un nombre de bâtonnets congru à $2$ modulo $3$

\answer
jouer de manière à ce qu'il y ait un nombre impair de lignes ayant un
nombre de bâtonnets congru à $1$ modulo $3$ et aussi un nombre pair de
lignes ayant un nombre de bâtonnets congru à $2$ modulo $3$

\answer
jouer de manière à ce qu'il y ait un nombre pair de lignes ayant un
nombre de bâtonnets non multiple de $3$

\answer
jouer de manière à ce que le nombre total de bâtonnets (sur toutes les
lignes) soit multiple de $3$

\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}