path: root/controle-20210412.tex

%% 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{12 avril 2021}
\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.

\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} : chaque question numérotée aura
approximativement la même valeur (environ $1$ à $1.5$ points).

\ifcorrige
Ce corrigé comporte \textcolor{red}{nnn} pages (page de garde incluse).
\else
Cet énoncé comporte 5 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 considère le jeu en forme normale, à deux joueurs, à somme nulle,
dont la matrice de gains est la suivante, où $x$ est un réel (la table
donne les gains d'Alice, qui choisit la ligne, ceux de Bob, qui
choisit la colonne, sont opposés) :

\begin{center}
\begin{tabular}{r|rrrr}
$\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline
$\mathrm{P}$&$0$&$1$&$-1$&$x$\\
$\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\
$\mathrm{R}$&$1$&$-2$&$0$&$-1$\\
$\mathrm{S}$&$-x$&$1$&$1$&$0$\\
\end{tabular}
\end{center}

On rappelle qu'une \emph{stratégie optimale} est une stratégie mixte
qui réalise un gain espéré au moins égal à la valeur du jeu contre
toute stratégie (pure donc mixte) de l'adversaire.

(0) Quelle est la valeur du jeu dans ce cas ?

\begin{corrige}
On a affaire à un jeu à somme nulle \emph{symétrique} (c'est-à-dire
que sa matrice de gains est antisymétrique), donc la valeur du jeu est
nulle.
\end{corrige}

(1) À quelle condition sur $x$ la stratégie $\frac{1}{2}\mathrm{P} +
\frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$ (consistant à choisir P
avec probabilité $\frac{1}{2}$, et chacun de Q et R avec
probabilité $\frac{1}{4}$) est-elle optimale ?

\begin{corrige}
Ajoutons à la matrice des gains du jeu une ligne correspondant à la
stratégie considérée :
\begin{center}
\begin{tabular}{r|rrrr}
$\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline
$\mathrm{P}$&$0$&$1$&$-1$&$x$\\
$\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\
$\mathrm{R}$&$1$&$-2$&$0$&$-1$\\
$\mathrm{S}$&$-x$&$1$&$1$&$0$\\\hline
\hbox{\vrule height12pt depth5pt width0pt}$\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$&
$0$&$0$&$0$&$\frac{x-1}{2}$\\
\end{tabular}
\end{center}
Pour qu'elle réalise un gain au moins égal à la valeur du jeu,
c'est-à-dire $\geq 0$, contre toute stratégie (pure donc mixte) de
l'adversaire, il faut et il suffit donc que $\frac{x-1}{2} \geq 0$,
c'est-à-dire $x\geq 1$.
\end{corrige}

(2) À quelle condition sur $x$ l'expression $\frac{1}{x+2}\,\mathrm{P} +
\frac{x}{x+2}\,\mathrm{R} + \frac{1}{x+2}\,\mathrm{S}$ (consistant à
choisir R avec probabilité $\frac{x}{x+2}$, et chacun de P et S avec
probabilité $\frac{1}{x+2}$) définit-elle une stratégie optimale ?

\begin{corrige}
L'expression $\frac{1}{x+2}\,\mathrm{P} + \frac{x}{x+2}\,\mathrm{R} +
\frac{1}{x+2}\,\mathrm{S}$ définit une stratégie mixte lorsque ses
coefficients sont positifs de somme $1$ : le fait qu'ils soient de
somme $1$ est toujours vrai, et ils sont tous positifs lorsque $x\geq
0$.

Ajoutons à la matrice des gains du jeu une ligne correspondant à la
stratégie en question :
\begin{center}
\begin{tabular}{r|rrrr}
$\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline
$\mathrm{P}$&$0$&$1$&$-1$&$x$\\
$\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\
$\mathrm{R}$&$1$&$-2$&$0$&$-1$\\
$\mathrm{S}$&$-x$&$1$&$1$&$0$\\\hline
\hbox{\vrule height12pt depth5pt width0pt}$\frac{1}{x+2}\,\mathrm{P} +
\frac{x}{x+2}\,\mathrm{R} + \frac{1}{x+2}\,\mathrm{S}$&
$0$&$\frac{2(1-x)}{x+2}$&$0$&$0$\\
\end{tabular}
\end{center}
Pour qu'elle réalise un gain au moins égal à la valeur du jeu,
c'est-à-dire $\geq 0$, contre toute stratégie (pure donc mixte) de
l'adversaire, il faut et il suffit donc que $\frac{2(1-x)}{x+2} \geq
0$, c'est-à-dire $x\leq 1$, donc finalement $0\leq x\leq 1$.
\end{corrige}

(3) Donner une stratégie optimale lorsque $x\leq 0$.

