summaryrefslogtreecommitdiffstats
path: root/controle-20190408.tex
blob: 6e4da383034a21b0d11c71586bb62e92b07139d2 (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
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
%% 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.

La longueur du sujet ne doit pas effrayer : d'une part, l'énoncé est
long parce que des rappels ont été faits et que la rédaction des
questions cherche à éviter toute ambiguïté ; d'autre part, il ne sera
pas nécessaire de tout traiter pour obtenir la totalité des points
(cf. barème).

\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 : $9$ points ; exercice 2 :
$9$ points ; exercice 3 : $4$ points.

\ifcorrige
Ce corrigé comporte 10 pages (page de garde incluse).
\else
Cet énoncé comporte 6 pages (page de garde incluse).
\fi

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

\begin{corrige}
On associe à la position $J(n_1,\ldots,n_r)$ (définie en (2)
ci-dessous), quitte à supposer $n_1>\cdots>n_r$ l'ordinal
$\omega^{n_1} + \cdots + \omega^{n_r}$ ; ou, ce qui revient au même,
s'il y a $r_n := \#\{i : n_i = n\}$ jetons de type $n$, on considère
l'ordinal $\omega^N r_n + \cdots + \omega^2 r_2 + \omega\, r_1 + r_0$
où $N := \max\{n_i\}$ est le plus grand type d'un jeton sur la table.
Par la comparaison des ordinaux écrits en forme normale de Cantor, cet
ordinal décroît à chaque coup (puisqu'on remplace un $\omega^n$ par
des $\omega^{n'}$ avec $n' < n$, la suite $(r_n,\ldots,r_0)$ décroît
lexicographiquement).  Le jeu termine donc en temps fini.
\end{corrige}

\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 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 sur la table.  Notamment, on a $\gr J() = 0$.  On ne le
confondra pas avec $J(0)$ où il reste un jeton de type $0$.)

\begin{corrige}
(a) Il s'agit simplement d'observer que les différents jetons
  n'interagissent pas du tout.  Jouer à la somme de nim de
  $J(n_1),\ldots,J(n_r)$ revient à jouer sur $r$ tables différentes à
  partir d'un jeton de type $n_i$ sur chacune, c'est équivalent à
  jouer à $J(n_1,\ldots,n_r)$.

(b) On en déduit que $\gr J(n_1,\ldots,n_r) = \gr(J(n_1) \oplus \cdots
  \oplus J(n_r)) = \gr J(n_1) \oplus \cdots \oplus \gr J(n_r)$ (la
  première égalité par (a), la seconde d'après le fait que la valeur
  de Grundy d'une somme de nim est la somme de nim des valeur de
  Grundy).

(c) Le second joueur a une stratégie gagnante à $J(n,n)$ (ceci se voit
  par le fait que sa valeur de Grundy vaut $0$).  Cette stratégie
  consiste à reproduire systématiquement les coups de son adversaire
  (ce qui maintiendra un nombre pair de jetons de chaque type à la fin
  de son coup).
\end{corrige}

\medskip

(3)(a) Pour une règle de remplacement donnée, expliquer comment se
calcule $\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 : en
déduire la valeur de $\gr J(0)$ et celle de $\gr J(0,\ldots,0)$ (où il
y a $r$ jetons de type $0$).

\begin{corrige}
(a) Puisque $\gr x$, pour une position $x$ d'un jeu combinatoire
  impartial bien-fondé, vaut $\mex\{\gr y : y\in\outnb(x)\}$, on a ici
  $\gr J(n) = \mex\{\gr J(n'_1,\ldots,n'_r) : J(n'_1,\ldots,n'_r)
  \in\outnb J(n)\}$, c'est-à-dire $\gr J(n) = \mex\{\gr J(n'_1) \oplus
  \cdots \oplus \gr J(n'_r) : J(n'_1,\ldots,n'_r)\in\outnb J(n)\}$
  d'après (2)(b) ; la règle de remplacement consiste justement à
  décrire les $J(n'_1,\ldots,n'_r)\in\outnb J(n)$.

(b) Dans le cas de $n=0$, comme $\outnb J(0) = \{J()\}$, on trouve
  $\gr J(0) = \mex\{0\} = 1$, et par conséquent $\gr J(0,\ldots,0) =
  1\oplus \cdots\oplus 1$ vaut $0$ ou $1$ selon que $r$ est pair ou
  impair.
\end{corrige}

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

\begin{corrige}
(a) On a vu en (3)(b) que $\gr J(0,\ldots,0)$ vaut $0$ ou $1$ selon
  que le nombre de jetons est pair ou impair ; on en déduit que $\gr
  J(1) = \mex\{0,1\} = 2$, et alors (en se rappelant que $2\oplus
  2=0$) on trouve que $\gr J(1,\ldots,1)$ vaut $0$ ou $2$ selon que le
  nombre de jetons est pair ou impair ; on en déduit que $\gr J(2) =
  \mex\{0,2\} = 1$, et donc $\gr J(2,\ldots,2)$ vaut $0$ ou $1$ selon
  que le nombre de jetons est pair ou impair ; par conséquent, $\gr
  J(3) = \mex\{0,1\} = 2$.  En général on imagine facilement que $\gr
  J(n)$ vaut $1$ ou $2$ selon que $n$ est pair ou impair, et ceci se
  démontre par une récurrence immédiate avec exactement le même
  argument qu'on vient de faire.

(b) La valeur de Grundy de $\gr J(n_1,\ldots,n_r)$ est le XOR (= la
  somme de nim) de $r$ valeurs $1$ si $r$ est le nombre de jetons de
  type pair, et $r'$ valeurs $2$ si $r'$ est le nombre de jetons de
  type impair : ce nombre vaut $0$, $1$, $2$ ou $3$ selon que $r$ et
  $r'$ sont tous les deux pairs, que $r$ est impair et $r'$ pair,
  qu'on a le contraire, ou qu'ils sont tous les deux impairs.  La
  stratégie gagnante consiste donc à jouer de façon que le nombre $r$
  de jetons de type pair et le nombre $r'$ de jetons de type impair
  soient tous les deux pairs (de façon à annuler Grundy).
\end{corrige}

\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$, le type $k$
pouvant être quelconque mais doit être le même pour tous les jetons
posé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$.)

