1 files changed, 576 insertions, 0 deletions

diff --git a/controle-20240422.tex b/controle-20240422.tex
new file mode 100644
index 0000000..8bab6a4
--- /dev/null
+++ b/controle-20240422.tex
@@ -0,0 +1,576 @@
+%% 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}