\begin{corrige}
Lorsque $x\leq 0$, la stratégie pure $\mathrm{S}$ est optimale
puisqu'elle réalise un gain $\geq 0$ contre toute stratégie (pure donc
mixte) de l'adversaire.
\end{corrige}

(4) Dans chacun des cas $x=0$ et $x=1$, exhiber une infinité de
stratégies optimales distinctes.

\begin{corrige}
Lorsque $x = 0$, on a trouvé deux stratégies optimales, à savoir
$\frac{1}{2}\mathrm{P} + \frac{1}{2}\mathrm{S}$ (trouvée en (2)) et
$\mathrm{S}$ (trouvée en (3)).  Toute combinaison convexe de ces deux
stratégies optimales est donc encore optimale, c'est-à-dire
$\frac{t}{2}\,\mathrm{P} + \frac{2-t}{2}\,\mathrm{S}$
pour $t\in[0;1]$.

Lorsque $x = 1$, on a trouvé deux stratégies optimales, à savoir
$\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} +
\frac{1}{4}\mathrm{R}$ (trouvée en (1)) et $\frac{1}{3}\mathrm{P} +
\frac{1}{3}\mathrm{R} + \frac{1}{3}\mathrm{S}$ (trouvée en (2)).
Toute combinaison convexe de ces deux stratégies optimales est donc
encore optimale, c'est-à-dire $\frac{2+t}{6}\,\mathrm{P} +
\frac{t}{4}\,\mathrm{Q} + \frac{4-t}{12}\,\mathrm{R} +
\frac{1-t}{3}\,\mathrm{S}$ pour $t\in[0;1]$.
\end{corrige}

(5) En supposant que $x$ ne soit pas un réel fixé mais \emph{tiré au
  hasard} selon une loi uniforme entre $0$ et $1$ une fois que les
joueurs ont joué (autrement dit, si un joueur choisit P et l'autre S,
le joueur qui a choisi P reçoit un gain aléatoire uniforme entre
$0$ et $1$ ; cet aléa est, évidemment, indépendant de tous ceux que
les joueurs auraient pu utiliser dans la détermination de leur propre
stratégie !), quelle stratégie adopteriez-vous dans ce jeu ?

\begin{corrige}
On cherche à maximiser le gain \emph{espéré} minimal contre toute
stratégie de l'adversaire ; mais comme $x$ est indépendant des choix
qu'ont pu faire les joueurs, on peut le remplacer par son espérance,
c'est-à-dire que le jeu considéré revient à prendre $x = \frac{1}{2}$.
D'après la question (2), une stratégie optimale est donnée par
$\frac{2}{5}\mathrm{P} + \frac{1}{5}\mathrm{R} +
\frac{2}{5}\,\mathrm{S}$.
\end{corrige}


%
%
%

\exercice

Dans cet exercice, on va d'abord définir les ordinaux
$\varepsilon_\iota$, puis on va s'intéresser à ceux qui
sont $<\varepsilon_1$.  Les parties de cet exercice sont indépendantes
à l'exception de ce qui est explicitement rappelé.

\medskip

\underline{Première partie.}

\nobreak
On définit une fonction $\varphi$ des ordinaux vers les ordinaux par
$\varphi(\alpha) = \omega^\alpha$.  On rappelle que $\varphi$ est
\emph{strictement croissante} (c'est-à-dire que si $\alpha < \beta$
alors $\varphi(\alpha) < \varphi(\beta)$).

(1) Rappeler pourquoi $\varphi$ est \emph{continue}, ce qui signifie
par définition la chose suivante : si $\delta$ est un ordinal limite,
alors $\lim_{\xi\to\delta} \varphi(\xi) = \varphi(\delta)$, où
$\lim_{\xi\to\delta} \varphi(\xi)$ est une notation pour
$\sup\{\varphi(\xi) : \xi < \delta\}$.

\begin{corrige}
La continuité de la fonction $\varphi\colon \alpha \mapsto
\omega^\alpha$ fait partie de la définition inductive de
l'exponentiation ordinale ($\omega ^ \delta = \lim_{\xi\to\delta}
\omega^\xi$ si $\delta$ est limite).
\end{corrige}

Pour éviter de partir dans des fausses directions, il est conseillé,
jusqu'à la question (5) incluse, d'oublier la définition de $\varphi$
et de retenir simplement que $\varphi$ est strictement croissante et
continue.

(2) Rappeler pourquoi $\varphi(\alpha) \geq \alpha$ pour
tout $\alpha$.