\begin{corrige}
On a vu en (3)(b) que $\gr J(0,\ldots,0)$ vaut $0$ ou $1$ selon que le
nombre de jetons est pair ou impair ; on en déduit que $\gr J(1) =
\mex\{0,1\} = 2$, et alors (en se rappelant que $2\oplus 2=0$) on
trouve que $\gr J(1,\ldots,1)$ vaut $0$ ou $2$ selon que le nombre de
jetons est pair ou impair ; on en déduit que $\gr J(2) = \mex\{0,1,2\}
= 3$ (la différence avec (4)(a) est que maintenant on peut aussi aller
en $\gr J(0,\ldots,0)$ donc $1$ apparaît dans le $\mex$), et donc $\gr
J(2,\ldots,2)$ vaut $0$ ou $3$ selon que le nombre de jetons est pair
ou impair ; par conséquent, $\gr J(3) = \mex\{0,1,2,3\} = 4$.  En
général on imagine facilement que $\gr J(n)$ vaut $n+1$, et ceci se
démontre par une récurrence immédiate avec exactement le même argument
qu'on vient de faire.
\end{corrige}

\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$, qui cette fois
n'ont pas d'obligation d'être tous du même type.  (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.

\begin{corrige}
(a) On a vu en (3)(b) que $\gr J(0,\ldots,0)$ vaut $0$ ou $1$ selon
  que le nombre de jetons est pair ou impair ; on en déduit que $\gr
  J(1) = \mex\{0,1\} = 2$, et alors (en se rappelant que $2\oplus
  2=0$) on trouve que $\gr J(0,\ldots,0,\penalty0\relax 1,\ldots,1)$
  vaut $0$, $1$, $2$ ou $3$ selon que le nombre de jetons de chaque
  type est pair ou impair (comme expliqué en (4)(b)) ; on en déduit
  que $\gr J(2) = \mex\{0,1,2,3\} = 4$, et donc $\gr
  J(0,\ldots,0,\penalty0\relax 1,\ldots,1,\penalty0\relax 2,\ldots,2)$
  prend exactement les valeurs entre $0$ et $7$ selon la parité des
  jetons de chaque type ; par conséquent, $\gr J(3) =
  \mex\{0,\ldots,7\} = 8$.  En général on imagine facilement que $\gr
  J(n)$ vaut $2^n$, et ceci se démontre par une récurrence immédiate
  en remarquant que le $\gr J(n'_1,\ldots,n'_r)$, si les $n'_i$
  sont $<n$, peut prendre toutes les valeurs de $0$ à $2^n - 1$ selon
  la parité des jetons de chaque type (donnant l'écriture binaire du
  résultat).

