summaryrefslogtreecommitdiffstats
path: root/controle-20190408.tex
blob: 429447bc51b96d4b4292c72a65176f548eaa7b82 (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
%% 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]
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
\renewcommand{\qedsymbol}{\smiley}
%
\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}
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\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\\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{8 avril 2019}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Les exercices sont totalement indépendants.  Ils pourront être traités
dans un ordre quelconque, mais on demande de faire apparaître de façon
très visible dans les copies où commence chaque exercice.

\medbreak

L'usage de tous les documents (notes de cours manuscrites ou
imprimées, feuilles d'exercices, livres) est autorisé.

L'usage des appareils électroniques est interdit.

\medbreak

Durée : 2h

Barème \emph{indicatif} : exercice 1 : $3$ points ; exercice 2 :
$4$ points ; exercice 3 : $10$ points ; exercice 4 : $3$ points ;
points bonus : comme indiqué.

\emph{Avertissement :} Les exercices ne sont pas tous une application
immédiate du cours ; il est parfois nécessaire de s'inspirer des
techniques ou raisonnements vus en cours pour raisonner dans des
cadres légèrement différents.

\vfill
{\noindent\tiny
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pagebreak


%
%
%

\exercice

On s'intéresse dans cet exercice à des jeux à deux joueurs (que l'on
appellera Alice et Bob) de la forme suivante :
\begin{itemize}
\item Alice et Bob sont autour d'une table sur laquelle se trouvent un
  certain nombre (fini) de \emph{jetons} ; chaque jeton porte un
  entier naturel qu'on appellera son \emph{type} ; il peut y avoir
  plusieurs jetons de même type (par exemple, trois jetons de
  type $0$, deux jetons de type $1$ et un jeton de type $1729$) ; le
  nombre (fini) de jetons de jetons de chaque type constitue l'état du
  jeu, et il est visible de tous ;
\item Alice et Bob jouent tour à tour, et chacun, quand vient son
  tour, doit retirer un jeton de la table et le \emph{remplacer}
  éventuellement par des jetons de type(s) strictement plus petit(s) :
  les règles exactes de remplacement seront différentes d'une question
  à l'autre, mais prendront toujours la forme « un joueur peut
  remplacer un jeton de type $n$ par telle ou telle combinaison de
  jetons de types $<n$ » ; dans tous les cas, un coup consiste à
  retirer un unique jeton et à en poser éventuellement plusieurs ; il
  y aura toujours au moins une manière de remplacer un jeton de
  type $n$ donné ;
\item il n'y a aucune interaction entre les jetons, c'est-à-dire que
  les remplacements permis pour un jeton de type $n$ ne dépendront que
  de $n$ et pas des autres jetons présents sur la table (ni de
  l'identité du joueur, ni du numéro du coup, ni de quelque autre
  information) ;
\item on notera que les jetons de type $0$ ne peuvent être que retirés
  (il n'y a aucun remplacement possible puisqu'il n'existe pas de
  jeton de type $<0$) ;
\item le gagnant est celui qui retire le dernier jeton (puisque son
  adversaire ne peut plus jouer).
\end{itemize}

\smallskip

Dans les questions (1) à (3), on ne fait pas d'hypothèse particulière
sur les règles de remplacement autre que celles qui sont indiquées
ci-dessus.  Dans les questions (4) à (6), on traite le cas de règles
de remplacement particulières.

\medskip

(1) Montrer que le jeu termine toujours en temps fini.  On pourra pour
cela associer judicieusement un ordinal à l'état du jeu et montrer
qu'il décroît strictement à chaque tour.

\medskip

(2)(a) En notant $J(n_1,\ldots,n_r)$ l'état du jeu dans lequel $r$
jetons se trouvent sur la table et ont les types $n_1,\ldots,n_r$
(éventuellement répétés, p.ex. $J(0,0,0,1,1,1729)$), expliquer
pourquoi $J(n_1,\ldots,n_r)$ peut s'identifier à la somme de nim des
positions $J(n_1),\ldots,J(n_r)$ (où $J(n)$ désigne l'état du jeu
ayant un unique jeton de type $n$).\quad(b) En déduire la valeur de
Grundy $\gr J(n_1,\ldots,n_r)$ de $J(n_1,\ldots,n_r)$ en fonction de
celles $\gr J(n_i)$ des $J(n_i)$.\quad(c) Qui a une stratégie gagnante
dans une position du type $J(n,n)$ ?  Expliciter une telle stratégie
en termes simples.