\begin{corrige}
On a vu en cours que si $\varphi$ est une fonction strictement
croissante d'un ensemble bien-ordonné vers lui-même, alors $\varphi(x)
\geq x$ pour tout $x$ : il suffit d'appliquer ce résultat à la
fonction $\varphi$.  (Pour être tout à fait exact, on veut plutôt
appliquer la \emph{démonstration} de ce résultat, vu que le résultat
ne s'applique pas tel quel faute d'un ensemble bien-ordonné auquel
l'appliquer vu que les ordinaux ne constituent pas un ensemble ; mais
la démonstration s'applique exactement sans changement : on montre $x
\leq \varphi(x)$ par induction, en effet, si par l'absurde on avait
$\varphi(x) < x$, alors l'hypothèse d'induction appliquée à $y :=
\varphi(x)$ donnerait $\varphi(x) \leq \varphi(\varphi(x))$, tandis
que la stricte croissance de $\varphi$ appliquée à $\varphi(x) < x$
donnerait $\varphi(\varphi(x)) < \varphi(x)$, ce qui est une
contradiction.)
\end{corrige}

On dira qu'un ordinal $\gamma$ est un \emph{point fixe} de $\varphi$
lorsque $\varphi(\gamma) = \gamma$.

(3) Soit dans cette question $\alpha$ un ordinal quelconque :
considérons la suite $(\gamma_n)$ (indicée par les entiers
naturels $n$) définie par $\gamma_0 = \alpha$ et $\gamma_{n+1} =
\varphi(\gamma_n)$.  Montrer que $(\gamma_n)$ est croissante
(c'est-à-dire que $m\leq n$ implique $\gamma_m \leq \gamma_n$).
Montrer que sa limite $\gamma_\omega := \lim_{n\to\omega} \gamma_n :=
\sup\{\gamma_n : n \in \mathbb{N}\}$ est un point fixe de $\varphi$.
Montrer qu'il s'agit du plus petit point fixe de $\varphi$ qui
soit $\geq\alpha$ (c'est-à-dire que si $\delta$ est un point fixe
de $\varphi$ et $\delta\geq\alpha$ alors $\delta\geq\gamma_\omega$ :
on pourra pour cela montrer que $\delta\geq\gamma_n$ pour tout $n$).

\begin{corrige}
On vient de voir que $\varphi(\alpha)\geq\alpha$ pour tout $\alpha$,
ce qui montre $\gamma_{n+1}\geq\gamma_n$, donc la suite $(\gamma_n)$
est croissante.  (Si on veut vraiment faire la démonstration jusqu'au
bout : montrons que $m\leq n$ implique $\gamma_m \leq \gamma_n$ par
récurrence sur $n\geq m$ : pour $n=m$ c'est évident, et si on a
$\gamma_m \leq \gamma_n$, alors $\gamma_m \leq \gamma_n \leq
\varphi(\gamma_n) = \gamma_{n+1}$ ce qui conclut la récurrence.)
\end{corrige}

La question (3) implique notamment : \emph{pour tout ordinal $\alpha$
  il existe un point fixe de $\varphi$ qui soit $\geq\alpha$}.

On définit maintenant $\varepsilon_\iota$ pour tout ordinal $\iota$
par :
\begin{itemize}
\item $\varepsilon_0$ est le plus petit point fixe de $\varphi$
  (c'est-à-dire, si on veut, le plus petit point fixe qui soit $\geq
  0$) ;
\item pour $\iota+1$ ordinal successeur, $\varepsilon_{\iota+1}$ est
  le plus petit point fixe de $\varphi$ qui soit $>\varepsilon_\iota$
  (c'est-à-dire, si on veut, le plus petit point fixe qui soit $\geq
  (\varepsilon_\iota)+1$),
\item pour $\delta$ ordinal limite, $\varepsilon_\delta$ est
  $\lim_{\xi\to\delta} \varepsilon_\xi$ (c'est-à-dire
  $\sup\{\varepsilon_\xi : \xi < \delta\}$).
\end{itemize}

(4) Montrer que $\iota \mapsto \varepsilon_\iota$ est strictement
croissante.  Montrer que $\varepsilon_\delta$ est un point fixe
de $\varphi$ aussi pour $\delta$ limite (c'est vrai pour les autres
cas par la définition) : pour cela, on expliquera pourquoi
$\varphi(\lim_{\xi\to\delta} \varepsilon_\xi) = \lim_{\xi\to\delta}
\varphi(\varepsilon_\xi)$.

\begin{corrige}
Remarquons tout d'abord que $\varepsilon_{\iota+1}$ est le plus petit
point fixe de $\varphi$ qui soit strictement supérieur à
$\varepsilon_\iota$, et notamment $\varepsilon_{\iota+1} >
\varepsilon_\iota$, quel que soit $\iota$.

Il est sans doute plus agréable, ensuite, de montrer que $\iota
\mapsto \varepsilon_\iota$ est croissante à partir du fait que
$\varepsilon_{\iota+1} \geq \varepsilon_\iota$ et de la continuité aux
ordinaux limites (on peut légitimement tenir ce fait pour évident vu
qu'il est sous-entendu par l'énoncé de la question en ce qu'elle
définit $\lim_{\xi\to\delta} \varepsilon_\xi$ comme
$\sup\{\varepsilon_\xi : \xi < \delta\}$).  Pour cela, on montre par
induction transfinie sur $\beta$ que $\alpha \leq \beta$ implique
$\varepsilon_\alpha \leq \varepsilon_\beta$.  Or si $\alpha = \beta$
il n'y a rien à prouver, donc supposons $\alpha < \beta$.  Si $\beta$
est successeur, disons $\beta = \gamma+1$, alors $\alpha < \beta$,
signifie $\alpha \leq \gamma$, auquel cas l'hypothèse d'induction
(comme $\gamma<\beta$) donne $\varepsilon_\alpha \leq
\varepsilon_\gamma$ et d'après la remarque qu'on a faite,
$\varepsilon_\alpha \leq \varepsilon_\gamma \leq
\varepsilon_{\gamma+1} = \varepsilon_\beta$ comme on voulait.  Enfin,
si $\beta$ est limite, alors $\varepsilon_\beta$ est défini comme la
borne supérieure des $\varepsilon_\xi$ pour $\xi<\beta$, mais en
particulier $\varepsilon_\alpha$ est dans cet ensemble dont on a pris
la borne supérieure, donc $\varepsilon_\alpha \leq \varepsilon_\beta$.

Ensuite, pour passer de croissant à strictement croissant, il suffit
de dire que $\alpha < \beta$ équivaut à $\alpha+1 \leq \beta$, la
croissance donne $\varepsilon_{\alpha+1} \leq \varepsilon_\beta$, et
on a déjà remarqué $\varepsilon_\alpha < \varepsilon_{\alpha+1}$, d'où
$\varepsilon_\alpha < \varepsilon_\beta$.

Montrons enfin que $\varepsilon_\delta$ est point fixe de $\varphi$
pour $\delta$ limite.  Le point crucial est qu'on a
$\varphi(\lim_{\xi\to\delta} \varepsilon_\xi) = \lim_{\xi\to\delta}
\varphi(\varepsilon_\xi)$ par continuité de $\varphi$ (pour etre tout
à fait complet dans la démonstration de cette affirmation :
$\varepsilon_\delta$ est par définition le plus petit ordinal
supérieur ou égal à tous les $\varepsilon_\xi$ pour $\xi<\delta$, donc
tout ordinal $\zeta<\varepsilon_\delta$ est majoré par un
$\varepsilon_\xi$ pour un certain $\xi<\delta$, et par croissance de
$\varphi$ on a alors $\varphi(\zeta)$ majoré par
$\varphi(\varepsilon_\xi)$, donc la borne supérieure des
$\varphi(\varepsilon_\xi)$ pour $\xi<\delta$ est aussi la borne
supérieure des $\varphi(\zeta)$ pour $\zeta<\varepsilon_\delta$ : or
cette dernière borne supérieure est $\varphi(\varepsilon_\delta)$ par
continuité de $\varphi$, ce qui montre $\varphi(\varepsilon_\delta) =
\lim_{\xi\to\delta} \varphi(\varepsilon_\xi)$).  On montre alors
$\varphi(\varepsilon_\iota) = \varepsilon_\iota$ par induction
sur $\xi$ : le cas successeur étant contenu dans la définiton même
de $\varepsilon$, il n'y a qu'à traiter le cas limite, et on a alors
$\varphi(\varepsilon_\delta) = \varphi(\lim_{\xi\to\delta}
\varepsilon_\xi) = \lim_{\xi\to\delta} \varphi(\varepsilon_\xi) =
\lim_{\xi\to\delta} \varepsilon_\xi = \varepsilon_\delta$.
\end{corrige}

(5) Montrer que tout ordinal $\gamma$ qui est un point fixe de
$\varphi$ est de la forme $\varepsilon_\alpha$ pour un certain
ordinal $\alpha$ (on pourra montrer qu'il existe $\alpha$ tel que
$\varepsilon_\alpha\geq\gamma$ puis considérer le plus petit
tel $\alpha$).

\begin{corrige}
Pour la même raison qu'en (2), on a $\varepsilon_\alpha \geq \alpha$
pour tout $\alpha$.  Donné un point fixe $\gamma$ de $\varphi$, on
sait donc qu'il existe $\alpha$ tel que $\varepsilon_\alpha \geq
\gamma$ (on vient de voir que $\alpha=\gamma$ convient).  Considérons
le plus petit tel $\alpha$ : ceci a un sens car les ordinaux sont
bien-ordonnés.  On veut montrer qu'on a $\varepsilon_\alpha = \gamma$.
Si $\alpha$ est successeur, disons $\alpha = \beta+1$, alors
$\varepsilon_\beta < \gamma$ par minimalité de $\alpha$, mais comme
$\gamma$ est un point fixe de $\varphi$ et que $\varepsilon_{\beta+1}$
est le plus petit point fixe après $\varepsilon_\beta$, on doit avoir
$\varepsilon_{\beta+1} \leq \gamma$, soit $\varepsilon_\alpha \leq
\gamma$, et on a bien prouvé $\varepsilon_\alpha = \gamma$.  Si
$\alpha$ est limite, en revanche, par minimalité de $\alpha$, on a
$\varepsilon_\xi < \gamma$ pour tout $\xi<\alpha$; or
$\varepsilon_\alpha$ a été défini comme la borne supérieure de
ces $\varepsilon_\xi$, donc on a $\varepsilon_\alpha \leq \gamma$, et
on a bien prouvé $\varepsilon_\alpha = \gamma$.
\end{corrige}

\medskip

\underline{Deuxième partie.}

\nobreak
On appelle $\varepsilon_0$ le plus petit ordinal tel que $\varepsilon
= \omega^\varepsilon$, et $\varepsilon_1$ le suivant, c'est-à-dire le
plus petit ordinal $>\varepsilon_0$ vérifiant cette même équation
$\varepsilon = \omega^\varepsilon$ (l'existence de ces ordinaux
résulte de la première partie de cet exercice).

On a vu en cours que les ordinaux $<\varepsilon_0$ possèdent une
représentation unique sous forme normale de Cantor itérée, et que
celle-ci permet de les comparer, de les ajouter et de les multiplier.
On va se pencher ici sur \emph{deux} systèmes différents d'écriture
des ordinaux $<\varepsilon_1$, qu'on appellera « écriture 1 » et
« écriture 2 ».

(6) Soit $\alpha < \varepsilon_1$ un ordinal différent
de $\varepsilon_0$ : montrer que dans sa forme normale de Cantor
$\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$, tous les
exposants $\gamma_i$ sont $<\alpha$ (on pourra utiliser le fait,
démontré en (2), que $\omega^\gamma \geq \gamma$ pour tout
ordinal $\gamma$).

\begin{corrige}
Notons pour commencer que $\omega^{\gamma_i} \leq \alpha$ (ceci
résulte de la comparaison entre les formes normales de Cantor).  Si on
avait $\gamma_i \geq \alpha$ alors on aurait $\alpha \geq
\omega^{\gamma_i} \geq \gamma_i \geq \alpha$ : donc en fait toutes ces
inégalités sont des égalités et $\alpha = \gamma_i =
\omega^{\gamma_i}$ est un point fixe de la fonction $\gamma \mapsto
\omega^\gamma$, ce qui, pour $\alpha < \varepsilon_1$, n'est possible
que lorsque $\alpha = \varepsilon_0$, or on a supposé le contraire.
C'est donc bien que $\gamma_i < \alpha$.
\end{corrige}

On appellera \emph{écriture 1} d'un ordinal $\alpha < \varepsilon_1$
l'écriture qui est \underline{ou bien} $\varepsilon_0$ (considéré
comme un symbole spécial), \underline{ou bien} une forme normale de
Cantor $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ où les
exposants $\gamma_s > \cdots > \gamma_1$ sont tous $<\alpha$ et
eux-mêmes écrits en écriture 1 (ceci a bien un sens par (6)).

