summaryrefslogtreecommitdiffstats
path: root/controle-20160421.tex
blob: 2951680edc75ebda6ebb0be48b0d706b89faaa3e (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
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
%% 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{xr-hyper}
%
\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}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\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\relax\else\egroup\fi\par}
%
%
%
\begin{document}
\ifcorrige
\title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des jeux}}
\else
\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théorie des jeux}}
\fi
\author{}
\date{21 avril 2016}
\maketitle

%% {\footnotesize
%% \immediate\write18{sh ./vc > vcline.tex}
%% \begin{center}
%% Git: \input{vcline.tex}
%% \end{center}
%% \immediate\write18{echo ' (stale)' >> vcline.tex}
%% \par}

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Les exercices sont indépendants sauf dans la mesure où le contraire
est précisé.  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 de l'énoncé ne doit pas décourager : les exercices ont été
formulés de manière à rappeler le contexte et certaines notions du
cours.

Il n'est pas nécessaire de faire des réponses longues.  Notamment, si
certaines réponses sont très semblables à des exercices déjà traités
en cours, on pourra donner une justification lapidaire, mais on
prendra bien soin de souligner tout ce qui diffère.

\medbreak

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

L'usage des calculatrices électroniques est interdit.

\medbreak

Durée : 3h

\medbreak

Barème indicatif : chaque question a approximativement la même valeur.
Il ne sera pas nécessaire de tout traiter pour avoir le maximum des
points.

\pagebreak


%
%
%

\exercice

Alice joue contre Bob un jeu dans lequel elle choisit une option parmi
deux possibles appelées U et V, et Bob choisit une option parmi deux
appelées X et Y (les modalités du choix varient selon les questions
ci-dessous) : les gains d'\emph{Alice} (c'est-à-dire, la fonction
qu'elle cherche à maximiser) sont donnés par le tableau ci-dessous, en
fonction de son choix (colonne de gauche) et de celui de Bob (ligne du
haut) :

\begin{center}
\begin{tabular}{r|ccc}
$\downarrow$A, B$\rightarrow$&X&Y\\\hline
U&$3$&$1$\\
V&$0$&$4$\\
\end{tabular}
\end{center}

\smallbreak

(1) On suppose que Bob fait son choix \emph{après} Alice, et en
connaissant le choix d'Alice, et qu'il cherche à minimiser le gain
d'Alice (i.e., le gain de Bob est l'opposé de celui d'Alice).  Comment
Alice a-t-elle intérêt à jouer et comment Bob répondra-t-il ?  Quelle
est le gain d'Alice dans ce cas ?

\begin{corrige}
Si Alice choisit U, Bob répondra par Y et le gain d'Alice sera $1$ ;
si Alice choisit V, Bob répondra par X et le gain d'Alice sera $0$.
Comme Alice veut maximiser son gain, elle a intérêt à choisir U, et
Bob répondra par Y, et le gain d'Alice sera $1$ dans ce cas.
\end{corrige}

\smallbreak

(2) On suppose maintenant que Bob fait son choix \emph{avant} Alice,
et qu'Alice connaîtra le choix de Bob ; on suppose toujours que Bob
cherche à minimiser le gain d'Alice.  Que fera Bob et comment Alice
répondra-t-elle ?  Quelle est le gain d'Alice dans ce cas ?

\begin{corrige}
Si Bob choisit X, Alice répondra par U et le gain d'Alice sera $3$ ;
si Bob choisit Y, Alice répondra par V et le gain d'Alice sera $4$.
Comme Bob veut minimiser le gain d'Alice, il a intérêt à choisir X, et
Alice répondra par U, et le gain d'Alice sera $3$ dans ce cas.
\end{corrige}

\smallbreak

(3) On suppose qu'Alice et Bob font leur choix séparément, sans
connaître le choix de l'autre, et toujours que Bob cherche à minimiser
le gain d'Alice.  Comment ont-ils intérêt à faire leurs choix ?  Quel
est le gain (espéré) d'Alice dans ce cas ?