(b) La stratégie gagnante consiste donc à jouer de façon que le nombre
  de jetons de chaque type soit pair.
\end{corrige}


%
%
%

\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

%% À toutes fins utiles, on signale le fait évident qu'on a $\xi =
%% \sup^+ S$ si et seulement si on a (i) $\xi$ est strictement
%% supérieur à tout élément de $S$, et (ii) tout ordinal $<\xi$ est
%% inférieur ou égal à un élément de $S$.

À toutes fins utiles, on signale le fait évident que $\sup^+ S$ ne
change pas si on insère dans $S$ des nouveaux éléments qui sont
majorés par des éléments déjà dans $S$.

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

\begin{corrige}
(a)/(b) On construit le tableau de proche en proche en inscrivant dans
  chaque case le plus petit entier strictement supérieur à tous les
  nombres écrits plus haut dans la colonne ou plus à gauche dans la
  ligne : on obtient $m\boxplus n = m + n$, et on peut imaginer que
  c'est vrai en général.

(c) Montrons que $m\boxplus n = m + n$ pour tous $m,n\in\mathbb{N}$ :
  par récurrence (sur $m+n$), on peut supposer connu le fait que
  $m'\boxplus n = m' + n$ pour tout $m'<m$ et $m\boxplus n' = m + n'$
  pour tout $n'<n$.  On a alors $m \boxplus n = \sup^+ \big( \{m'
  \boxplus n : m' < m\} \penalty0 \cup \penalty0 \{m \boxplus n' : n'
  < n\}\big) = \sup^+ \big( \{m' + n : m' < m\} \penalty0 \cup
  \penalty0 \{m + n' : n' < n\}\big)$ ; or l'ensemble dont on prend le
  $\sup^+$ ne contient que des entiers $<m+n$ et contient $m+n-1$ donc
  ce $\sup^+$ vaut $m+n$, ce qui conclut la récurrence.
\end{corrige}

\medskip

(2)(a) Montrer que $\boxplus$ est commutative, c'est-à-dire que
$\alpha_1\boxplus\alpha_2 = \alpha_2\boxplus\alpha_1$ quels que
soient $\alpha_1,\alpha_2$.\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$.\quad(c) Montrer
que si $\alpha'\leq\alpha$ et $\beta'\leq\beta$ alors
$\alpha'\boxplus\beta' \leq \alpha\boxplus\beta$, avec inégalité stricte
dans la conclusion si au moins une d'elles est stricte dans
l'hypothèse.

\begin{corrige}
(a) Par induction transfinie sur $\alpha_1$ et $\alpha_2$, on prouve
  $\alpha_2\boxplus\alpha_1 = \alpha_1\boxplus\alpha_2$ : en effet,
  $\alpha_2\boxplus\alpha_1 = \sup^+ (\{\alpha_2\boxplus\beta_1:
  \beta_1<\alpha_1\} \penalty0 \cup \penalty0
  \{\beta_2\boxplus\alpha_1: \beta_2<\alpha_2\})$, et par hypothèse
  d'induction ceci vaut $\sup^+ (\{\beta_1\boxplus\alpha_2:
  \beta_1<\alpha_1\} \penalty0 \cup \penalty0
  \{\alpha_1\boxplus\beta_2: \beta_2<\alpha_2\}) =
  \alpha_1\boxplus\alpha_2$.

(b) Par induction sur $\alpha$, on prouve $\alpha \boxplus 0 =
  \alpha$ : en effet, $\alpha \boxplus 0 = \sup^+ \{\beta\boxplus 0:
  \beta<\alpha\}$, et par hypothèse d'induction ceci vaut $\sup^+
  \{\beta: \beta<\alpha\} = \alpha$.  Par la commutativité déjà
  prouvée, $0 \boxplus \alpha$ vaut lui aussi $\alpha$.