(\emph{Convention :} $J()$ est le jeu nul dans lequel il ne reste plus
aucun jeton.  Notamment, on a $\gr J() = 0$.)

\medskip

(3)(a) Pour une règle de remplacement $\mathscr{R}$ donnée, en notant
par exemple $\mathscr{R}_n$ l'ensemble (non vide) de tous les
remplacements possibles d'un jeton de type $n$ (considérés comme des
suites finies d'entiers $<n$), expliquer comment on peut calculer $\gr
J(n)$ si on suppose connus tous les $\gr J(n')$
pour $n'<n$.\quad(b) On rappelle que le seul remplacement possible
d'un jeton de type $0$ est de l'enlever purement et simplement (i.e.,
$\mathscr{R}_0 = \{()\}$ si on veut) : en déduire la valeur de $\gr
J(0)$ et celle de $\gr J(0,\ldots,0)$ (avec, disons, $r$ jetons de
type $0$).

\medskip

(4) On suppose dans cette question que la règle de remplacement est la
suivante : un joueur peut remplacer un jeton de type $n$ par un nombre
quelconque (y compris $0$) de jetons de type $n-1$.  (Autrement dit, à
chaque coup, le joueur retire un jeton de type $n$ et si $n>0$ il
ajoute ensuite, optionnellement, le nombre qu'il souhaite de jetons de
type $n-1$.  Par exemple, on peut remplacer un jeton de type $1729$
par $42$ jetons de type $1728$ ; on peut aussi le retirer sans
remplacement.)\quad(a) Dans ces conditions, que vaut $\gr J(n)$ ?  (On
pourra par exemple commencer par calculer $\gr J(n)$ pour $n=0,1,2,3$,
conjecturer une formule générale, et la démontrer par récurrence
sur $n$.)\quad(b) Exprimer de façon simple la stratégie gagnante du
jeu considéré dans cette question.

\medskip

(5) On suppose dans cette question que la règle de remplacement est la
suivante : un joueur peut remplacer un jeton de type $n$ par un nombre
quelconque (y compris $0$) de jetons de type $k<n$, mais le type doit
être le même pour tous les jetons remplacés.  (Autrement dit, à chaque
coup, le joueur retire un jeton de type $n$ et si $n>0$ il ajoute
ensuite, optionnellement, le nombre qu'il souhaite de jetons d'un même
type $k\leq n-1$.  Par exemple, on peut remplacer un jeton de
type $1729$ par $42$ jetons de type $1728$ ou $1728$ jetons de
type $42$ ; on peut aussi le retirer sans remplacement.)  Dans ces
conditions, que vaut $\gr J(n)$ ?  (On pourra par exemple commencer
par calculer $\gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule
générale, et la démontrer par récurrence sur $n$.)

\medskip

(6) On suppose dans cette question que la règle de remplacement est la
suivante : un joueur peut remplacer un jeton de type $n$ par un nombre
quelconque (y compris $0$) de jetons de types $<n$.  (Autrement dit, à
chaque coup, le joueur retire un jeton de type $n$ et si $n>0$ il
ajoute ensuite, optionnellement, le nombre qu'il souhaite de jetons de
n'importe quels types $<n$.  Par exemple, on peut remplacer un jeton
de type $1729$ par $42$ jetons de type $1728$ et $666$ de type $0$ ;
on peut aussi le retirer sans remplacement.)\quad(a) Dans ces
conditions, que vaut $\gr J(n)$ ?  (On pourra par exemple commencer
par calculer $\gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule
générale, et la démontrer par récurrence sur $n$.)\quad(b) Exprimer de
façon simple la stratégie gagnante du jeu considéré dans cette
question.


%
%
%

\exercice

On définit une opération binaire $\alpha\boxplus\beta$ (appelée
« somme naturelle » ou « somme de Hessenberg ») sur les ordinaux (ici
notés $\alpha,\beta$) par la formule suivante :
\[
\alpha \boxplus \beta = \sup\nolimits^+ \Big( \{\alpha'\boxplus\beta :
\alpha' < \alpha\} \cup\, \{\alpha\boxplus\beta' : \beta' <
\beta\}\Big)
\]
où on rappelle que $\sup^+ S$, si $S$ est un ensemble d'ordinaux,
désigne \emph{le plus petit ordinal strictement plus grand que tous
  les éléments de $S$} (c'est aussi $\sup\{\gamma+1 : \gamma\in S\}$
mais c'est probablement moins utile d'y penser sous cette forme).
Autrement dit, $\alpha\boxplus\beta$ désigne le plus petit ordinal qui
soit strictement supérieur à tous les $\alpha'\boxplus\beta$ pour
$\alpha'<\alpha$ ainsi qu'à tous les $\alpha\boxplus\beta'$
pour $\beta'<\beta$.  Cette définition a bien un sens par induction
bien-fondée.

\medskip

(1)(a) Calculer $m\boxplus n$ pour $0\leq m\leq 5$ et $0\leq n\leq
5$.\quad(b) Conjecturer une formule générale pour $m\boxplus n$
lorsque $m,n\in\mathbb{N}$ (c'est-à-dire
$m,n<\omega$).\quad(c) Démontrer cette formule.

\medskip

(2)(a) Montrer que $\boxplus$ est commutative, c'est-à-dire que
$\alpha\boxplus\beta = \beta\boxplus\alpha$ quels que
soient $\alpha,\beta$.\quad(b) Montrer que $\boxplus$ admet $0$ pour
élément neutre, c'est-à-dire que $\alpha\boxplus 0 = 0\boxplus\alpha =
\alpha$ pour tout ordinal $\alpha$.

\medskip

On \underline{admettra} pour la suite que $\boxplus$ est associative,
c'est-à-dire que $(\alpha_1\boxplus\alpha_2) \boxplus \alpha_3 =
\alpha_1 \boxplus (\alpha_2\boxplus\alpha_3)$ quels que soient
$\alpha_1,\alpha_2,\alpha_3$, et que
$\alpha_1\boxplus\cdots\boxplus\alpha_n$ est le plus petit ordinal
strictement supérieur à tous les
$\alpha_1\boxplus\cdots\boxplus\beta_i\boxplus
\cdots\boxplus\alpha_n$, où exactement un des $\alpha_i$ a été
remplacé par un ordinal $\beta_i$ strictement plus petit
(généralisation de la définition au cas de $n$ termes).

\smallskip

Si $\alpha$ est un ordinal et $n\geq 1$ un entier naturel, on
\underline{notera} $\alpha\boxdot n$ pour la somme naturelle $\alpha
\boxplus \cdots \boxplus \alpha$ de $n$ fois l'ordinal $\alpha$ (on
pourra aussi poser $\alpha\boxdot 0 = 0$).  Dans ces conditions, il
est trivial que $(\alpha\boxdot n) \boxplus (\alpha\boxdot n') =
\alpha\boxdot (n+n')$.

\medskip

(3) Montrer par induction transfinie sur $\alpha$ que si $\alpha =
\omega^{\gamma_1} n_1 + \cdots + \omega^{\gamma_r} n_r$ (où $\gamma_1
> \cdots > \gamma_r$ sont des ordinaux en ordre strictement
décroissant et $n_1,\ldots,n_r$ des entiers naturels non nuls ;
c'est-à-dire qu'il s'agit de la forme normale de Cantor de $\alpha$)
alors on a $\alpha = (\omega^{\gamma_1} \boxdot n_1) \boxplus \cdots
\boxplus (\omega^{\gamma_r} \boxdot n_r)$.

\emph{Indication :} On imitera de près la démonstration du fait donné
en cours que si $\alpha = 2^{\gamma_1} + \cdots + 2^{\gamma_r}$ (où
$\gamma_1 > \cdots > \gamma_r$ sont des ordinaux en ordre strictement
décroissant ; c'est-à-dire qu'il s'agit de la l'écriture binaire
de $\alpha$) alors on a $\alpha = 2^{\gamma_1} \oplus \cdots \oplus
2^{\gamma_r}$.  Il n'y a pas grand-chose à modifier à part remplacer
$\mex$ par $\sup^+$ aux endroits utiles.  (Cette question est un peu
longue, mais il est possible de traiter la suite en l'admettant.)

\medskip

(4)(a) En déduire la manière dont on calcule $\alpha\boxplus\beta$ à
partir des formes normales de Cantor de
$\alpha$ et $\beta$.\quad(b) En particulier, calculer
$(\omega+1)\boxplus(\omega+1)$, et comparer avec $(\omega+1) +
(\omega+1)$.

\medskip

(5) On considère le jeu à deux joueurs suivant : les deux joueurs
s'appellent Blaise et Roxane, et ils jouent tour à tour (on ne précise
pas qui commence) ; l'état du jeu est défini par trois ordinaux, qu'on
notera $(\alpha,\beta,\rho)$, et il est visible de tous ; les coups
possibles de Blaise consistent à diminuer strictement soit l'ordinal
$\alpha$ soit l'ordinal $\beta$ (c'est-à-dire passer de
$(\alpha,\beta,\rho)$ à $(\alpha',\beta,\rho)$ avec $\alpha'<\alpha$
ou à $(\alpha,\beta',\rho)$ avec $\beta'<\beta$), tandis que les coups
possibles de Roxane consistent à diminuer strictement l'ordinal $\rho$
(c'est-à-dire passer de $(\alpha,\beta,\rho)$ à $(\alpha,\beta,\rho')$
avec $\rho'<\rho$) ; le joueur qui ne peut plus jouer a perdu.

Montrer que, dans ce jeu, Blaise possède une stratégie gagnante
lorsque $\rho > \alpha\boxplus\beta$, que Roxane possède une stratégie
gagnante lorsque $\rho < \alpha\boxplus\beta$, et que le second joueur
possède une stratégie gagnante lorsque $\rho = \alpha\boxplus\beta$.


%
%
%

\exercice

Soit $n\geq 3$ un entier naturel.  On considère le jeu suivant : Alice
et Bob choisissent chacun en secret un entier naturel $0\leq i\leq
n-1$ et le révèlent simultanément.  Si les deux nombres sont égaux, la
partie est nulle ; sinon, le gagnant est celui qui a choisi le plus
grand, \emph{sauf} dans le cas où un joueur a choisi $n-1$ et l'autre
joueur a choisi $0$, et alors c'est celui qui a choisi $0$ qui gagne.

(On considérera qu'un gain apporte une valeur de $+1$ à celui qui
gagne, une perte une valeur de $-1$ à celui qui perd, et qu'une partie
nulle a une valeur de $0$ pour les deux joueurs.)

(1) De quelle sorte de jeu s'agit-il ?  Écrire explicitement sa
matrice de gains dans le cas $n=5$.  Pour des raisons de symétrie,
quelle est la valeur du jeu ?

(2) Montrer qu'une stratégie mixte optimale consiste à jouer chacune
des options $0$, $n-2$ et $n-1$ avec probabilité $\frac{1}{3}$ (et
jamais les autres).  On l'appellera $s_0$.

(3) Si Alice joue selon la stratégie $s_0$ décrite en (2) et si Bob
joue l'option $i$, quel est le gain espéré de Bob en fonction de $i$ ?

(4) Déduire de (3) qu'aucune stratégie optimale ne peut avoir une
option autre que $0$, $n-2$ ou $n-1$ dans son support.  (On pourra
faire jouer une telle stratégie contre $s_0$.)

(5) Montrer que la stratégie $s_0$ décrite en (2) est la seule
stratégie optimale de ce jeu.


%
%
%
\end{document}