À titre d'exemple, $\omega^\omega\,2$ ou $\varepsilon_0$ ou bien
$\omega^{\varepsilon_0} + 1$ ou encore
$\omega^{\omega^{\varepsilon_0}+1}\,2$ sont des écritures 1.  En
revanche, $\omega^{\varepsilon_0}$ n'en est pas une (elle ne vérifie
pas la contrainte sur les exposants), ni $\varepsilon_0 + 1$ (ce n'est
ni le symbole spécial $\varepsilon_0$ ni une forme normale de Cantor),
ni $(\varepsilon_0)^2$.

(7) Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$
possède bien une écriture 1 unique.  Il est facile de voir que cette
écriture 1 permet algorithmiquement de manipuler les ordinaux
$<\varepsilon_1$ : c'est-à-dire de les comparer, de les ajouter et de
les multiplier (on ne demande pas de le justifier, les algorithmes
étant essentiellement les mêmes que vus en cours pour les ordinaux
$<\varepsilon_0$) : il faut simplement bien se rappeler dans les
calculs intermédiaires le fait que $\varepsilon_0 =
\omega^{\varepsilon_0}$.  Notamment calculer $\varepsilon_0\cdot 2$ et
$\varepsilon_0\cdot \omega$ en écriture 1.  Expliquer comment calculer
$(\varepsilon_0)^\alpha$ en écriture 1 lorsque $\alpha$ est lui-même
donné en écriture 1.  Notamment, écrire $(\varepsilon_0)^{\omega 2}$
en écriture 1.