(c) Si $\alpha'<\alpha$ alors $\alpha'\boxplus\beta <
  \alpha\boxplus\beta$ par définition même de $\alpha\boxplus\beta$,
  et de même si $\beta'<\beta$ alors $\alpha\boxplus\beta' <
  \alpha\boxplus\beta$.  Si on a à la fois $\alpha'<\alpha$ et
  $\beta'<\beta$ alors $\alpha'\boxplus\beta' < \alpha'\boxplus\beta <
  \alpha\boxplus\beta$ d'après ce qu'on vient de dire.  C'est
  exactement ce qu'il fallait démontrer.
\end{corrige}

\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 on admettra aussi 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, analogue à un
résultat vu en cours sur les sommes de nim).

\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')$ ; par ailleurs, on a $1\boxdot n = n$ d'après la
question (1).

\medskip

Considérons l'affirmation suivante :

{\narrower\noindent\leavevmode\llap{(*) }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)$\par}

\noindent (ceci est à comparer au fait, démontré 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 l'écriture binaire de $\alpha$, alors on
a $\alpha = 2^{\gamma_1} \oplus \cdots \oplus 2^{\gamma_r}$).

On pourrait démontrer (*) par induction transfinie sur $\alpha$.
Comme c'est notationnellement un peu fastidieux, on va seulement, dans
la question suivante, montrer un cas particulier assez représentatif
de l'idée générale :

\medskip