\begin{corrige}
On a affaire à un jeu à somme nulle écrit en forme normale :
l'algorithme \ref{zero-sum-games-by-linear-programming-algorithm} nous
indique qu'on obtient la stratégie optimale d'Alice en résolvant le
problème de programmation linéaire suivant :
\[
\left\{
\begin{aligned}
\text{maximiser\ }v&\text{\ avec}\\
p_U \geq 0\;, \;\; p_V \geq 0&\\
p_U + p_V &= 1\\
v - 3p_U - 0p_V &\leq 0\;\;\text{(X)}\\
v - 1p_U - 4p_V &\leq 0\;\;\text{(Y)}\\
\end{aligned}
\right.
\]
On peut l'écrire sous forme normale en réécrivant $v = v_+ - v_-$ avec
$v_+,v_- \geq 0$, mais on gagne un petit peu en remarquant que $v$
sera forcément positif puisque tous les gains du tableau le sont, donc
on peut ajouter la contrainte $v \geq 0$.  Pour la même raison, on
peut transformer la contrainte d'égalité $p_U + p_V = 1$ en
l'inégalité $p_U + p_V \leq 1$.  Une application de l'algorithme du
simplexe donne finalement l'optimum $v = 2$ atteint pour $p_U =
\frac{2}{3}$ et $p_V = \frac{1}{3}$, avec pour le dual $q_X =
\frac{1}{2}$ et $q_Y = \frac{1}{2}$ (les inégalités (X) et (Y) sont
toutes les deux saturées).

Autrement dit, Alice joue les options U et V avec probabilités
$\frac{2}{3}$ et $\frac{1}{3}$, Bob réplique avec les options X et Y
de façon équiprobable, et le gain espéré d'Alice est $2$, qui est la
valeur du jeu à somme nulle en forme normale considéré ici.
\end{corrige}

\smallbreak

(4) On suppose maintenant que Bob cherche à \emph{maximiser} le gain
d'Alice (i.e., il n'est plus son adversaire comme dans les questions
(1), (2) et (3), mais son allié).  On cherche à déterminer quels sont
les équilibres de Nash possibles.  On notera $(p_U,p_V, q_X,q_Y)$ un
profil de stratégies mixtes général, où $p_U,p_V$ (positifs de
somme $1$) sont les poids des deux options d'Alice (=probabilités
qu'elle les joue), et $q_X,q_Y$ (positifs, également de somme $1$) les
poids des deux options de Bob.  On va discuter selon le support des
stratégies (i.e., selon les ensembles d'options qui ont un poids
strictement positif).\spaceout (a) Quels sont les équilibres de Nash
évidents en stratégies pures ?  Expliquer pourquoi ce sont bien les
seuls équilibres de Nash où l'un des deux joueurs a une stratégie
pure.\spaceout (b) Calculer ce que doivent valoir $p_U$ et $p_V$ dans
un équilibre de Nash où $q_X > 0$ et $q_Y > 0$ (i.e., les options X et
Y de Bob sont dans le support), et ce que doivent valoir $q_X$ et
$q_Y$ dans un équilibre de Nash où $p_U > 0$ et $p_V > 0$ (i.e., les
options U et V d'Alice sont dans le support).  Ces contraintes
donnent-elles effectivement un équilibre de Nash ?\spaceout
(c) Conclure quant à l'ensemble des équilibres de Nash du jeu
considéré.

\begin{corrige}
(a) Deux équilibres de Nash sont évidents : si Alice joue (purement) U
  et Bob joue (purement) X, aucun n'a intérêt à changer puisque $3$
  est maximum sur la ligne et sur la colonne ; si Alice joue
  (purement) V et Bob joue (purement) Y, aucun n'a intérêt à changer
  puisque $4$ est maximum sur la ligne et sur la colonne.  Les gains
  d'Alice (et de Bob) dans chacun de ces cas sont donc $3$ et $4$
  respectivement.

Il s'agit là de l'ensemble des équilibres de Nash où l'un des deux
joueurs a une stratégie pure : par exemple, si Alice joue purement U,
Bob ne peut que répondre par purement X puisque le gain $3$ est
strictement plus grand que tout autre gain sur la ligne (i.e., donner
un poids non nul à une autre option de Bob ne pourrait que diminuer le
gain).

(b) Si $q_X > 0$ et $q_Y > 0$, les stratégies pures X et Y de Bob
donnent forcément le même gain, car si l'une d'elle donnait un gain
strictement supérieure à l'autre, Bob aurait intérêt à augmenter le
poids $q$ correspondant et améliorerait ainsi strictement sa réponse.
Autrement dit, l'espérance de gain contre la stratégie pure X,
c'est-à-dire $3 p_U$, est égale à l'espérance de gain contre la
stratégie pure Y, soit $p_U + 4 p_V$.  On a donc $3 p_U = p_U + 4
p_V$, et comme aussi $p_U + p_V = 1$ on trouve $(p_U, p_V) =
(\frac{2}{3}, \frac{1}{3})$ en résolvant le système (soit la même
stratégie mixte que trouvée en (3), ce qui n'est pas un hasard vu que
le signe des gains de Bob n'est pas du tout intervenu dans le
raisonnement).  De même, si $p_U > 0$ et $p_V > 0$, on a $3 q_X + q_Y
= 4 q_Y$, et comme aussi $q_X + q_Y = 1$ on trouve $(q_X, q_Y) =
(\frac{1}{2}, \frac{1}{2})$ en résolvant le système (même remarque).

Bref, on a un équilibre de Nash \emph{potentiel} donné par $(p_U,p_V,
q_X,q_Y) = (\frac{2}{3}, \frac{1}{3}, \frac{1}{2}, \frac{1}{2})$,
c'est-à-dire exactement le même profil que dans la question (3) quand
les joueurs étaient adversaires.  Ceci peut surprendre, mais le fait
est qu'aucun des deux joueurs n'a (strictement) intérêt à changer
unilatéralement sa stratégie puisque les deux options qui se
présentent à lui sont indifférentes (elles ont le même gain espéré)
compte tenu du comportement de l'autre.  On a donc bien trouvé un
troisième équilibre de Nash.

(c) Pour résumer, on a trois équilibres de Nash récapitulés par le
tableau (triés par ordre de gain espéré décroissant) :
\begin{center}
\vskip-\baselineskip
\begin{tabular}{cc|cc|c}
$p_U$&$p_V$&$q_X$&$q_Y$&gain\\\hline
$0$&$1$&$0$&$1$&$4$\\
$1$&$0$&$1$&$0$&$3$\\
$\frac{2}{3}$&$\frac{1}{3}$&$\frac{1}{2}$&$\frac{1}{2}$&$2$\\
\end{tabular}
\end{center}
et on a prouvé que c'étaient bien les seuls.
\end{corrige}


%
%
%

\exercice\label{game-for-nim-product}

On considère le jeu suivant : une position du jeu consiste en un
certain nombre fini de jetons placés sur un damier possiblement
transfini dont les cases étiquetées par un couple $(\alpha,\beta)$
d'ordinaux (on dira que $\alpha$ est [le numéro de] la ligne de la
case et $\beta$ [le numéro de] la colonne).  Plusieurs jetons peuvent
se trouver sur la même case sans effet particulier (ils s'empilent).

Un coup du jeu consiste à faire l'opération suivante : le joueur qui
doit jouer choisit un jeton du jeu, disons sur la case
$(\alpha,\beta)$, et il choisit aussi arbitrairement $\alpha' <
\alpha$ (i.e., une ligne située plus haut) et $\beta' < \beta$ (i.e.,
une colonne située plus à gauche) : il retire alors le jeton choisi de
la case $(\alpha,\beta)$ et le remplace par \emph{trois} jetons, sur
les cases $(\alpha',\beta)$, $(\alpha,\beta')$ et $(\alpha',\beta')$.
(Par exemple, un coup valable consiste à remplacer un jeton sur la
case $(42,7)$ par trois sur les cases $(18,7)$, $(42,5)$ et $(18,5)$.)
Le nombre de jetons augmente donc de $2$ à chaque coup.

