path: root/controle-20240422.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[a4paper,margin=2.5cm]{geometry}
\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{\dur}{\operatorname{dur}}
\newcommand{\fuzzy}{\mathrel{\|}}
%
\newcommand{\dblunderline}[1]{\underline{\underline{#1}}}
%
\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{22 avril 2024}
\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

\ifcorrige
Ce corrigé comporte 6 pages (page de garde incluse).
\else
Cet énoncé comporte 3 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

\textbf{(1)} On considère le jeu en forme normale défini par la
matrice de gain suivante :
\begin{center}
\begin{tabular}{r|cc}
$\downarrow$Alice, Bob$\rightarrow$&$X$&$Y$\\\hline
$X$&$1$&$0$\\
$Y$&$0$&$2$\\
\end{tabular}
\end{center}
Un seul nombre a été inscrit dans chaque case car les gains des deux
joueurs sont \emph{égaux}, et c'est ce nombre-là qui est écrit
(attention, il ne s'agit pas d'un jeu à somme nulle, au contraire : au
lieu d'être opposés, les intérêts des deux joueurs sont parfaitement
identiques).

Étudier et déterminer tous les équilibres de Nash de ce jeu : on
commencera par considérer ceux en stratégies pures, puis par
considérer les cas où un joueur, ou l'autre, ou les deux, joue une
stratégie strictement mixte (i.e., ayant pour support $\{X,Y\}$).

\begin{corrige}
Si Alice joue (purement) $X$, les options de Bob apportent les gains
$1$ pour $X$ et $0$ pour $Y$, dont la seule meilleure réponse de Bob
est de jouer purement $X$.  De même, si Alice joue (purement) $Y$, les
options de Bob apportent les gains $0$ pour $X$ et $2$ pour $Y$, dont
la seule meilleure réponse de Bob est de jouer purement $Y$.  Le rôle
des deux joueurs étant symétrique, ceci prouve que, dans un équilibre
de Nash, si l'un joue purement une des deux options, l'autre doit
jouer la même, et ceci donne bien deux équilibres de Nash, $(X,X)$
(avec gain $1$) et $(Y,Y)$ (avec gain $2$).

Si Alice joue une stratégie strictement mixte dans un équilibre de
Nash, on vient de voir que Bob joue $pX + (1-p)Y$, l'espérance de gain
d'Alice doit être la même pour les deux options du support de sa
stratégie, c'est-à-dire que $p = 2(1-p)$, donc $p = \frac{2}{3}$.  Par
symétrie, Bob joue aussi cette stratégie, et on vérifie que ceci donne
bien un équilibre de Nash, $(\frac{2}{3}X + \frac{1}{3}Y, \;
\frac{2}{3}X + \frac{1}{3}Y)$.
\end{corrige}

\textbf{(2)} Plus généralement, on considère un jeu de la forme
suivante : les deux joueurs ont le même ensemble d'options, notons-le
$\{X_1,\ldots,X_N\}$, et ils ont le même gain $u_A(a,b) = u_B(a,b)$
pour $a,b\in \{X_1,\ldots,X_N\}$, et de plus ce gain vaut $0$ lorsque
$b\neq a$ et il vaut $g_i$ lorsque $a = b = X_i$, où tous les $g_i$
sont des réels strictement positifs ($g_i > 0$).  Pour résumer :
\begin{center}
\begin{tabular}{r|ccc}
$\downarrow$Alice, Bob$\rightarrow$&$X_1$&$\cdots$&$X_N$\\\hline
$X_1$&$g_1$&$\cdots$&$0$\\
$\vdots$&$\vdots$&$\ddots$&$\vdots$\\
$X_N$&$0$&$\cdots$&$g_N$\\
\end{tabular}
\end{center}

\textbf{(a)} Montrer que, dans un équilibre de Nash d'un jeu comme on
vient de le dire, si $I \subseteq \{X_1,\ldots,X_N\}$ est le
support\footnote{On rappelle que le support d'une stratégie mixte est
l'ensemble des options qu'elle choisit avec une probabilité $>0$.} de
la stratégie d'Alice, le support $J$ de la stratégie de Bob est inclus
dans $I$.  (\emph{Indication :} toute option hors de $I$ apporte un
gain espéré nul, donc strictement moins bon que n'importe quelle
combinaison convexe d'options dans $I$.)  En déduire par symétrie
que $I=J$.

\begin{corrige}
Si $X_j \not\in I$, alors l'option $X_j$ apporte un gain nul à Bob,
tandis que toute option $X_i \in I$ apporte un gain strictement
positif (puisque $g_i$ est pondéré avec un coefficient strictement
positif, tout le reste étant nul).  Il s'ensuit qu'une meilleure
réponse possible de Bob ne peut pas inclure $X_j$ : elle ne peut donc
inclure que des options dans $I$.  Donc $J \subseteq I$.  Et par
symétrie des deux joueurs, $I \subseteq J$.  Donc finalement $I = J$.
\end{corrige}

\textbf{(b)} Toujours en considérant un équilibre de Nash d'un tel
jeu, en notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie (mixte)
d'Alice, montrer que les $g_i p_i$ tels que $p_i > 0$ (c'est-à-dire
$X_i \in I$) sont tous égaux entre eux.  En déduire par symétrie le
résultat analogue pour la stratégie de Bob, donc qu'elles sont égales.
En déduire qu'il existe au plus $2^N - 1$ équilibres de Nash, un pour
chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$.

\begin{corrige}
En notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie d'Alice, pour
toute option $X_i \in J = I$ de Bob, le gain espéré de $X_i$ doit être
toujours le même.  Or ce gain est $g_i p_i$.  Donc tous les $g_i p_i$
pour $X_i \in I$ sont égaux.  C'est-à-dire que les $p_i$ sont
proportionnels aux $\frac{1}{g_i}$ pour $X_i \in I$ (les autres étant
nuls).  Ceci détermine la stratégie d'Alice, et par symétrie c'est
aussi celle de Bob.  On a donc trouvé $2^N - 1$ équilibres de Nash
potentiels : pour toute partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on
pose calcule $p_i$ comme le quotient de $\frac{1}{g_i}$ par la somme
des $\frac{1}{g_j}$ pour $X_j \in I$ si $X_i \in I$ (et $0$ sinon), et
Alice et Bob jouent chacun $p_1 X_1 + \cdots + p_N X_N$.
\end{corrige}

\textbf{(c)} Vérifier que les stratégies mixtes trouvées en (b) sont
bien des équilibres de Nash du jeu, et conclure qu'il a exactement
$2^N - 1$ équilibres de Nash, qu'on décrira explicitement.

\begin{corrige}
Pour chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on a bien
décrit une stratégie mixte pour chacun des deux joueurs (c'est la
même) : on a bien affaire à des réels $p_i$ positifs de somme $1$.  Le
gain espéré de $X_j$ contre $p_1 X_1 + \cdots + p_N X_N$ est $0$ si
$X_j \not\in I$ et $g_j p_j$ (qui ne dépend pas de $j$) si $X_j \in
I$ : on ne peut pas faire mieux (avec une stratégie pure, donc a
fortiori avec une stratégie mixte), donc cette stratégie est bien une
meilleure réponse possible contre elle-même, et on a bien affaire à un
équilibre de Nash.

Pour résumer : tous les équilibres de Nash sont décrits de la façon
suivante : pour une certaine partie non vide $I$ de
$\{X_1,\ldots,X_N\}$, on pose
\[
\left\{
\begin{array}{ll}
p_i = \frac{\textstyle 1/g_i}{\textstyle \sum_{X_j\in I}(1/g_j)}&\text{si $p_i\in I$}\\
p_i = 0&\text{sinon}
\end{array}
\right.
\]
et les deux joueurs jouent $p_1 X_1 + \cdots + p_N X_N$ : ceci est
bien un équilibre de Nash et tous sont de cette forme (et $I$ est bien
déterminé par l'équilibre puisque c'est le support commun des
stratégies des deux joueurs, donc tous les équilibres qu'on vient de
décrire sont distincts).  Il y en a donc exactement $2^N - 1$.
\end{corrige}


%
%
%

\exercice

On considère un jeu de la forme suivante.  Soit $A \subseteq
\mathbb{R}$ un ensemble de réels, soit $X \subseteq \mathbb{R}$ un
ensemble \emph{fini} de réels, et soit enfin $b>1$ un réel.  (Toutes
ces données sont fixées à l'avance et sont des paramètres définissant
le jeu.  Ils sont supposés connus des deux joueurs.)

Chaque joueur quand vient son tour choisit un élément $x_i \in X$ :
plus exactement, Alice choisit $x_0$, puis Bob choisit $x_1$, puis
Alice choisit $x_2$, et ainsi de suite.  Il n'y a aucune contrainte
sur le choix du $x_i$ et chacun a connaissance de tous les coups
antérieurs.

Au bout d'un nombre infini de tours, on considère le réel
\[
u = x_0 + \frac{x_1}{b} + \frac{x_2}{b^2} + \frac{x_3}{b^3} + \cdots
\]
c'est-à-dire la somme de la série
$\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$.  Cette série converge car elle
converge absolument\footnote{\label{footnote-series-converges}Preuve :
$\sum_{i=0}^{+\infty}\left|\frac{x_i}{b^i}\right| \leq
\sum_{i=0}^{+\infty}\frac{M}{b^i} = \frac{M}{1-b}$ où $M$ est un
majorant des $|x|$ pour $x\in X$, qui existe car $X$ est fini.}.  Si
$u\in A$ alors Alice a gagné ; sinon, Bob a gagné.

(Un cas particulier qu'on peut garder à l'esprit est celui où $X =
\{0,1\}$ et $b = 2$, auquel cas Alice et Bob construisent un nombre
binaire entre $0$ et $2$ en choisissant alternativement ses chiffres :
$u = x_0.x_1 x_2 x_3\cdots$ en binaire.)

On cherche à montrer que sous certaines conditions sur $A$, l'un des
joueurs a une stratégie gagnante.

\textbf{(1)} On considère l'application $\psi\colon X^{\mathbb{N}} \to
\mathbb{R}$ qui à une suite $\dblunderline{x} = (x_i)_{i\in\mathbb{N}}
\in X^{\mathbb{N}}$ associe $\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$.
Montrer que si $\psi(\dblunderline{x}) = u$ et $\varepsilon > 0$,
alors il existe $\ell \in \mathbb{N}$ tel que toute suite
$\dblunderline{y}$ commençant par $x_0,\ldots,x_{\ell-1}$ vérifie
$|\psi(\dblunderline{y})-u| < \varepsilon$.  Autrement dit, il existe
$\ell$ tel que l'image du $\ell$-ième voisinage
fondamental\footnote{Rappel : $V_\ell(\dblunderline{x})$ est
l'ensemble des suites commençant par les $\ell$ termes
$x_0,\ldots,x_{\ell-1}$.}  $V_\ell(\dblunderline{x})$ de
$\dblunderline{x}$ par $\psi$ soit incluse dans la boule ouverte
$B_\varepsilon(u) :=
\mathopen]u-\varepsilon,u+\varepsilon\mathclose[$.
    (\emph{Indication :} s'inspirer de la
    note \ref{footnote-series-converges}.)

\begin{corrige}
Si $\dblunderline{x}$ et $\dblunderline{y}$ coïncident sur les
termes $i<\ell$, alors $|\psi(\dblunderline{y})-u| =
|\psi(\dblunderline{y})-\dblunderline{x}| =
\left|\sum_{i=\ell}^{+\infty} \frac{x_i}{b^i}\right| \leq
\sum_{i=\ell}^{+\infty} \left|\frac{x_i}{b^i}\right| \leq
\sum_{i=\ell}^{+\infty} \frac{M}{b^i} = \frac{Mb^\ell}{1-b}$.  Cette
quantité tend vers $0$ quand $\ell\to+\infty$, donc il existe $\ell$
tel qu'elle soit $<\varepsilon$.  Ceci montre bien que si
$\dblunderline{y} \in V_\ell(\dblunderline{x})$ on a
$|\psi(\dblunderline{y})-u| < \varepsilon$.
\end{corrige}

\textbf{(2)} En déduire que si $U \subseteq \mathbb{R}$ est ouvert (au
sens de la topologie usuelle des réels\footnote{Rappel : $U \subseteq
\mathbb{R}$ est ouvert lorsque pour tout $u\in U$ il existe
$\varepsilon>0$ tel que $B_\varepsilon(u) \subseteq U$.}), alors
l'image réciproque $\psi^{-1}(U) \subseteq X^{\mathbb{N}}$ est ouverte
(au sens de la topologie produit de la topologie discrète sur
$X^{\mathbb{N}}$, qu'on a considérée en cours).

\begin{corrige}
Supposons que $U$ soit ouvert.  Si $\dblunderline{x} \in
\psi^{-1}(U)$, c'est-à-dire $\psi(\dblunderline{x}) =: u \in U$, comme
$U$ est ouvert, il existe $\varepsilon>0$ tel que $B_\varepsilon(u)
\subseteq U$, et d'après la question (1), il existe $\ell$ tel que
$\psi(V_\ell(\dblunderline{x})) \subseteq B_\varepsilon(u) \subseteq
U$, ce qui signifie $V_\ell(\dblunderline{x}) \subseteq \psi^{-1}(U)$.
On vient de montrer que tout $\dblunderline{x} \in \psi^{-1}(U)$ a un
voisinage fondamental $V_\ell(\dblunderline{x})$ inclus dans
$\psi^{-1}(U)$, c'est-à-dire que $\psi^{-1}(U)$ est ouvert.

(Note : on a évité dans ce corrigé d'utiliser le mot « continu » car
il n'a pas été défini en cours dans le contexte d'une application de
$X^{\mathbb{N}}$ vers $\mathbb{R}$.  Mais bien sûr, il est correct de
dire que $\psi$ est continue en tant qu'application entre espaces
topologiques.)
\end{corrige}

\textbf{(3)} En déduire que si $A$ est ouvert, ou bien fermé,
dans $\mathbb{R}$, alors l'un des deux joueurs possède une stratégie
gagnante au jeu qu'on a décrit.

\begin{corrige}
Le jeu qu'on a décrit est exactement le jeu de Gale-Stewart défini par
la partie $\psi^{-1}(A)$.  Si $A$ est ouvert, alors la question (2)
montre que $\psi^{-1}(A)$ est ouvert, donc le jeu est déterminé
d'après le théorème de détermination des jeux ouverts.  Si $A$ est
fermé, alors son complémentaire $\mathbb{R}\setminus A$ est ouvert,
donc la question (2) montre que $\psi^{-1}(\mathbb{R}\setminus A) =
X^{\mathbb{N}} \setminus \psi^{-1}(A)$ est ouvert, c'est-à-dire que
$\psi^{-1}(A)$ est fermé, donc le jeu est déterminé d'après le
théorème de détermination des jeux fermés.
\end{corrige}

\textbf{(4)} Montrer aussi ce résultat lorsque $A = \mathbb{Q}$
(autrement dit, Alice gagne si la somme $u$ de la série est
rationnelle\footnote{Merci d'avance de ne pas prétendre que
$\mathbb{Q}$ est ouvert, ni qu'il est fermé.}).  Plus généralement,
montrer ce résultat lorsque $A$ est borélien.

\begin{corrige}
L'ensemble $\mathbb{Q}$ est la réunion dénombrable des fermés $\{r\}$
pour $r\in\mathbb{Q}$ : il est donc borélien (dans $\mathbb{R}$) ;
l'image réciproque $\psi^{-1}(\mathbb{Q})$ est donc la réunion
dénombrable des fermés $\psi^{-1}(\{r\})$ : il est donc borélien (dans
$X^{\mathbb{N}}$).  D'après le théorème de détermination des jeux
boréliens, le jeu est déterminé.

Plus généralement, l'ensemble des $B$ tels que $\psi^{-1}(B)$ soit
borélien dans $X^{\mathbb{N}}$ est une tribu (puisque $\psi^{-1}$
préserve les réunions et intersections quelconques, ainsi que le
complémentaire) et elle contient les ouverts (puisqu'on a vu que
$\psi^{-1}(U)$ est ouvert pour $U$ ouvert).  Elle contient donc les
boréliens de $\mathbb{R}$.  C'est-à-dire que si $B$ est borélien
dans $\mathbb{R}$ alors $\psi^{-1}(B)$ est borélien dans
$X^{\mathbb{N}}$.  D'après le théorème de détermination des jeux
boréliens, le jeu est déterminé dès que $A$ est borélien.
\end{corrige}


%
%
%

\exercice

On va développer dans cet exercice un algorithme pour calculer la
somme et le produit d'ordinaux écrits en forme normale de Cantor
(itérée).

\textbf{(1)} On rappelle que $1 + \omega = \omega$.  En déduire que si
un ordinal $\alpha$ vérifie $\alpha \geq \omega$, alors on a $1 +
\alpha = \alpha$ (\emph{indication :} justifier qu'on peut écrire
$\alpha = \omega + \beta$).  En déduire que $1 + \omega^\gamma =
\omega^\gamma$ lorsque $\gamma > 0$, puis que $\omega^{\gamma_1} +
\omega^{\gamma_2} = \omega^{\gamma_2}$ lorsque $\gamma_1 < \gamma_2$,
et enfin que $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} n_2 =
\omega^{\gamma_2} n_2$ si $n_1,n_2$ sont deux entiers naturels non
nuls (et toujours avec $\gamma_1 < \gamma_2$).

\begin{corrige}
On a vu que lorsque $\alpha_0 \leq \alpha$, il existe un unique
$\beta$ tel que $\alpha = \alpha_0 + \beta$ : en particulier, si
$\alpha \geq \omega$, on peut écrire $\alpha = \omega + \beta$, et on
en déduit que $1 + \alpha = 1 + \omega + \beta = \omega + \beta =
\alpha$.

Or si $\gamma > 0$, c'est-à-dire $\gamma \geq 1$, on a $\omega^\gamma
\geq \omega$, et on vient de voir que ceci implique $1 + \omega^\gamma
= \omega^\gamma$.

Si $\gamma_1 < \gamma_2$, on peut écrire $\gamma_2 = \gamma_1 +
\gamma$ (cf. deux paragraphes plus haut), donc $\omega^{\gamma_1} +
\omega^{\gamma_2} = \omega^{\gamma_1} + \omega^{\gamma_1 + \gamma} =
\omega^{\gamma_1} + \omega^{\gamma_1} \, \omega^{\gamma} =
\omega^{\gamma_1} (1 + \omega^\gamma) = \omega^{\gamma_1} \,
\omega^\gamma = \omega^{\gamma_1+\gamma} = \omega^{\gamma_2}$.

Une fois acquis que $\omega^{\gamma_1} + \omega^{\gamma_2} =
\omega^{\gamma_2}$, on a $\omega^{\gamma_1} n_1 + \omega^{\gamma_2}
n_2 = \omega^{\gamma_1} + \cdots + \omega^{\gamma_1} +
\omega^{\gamma_2} + \cdots + \omega^{\gamma_2}$ (avec $n_1$ termes
$\omega^{\gamma_1}$ et $n_2$ termes $\omega^{\gamma_2}$), et en
utilisant de façon répétée l'égalité qu'on vient de dire, ceci vaut
$\omega^{\gamma_2} + \cdots + \omega^{\gamma_2} = \omega^{\gamma_2}
n_2$, comme annoncé.
\end{corrige}

\textbf{(2)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots +
\omega^{\gamma_1} n_1$ (avec $\gamma_s > \cdots > \gamma_1$ et
$n_1,\ldots,n_s$ des entiers naturels non nuls) et $\alpha' =
\omega^{\gamma'_{s'}} n'_{s'} + \cdots + \omega^{\gamma'_1} n'_1$
(idem) sont deux ordinaux écrits en forme normale de Cantor, en
utilisant les résultats de la question précédente, expliquer comment
calculer $\alpha + \alpha'$, en supposant qu'on sache
algorithmiquement comparer les $\gamma_i$ et les $\gamma'_j$.

\begin{corrige}
On écrit $\alpha + \alpha' = \omega^{\gamma_s} n_s + \cdots +
\omega^{\gamma_1} n_1 + \omega^{\gamma'_{s'}} n'_{s'} + \cdots +
\omega^{\gamma'_1} n'_1$ et, d'après ce qu'on vient de voir, dès que
deux termes ne sont pas dans le bon ordre (i.e., si un
$\omega^{\gamma_i} n_i$ précède $\omega^{\gamma_j} n_j$ avec $\gamma_i
< \gamma_j$), alors le premier disparaît purement et simplement ; et
bien sûr, si $\gamma_i = \gamma_j$, les termes fusionnent en
$\omega^{\gamma_i} (n_i+n_j)$ par distributivité à droite.  On se
retrouve donc avec l'écriture en forme normale de Cantor de $\alpha +
\alpha'$.
\end{corrige}

\textbf{(3)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot
3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha +
\alpha'$ et $\alpha' + \alpha$.

\begin{corrige}
Dans le sens $\alpha + \alpha'$, on a $(\omega^3\cdot 2 + \omega\cdot
3 + 5) + (\omega^2 + \omega\cdot 4) = \omega^3\cdot 2 + \omega^2 +
\omega\cdot 4$.

Dans le sens $\alpha' + \alpha$, on a $(\omega^2 + \omega\cdot 4) +
(\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^3\cdot 2 + \omega\cdot
3 + 5$.
\end{corrige}

\textbf{(4)} Déduire de la question (2) que si $\alpha =
\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ en forme
normale de Cantor et $k \geq 1$ est un entier naturel, alors
$\alpha\cdot k = \omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}}
n_{s-1} + \cdots + \omega^{\gamma_1} n_1$ (c'est-à-dire que seul le
coefficient $n_s$ de la plus haute puissance de $\omega$ est multiplié
par $k$ ; \emph{indication} : on a $\alpha\cdot k = \alpha + \cdots +
\alpha$ avec $k$ termes identiques).

\begin{corrige}
En écrivant $\alpha\cdot k = \alpha + \cdots + \alpha$ (qui résulte de
la distributivité à droite) et en appliquant les règles expliquées
en (2), on voit que tous les termes autres que le plus haut de tous
les termes autres que le dernier de la terme disparaissent purement et
simplement (ils sont absorbés par le terme le plus haut du $\alpha$
suivant), donc seul subsistent $k-1$ copies de $\omega^{\gamma_s} n_s$
plus le dernier $\alpha$, ce qui donne bien $\alpha\cdot k =
\omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} n_{s-1} + \cdots +
\omega^{\gamma_1} n_1$ comme annoncé.
\end{corrige}

\textbf{(5)} En déduire que, toujours pour $\alpha = \omega^{\gamma_s}
n_s + \cdots + \omega^{\gamma_1} n_1$, on a $\alpha\cdot\omega =
\omega^{\gamma_s+1}$ (\emph{indication} : on pourra calculer
$\lim_{k\to\omega} \alpha \cdot k$), et plus généralement $\alpha\cdot
\omega^{\gamma'} = \omega^{\gamma_s+\gamma'}$ si $\gamma'\geq 1$
(\emph{indication} : on pourra écrire $\gamma' = 1+\gamma''$).

\begin{corrige}
On cherche à calculer $\alpha\cdot\omega = \lim_{k\to\omega} \alpha \cdot
k$ (rappelons que cette limite est juste une borne supérieure).  Par
comparaison des formes normales de Cantor, $\omega^{\gamma_s+1}$ est
plus grand que tous les $\alpha\cdot k = \omega^{\gamma_s} n_sk +
\omega^{\gamma_{s-1}} n_{s-1} + \cdots + \omega^{\gamma_1} n_1$, donc
$\omega^{\gamma_s+1} \geq \lim_{k\to\omega} \alpha \cdot k$.  Mais
inversement, la forme normale de Cantor de tout ordinal
$<\omega^{\gamma_s+1}$ commence par un terme $\leq\omega^{\gamma_s}
N$, donc majoré par $\alpha\cdot k$ pour $k$ assez grand (certainement
pour $k\geq N$) : donc $\lim_{k\to\omega} \alpha \cdot k$ ne peut pas
être $<\omega^{\gamma_s+1}$.  Donc c'est exactement
$\omega^{\gamma_s+1}$, et on a prouvé $\alpha\cdot\omega =
\omega^{\gamma_s+1}$.

Plus généralement, si $\gamma'\geq 1$, on peut écrire $\gamma' =
1+\gamma''$ comme on l'a déjà rappelé plus haut, et
$\alpha\cdot\omega^{\gamma'} = \alpha\cdot\omega^{1+\gamma''} =
\alpha\cdot\omega\omega^{\gamma''} =
\omega^{\gamma_s+1}\omega^{\gamma''} = \omega^{\gamma_s+1+\gamma''} =
\omega^{\gamma_s+\gamma'}$.
\end{corrige}

\textbf{(6)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots +
\omega^{\gamma_1} n_1$ et $\alpha' = \omega^{\gamma'_{s'}} n'_{s'} +
\cdots + \omega^{\gamma'_1} n'_1$ sont deux ordinaux écrits en forme
normale de Cantor, en utilisant les résultats de la question
précédente, expliquer comment calculer $\alpha \cdot \alpha'$, en
supposant qu'on sache algorithmiquement comparer et ajouter les
$\gamma_i$ et les $\gamma'_j$.

\begin{corrige}
Par distributivité à droite et comme on sait déjà calculer des sommes,
on peut se ramener au cas où $\alpha'$ est un seul terme
$\omega^{\gamma'} n'$.  Par associativité, il suffit de savoir
calculer le produit par $\omega^{\gamma'}$ à droite, et par $n'$.  Le
produit par $\omega^{\gamma'}$ est trivial si $\gamma'=0$ et est réglé
par la question (5) si $\gamma'>0$.  Et le produit par $n'$ est réglé
par la question (4).

Un peu plus concrètement, pour chaque terme de $\alpha'$ pour lequel
$\gamma'_j > 0$, on a $\alpha\cdot \omega^{\gamma'_j} n'_j =
\omega^{\gamma_s + \gamma'_j} n_s n_j$, et le terme fini, s'il existe
(c'est-à-dire si $\gamma'_1 = 0$) vaut $\alpha\cdot n'_1 =
\omega^{\gamma_s} n_s n'_1 + \omega^{\gamma_{s-1}} n_{s-1} + \cdots +
\omega^{\gamma_1} n_1$.  Il n'y a plus qu'à ajouter tous ces termes
dans l'ordre (qui est déjà le bon, et qui donne déjà une forme normale
de Cantor, puisque $\gamma_s + \gamma'_s > \cdots + \gamma_s +
\gamma'_2 > \gamma_s > \cdots > \gamma_1$).
\end{corrige}

\textbf{(7)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot
3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha \cdot
\alpha'$ et $\alpha' \cdot \alpha$.

\begin{corrige}
Dans le sens $\alpha\alpha'$ on trouve $(\omega^3\cdot 2 + \omega\cdot
3 + 5) (\omega^2 + \omega\cdot 4) = \omega^5 + \omega^4\cdot 4$ (il
n'y a pas de terme fini à la fin de $\alpha'$ donc seul le premier
terme de $\alpha$ survit).

Dans le sens $\alpha'\alpha$ on trouve $(\omega^2 + \omega\cdot 4)
(\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^5\cdot 2 +
\omega^3\cdot 3 + \omega^2\cdot 5 + \omega\cdot 4$.
\end{corrige}



%
%
%
\end{document}