(3)(a) Pour $n_0,n_1 \in \mathbb{N}$, montrer que $(\omega\boxdot n_1)
\boxplus n_0 = \sup^+ \big( \{(\omega\boxdot n'_1) \boxplus n_0' :
n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \penalty0 \cup
\penalty0 \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 <
n_0\}\big)$.\quad (b) En déduire par induction transfinie sur $\alpha$
que si $\alpha = \omega\, n_1 + n_0$ où $n_0,n_1 \in \mathbb{N}$,
alors $\alpha = (\omega \boxdot n_1) \boxplus n_0$ (ceci est un cas
particulier de (*)).

\begin{corrige}
(a) D'après ce qu'on a admis ci-dessus, $(\omega\boxdot n_1) \boxplus
  n_0$, qui est une somme naturelle de $n_1$ copies de $\omega$ et
  $n_0$ fois $1$, est le plus petit ordinal strictement supérieur à
  toutes les sommes naturelles obtenues en remplaçant un
  des ($n_1+n_0$) termes par un terme strictement plus petit,
  c'est-à-dire à tous les $(\omega\boxdot (n_1-1)) \boxplus b \boxplus
  n_0$ pour $b<\omega$ (cas où on remplace un $\omega$ par $b$) et à
  $(\omega\boxdot n_1) \boxplus (n_0-1)$ (cas où on remplace un $1$
  par $0$).  En se rappelant que $b \boxplus n_0 = b + n_0$ (qui prend
  donc toutes les valeurs $\geq n_0$) et qu'on a le droit d'insérer
  dans un ensemble dont on prend le $\sup^+$ des nouveaux éléments qui
  sont majorés par des éléments déjà dedans (et comme $\boxplus$ est
  croissante en chaque variable d'après (2)(c)), on peut écrire
  $(\omega\boxdot n_1) \boxplus n_0 = \sup^+ \big( \{(\omega\boxdot
  n'_1) \boxplus n_0' : n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\}
  \penalty0 \cup \penalty0 \{(\omega\boxdot n_1) \boxplus n_0' : n'_0
  < n_0\}\big)$ comme annoncé.

(b) On procède par induction transfinie sur $\alpha = \omega n_1 +
  n_0$.  On veut montrer que $\alpha = (\omega \boxdot n_1) \boxplus
  n_0$.  Or, d'après ce qu'on vient de voir, $(\omega\boxdot n_1)
  \boxplus n_0 = \sup^+ \big( \{(\omega\boxdot n'_1) \boxplus n_0' :
  n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \penalty0 \cup
  \penalty0 \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 < n_0\}\big)$.
  D'après l'hypothèse d'induction, et en utilisant le fait que les
  formes normales de Cantor des ordinaux se comparent
  lexicographiquement, ceci vaut encore $\sup^+ \big( \{\omega\, n'_1
  + n_0' : n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \penalty0
  \cup \penalty0 \{\omega\, n_1 + n_0' : n'_0 < n_0\}\big)$, qui est
  bien $\omega\, n_1 + n_0$ comme souhaité (il s'agit précisément du
  $\sup^+$ de l'ensemble des ordinaux $<\omega\, n_1 + n_0$).
\end{corrige}

\medskip

(4)(a) On admet maintenant l'affirmation (*) en toute généralité.  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)$.

\begin{corrige}
(a) Soient $\alpha = \omega^{\gamma_1} p_1 + \cdots +
  \omega^{\gamma_r} p_r$ et $\beta = \omega^{\gamma_1} q_1 + \cdots +
  \omega^{\gamma_r} q_r$ (quitte à insérer des $p_i$ et $q_i$ nuls
  dans la forme normale de Cantor) avec $\gamma_1 > \cdots >
  \gamma_r$.  En utilisant (*), on peut écrire $\alpha =
  (\omega^{\gamma_1} \boxdot p_1) \boxplus \cdots \boxplus
  (\omega^{\gamma_r} \boxdot p_r)$ et $\beta = (\omega^{\gamma_1}
  \boxdot q_1) \boxplus \cdots \boxplus (\omega^{\gamma_r} \boxdot
  q_r)$.  En utilisant la commutativité et l'associativité
  de $\boxdot$ et en regroupant les puissances égales de $\omega$, on
  obtient $\alpha \boxplus \beta = (\omega^{\gamma_1} \boxdot
  (p_1+q_1)) \boxplus \cdots \boxplus (\omega^{\gamma_r} \boxdot
  (p_r+q_r))$.  Et quitte à utiliser de nouveau (*), on trouve $\alpha
  \boxplus \beta = \omega^{\gamma_1} (p_1+q_1) + \cdots +
  \omega^{\gamma_r} (p_r+q_r)$.  On a ainsi montré que la somme
  naturelle se fait en ajoutant simplement terme à terme les formes
  normales de Cantor, i.e., on ajoute les chiffres (=coefficients) de
  chaque puissance de $\omega$.

(b) En particulier, $(\omega+1)\boxplus(\omega+1) = \omega\,2 + 2$
  (qui est aussi $(\omega\boxdot 2)\boxplus 2$ comme on l'a vu), alors
  que $(\omega+1) + (\omega+1) = \omega + (1+\omega) + 1 = \omega +
  \omega + 1 = \omega\,2 + 1$ est strictement plus petit.
\end{corrige}

\medskip

(La question qui suit ne fait pas appel aux questions (3) et (4).)

(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$.

\begin{corrige}
On procède par induction transfinie (sur
$\alpha\boxplus\beta\boxplus\rho$, si l'on veut) : on peut supposer la
conclusion déjà connue pour tous les $(\alpha',\beta,\rho)$,
$(\alpha,\beta',\rho)$ et $(\alpha,\beta,\rho')$ tels que dans la
question.

Si Blaise joue en premier : si $\rho < \alpha\boxplus\beta$, alors par
définition de $\alpha\boxplus\beta$, il existe un
$\alpha'\boxplus\beta$ avec $\alpha'<\alpha$ ou $\alpha\boxplus\beta'$
avec $\beta'<\beta$ qui majore $\rho$ (au sens large), et Blaise peut
faire le coup correspondant $(\alpha',\beta,\rho)$ ou
$(\alpha,\beta',\rho)$ auquel cas il aura une stratégie gagnante comme
second joueur par hypothèse d'induction ; si $\rho \geq
\alpha\boxplus\beta$, alors quel que soit le coup
$(\alpha',\beta,\rho)$ ou $(\alpha,\beta',\rho)$ fait par Blaise, on
aura $\rho > \alpha'\boxplus\beta$ ou $\rho > \alpha\boxplus\beta'$
donc Roxane aura une stratégie gagnante par hypothèse d'induction.

Si Roxane joue en premier : si $\rho > \alpha\boxplus\beta$, alors
elle peut jouer vers $(\alpha,\beta,\rho')$ avec $\rho' =
\alpha\boxplus\beta$, auquel cas elle comme second joueur aura une
stratégie gagnante par hypothèse d'induction.  Si $\rho \leq
\alpha\boxplus\beta$, alors quel que soit le coup qu'elle fait, elle
arrivera à un $(\alpha,\beta,\rho')$ avec $\rho' <
\alpha\boxplus\beta$ auquel cas Blaise a une stratégie gagnante par
hypothèse d'induction.
\end{corrige}

{\footnotesize Autrement dit, on a montré que l'addition des « nombres
  (surréels) » de Conway coïncide, dans le cas particulier des
  ordinaux, avec l'opération $\boxplus$ de somme naturelle.\par}


%
%
%

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

\begin{corrige}
Il s'agit d'un jeu en forme normale et à somme nulle.  Pour $n=5$, la
matrice des gains d'Alice vaut :

\begin{center}
\begin{tabular}{r|ccccc}
$\downarrow$Alice, Bob$\rightarrow$&${0}$&${1}$&${2}$&${3}$&${4}$\\\hline
${0}$&$0$&$-1$&$-1$&$-1$&$+1$\\
${1}$&$+1$&$0$&$-1$&$-1$&$-1$\\
${2}$&$+1$&$+1$&$0$&$-1$&$-1$\\
${3}$&$+1$&$+1$&$+1$&$0$&$-1$\\
${4}$&$-1$&$+1$&$+1$&$+1$&$0$\\
\end{tabular}
\end{center}

Pour des raisons de symétrie (la matrice étant antisymétrique,
c'est-à-dire que les deux joueurs sont dans la même situation
vis-à-vis du jeu), la valeur du gain vaut $0$.
\end{corrige}

(2) On considère la stratégie mixte consistant à jouer chacune des
options $0$, $n-2$ et $n-1$ avec probabilité $\frac{1}{3}$ (et jamais
les autres).  On l'appellera $s_0$.  Si Alice joue selon cette
stratégie $s_0$ et si Bob joue l'option $i$, quel est le gain espéré
d'Alice en fonction de $i$ ?

\begin{corrige}
Si Bob joue $0$, Alice obtient le gain espéré $\frac{1}{3}(0 + 1 - 1)
= 0$.  Si Bob joue une option entre $1$ et $n-3$ inclus, Alice obtient
le gain espéré $\frac{1}{3}(-1 + 1 + 1) = \frac{1}{3} > 0$.  Si Bob
joue $n-2$, Alice obtient le gain espéré $\frac{1}{3}(-1 + 0 + 1) =
0$.  Si Bob joue $n-1$, Alice obtient le gain espéré $\frac{1}{3}(+1 -
1 + 0) = 0$.
\end{corrige}

(3) Pourquoi $s_0$ est-elle une stratégie optimale ?

\begin{corrige}
Pour vérifier que $s_0$ est optimale, il s'agit de vérifier qu'elle
réalise au moins la valeur du jeu contre toute option (=stratégie
pure) de l'adversaire.  C'est ce qu'on vient de faire puisque la
valeur du jeu est $0$.
\end{corrige}

(4) Déduire de (2) 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$.)

\begin{corrige}
Si $t$ est une stratégie ayant une autre option que $0$, $n-2$
et $n-1$ dans son support, les espérances trouvées en (2) montrent que
son espérance de gain contre $s_0$ est strictement négative
(strictement positive pour le joueur qui applique $s_0$, donc
strictement négative pour celui qui applique $t$).  Donc $t$ ne peut
pas être optimale.
\end{corrige}

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

\begin{corrige}
On vient de voir que toute stratégie optimale $s$ a un support inclus
dans $\{0, n-2, n-1\}$.  Si on appelle $p_0, p_{-2}, p_{-1}$ les
probabilités respectives de ces options dans $s$, on sait que $s$ doit
avoir une espérance de gain nulle contre $s_0$, donc contre chacune
des options pures $0$, $n-2$ et $n-1$, ce qui donne $p_{-2} = p_{-1}$,
$p_{-1} = p_0$ et $p_0 = p_{-2}$, bref, la seule possibilité est $p_0
= p_{-2} = p_{-1} = \frac{1}{3}$.
\end{corrige}


%
%
%
\end{document}