\begin{center}
\vskip-\baselineskip
\begin{tikzpicture}
\draw[step=.5cm,help lines] (0,-2) grid (3.5,0);
\begin{scope}[every node/.style={circle,fill,inner sep=1.2mm}]
\node at (1.25,-0.75) {};
\node at (1.25,-1.75) {};
\node at (2.75,-0.75) {};
\node[fill=gray] at (2.75,-1.75) {};
\end{scope}
\node[anchor=east] at (0,-0.75) {$\alpha'$};
\node[anchor=east] at (0,-1.75) {$\alpha$};
\node[anchor=south] at (1.25,-0.1) {$\beta'$};
\node[anchor=south] at (2.75,-0.1) {$\beta$};
\end{tikzpicture}
\\{\footnotesize (Le jeton en gris remplacé par les trois noirs.)}
\end{center}

On remarquera que les jetons sur la ligne ou la colonne $0$ ne peuvent
plus être retirés ou servir de quelque manière que ce soit : on pourra
dire que cette ligne et cette colonne $0$ sont la « défausse » des
jetons.  Le jeu se termine lorsque chacun des jetons est sur la ligne
ou la colonne $0$ (=dans la défausse), car il n'est alors plus
possible de jouer.  Les joueurs (Alice et Bob) jouent à tour de rôle
et le premier qui ne peut plus jouer a perdu.

\smallbreak

(0) Décrire brièvement le jeu complètement équivalent dans lequel il
n'y a pas de ligne ou de colonne $0$ (on fait démarrer la numérotation
à $1$), c'est-à-dire pas de défausse (les jetons disparaissent plutôt
qu'être défaussés) : quels sont les types de coups possibles à ce
jeu ?  (Distinguer selon que $\alpha'=0$ ou non, et selon que
$\beta'=0$ ou non.)  On se permettra dans la suite d'utiliser
librement l'une ou l'autre variante du jeu.

\begin{corrige}
Les jetons défaussés ne jouant aucun rôle dans le jeu, on peut les
ignorer et obtenir un jeu équivalent.  Les lignes et les colonnes sont
alors numérotés par des ordinaux non nuls, c'est-à-dire $\geq 1$.  Les
quatre types de coups possibles dans ce jeu, selon que $\alpha'$ et/ou
$\beta'$ vaut $0$, sont alors :
\begin{itemize}
\item simplement retirer un jeton de la case $(\alpha,\beta)$ [cas où
  $\alpha' = 0$ et $\beta' = 0$],
\item déplacer un jeton de la case $(\alpha,\beta)$ vers une case
  $(\alpha,\beta')$ plus à gauche (i.e., $\beta' < \beta$) dans la
  ligne [cas où $\alpha' = 0$ et $\beta' \neq 0$],
\item déplacer un jeton de la case $(\alpha,\beta)$ vers une case
  $(\alpha',\beta)$ plus haut (i.e., $\alpha' < \alpha$) dans la
  colonne [cas où $\alpha' \neq 0$ et $\beta' = 0$],
\item remplacer un jeton de la case $(\alpha,\beta)$ par un jeton sur
  une case $(\alpha,\beta')$ plus à gauche dans la ligne, un autre sur
  une case $(\alpha',\beta)$ plus haut dans la colonne, et un
  troisième sur la case $(\alpha',\beta')$ à l'intersection de la
  nouvelle ligne et de la nouvelle colonne, comme dans le jeu
  d'origine [cas où $\alpha' \neq 0$ et $\beta' \neq 0$].
\end{itemize}
\vskip-\baselineskip\vskip-\baselineskip
\end{corrige}

\smallbreak

(1) (a) Montrer qu'il existe une fonction $h(\alpha,\beta)$ de deux
ordinaux $\alpha,\beta$ et à valeurs ordinales qui soit strictement
croissante en chaque variable (c'est-à-dire que si $\alpha' < \alpha$
alors $h(\alpha',\beta) < h(\alpha,\beta)$ et que si $\beta' < \beta$
alors $h(\alpha,\beta') < h(\alpha,\beta)$).  Pour cela, on pourra,
comme on préfère, poser $h(\alpha,\beta) = \omega^{\max(\alpha,\beta)}
+ \omega^{\min(\alpha,\beta)}$ ou bien $h(\alpha,\beta) =
\alpha\boxplus\beta$ où $\alpha\boxplus\beta$ désigne l'ordinal dont
les chiffres de la forme normale de Cantor sont la somme des chiffres
correspondants de $\alpha$ et de $\beta$.\spaceout (b) En déduire que
le jeu considéré dans cet exercice termine toujours en temps fini.
(On pourra par exemple considérer la somme des $\omega^\gamma$ où
$\gamma$ parcourt, dans l'ordre décroissant, les valeurs
$h(\alpha,\beta)$ pour les cases $(\alpha,\beta)$ où il y a un jeton.)

\begin{corrige}
(a) Si on pose $h(\alpha,\beta) = \omega^{\max(\alpha,\beta)} +
  \omega^{\min(\alpha,\beta)}$ et si $\alpha' < \alpha$, alors soit
  $\max(\alpha',\beta) < \max(\alpha,\beta)$ soit $\max(\alpha',\beta)
  = \max(\alpha,\beta)$ et alors $\min(\alpha',\beta) <
  \min(\alpha,\beta)$ : dans les deux cas, $h(\alpha',\beta) <
  h(\alpha,\beta)$ par comparaison des formes normales de Cantor.
  Comme la fonction $h$ est symétrique en ses deux arguments, on a
  aussi $h(\alpha,\beta') < h(\alpha,\beta)$ si $\beta' < \beta$.

Si on préfère poser $h(\alpha,\beta) = \alpha\boxplus\beta$, et si
$\alpha' < \alpha$, le chiffre correspondant à la plus haute puissance
de $\omega$ qui diffère est strictement plus petit dans la forme
normale de Cantor de $\alpha'$ que celui de $\alpha$, et cette
affirmation est encore vraie lorsqu'on ajoute chiffre à chiffre la
forme normale de Cantor de $\beta$, donc on a bien $h(\alpha',\beta) <
h(\alpha,\beta)$.  Comme la fonction $h$ est symétrique en ses deux
arguments, on a aussi $h(\alpha,\beta') < h(\alpha,\beta)$ si $\beta'
< \beta$.

{\footnotesize
(\emph{Remarque :} En fait, la fonction $\boxplus$, aussi appelée
« somme naturelle » sur les ordinaux, est plus adaptée dans ce
contexte, parce qu'on peut se convaincre que $\alpha \boxplus \beta =
\sup^+ \big( \{\alpha'\boxplus\beta : \alpha' < \alpha\} \cup\,
\{\alpha\boxplus\beta' : \beta' < \beta\}\big)$, c'est-à-dire qu'elle
est justement la plus petite fonction strictement croissante en chacun
de ses arguments.  On comparera cette définition avec $\alpha \oplus
\beta = \mex \big( \{\alpha'\oplus\beta : \alpha' < \alpha\} \cup\,
\{\alpha\oplus\beta' : \beta' < \beta\}\big)$.  En revanche,
l'addition usuelle ne convient pas, parce que $\alpha'+\beta$ peut
être égal à $\alpha+\beta$ même si $\alpha'<\alpha$, par exemple
$1+\omega = 0+\omega$.)
\par}

(b) À une position du jeu ayant $s$ jetons sur les
cases $(\alpha_i,\beta_i)$ (pour $i=1,\ldots,s$) on peut associer
l'ordinal $\omega^{\gamma_1} + \cdots + \omega^{\gamma_s}$ où les
$\gamma_i := h(\alpha_i,\beta_i)$ ont été triés de façon à avoir
$\gamma_1 \geq \cdots \geq \gamma_s$ (donc, quitte à regrouper les
mêmes puissances, à avoir une forme normale de Cantor).  Un coup
consiste à remplacer un terme $\omega^{\gamma_i}$ par une somme de
$\omega^{\gamma'}$ pour des $\gamma' < \gamma_i$ vu que
$h(\alpha',\beta) < h(\alpha,\beta)$ et $h(\alpha,\beta') <
h(\alpha,\beta)$ et \textit{a fortiori} $h(\alpha',\beta') <
h(\alpha,\beta)$ si $\alpha'<\alpha$ et $\beta'<\beta$.  Ceci fait
donc décroître strictement l'ordinal en question, et en particulier,
la partie doit terminer en temps fini.
\end{corrige}

(2) Dans le cas particulier où il n'y a qu'une ligne de jetons
(numérotée $1$ ; ou bien deux lignes numérotées $0$ et $1$ si on garde
la défausse), expliquer pourquoi le jeu est simplement une
reformulation du jeu de nim.

\begin{corrige}
Un coup joué sur un jeton de la ligne $1$ consiste simplement soit à
le retirer soit à le déplacer vers une colonne plus à gauche ; on peut
identifier la position ayant $n_i$ jetons sur la case $(1,\alpha_i)$ à
un partie de nim ayant $n_i$ lignes avec $\alpha_i$ allumettes : le
coup consistant à déplacer un jeton de la case $\alpha_i$ vers la case
$\alpha_i' < \alpha_i$ peut se voir comme un coup de nim consistant à
diminuer le nombre d'allumettes de la ligne qui en a $\alpha_i$ pour
qu'il en reste $\alpha'_i$ ; et le fait de retirer un jeton sur la
case $(1,\alpha_i)$ comme le coup de nim consistant à retirer toutes
les allumettes de la ligne correspondante.  Les jeux sont donc
complètement équivalents.
\end{corrige}

\smallbreak

(3) Montrer que la valeur de Grundy d'un état quelconque du jeu vaut
\[
\bigoplus_{i=1}^s (\alpha_i\otimes\beta_i)
\]
où $(\alpha_1,\beta_1),\ldots,(\alpha_s,\beta_s)$ sont les cases où se
trouvent les $s$ jetons (répétées en cas de jetons multiples), où
$\oplus$ désigne la somme de nim, et où l'opération $\otimes$ sur les
ordinaux est définie inductivement par
\[
\alpha\otimes\beta := \mex\Big\{(\alpha'\otimes\beta)
\oplus (\alpha\otimes\beta') \oplus (\alpha'\otimes\beta')
: \alpha'<\alpha,\text{~et~}\beta'<\beta\Big\}
\tag{*}
\]

\begin{corrige}
Il n'y a aucune interaction entre les jetons dans le jeu.  En
particulier, jouer à une somme de nim de deux positions du jeu
considéré dans cet exercice revient au même que de jouer à la position
ayant la réunion de ces deux ensembles de jetons.  Si on note
$u_{\alpha,\beta}$ la position du jeu ayant un unique jeton sur la
case $(\alpha,\beta)$, on déduit de \ref{summary-of-grundy-theory} que
la valeur de Grundy d'un état quelconque du jeu vaut
$\bigoplus_{i=1}^s \gr(u_{\alpha_i,\beta_i})$.  Or
$\gr(u_{\alpha,\beta})$ est le plus petit ordinal qui n'est pas de la
forme $\gr(z)$ pour $z$ une position voisine sortante
de $u_{\alpha,\beta}$, et d'après ce qu'on vient de dire, on obtient
exactement $\gr(u_{\alpha,\beta}) = \mex\big\{\gr(u_{\alpha',\beta})
\oplus \gr(u_{\alpha,\beta'}) \oplus \gr(u_{\alpha',\beta'}) :
\alpha'<\alpha, \beta'<\beta\big\}$, c'est-à-dire bien
$\gr(u_{\alpha,\beta}) = \alpha\otimes\beta$ (même définition
inductive), et on a montré ce qui était demandé.
\end{corrige}

\smallbreak

(4) Calculer la valeur de $\alpha\otimes\beta$ pour $0\leq\alpha\leq
5$ et $0\leq\beta\leq 5$.  Pour accélérer les calculs ou bien pour les
confirmer, on pourra utiliser les résultats de
l'exercice \ref{inductions-on-nim-product} (il n'est pas nécessaire
d'avoir traité l'exercice en question).  On ne demande pas de
détailler les calculs, mais on recommande de les vérifier
soigneusement.

\begin{corrige}
En procédant inductivement, on trouve :
{\[
\begin{array}{c|cccccccccccccc}
\otimes&0&1&2&3&4&5\\\hline
0&0&0&0&0&0&0\\
1&0&1&2&3&4&5\\
2&0&2&3&1&8&10\\
3&0&3&1&2&12&15\\
4&0&4&8&12&6&2\\
5&0&5&10&15&2&7\\
\end{array}
\]}
(pour simplifier les calculs, on peut notamment utiliser la
commutativité, et le fait que $\alpha\otimes 3 = \alpha\otimes(2\oplus
1) = (\alpha\otimes 2) \oplus \alpha$ et de même $\alpha\otimes 5 =
\alpha\otimes(4\oplus 1) = (\alpha\otimes 4) \oplus \alpha$ ; si on
n'a pas l'habitude de calculer des sommes de nim, le mieux est sans
doute de tout écrire en binaire, quitte à reconvertir ensuite).
\end{corrige}

\smallbreak

(5) Si vous deviez jouer dans la position suivante (les lignes et
colonnes sont numérotées à partir de $1$, autrement dit la défausse
n'est pas figurée), quel coup feriez-vous ?

\begin{center}
\vskip-\baselineskip
\begin{tikzpicture}
\draw[step=.5cm,help lines] (0,-2.5) grid (2.5,0);
\begin{scope}[every node/.style={circle,fill,inner sep=1.2mm}]
\node at (0.25,-0.25) {};
\node at (0.75,-0.75) {};
\node at (1.25,-1.25) {};
\node at (1.75,-1.75) {};
\node at (2.25,-2.25) {};
\end{scope}
\node[anchor=east] at (0,-0.25) {$1$};
\node[anchor=east] at (0,-0.75) {$2$};
\node[anchor=east] at (0,-1.25) {$3$};
\node[anchor=east] at (0,-1.75) {$4$};
\node[anchor=east] at (0,-2.25) {$5$};
\node[anchor=south] at (0.25,0) {$1$};
\node[anchor=south] at (0.75,0) {$2$};
\node[anchor=south] at (1.25,0) {$3$};
\node[anchor=south] at (1.75,0) {$4$};
\node[anchor=south] at (2.25,0) {$5$};
\end{tikzpicture}
\end{center}

\begin{corrige}
La valeur de Grundy est $(1\otimes 1) \oplus (2\otimes 2) \oplus
(3\otimes 3) \oplus (4\otimes 4) \oplus (5\otimes 5) = 1 \oplus 3
\oplus 2 \oplus 6 \oplus 7 = 1$, et on veut l'annuler.  Plusieurs
coups sont possibles pour y arriver, par exemple : retirer le jeton en
$(1,1)$ (c'est-à-dire jouer $(\alpha,\beta,\alpha',\beta') =
(1,1,0,0)$) ; ou bien, remonter le jeton $(3,3)$ en $(1,3)$
(c'est-à-dire jouer $(\alpha,\beta,\alpha',\beta') = (3,3,1,0)$) ; ou
encore, remplacer le jeton $(5,5)$ par trois jetons en $(4,5)$,
$(5,4)$ et $(4,4)$ (c'est-à-dire jouer $(\alpha,\beta,\alpha',\beta')
= (5,5,4,4)$).
\end{corrige}


%
%
%

\exercice\label{inductions-on-nim-product}

On définit inductivement une opération $\alpha\otimes\beta$
(\emph{produit de nim}) de deux ordinaux $\alpha,\beta$ par
$\alpha\otimes\beta := \mex\{(\alpha'\otimes\beta) \oplus
(\alpha\otimes\beta') \oplus (\alpha'\otimes\beta') : \alpha'<\alpha,
\beta'<\beta\}$ (autrement dit, par la formule (*) de
l'exercice \ref{game-for-nim-product} ; il n'est pas nécessaire
d'avoir traité l'exercice en question, même s'il est permis de s'en
servir).  La notation $\oplus$ désigne la somme de nim.  On rappelle
par ailleurs que $\gamma = \mex S$ signifie que $\gamma\not\in S$ et
que tout ordinal $\gamma'<\gamma$ appartient à $S$.

(1) Montrer que $\otimes$ est commutative, c'est-à-dire que
$\beta\otimes\alpha = \alpha\otimes\beta$ quels que soient les
ordinaux $\alpha,\beta$.

\begin{corrige}
Par induction sur $\alpha$ et $\beta$, on prouve $\beta\otimes\alpha =
\alpha\otimes\beta$ en supposant que la même formule est vraie si l'un
de $\alpha$ ou $\beta$ est remplacé par un ordinal strictement plus
petit.  Or $\beta\otimes\alpha = \mex \{(\beta\otimes\alpha') \oplus
(\beta'\otimes\alpha) \oplus (\beta'\otimes\alpha') : \alpha'<\alpha,
\beta'<\beta\}$ (en utilisant la commutativité de $\oplus$), et par
hypothèse d'induction ceci vaut $\mex
\{(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
(\alpha'\otimes\beta') : \alpha'<\alpha, \beta'<\beta\} =
\alpha\otimes\beta$.

Si on préfère, on peut aussi utiliser le jeu défini dans
l'exercice \ref{game-for-nim-product}, en remarquant qu'échanger les
coordonnées des cases de tous les jetons ne change rien au jeu (i.e.,
les règles sont symétriques ligne/colonne) donc ne change pas la
fonction de Grundy.
\end{corrige}

\smallbreak

(2) Montrer que $0$ est absorbant pour $\otimes$,
c'est-à-dire $\alpha\otimes 0 = 0$ pour tout ordinal $\alpha$.
Montrer que $1$ est neutre pour $\otimes$, soit $\alpha\otimes 1 =
\alpha$ pour tout ordinal $\alpha$.

\begin{corrige}
On a $\alpha \otimes 0 = \mex \varnothing = 0$ (puisqu'il n'existe pas
de $\beta'<0$).  Pour la seconde affirmation, par induction sur
$\alpha$, on prouve $\alpha \otimes 1 = \alpha$ : en effet, $\alpha
\otimes 1 = \mex \{(\alpha'\otimes 1) \oplus (\alpha\otimes 0) \oplus
(\alpha'\otimes 0): \alpha'<\alpha\}$, et en utilisant le fait que $0$
est aborbant pour $\otimes$ et neutre pour $\oplus$ et l'hypothèse
d'induction, ceci vaut $\mex \{\alpha': \alpha'<\alpha\} = \alpha$.

Si on préfère, on peut aussi utiliser le jeu défini dans
l'exercice \ref{game-for-nim-product}, en remarquant qu'un jeton sur
la ligne ou colonne $0$ est mort (défaussé), et que jouer sur la ligne
ou colonne $1$ revient à jouer au jeu de nim d'après la question (2)
de l'exercice \ref{game-for-nim-product}.
\end{corrige}

\smallbreak

(3) (a) Montrer que si $\alpha'\neq\alpha$ et $\beta'\neq\beta$, alors
$(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
(\alpha'\otimes\beta') \neq \alpha\otimes\beta$.\spaceout (b) En
déduire que si $\alpha\otimes\beta = \alpha\otimes\beta'$ alors
$\alpha=0$ ou bien $\beta=\beta'$.

\begin{corrige}
(a) Grâce aux propriétés de la somme de nim ($\gamma \neq \gamma'$
  équivaut à $\gamma\oplus\gamma' \neq 0$), la condition qu'on veut
  montrer est équivalente à : $(\alpha\otimes\beta) \oplus
  (\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
  (\alpha'\otimes\beta') \neq 0$.  Sous cette forme, on voit qu'il y a
  symétrie entre $\alpha'$ et $\alpha$ et entre $\beta'$ et $\beta$ :
  on peut donc supposer $\alpha'<\alpha$ et $\beta'<\beta$, auquel cas
  la propriété est claire par la définition même de $\otimes$ comme
  un $\mex$.

(b) C'est le cas particulier du (a) lorsque $\alpha'=0$.
\end{corrige}

\smallbreak

(4) Montrer que $\otimes$ est distributive sur $\oplus$, c'est-à-dire
$\alpha \otimes (\beta\oplus\gamma) = (\alpha\otimes\beta) \oplus
(\alpha\otimes\gamma)$.  Pour cela, on pourra procéder par induction
et remarquer que pour montrer $\lambda = \mu$ il suffit de montrer que
(a) $\xi<\lambda$ implique $\xi\neq\mu$ et que (b) $\xi<\mu$ implique
$\xi\neq\lambda$.  (Et on rappelle que si $\xi < \mex S$ alors $\xi\in
S$.)

\begin{corrige}
Pour montrer $\lambda = \mu$ il suffit de montrer que
(a) $\xi<\lambda$ implique $\xi\neq\mu$ et que (b) $\xi<\mu$ implique
$\xi\neq\lambda$ : en effet, la contraposée de (a) est que
$\mu\geq\lambda$, et la contraposée de (b) est que $\lambda\geq\mu$.

Procédons par induction pour prouver $\alpha \otimes
(\beta\oplus\gamma) = (\alpha\otimes\beta) \oplus
(\alpha\otimes\gamma)$ : on peut supposer cette égalité connue si au
moins l'un des ordinaux $\alpha,\beta,\gamma$ est remplacé par un
strictement plus petit.

(a) Si $\xi < \alpha \otimes (\beta\oplus\gamma)$, alors on peut
écrire $\xi = (\alpha'\otimes(\beta\oplus\gamma)) \oplus
(\alpha\otimes\delta') \oplus (\alpha'\otimes\delta')$ où
$\alpha'<\alpha$ et $\delta' < \beta\oplus\gamma$.  La définition
inductive de $\oplus$ permet alors d'écrire soit $\delta' =
\beta'\oplus\gamma$ où $\beta'<\beta$, soit $\delta' =
\beta\oplus\gamma'$ où $\gamma'<\gamma$ : par symétrie, plaçons nous
sans perte de généralité dans le premier cas.  On a alors $\xi =
(\alpha'\otimes (\beta\oplus\gamma)) \oplus (\alpha\otimes
(\beta'\oplus\gamma)) \oplus (\alpha'\otimes (\beta'\oplus\gamma))$.
Par hypothèse d'induction, on peut développer les trois termes, et
quitte à simplifier les deux termes $\alpha'\otimes\gamma$ qui
apparaissent, on obtient $\xi = (\alpha'\otimes\beta) \oplus
(\alpha\otimes\beta') \oplus (\alpha'\otimes\beta') \oplus
(\alpha\otimes\gamma)$.  Puisque la somme $(\alpha'\otimes\beta)
\oplus (\alpha\otimes\beta') \oplus (\alpha'\otimes\beta')$ des trois
premiers termes est différente de $\alpha\otimes\beta$
(d'après (3)(a)), on en déduit que $\xi \neq (\alpha\otimes\beta)
\oplus (\alpha\otimes\gamma)$, ce qu'on voulait.

(b) Maintenant, si $\xi < (\alpha\otimes\beta) \oplus
(\alpha\otimes\gamma)$, on a soit $\xi = \delta' \oplus
(\alpha\otimes\gamma)$ avec $\delta' < \alpha\otimes\beta$, soit $\xi
= (\alpha\otimes\beta) \oplus \varepsilon'$ avec $\varepsilon' <
\alpha\otimes\gamma$ : par symétrie, plaçons nous sans perte de
généralité dans le premier cas.  On peut alors écrire $\delta' =
(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
(\alpha'\otimes\beta')$ avec $\alpha'<\alpha$ et $\beta'<\beta$, donc
on a : $\xi = (\alpha'\otimes\beta) \oplus (\alpha\otimes\beta')
\oplus (\alpha'\otimes\beta') \oplus (\alpha\otimes\gamma)$.  Quitte à
faire apparaître deux termes $\alpha'\otimes\gamma$ qui s'annulent,
l'hypothèse d'induction permet de réécrire $\xi = (\alpha'\otimes
(\beta\oplus\gamma)) \oplus (\alpha\otimes (\beta'\oplus\gamma))
\oplus (\alpha'\otimes (\beta'\oplus\gamma))$.  Or $\beta'\oplus\gamma
\neq \beta\oplus\gamma$ : en utilisant (3)(a), on a $\xi \neq \alpha
\otimes (\beta\oplus\gamma)$, ce qu'on voulait.
\end{corrige}

\smallbreak

On \emph{admet} que $\otimes$ est associative, c'est-à-dire
$(\alpha\otimes\beta) \otimes \gamma = \alpha \otimes
(\beta\otimes\gamma)$ (ce n'est pas très difficile à prouver).

(5) On va enfin montrer que pour tout $\alpha > 0$ il existe un
$\alpha^*$ tel que $\alpha\otimes\alpha^* = 1$, c'est-à-dire, un
\emph{inverse} pour le produit de nim.  Pour cela, on suppose par
l'absurde le contraire, et on considère $\alpha$ le \emph{plus petit}
ordinal non nul qui n'a pas d'inverse, et on va arriver à une
contradiction.  Pour cela, appelons $\delta_0 = \sup^+ \big(\{\alpha\}
\cup \{\beta^* : \beta<\alpha\} \big)$ (où $\beta^*$ désigne l'inverse
de $\beta$, qu'on a supposé exister vu que $\beta<\alpha$) le plus
petit ordinal strictement supérieur à $\alpha$ et aux inverses des
ordinaux $<\alpha$, et par récurrence sur l'entier naturel $n$,
posons $\delta_{n+1} = \sup^+ \big(\{\beta_1 \oplus \beta_2 :
\beta_1,\beta_2<\delta_n\} \cup \{\beta_1 \otimes \beta_2 :
\beta_1,\beta_2<\delta_n\}\big)$ le
plus petit ordinal strictement supérieur à la somme ou au produit de
nim de deux ordinaux strictement plus petits que $\delta_n$ (on a bien
sûr $\delta_{n+1} \geq \delta_n$).  Soit enfin $\delta =
\lim_{n\to\omega} \delta_n = \sup\{\delta_n :
n\in\mathbb{N}\}$.\spaceout (a) Expliquer pourquoi si $\beta_1,\beta_2
< \delta$ alors $\beta_1\oplus\beta_2 < \delta$ et
$\beta_1\otimes\beta_2 < \delta$.\spaceout (b) Montrer que si $0 <
\alpha' < \alpha$ alors nécessairement $\alpha' \otimes \delta \geq
\delta$ (dans le cas contraire, considérer le produit de nim de $\alpha'
\otimes \delta$ par $(\alpha')^*$ et utiliser (a)).\spaceout (c) En
déduire que si $0 < \alpha' < \alpha$ et $\delta' < \delta$, alors
$(\alpha'\otimes\delta) \oplus (\alpha\otimes\delta') \oplus
(\alpha'\otimes\delta')$ est $\geq \delta$ (dans le cas contraire,
montrer que le premier terme serait $<\delta$).  En particulier, il
est $\neq 1$.\spaceout (d) Expliquer pourquoi si $\alpha' = 0$ alors
$(\alpha'\otimes\delta) \oplus (\alpha\otimes\delta') \oplus
(\alpha'\otimes\delta')$ est encore une fois $\neq 1$.\spaceout (e) En
déduire que $\alpha\otimes\delta = 1$ et conclure.

\begin{corrige}
(a) Si $\beta < \delta$, comme $\delta$ est la borne supérieure
  des $\delta_n$, il existe $n$ tel que $\beta < \delta_n$.  Ainsi, si
  $\beta_1,\beta_2 < \delta$, il existe $n$ tel que $\beta_1,\beta_2 <
  \delta_n$ (en prenant le maximum des deux $n$ obtenus), donc
  $\beta_1\oplus\beta_2 < \delta_{n+1}$ et $\beta_1\otimes\beta_2 <
  \delta_{n+1}$ d'après la définition de $\delta_{n+1}$, ce qui donne
  bien $\beta_1\oplus\beta_2 < \delta$ et $\beta_1\otimes\beta_2 <
  \delta$.

(b) Si $0 < \alpha' < \alpha$ et si $\alpha' \otimes \delta < \delta$,
  alors comme $(\alpha')^* < \delta_0 \leq \delta$, on a
  $(\alpha')^*\otimes (\alpha' \otimes \delta) < \delta$ d'après (a).
  Or $(\alpha')^* \otimes (\alpha' \otimes \delta) = \delta$ par
  associativité et par le fait que $(\alpha')^*$ est l'inverse
  de $\alpha'$ : contradiction.

(c) Si $0 < \alpha' < \alpha$ et $\delta' < \delta$, montrons que
  $\gamma := (\alpha'\otimes\delta) \oplus (\alpha\otimes\delta')
  \oplus (\alpha'\otimes\delta')$ est $\geq\delta$.  Dans le cas
  contraire, $\alpha'\otimes\delta$ serait la somme de nim
  de $\gamma$, qui est $<\delta$ par hypothèse, de
  $\alpha\otimes\delta'$ qui est $<\delta$ par (a), et de
  $\alpha'\otimes\delta'$ qui l'est aussi ; de nouveau par (a), on
  aurait $\alpha'\otimes\delta < \delta$, ce qui contredit (b).

(d) Si $\alpha'=0$ alors $(\alpha'\otimes\delta) \oplus
  (\alpha\otimes\delta') \oplus (\alpha'\otimes\delta') =
  \alpha\otimes\delta' \neq 1$ puisqu'on a supposé que $\alpha$
  n'avait pas d'inverse.

(e) Par définition, $\alpha\otimes\delta$ est le plus petit ordinal
  qui n'est pas de la forme $(\alpha'\otimes\delta) \oplus
  (\alpha\otimes\delta') \oplus (\alpha'\otimes\delta')$ pour
  $\alpha'<\alpha$ et $\delta'<\delta$.  Or
  on a montré en (c) et (d) que cette expression n'est jamais $1$, et
  en revanche elle peut être $0$ (pour $\alpha'=\delta'=0$).  Le plus
  petit ordinal qui n'est pas de cette forme est donc $1$ : mais on a
  alors prouvé $\alpha\otimes\delta = 1$, ce qui contredit l'hypothèse
  que $\alpha$ n'ait pas d'inverse.
\end{corrige}

\smallbreak

{\footnotesize
\emph{Remarque :} On a donc vu que les ordinaux, pour les opérations
$\oplus$ et $\otimes$, i.e., les « nimbres », forment donc un
\emph{corps} commutatif, corps dit de « caractéristique $2$ »
car $1\oplus 1 = 0$.  Un raisonnement assez semblable à celui fait
en (5) permettrait de montrer, en outre, que ce corps est
« algébriquement clos », c'est-à-dire que tout polynôme non constant y
a une racine.  Les entiers naturels strictement inférieurs
à $2^{2^r}$, quant à eux, forment le corps fini ayant ce nombre
d'éléments.)
\par}



%
%
%
\end{document}