\begin{corrige}
L'existence et l'unicité de l'écriture 1 résulte du (6) : donné un
ordinal $<\varepsilon_1$, soit il est égal à $\varepsilon_0$, auquel
cas il a une écriture 1 par définition (et celle-ci est bien unique
car on n'autorise pas de forme normale de Cantor comme
$\omega^{\varepsilon_0}$), soit on l'écrit sous forme normale de
Cantor avec des exposants strictement plus petits que lui, cette
représentation est unique, et on peut recommencer le procédé, ce qui
termine au bout d'un nombre fini d'étapes puisqu'on a affaire à des
ordinaux qui décroissent strictement.  (Ou, si on préfère, on montre
par induction transfinie sur $\alpha < \varepsilon_1$ que $\alpha$
possède une écriture 1 unique par le raisonnement qu'on vient de
dire.)

Calculons $\varepsilon_0\cdot 2$ en écriture 1 : il suffit de réécrire
$\varepsilon_0$ comme $\omega^{\varepsilon_0}$, et alors
$\omega^{\varepsilon_0}\cdot 2$ est une écriture 1 légitime (c'est
bien une forme normale de Cantor dont les exposants sont tous écrits
en écriture 1 et plus petit que l'ordinal donné).  De même, calculons
$\varepsilon_0\cdot \omega$ : pour cela, on écrit $\varepsilon_0\cdot
\omega = \omega^\varepsilon_0\cdot \omega = \omega^{\varepsilon_0+1} =
\omega^{\omega^{\varepsilon_0}+1}$, ce qui est une écriture 1
légitime.

Pour calculer $(\varepsilon_0)^\alpha$, on l'écrit comme
$(\omega^{\varepsilon_0})^\alpha = \omega^{\varepsilon_0\,\alpha}$, or
on vient de dire qu'on peut calculer algorithmiquement l'écriture 1 de
$\varepsilon_0\,\alpha$ en fonction de celle de $\alpha$ : en la
remplaçant dans l'exposant, on obtient alors une écriture 1 de
$\omega^{\varepsilon_0\,\alpha}$ (sauf pour $\alpha=1$ auquel cas on
laisse $\varepsilon_0$ comme résultat).

Calculons $(\varepsilon_0)^{\omega 2}$ en écriture 1 : on vient de
voir qu'il vaut $\omega^{\varepsilon_0\,\omega 2}$, or
$\varepsilon_0\,\omega 2 = \omega^{\omega^{\varepsilon_0}+1}\,2$ comme
au-dessus, donc $(\varepsilon_0)^{\omega 2} =
\omega^{\omega^{\omega^{\varepsilon_0}+1}\,2}$ (avec le parenthésage :
$\omega^{((\omega^{((\omega^{\varepsilon_0})+1)})\cdot 2)}$).
\end{corrige}

(8) Indépendamment des questions précédentes, rappeler pourquoi tout
ordinal $\alpha$ possède une écriture unique sous la forme
$(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots +
(\varepsilon_0)^{\gamma_1}\, \xi_1$ où $\gamma_s > \cdots > \gamma_1$
sont des ordinaux et où $\xi_s,\ldots,\xi_1$ sont des ordinaux tous
non nuls et strictement inférieurs à $\varepsilon_0$.

\begin{corrige}
Il s'agit de l'écriture en base $\tau$ des ordinaux, dans le cas
particulier de $\tau = \varepsilon_0$.
\end{corrige}

(9) Indépendamment des questions précédentes, montrer que
$\varepsilon_0 + \varepsilon_1 = \varepsilon_1$ (on rappelle que
$\omega^\gamma + \omega^{\gamma'} = \omega^{\gamma'}$ lorsque $\gamma
< \gamma'$).  En déduire que $\varepsilon_0 \cdot \varepsilon_1 =
\varepsilon_1$.  En déduire que $(\varepsilon_0)^{\varepsilon_1} =
\varepsilon_1$.  Réciproquement, montrer que si $\delta$ est un
ordinal tel que $(\varepsilon_0)^{\delta} = \delta$ alors on a aussi
$\omega^\delta = \delta$ (on pourra montrer $\delta \leq \omega^\delta
\leq \omega^{\varepsilon_0 \delta} \leq \delta$) et en déduire que
$\delta \geq \varepsilon_1$.  En déduire que $\varepsilon_1$ est le
plus petit ordinal tel que $(\varepsilon_0)^{\delta} = \delta$.

\begin{corrige}
On a $\varepsilon_0 + \varepsilon_1 = \omega^{\varepsilon_0} +
\omega^{\varepsilon_1} = \omega^{\varepsilon_1}$ car $\varepsilon_0 <
\varepsilon_1$.  On en déduit $\varepsilon_0 \cdot \varepsilon_1 =
\omega^{\varepsilon_0} \cdot \omega^{\varepsilon_1} =
\omega^{\varepsilon_0 + \varepsilon_1} = \omega^{\varepsilon_1} =
\varepsilon_1$.  On en déduit $(\varepsilon_0)^{\varepsilon_1} =
((\omega^{\varepsilon_0})^{\varepsilon_1} =
\omega^{\varepsilon_0\cdot\varepsilon_1} = \omega^{\varepsilon_1} =
\varepsilon_1$.

Si $(\varepsilon_0)^{\delta} = \delta$ alors $\delta \leq
\omega^\delta \leq \omega^{\varepsilon_0 \delta} =
(\omega^{\varepsilon_0})^\delta = (\varepsilon_0)^{\delta} = \delta$
où les deux inégalités résultent de (2) et de la croissance de
$\gamma\mapsto\omega^\gamma$, donc toutes ces inégalités sont des
égalités et notamment $\omega^\delta = \delta$.  Comme $\varepsilon_1$
est le deuxième point fixe de $\gamma \mapsto \omega^\gamma$, on en
déduit que soit $\delta = \varepsilon_0$ soit $\delta \geq
\varepsilon_1$ : le premier est exclu car
$\varepsilon_0^{\varepsilon_0} > \varepsilon_0$ (par stricte
croissance de l'exponentiation ordinale en l'exposant lorsque la base
est $\geq 2$), et on a donc $\delta \geq \varepsilon_1$.  On a bien
prouvé que $\varepsilon_1$ est le plus petit ordinal tel que
$(\varepsilon_0)^{\delta} = \delta$.
\end{corrige}

On appellera \emph{écriture 2} d'un ordinal $\alpha < \varepsilon_1$
une écriture $(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots +
(\varepsilon_0)^{\gamma_1}\, \xi_1$ comme en (7), où les exposants
$\gamma_s > \cdots > \gamma_1$ sont tous $<\alpha$ et eux-mêmes écrits
en écriture 2, et où les $\xi_s,\ldots,\xi_1$ (qui
sont $<\varepsilon_0$) sont écrits en forme normale de Cantor itérée.

À titre d'exemple, $\omega^\omega\,2$ (il faut sous-entendre
$(\varepsilon_0)^0$ devant, qui vaut $1$) ou $(\varepsilon_0)^2 + 1$
ou bien $\varepsilon_0\,2 + \omega^\omega$ ou encore
$(\varepsilon_0)^{\varepsilon_0}\,\omega^\omega\,3$ sont des
écritures 2.  En revanche, $\omega^{\varepsilon_0+1}$ n'en est pas une
(les puissances de $\omega$ ne peuvent apparaître qu'au sein d'une
forme normale de Cantor itérée, donc ne faisant jamais intervenir
$\varepsilon_0$).

(10) Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$
possède bien une écriture 2 unique.  Esquisser un algorithme
permettant de convertire l'écriture 2 d'un ordinal $<\varepsilon_1$ en
écriture 1 (on utilisera la question (7)).

\begin{corrige}
L'existence et l'unicité de l'écriture 2 résulte de (8) et de
l'existence et unicité de la forme normale de Cantor itérée pour les
ordinaux $<\varepsilon_0$.

Pour convertir de l'écriture 2 en écriture 1, on part de l'écriture 2,
on convertit chaque exposant de $(\varepsilon_0)^\gamma$ de
l'écriture 1 en écriture 2 en utilisant l'algorithme récursivement
(ceci termine bien car les exposants sont strictement plus simples, ou
plus petits comme on voudra dire).  On calcule alors la valeur de
$(\varepsilon_0)^\gamma$ en partant de l'écriture 1 de $\gamma$ en
utilisant la question (7).  Il ne reste alors plus qu'à distribuer à
droite les produits $(\varepsilon_0)^\gamma\cdot\xi$ avec $\xi$ écrit
comme forme normale de Cantor itérée, et enfin calculer l'expression
globale en écriture 1 (ce qui ne fait intervenir que des sommes et des
produits, qu'on sait calculer).
\end{corrige}

{\footnotesize\textit{Remarque.} Il est aussi possible de convertir
  algorithmiquement de l'écriture 1 vers l'écriture 2 : ceci passe par
  calculer les $\omega^\alpha$ pour $\alpha$ donné en écriture 2.\par}

\medskip

\underline{Troisième partie.}

\nobreak
On aura besoin ici des définitions des ordinaux $\varepsilon_0$ et
$\varepsilon_1$ données en tête de la première partie, mais pas plus.

On s'intéresse à un jeu de Hercule et de l'hydre qui est analogue au
jeu considéré en cours mais avec une extension : comme en cours,
l'hydre est un arbre fini enraciné, mais l'hydre a maintenant deux
types de têtes (= feuilles de l'arbre) : des têtes normales, et des
\emph{œufs} (pouvant donner naissance à de nouvelles hydres).  Quand
Hercule coupe une tête $x$ normale, l'hydre se reproduit exactement
comme on l'a vu en cours, c'est-à-dire qu'elle reproduit autant
d'exemplaires qu'elle le veut de tout le sous-arbre partant du nœud
$y$ parent de $x$ dans l'arbre (ces copies étant ajoutées comme filles
du nœud $z$ parent de $y$), à condition que $y$ ne soit pas la racine
(sinon, l'hydre ne joue pas).  En revanche, si Hercule coupe un œuf,
cet œuf est remplacé par une nouvelle hydre, c'est-à-dire par un
sous-arbre, arbitrairement complexe, mais ne comportant pas lui-même
d'œuf.

(11) En associant à toute position du jeu (= tout arbre enraciné dont
certaines feuilles sont qualifiées d'œufs) un
ordinal $<\varepsilon_1$, montrer que Hercule gagne toujours,
c'est-à-dire qu'il va toujours réduire l'hydre à sa seule racine en
temps fini.

\begin{corrige}
À toute hydre $T$ on associe un ordinal $o(T) <\varepsilon_1$ par
récurrence sur la profondeur de l'arbre, de la façon suivante : si $T$
est un œuf, alors on pose $o(T) = \varepsilon_0$ ; sinon, si
$T_1,\ldots,T_r$ sont les sous-arbres ayant pour racine les fils de la
racine, triés de façon que $o(T_1) \geq \cdots \geq o(T_r)$, alors on
pose $o(T) = \omega^{o(T_1)} + \cdots + \omega^{o(T_r)}$.  Exactement
les mêmes démonstrations que dans le cours tiennent, il faut
simplement ajouter la clause suivante : si $T$ est un œuf et $T'$ est
une hydre sans œuf, alors $o(T') < \varepsilon_0 = o(T)$, donc en
remplaçant l'œuf par une hydre sans œuf quelconque, on fait
strictement décroître l'ordinal.

(Remarquons que, comme $\varepsilon_0 = \omega^{\varepsilon_0}$, une
tige de longueur arbitraire se finissant par un œuf a toujours la même
valeur $\varepsilon_0$ avec ce système : ce n'est pas un problème, et
ce n'est pas surprenant puisque de telles tiges offrent
essentiellement les mêmes possibilités à l'hydre.)
\end{corrige}

(12) Donner un exemple de position du jeu associé à l'ordinal
$(\varepsilon_0)^{\varepsilon_0}$ par le système proposé en (11).

\begin{corrige}
L'hydre suivante (dans laquelle les œufs ont été représentés par des
ovales gris) :
\begin{center}
\begin{tikzpicture}[baseline=0]
\draw[very thin] (-1.5,0) -- (1.5,0);
\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
\node (P0) at (0,0) {};
\node (P1) at (0,1) {};
\node (P2) at (0,2) {};
\node (P3) at (-1,3) {};
\node (P4) at (1,3) {};
\end{scope}
\begin{scope}[line width=1.5pt]
\draw (P0) -- (P1);
\draw (P1) -- (P2);
\draw (P2) -- (P3);
\draw (P2) -- (P4);
\fill[fill=gray] (P3) to[out=0,in=270] ($(P3) + (0.3,0.3)$) to[out=90,in=0] ($(P3) + (0,1.0)$) to[out=180,in=90] ($(P3) + (-0.3,0.3)$) to[out=270,in=180] (P3);
\fill[fill=gray] (P4) to[out=0,in=270] ($(P4) + (0.3,0.3)$) to[out=90,in=0] ($(P4) + (0,1.0)$) to[out=180,in=90] ($(P4) + (-0.3,0.3)$) to[out=270,in=180] (P4);
\end{scope}
\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
\node at (P3) {};
\node at (P4) {};
\end{scope}
\end{tikzpicture}
\end{center}
a la valeur $\omega^{\omega^{\varepsilon_0\,2}} =
\omega^{(\omega^{\varepsilon_0})^2} = \omega^{\varepsilon_0^2} =
(\omega^{\varepsilon_0})^{\varepsilon_0} =
(\varepsilon_0)^{\varepsilon_0}$, comme demandé.
\end{corrige}


%
%
%
\end{document}