% Ulm-Lyon-Cachan 2002, MP*, informatique
% corrig\'e de Jean-Fran\c{c}ois Husson (J-Fr.Husson@wanadoo.fr)
% et M. Quercia (michel.quercia@prepas.org)

                            %+----------+
                            %|  Macros  |
                            %+----------+

\input carnot.mac
\leftskip=7mm
\parindent=0mm

\def\q#1{\sv\goodbreak\hskip-\leftskip{\bf Question #1.}\par}

% Latex symbols
\font\tenlasy=lasy10
\font\sevenlasy=lasy7
\newfam\lasyfam
\def\hex#1{\ifcase#1 0\or1\or2\or3\or4\or5\or6\or7\or8\or9\or A\or B\or C\or D\or E\or F\fi}
\textfont\lasyfam=\tenlasy
\scriptfont\lasyfam=\sevenlasy
\mathchardef\gt="3\hex\lasyfam3D
\mathchardef\lt="3\hex\lasyfam3C
\mathchardef\teq"3\hex\lasyfam04
\def\t{\triangleright}
\def\ttt{\triangleright\hskip-2.5pt\triangleright\hskip-2.5pt\triangleright}

% AMS symbols
\mathchardef\succeq="3\hex\msafam3C
\mathchardef\bt="3\hex\msafam49
\mathchardef\bl="3\hex\msafam4A
\def\bteq{\mathrel{\rlap{$\ge$}\raise 1.0pt\hbox{$\bt$}}}
\def\bleq{\mathrel{\rlap{$\le$}\raise 1.0pt\hbox{$\bl$}}}
\mathchardef\dt="3\hex\msbfam6D
\mathchardef\dl="3\hex\msbfam6C
\def\dteq{\mathrel{\rlap{$\ge$}\raise 1.0pt\hbox{$\dt$}}}
\def\dleq{\mathrel{\rlap{$\le$}\raise 1.0pt\hbox{$\dl$}}}

% dessin d'arbres binaires
\def\bin#1#2#{\suitebin{#1}{#2}}
\def\suitebin#1#2#3{\vtop{\offinterlineskip
\def\dimbin{#2}\ifx\dimbin\empty\def\dimbin{0pt}\fi
\setbox0=\vtop{\vskip1pt\hbox{#1}}
\dimen0=\dimbin
\setbox1=\vtop{\vskip1pt\hbox{#3}}
\vskip9pt
\hbox{\hskip0.5\wd0\special{ps:currentpoint /momaaky exch def /momaakx exch def}}
\vskip-10pt
\hbox{\hskip0.75\wd0\hskip0.5\dimen0\hskip0.25\wd1\special{ps:currentpoint /mombbky exch def /mombbkx exch def}}
\vskip10pt
\hbox{\hskip\wd0\hskip\dimen0\hskip0.5\wd1\special{ps:currentpoint mombbkx mombbky lineto momaakx momaaky lineto gsave 2 setlinewidth stroke grestore moveto}}
\hbox{\hskip1.5\wd0\hskip\dimen0\hskip0.5\wd1}
\hbox to 0pt{\box0\hskip\dimen0\box1\hss}
}}

\def\dash#1#2#3{\vtop{\setbox0=\hbox{#3}
\offinterlineskip
\dimen0=0.5\wd0\advance\dimen0 by #1
\vskip-1pt
\hbox{\hskip\dimen0\special{ps:currentpoint /momaaky exch def /momaakx exch def}\hskip\dimen0}
\vskip#2
\hbox to 0pt{\hskip0.5\wd0\special{ps:currentpoint [4] 0 setdash momaakx momaaky lineto stroke [] 0 setdash moveto}\hss}
\vskip1pt
\hbox to 0pt{\box0\hss}}}

\def\ligne#1#2#3{\vtop{\setbox0=\hbox{#3}
\offinterlineskip
\dimen0=0.5\wd0\advance\dimen0 by #1
\vskip-1pt
\hbox{\hskip\dimen0\special{ps:currentpoint /momaaky exch def /momaakx exch def}\hskip\dimen0}
\vskip#2
\hbox to 0pt{\hskip0.5\wd0\special{ps:currentpoint momaakx momaaky lineto  gsave 2 setlinewidth stroke grestore moveto}\hss}
\vskip1pt
\hbox to 0pt{\box0\hss}}}

% fin de d\'emonstration
\def\cqfd{{\parfillskip=0pt\hfill\vrule height5pt width 5pt depth 0pt\par}}

% noms des fonctions
\def\add{\hbox{\ssf add}}
\def\arbre{\hbox{\ssf arbre}}
\def\dec{\hbox{\ssf dec1}}
\def\erbra{\hbox{\ssf erbra}}
\def\expr{\hbox{\ssf expr}}
\def\hd{\hbox{\ssf hd}}
\def\tl{\hbox{\ssf tl}}
\def\renv{\hbox{\ssf renv}}

%arbres particuliers
\def\O{{\bf O}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\def\E{{\cal E}}
\def\Q{{\cal Q}}
\def\R{{\cal R}}
\def\U{{\cal U}}
\def\V{{\cal V}}
\def\W{{\cal W}}
\def\X{{\cal X}}
\def\Y{{\cal Y}}
\def\d{\,\cdotp}

%puissance
\def\p{\,\hat{ }\,}

% haut et bas de page
\headline={\ifnum\pageno=1{\tenbf ULC 214}\hfil
\else{\tenit\ifodd\pageno\hfil Partie \botmark\else Partie \firstmark\hfil\fi}\fi}
\catcode`\@=11\font\@upstt=cmtt10\footline={\@upstt\hfil\jobname.tex\ - page
\the\count0\ifodd\count0\else\hfill\fi}\catcode64=\active\ifx\numerodepage\undefined
\else\count0=\numerodepage\fi

% divers
\doublecrochets
\guillemets

                     %+------------------------+
                     %|  Bandeau de l'\'epreuve  |
                     %+------------------------+

%\leftline{\bf ULC 214}
%\sv
{\let\par=\cr\obeylines\centerline{\vbox{\halign{&\hfil#\hfil\cr%
SESSION 2002
\noalign{\sv}%
\gros\bf Fili\`ere MP (groupes M/MP/MPI)
(\'Epreuve commune aux ENS de Paris, Lyon et Cachan)
\noalign{\sv}%
\gros\bf Fili\`eres MP et PC (groupe I)
(\'Epreuve commune aux ENS de Paris et Lyon)
\noalign{\sv}%
\gros\bf INFORMATIQUE
\noalign{\sv}%
\it Corrig\'e de Jean-Fran\c{c}ois Husson (J-Fr.Husson\char64 wanadoo.fr) et M. Quercia (michel.quercia\char64 prepas.org)
}}}}

                         %+----------------+
                         %|  Introduction  |
                         %+----------------+

\SV\goodbreak\centerline{\Gros\bf 1.  Introduction}\mark{1. Introduction}
\sv{\hskip-\leftskip\it Le principe d'induction structurelle donn\'e pour les triplets
d'arbres est peu compr\'ehensible. Il fallait lire~:
$$\bigl\{P(\O,\O,\O)\ \&\bigl[\forall a\in{\Bbb A}^3,\ (\forall b\in{\Bbb A}^3,\ a\ttt b \=> P(b)) \=> P(a)\bigr]\bigr\} \=> (\forall a\in{\Bbb A}^3,\ P(a)).$$}

\q{1}
Soit $\gt$ un ordre strict. On doit montrer qu'il n'existe pas
deux \'el\'ements (alors n\'ecessairement distincts) $x,y$ tels que $x \gt y$ et $y\gt x$.
De fait, si l'on suppose $x\gt y$ et $y\gt x$ alors on obtient $x\gt x$ par transitivit\'e,
ce qui contredit l'irr\'eflexivit\'e de~$\gt$.

\q{2}

\valign{\vfil#\vfill\cr
\advance \hsize by -3cm\advance\hsize by -\leftskip\leftskip=0mm\rightskip=5mm
De mani\`ere informelle, $R(\A,[\A_1;\dots;\A_n])$ est l'arbre
dessin\'e ci-contre. L'algorithme sui\-vant impl\'emente la fonction~$R$~:
\sv
{\bfsl\cleartabs\settabs\+\hskip5mm &\hskip5mm &\hskip5mm &\cr
\+&$R(\A$,{\it liste}$) =$\cr
\+&&si {\it liste} $=$ [ ] alors retourne $\A$\cr
\+&&sinon retourne $R(\hd(${\it liste}$)\d\A,\ \tl(${\it liste}$))$\cr
\+&fin\cr
}
\cr
\hsize=3cm\leftskip=0mm
\bin{$\A_n$}-6pt{\bin{$\A_{n-1}$}3pt%
{\dash{-11pt}{10pt}{\bin{$\A_2$}{\bin{$\A_1$}1em{$\A$}}}}}
\cr}

             %+----------------------------------------+
             %|  D\'ecomposition et suites de Goodstein  |
             %+----------------------------------------+

\SV\goodbreak\centerline{\Gros\bf 2.  D\'ecomposition compl\`ete d'un nombre}
\smallskip\centerline{\Gros\bf dans une base et suites de Goodstein}
\mark{2.  D\'ecomposition compl\`ete d'un nombre dans une base et suites de Goodstein}

\q{1}
$4 = 3^{(3^0 + 0)} + 3^0 + 0$,\qquad $83 = 3^{(3^{(3^0 + 0)} + 3^0 + 0)} + 3^0 + 3^0 + 0$.

\q{2}
{\it On suppose dans cette question et dans toute la suite du probl\`eme que $b\ge 2$.\sv}
La d\'efinition d'une d\'ecomposition compl\`ete donn\'ee dans l'\'enonc\'e ne fait
appara\^{\i}tre que le nombre $0$, des additions et des exponentiations,
donc si un nombre admet une d\'ecomposition compl\`ete, alors elle est bien
de la forme demand\'ee. Le but de la question est en fait de prouver
que tout entier naturel $n$ admet effectivement une d\'ecomposition compl\`ete.
On raisonne par r\'ecurrence forte sur~$n$. Si $n = 0$ alors $n$ admet une
d\'ecomposition compl\`ete~: $0=0$.
Supposons \`a pr\'esent que  $n$ est un entier naturel non nul et que tous les entiers
de $\{0,\dots,n-1\}$ admettent des d\'ecompositions compl\`etes
en base~$b$. Soit $p$ l'exposant maximal de~$n$
en base~$b$ ($p = \lfloor\ln n/\ln b\rfloor$) et $q=n-b^p$.
On a $p,q\in\{0,\dots,n-1\}$ donc $p$ et $q$ admettent des d\'ecompositions compl\`etes en
base~$b$, puis $n = b^{\text{d\'ecomposition de } p} + (\text{d\'ecomposition de } q)$,
ce qui prouve que $n$ admet lui aussi une d\'ecomposition compl\`ete en base~$b$.

\q{3}

\leavevmode\hskip5mm{\advance\hsize-5mm\advance\hsize-\leftskip\hsize=0.25\hsize\leftskip=0mm\valign{\vfill#\cr
\bin{\O}1em{\O}
\sv\hskip-5mm$1 = b^0 + 0$
\cr
\bin{\bin{\O}8.5pt{\O}}{\O}
\sv\hskip-5mm$b = b^{(b^0 + 0)}+0$
\cr
\bin{\bin{\O}1em{\O}}1em{\bin{\O}1em{\O}}
\sv\hskip-7mm$b+1 = b^{(b^0 + 0)}+b^0 + 0$
\cr
\bin{\bin{\bin{\O}8.5pt{\O}}{\O}}-8pt{\O}
\sv\hskip-5mm$b^b = b\p(b^{(b^0 + 0)}+0) + 0$
\cr}}
\sv
D\'efinition formelle de \arbre~:
$$\eqalign{
\arbre(b,0) &= \O\cr
\arbre(b,n) &= \arbre(b,p)\d\arbre(b,q)\quad\text{avec }(p,q) = \dec(b,n),\text{ pour }n\ge 1.\cr}$$
La correction et la terminaison de cet algorithme sont \'evidentes.

\q{4}
{\it Le code donn\'e pour {\ssit arbre} est mal parenth\'es\'e, il faut ignorer les parenth\`eses
fermantes surnum\'eraires dans les affectations \`a la variable courant. On reproduit ci-dessous
le code rectifi\'e en num\'erotant les lignes.}
\sv
{\def\0{\phantom0}\bfsl\cleartabs\settabs\+\hskip\leftskip\hskip5mm &\hskip5mm &\hskip5mm &\hskip5mm &\hskip5mm &\cr
\+&\it\01&\ssit arbre$(b,n) ={}$\cr
\+&\it\02&&{\it pile} $:= [(0,[\ ])]$\cr
\+&\it\03&&{\it courant} $:= (n,[\ ])$\cr
\+&\it\04&&tant que {\it pile} $\ne [\ ]$ faire\cr
\+&\it\05&&&$k$, {\it liste\_res} $:=$ {\it courant}\cr
\+&\it\06&&&si $k\ne 0$ alors\cr
\+&\it\07&&&&$m,r := \dec(b,k)$\cr
\+&\it\08&&&&{\it pile} $:=$ $(r,$ {\it liste\_res}$) ::$ {\it pile}\cr
\+&\it\09&&&&{\it courant} $:=$ $(m,[\ ])$\cr
\+&\it10&&&sinon\cr
\+&\it11&&&&$q,l := \hd(${\it pile}$)$\cr
\+&\it12&&&&{\it pile} $:= \tl(${\it pile}$)$\cr
\+&\it13&&&&{\it courant} $:=$ $(q, \renv(${\it liste\_res}$) :: l)$\cr
\+&\it14&&fait\cr
\+&\it15&&$k$, {\it liste\_res} $:=$ {\it courant}\cr
\+&\it16&&retourne $(\hd(${\it liste\_res}$))$\cr
\+&\it17&fin\cr
}
\sv
D'apr\`es la ligne~{\it 2}, {\it pile\/} est une liste de couples {\it (nombre,liste-1)}.
D'apr\`es la ligne~{\it 3}, {\it courant\/} est un couple {\it (nombre,liste-2)}.
D'apr\`es la ligne~{\it 5}, {\it liste\_res} est une liste de type {\it liste-2}.
D'apr\`es la ligne~{\it 8}, les types {\it liste-1} et {\it liste-2} sont \'egaux.
Enfin, d'apr\`es la ligne~{\it 13}, {\it liste-2} est le type des listes d'arbres binaires.
\sv
En conclusion, {\it pile\/} contient une liste de couples {\it (nombre, liste d'arbres binaires)},
{\it courant\/} contient un couple de ce type, et {\it liste\_res\/} contient
une liste d'arbres binaires.
On v\'erifie ais\'ement que les types indiqu\'es sont compatibles avec toutes les op\'erations
cod\'ees dans {\ssit arbre}, et l'on en d\'eduit que {\ssit arbre}$(b,n)$ retourne un arbre binaire,
sous r\'eserve de terminaison.
\sv
{\bf Invariant de boucle~:} soit $[(k,l);(k_1,l_1);\dots;(k_p,l_p)]$
la valeur de {\it courant\/} $::$ {\it pile} lors d'un passage en ligne~{\it 5}.
Alors les nombres $k,k_1,\dots,k_p$ sont des entiers naturels.
De plus, soient les arbres binaires $\A_0,\dots,\A_{p-1}$ d\'efinis par les relations~:
$$\A_0 = R(\arbre(b,k),l),
\quad \A_1 = R(\arbre(b,k_1),\ \A_0::l_1),
\quad\dots,
\quad \A_{p-1} = R(\arbre(b,k_{p-1}),\ \A_{p-2}::l_{p-1}).$$
Alors l'expression~:
$$\A_{p-1}::l_p = R(\arbre(b,k_{p-1}),\ R(\quad \dots,\ R(\arbre(b,k_1),\ R(\arbre(b,k),l) :: l_1):: \dots\quad) :: l_{p-1})::l_p\eqno(*)$$
est constante.
\sv{\bf D\'emonstration~:}
le fait que $k,k_1,\dots,k_p$ soient entiers naturels est imm\'ediat.
En ce qui concerne l'expression~$(*)$,
les instructions lignes {\it 7,8,9} ont pour effet de remplacer dans~$(*)$
l'arbre $R(\arbre(b,k),l)$ par~:
$$\eqalign{R(\arbre(b,r),\ R(\arbre(b,m),[\ ])::l)
&= R(\arbre(b,r),\ \arbre(b,m)::l)\cr
&= R(\arbre(b,m)\d\arbre(b,r),\ l)\cr
&= R(\arbre(b,k),\ l),\cr}
$$
tandis que les instructions lignes {\it 11,12,13} ont pour effet de remplacer dans~$(*)$
la liste $R(\arbre(b,k),l)::l_1$ par~:
$$\renv(l)::l_1
= R(\O,l)::l_1
= R(\arbre(b,0),l)::l_1
= R(\arbre(b,k),l)::l_1.$$
Dans les deux cas, la valeur de $(*)$ est donc inchang\'ee.\cqfd
\sv
{\bf Contenu de {\it liste\_res} lorsque l'algorithme se termine~:}
la valeur de~$(*)$ est celle d\'etermin\'ee lors du premier
passage en ligne~{\it 5}, \`a savoir~:
$R(\arbre(b,n),[\ ])::[\ ] = [\arbre(b,n)]$.
Au d\'ebut de la derni\`ere it\'eration de la boucle {\bfsl tant que},
on a {\it pile} $= [(k_1,l_1)]$ et {\it courant} $=(0,l)$, et donc en ligne~{\it 15\/}
on a~:
$$\text{\it liste\_res} = \renv(l)::l_1 = R(\arbre(b,0),l)::l_1 = [\arbre(b,n)].$$
Ceci prouve que l'algorithme {\ssit arbre}, s'il termine, retourne effectivement
la valeur $\arbre(b,n)$.
\sv
{\bf Contenu de {\it liste\_res} dans les \'etapes de l'algorithme~:}
l'\'enonc\'e ne pr\'ecisant pas en fonction de quoi il faut d\'ecrire ce contenu,
on est fond\'e \`a r\'epondre que, apr\`es chaque passage en ligne~{\it 5}, la variable
{\it liste\_res} contient une liste $l$ d'arbres binaires telle que
l'expression~$(*)$ a pour valeur $[\arbre(b,n)]$.
\sv
{\bf Terminaison~:} la terminaison de l'algorithme {\ssit arbre\/}
n'est pas demand\'ee explicitement dans l'\'enonc\'e, mais elle peut \^etre
prouv\'ee facilement en constatant que,
avec les notations donn\'ees dans de l'invariant de boucle,
la quantit\'e $2(k+k_1+\dots +k_p) + p$
d\'ecro\^{\i}t strictement entre deux passages cons\'ecutifs
en ligne~{\it 5}.

\q{5}
Algorithme~:
\sv
{\bfsl\cleartabs\settabs\+\hskip\leftskip\hskip5mm &\hskip5mm &\hskip5mm &\cr
\+&{\ssit erbra}$(b,\A) =$\cr
\+&&si $\A=\O$ alors retourne $0$\cr
\+&&sinon, {\it soient $\B$ et $\C$ tels que $\A = \B\d\C$~:} retourne $b^{\fct{\petit\ssit erbra}(\B)} + \fct{\ssit erbra}(\C)$\cr
\+&fin\cr
}
\sv
La correction et la terminaison sont imm\'ediates. En ce qui concerne la
complexit\'e, si l'on note $T(\A)$ le temps de calcul de {\ssit erbra}$(\A)$
compt\'e en nombre d'additions et d'exponentiations
et $N(\A)$ la taille de~$\A$, alors on a les relations~:
$$\eqalign{
T(\O) = 0,\quad &T(\B\d\C) = T(\B) + T(\C) + 2,\cr
N(\O) = 0,\quad &N(\B\d\C) = N(\B) + N(\C) + 1.\cr
}$$
D'o\`u $T(\A) = 2N(\A)$ par induction structurelle sur~$\A$.

\q{6}
Pour calculer $g_4$, on part de la d\'ecomposition compl\`ete de $83$ en
base 3~: $83 = 3^{(3^{(3^0 + 0)} + 3^0 + 0)} + 3^0 + 3^0 + 0$, on remplace tous les
$3$ par des $4$ dans cette expression, on \'evalue l'expression r\'esultante
et on retranche~$1$. D'o\`u
$g_4 = 4^{(4^{(4^0 + 0)} + 4^0 + 0)} + 4^0 + 4^0 + 0 - 1 = 4^5 + 1 =1025$.
\sv
Pour calculer $g_2$, on commence par inverser la relation de
d\'efinition des suites de Goodstein~:
$$g_{k+1} = \erbra(k+1, \arbre(k,g_k))-1 \<=> g_k = \erbra(k, \arbre(k+1, g_{k+1} + 1)).$$
On obtient donc $g_k$ \`a partir de~$k$ et $g_{k+1}$ en \'ecrivant la d\'ecomposition
compl\`ete de $g_{k+1}+1$ en base~$k+1$, en rempla\c{c}ant $k+1$ par~$k$ dans cette
d\'ecomposition et en \'evaluant le r\'esultat sous r\'eserve que la formule
obtenue soit une d\'ecomposition compl\`ete en base~$k$ valide.
\par
D'o\`u~:
$g_3 = 83 \=> g_3+1 = 84 = 3^{(3^{(3^0 + 0)} + 3^0 + 0)} + 3^{(3^0+0)} + 0
\=> g_2 = 2^{(2^{(2^0 + 0)} + 2^0 + 0)} + 2^{(2^0+0)} + 0
        = 10$.
\sv
$g_k > 1000^{1000}$~? Calculons quelques valeurs suppl\'ementaires
de la suite $(g_k)$~:
$$\eqalign{g_5 &= 5^{(5^{(5^0 + 0)} + 5^0 + 0)} + 5^0 + 0 - 1 = 5^6,\cr
           g_6 &= 6^{(6^{(6^0 + 0)} + 6^0 + 0)}  + 0 - 1 = 6^7-1 = 6^6 + 233279.\cr}$$
On montre alors par r\'ecurrence sur~$k$ que l'on a $g_k = k^k+h_k$
avec $233285 -k \le h_k < 5\,k^k$ pour tout entier~${k\in{[[6,233285]]}}$.
Cette hypoth\`ese est v\'erifi\'ee pour $k=6$, et si elle l'est pour un certain
entier $k<233285$ alors la d\'ecomposition compl\`ete de~$g_k$ en base~$k$ est
de la forme~:
$$g_k = \underbrace{k^{(k^{(k^0+0)}+\,0)}}_{k^k} + \underbrace{k^{a_1} + \dots + k^{a_p} + 0}_{h_k}$$
o\`u $a_1,\dots,a_p$ sont des entiers (compl\`etement d\'ecompos\'es en base~$k$) tels
que $k\ge a_1\ge \dots \ge a_p \ge 0$ et $k>a_5$ si $p\ge 5$. Alors~:
$$g_{k+1} = \underbrace{(k+1)^{((k+1)^{((k+1)^0+0)}+\,0)}}_{(k+1)^{k+1}} + \underbrace{(k+1)^{b_1} + \dots + (k+1)^{b_p} + 0 - 1}_{h_{k+1}}$$
o\`u $b_i$ est l'entier obtenu \`a partir de~$a_i$ en rempla\c{c}ant $k$ par $k+1$
dans la d\'ecomposition compl\`ete de~$a_i$ en base~$k$.
On a donc $b_i = k+1$ si $a_i = k$ et $b_i= a_i$ sinon, d'o\`u~:
$5(k+1)^{k+1} > h_{k+1}\ge h_k-1\ge 233285-k - 1 = 233285 -(k+1)$.
\cqfd
\sv
Conclusion~: on a
$g_{999} < 6\times 999^{999} < 1000^{1000} < g_{1000}$,
donc $g_{1000}$ est le premier entier de la suite~$(g_k)$ sup\'erieur \`a~$1000^{1000}$.
\q{7}
{\bf Premier algorithme~:} l'\'enonc\'e autorise pour ce premier algorithme l'usage de l'addition
des entiers naturels, mais ne pr\'ecise pas si l'exponentiation effectu\'ee
dans l'algorithme {\ssit erbra}, question~{\bf 5}, est aussi autoris\'ee,
ni si les op\'erations effectu\'ees dans une impl\'ementation (non explicit\'ee)
de \dec\ sont elles aussi autoris\'ees. On choisit ici d'interpr\'eter na\"{\i}vement
la question~:
\sv
\centerline{{\ssit addition\_arbres}$(b,\A,\B) =
\arbre(b,\ \erbra(b,\A) + \erbra(b,\B))$.}
\sv
{\bf Deuxi\`eme algorithme~:} soient $u,v\in \N$ deux nombres entiers donn\'es
par leurs arbres associ\'es. Ces arbres fournissent des d\'ecompositions
de~$u$ et~$v$ comme sommes de puissances de~$b$~:
$$u = b^{u_1} + \dots + b^{u_p} + 0,\qquad v = b^{v_1} + \dots + b^{v_q} + 0,$$
o\`u $(u_1,\dots,u_p)$ et $(v_1,\dots,v_q)$ sont des suites d\'ecroissantes
d'entiers naturels connus par leurs arbres associ\'es. On peut calculer
$u+v$ par additions successives d'une puissance de~$b$ \`a un nombre entier~:
$$u + v = (\dots((u + b^{v_1}) + b^{v_2}) + \dots ) + b^{v_q},$$
d'o\`u l'algorithme~:
\sv
{\bfsl\cleartabs\settabs\+\hskip\leftskip\hskip5mm &\hskip5mm &\hskip5mm &\cr
\+&{\ssit addition}$(b,\U,\V) =$\cr
\+&&si $\V=\O$ alors retourne $\U$\cr
\+&&sinon, {\it soient $\X$ et $\Y$ tels que $\V = \X\d\Y$~:} retourne $\fct{\ssit addition}(b,\ \fct{\ssit add\_puiss}(b, \U, \X),\ \Y)$\cr
\+&fin\cr
}
\sv
o\`u {\ssit add\_puiss\/} est un algorithme calculant $u + b^x$ pour
$u,x$ entiers naturels donn\'es sous forme d'arbres.
En supposant {\ssit add\_puiss\/} correctement impl\'ement\'ee, la correction
et la terminaison de {\ssit addition\/} sont \'evidentes. {\ssit add\_puiss\/}
s'apparente \`a un algorithme d'insertion. Il s'agit d'ins\'erer $b^x$ au
bon endroit dans la d\'ecomposition de~$u$, en traitant \`a part le cas o\`u l'on cr\'ee ainsi une
suite de $b$ termes \'egaux \`a $b^x$~: il faut alors remplacer cette sous-suite par $b^{x+1}$,
et propager la retenue ainsi cr\'e\'ee vers le d\'ebut de la d\'ecomposition.
On aura donc besoin pour \'ecrire {\ssit add\_puiss} de savoir comparer
deux exposants de~$b$ pour d\'eterminer l'endroit o\`u ins\'erer $b^x$, et
aussi de savoir calculer $x+1$. Ce dernier probl\`eme peut \^etre r\'esolu
par l'utilisation r\'ecursive de {\ssit add\_puiss\/} puisque $x+1 = x+b^0$.
En reportant \`a plus tard l'\'ecriture d'un algorithme de comparaison,
on a donc l'algorithme suivant pour {\ssit add\_puiss}~:
\sv
{\def\0{\phantom0}\it\cleartabs\settabs\+\hskip\leftskip\hskip5mm &\hskip5mm &\hskip5mm &\hskip5mm &\hskip5mm &\hskip5mm &\cr
\+&\01&{\ssit add\_puiss}$(b,\U,\X) =$\cr
\+&\02&&{\bfsl si} $\U=\O$ {\bfsl alors retourne} $\X\d\O$\cr
\+&\03&&{\bfsl sinon}, soient $\V$ et $\W$ tels que $\U = \V\d\W$~:\cr
\+&\04&&&comparer $\V$ et $\X$\cr
\+&\05&&&{\bfsl si} $\V < \X$ {\bfsl alors retourne} $\X\d\U$\cr
\+&\06&&&{\bfsl si} $\V > \X$ {\bfsl alors retourne} $\fct{\ssit add\_puiss}(b,\ \fct{\ssit add\_puiss}(b,\W,\X),\ \V)$\cr
\+&\07&&&{\bfsl si} $\V = \X$ {\bfsl alors} :\cr
\+&\08&&&&$l := [\X; \X]$;\quad $n := 2$;\quad $a := \W$\cr
\+&\09&&&&{\bfsl tant que} $a$ est de la forme $a = \X\d a'$ {\bfsl faire} :\cr
\+&10&&&&&$l := \X::l$;\quad $n := n+1$;\quad $a := a'$\cr
\+&11&&&&{\bfsl fait}\cr
\+&12&&&&{\bfsl si} $n < b$ {\bfsl alors retourne} $R(a,l)$\cr
\+&13&&&&{\bfsl sinon}, {\bfsl retourne} $\fct{\ssit add\_puiss}(b, \X, \O)\d a$\cr
\+&14&{\bfsl fin}\cr
}
\sv\goodbreak
La terminaison et la correction de {\ssit add\_puiss\/} s'\'etablissent facilement par
r\'ecurrence sur le nombre $u$ associ\'e au deuxi\`eme argument de {\ssit add\_puiss}.
En effet, les deux appels r\'ecursifs en ligne~{\it 6} et l'appel r\'ecursif en ligne~{\it 13}
portent sur des arbres associ\'es aux nombres $w$, $w+b^x$ et $x$ et ces
nombres sont strictement inf\'erieurs \`a~$u$ dans les conditions o\`u
l'on passe par ces lignes.
\sv
Finalement, il ne reste plus qu'\`a \'ecrire un algorithme comparant
deux nombres $u$ et~$v$ donn\'es par leurs arbres binaires associ\'es.
Le cas o\`u l'un des nombres $u$ ou $v$ est nul est trivial.
Dans le cas g\'en\'eral, les arbres associ\'es \`a $u$ et~$v$ fournissent des d\'ecompositions de~$u$
et~$v$ comme sommes de puissances d\'ecroissantes de~$b$~:
$$u = b^{u_1} + \dots + b^{u_p} + 0 = b^{u_1} + u',\qquad v = b^{v_1} + \dots + b^{v_q} + 0 = b^{v_1} + v',$$
o\`u $u_1$ et $v_1$ sont les exposants maximaux de~$u$ et~$v$.
Donc, si $u_1 < v_1$ on a $u < v$, si $u_1 > v_1$ on a $u > v$, et
si $u_1 = v_1$ alors $u$ et~$v$ sont dans le m\^eme ordre que $u'$ et~$v'$.
L'algorithme ci-dessous impl\'emente ce principe de comparaison, et retourne l'une des constantes symboliques
{\ssf sup}, {\ssf egal} ou {\ssf inf} selon que $u > v$, $u = v$ ou $u < v$~:
\sv
{\bfsl\cleartabs\settabs\+\hskip\leftskip\hskip5mm &\hskip5mm &\hskip5mm &\cr
\+&{\ssit compare}$(\U,\V) =$\cr
\+&&si $\U=\O$ {\it et} $\V=\O$ alors retourne {\ssf egal}\cr
\+&&sinon, si $\U=\O$ alors retourne {\ssf inf}\cr
\+&&sinon, si $\V=\O$ alors retourne {\ssf sup}\cr
\+&&sinon, {\it soient $\U_1,\U_2,\V_1,\V_2$ tels que $\U = \U_1\d\U_2$ et $\V = \V_1\d\V_2$~:}\cr
\+&&&$r :=\fct{\ssit compare}(\U_1,\V_1)$\cr
\+&&&si $r=$ {\ssf egal} alors retourne {\ssit compare}$(\U_2,\V_2)$\cr
\+&&&sinon, retourne $r$\cr
\+&fin\cr
}
\sv
{\bf Conclusion~:} le contrat est rempli, on a obtenu un algorithme
r\'ealisant l'addition de deux arbres binaires dans lequel la seule addition
entre nombres entiers effectu\'ee est l'incr\'ementation de la variable~$n$
dans la fonction {\ssit add\_puiss}, ligne~{\it 10}, et la valeur de~$n$
est toujours inf\'erieure ou \'egale \`a $b$ (apr\`es incr\'ementation).
Cet algorithme d'addition n'est pas le plus rapide qui puisse se concevoir,
car la fusion des listes de puissances de~$b$ composant $u$ et~$v$ dans {\ssit addition\/}
est r\'ealis\'ee "par le haut", donc la complexit\'e de cette fusion est $O(n^2)$
pour des arbres de taille $O(n)$, alors qu'on pourrait r\'ealiser une fusion en temps $O(n)$
"en partant du bas". Mais l'\'enonc\'e n'a
pas demand\'e d'impl\'ementer une addition de complexit\'e optimale, et il y a
encore beaucoup de questions \`a traiter\dots


\q{8}
Soient $u,v$ deux entiers naturels donn\'es par leurs arbres associ\'es.
De m\^eme que pour l'addition, on ram\`ene le calcul de l'arbre repr\'esentant $uv$
\`a une s\'erie de calculs o\`u le multiplicateur est une puissance de~$b$.
Ce cas simplifi\'e de multiplication s'impl\'emente par translation des exposants du multiplicande.
\sv
{\bfsl\cleartabs\settabs\+\hskip\leftskip\hskip5mm &\hskip5mm &\hskip5mm &\cr
\+&{\ssit multiplie}$(b,\U,\V) =$\cr
\+&&si $\V=\O$ alors retourne \O\cr
\+&&sinon, {\it soient $\X$ {\it et} $\Y$ {\it tels que}  $\V = \X\d\Y$~:}\cr
\+&&&retourne $\fct{\ssit addition}(b,\ \fct{\ssit translate}(b,\U,\X),\ \fct{\ssit multiplie}(b,\U,\Y))$\cr
\+&fin\cr
\sv
\+&{\ssit translate}$(b,\U,\X) =$\cr
\+&&si $\U=\O$ alors retourne \O\cr
\+&&sinon, {\it soient $\V$ {\it et} $\W$ {\it tels que}  $\U = \V\d\W$~:}\cr
\+&&&retourne $\fct{\ssit addition}(b,\V,\X)\d \fct{\ssit translate}(b,\W,\X)$\cr
\+&fin\cr
}


                     %+------------------------+
                     %|  Ordre sur les arbres  |
                     %+------------------------+

\SV\goodbreak\centerline{\Gros\bf 3.  Un ordre sur les arbres}
\mark{3.  Un ordre sur les arbres}

\q{1}
Remarquons d\'ej\`a que si $\A$ et $\B$ sont des arbres binaires,
alors la relation $\A\succ\B$ implique $\A\ne\O$.
\sv
Irr\'eflexivit\'e~: soit $\A\in{\Bbb A}$. On montre par r\'ecurrence sur la
taille~$n$ de~$\A$ que $\A\not\succ\A$.
Pour $n=0$ on a $\A = \O$ donc $\A\not\succ\A$
d'apr\`es la remarque pr\'ec\'edente. Pour $n > 0$, on a $\A = \A_1\d\A_2$
o\`u $\A_1$ et $\A_2$ sont deux arbres binaires de tailles
inf\'erieures \`a~$n$. Par hypoth\`ese de r\'ecurrence,
$\A_1\not\succ\A_1$ et 
$(\A_1 = \A_1,\ \A_2\not\succ\A_2)$
donc $\A\not\succ\A$.
\sv
Transitivit\'e~: on montre de m\^eme la propri\'et\'e
$(\A\succ\B,\ \B\succ\C)\=> \A\succ\C$
par r\'ecurrence sur la taille de~$\C$ (il y a 4 cas \`a examiner).

\q{2}
Soit $(\A_n)$ la suite d'arbres d\'efinie par les relations~:
$\A_0 = (\O\d\O)\d\O$,
$\A_{n+1} = \O\d\A_n$.

On a par construction $(\A_n \succ\A_{n+1}) \=> (\A_{n+1} \succ\A_{n+2})$,
et aussi $\A_0 \succ \A_1$, d'o\`u $\A_n \succ \A_{n+1}$
pour tout entier~$n$.

\q{3}
Le caract\`ere "ordre strict" se d\'emontre sans difficult\'e.
En ce qui concerne la bonne fondation, supposons qu'il existe une
suite infinie de couples $(a_n,b_n)\in A\times B$
strictement d\'ecroissante pour $>_A\times >_B$.
Par d\'efinition de $>_A\times >_B$, la suite $(a_n)$ est
d\'ecroissante au sens large.
Si elle prend une infinit\'e de valeurs distinctes
alors, quitte \`a se restreindre \`a une sous-suite, on peut supposer
que tous les $a_n$ sont distincts donc $A$ contient une
suite infinie strictement d\'ecroissante, ce qui est exclus.
De m\^eme, si la suite $(a_n)$ ne prend qu'un nombre fini de valeurs
distinctes, alors \`a partir d'un certain rang $n_0$ tous les $a_n$
sont \'egaux et la sous-suite $(b_n)_{n\ge n_0}$ est une
suite infinie de~$B$ strictement d\'ecroissante, c'est impossible.
Dans les deux cas on aboutit \`a une impossibilit\'e, donc
$A\times B$ ne contient pas de suite infinie strictement d\'ecroissante
pour $>_A\times >_B$.

\q{4}
{\it Remarque~: traditionnellement, un alphabet est un ensemble fini non vide.
Ici il faut autoriser les "alphabets" \`a \^etre infinis, sinon
la question de la bonne fondation de $(A,>_A)$ ne se pose pas.}
\sv
En consid\'erant que $A$ est le sous-ensemble de $A^{\text{dec}}$
constitu\'e des mots \`a une seule lettre, l'ordre $>_{A^*}$ prolonge $>_A$.
Donc si $(A^{\text{dec}},>_{A^*})$ est bien fond\'e, $(A,>_A)$ l'est aussi.
Pour la r\'eciproque, supposons $(A,>_A)$ bien fond\'e,
$(A^{\text{dec}},>_{A^*})$ mal fond\'e, et
soit $(u_n)$ une suite infinie de mots d\'ecroissants strictement
d\'ecroissante pour $>_{A^*}$. On en extrait une sous-suite $(v_i)$
telle que $v_i$ est de longueur sup\'erieure ou \'egale \`a~$i$ et $v_i,v_{i+1}$
ont les m\^emes $i$ premi\`eres lettres de la mani\`ere suivante~:
\sv
{\marge{\hskip5mm}
1. Supposons que la suite des longueurs, $(|u_n|)$, est born\'ee.
Alors $(u_n)$ contient une sous-suite strictement d\'ecroissante de mots
ayant tous m\^eme longueur~$\ell>0$, donc la restriction
de $>_{A^*}$ \`a~$A^\ell$  est un ordre mal fond\'e. Mais ceci est impossible
d'apr\`es la question pr\'ec\'edente, g\'en\'eralis\'ee par r\'ecurrence sur~$\ell$
\`a un produit cart\'esien de $\ell$ ordres bien fond\'es.
Donc la suite $(|u_n|)$ est non born\'ee et, quitte \`a se restreindre \`a une
sous-suite, on peut supposer $|u_n| \ge n$ pour tout entier~$n\ge 1$.
\sv
2. Soit $a_{n,1}$ la premi\`ere lettre de $u_n$. Alors la suite $(a_{n,1})$
est une suite d\'ecroissante de lettres, elle ne prend qu'un nombre fini
de valeurs puisque $>_A$ est un ordre bien fond\'e. Soit $a_1$
la plus petite de ces valeurs et $n_1$ un rang tel que $n\ge n_1\=> a_{n,1} = a_1$.
On pose $v_1 = u_{n_1}$.
\sv
3. Soit $a_{n,2}$ la deuxi\`eme lettre de~$u_n$, bien d\'efinie si $n\ge 2$.
D'apr\`es le choix de~$n_1$, la sous-suite $(a_{n,2})_{n>n_1}$ est d\'ecroissante
donc il existe une lettre $a_2$ et un rang $n_2>n_1$ tels que
$n\ge n_2\=> a_{n,2} = a_2$.
On pose $v_2 = u_{n_2}$.
\sv
4. Etc.
\par}
\sv
La suite $(a_n)$ mise en \'evidence au cours de cette
construction est une suite d\'ecroissante dans~$A$ car $a_n,a_{n+1}$
sont deux lettres successives de~$v_{n+1}$, mot d\'ecroissant. Donc cette
suite ne prend qu'un nombre fini de valeurs, et il existe un rang~$p$
et une lettre~$a$ tels que $n\ge p \=> a_n = a$. A partir de ce rang
tous les~$v_n$ sont de la forme~: $v_n = ma^{\ell_n}$ o\`u $m = a_1\dots a_{p-1}$
et $\ell_n = |v_n|-p+1$. Comme la suite $(v_n)$ est strictement d\'ecroissante,
la suite $(\ell_n)$ est une suite strictement d\'ecroissante d'entiers naturels,
ce qui est impossible.
On a ainsi prouv\'e que les propositions "$(A,>_A)$ est bien fond\'e" et
"$(A^{\text{dec}},>_{A^*})$ est mal fond\'e" sont contradictoires.
\cqfd

\q{5}
$$\A = \vcenter{
\bin{$\A_1$}-1pt{\bin{$\A_2$}9pt%
{\dash{-11pt}{10pt}{\bin{$\A_n$}1em{\O}}}}}\hskip 70pt
s(\A) = \vcenter{
\bin{$\A_1$}-1pt{\bin{$\A_2$}9pt%
{\dash{-11pt}{10pt}{\bin{$\A_n$}{\bin{\O}1em{\O}}}}}}
$$

Soient $\A_1,\dots,\A_n$ des arbres binaires et $\A$, $s(\A)$
les arbres dessin\'es ci-dessus ($s(\O) = \O\d\O$).
On remarque que $\A$ est ordonn\'e
si et seulement $\A_1,\dots,\A_n$ le sont
et $\A_1\succeq\dots\succeq\A_n$. Dans ce cas, $s(\A)$
est aussi un arbre ordonn\'e et l'on a $s(\A)\succ\A$.
On d\'emontre de mani\`ere imm\'ediate la propri\'et\'e suivante~:
\sv
\centerline{\it que $\A$ soit ordonn\'e ou non,
pour tout arbre $\B$ on a $\B\succ\A\=>\B\succeq s(\A)$.}
\sv
Donc $s(\A)$ est le successeur de~$\A$, aussi bien dans~$\Bbb A$
que dans~$\Bbb O$.

\q{6}
${\Bbb O}_\O = \{\O\}$ donc la restriction de $\succ$ \`a~${\Bbb O}_\O$ est bien fond\'ee.
Supposons que pour tout arbre~$\A$ de taille inf\'erieure \`a~$n$
la restriction de~$\succ$ \`a~${\Bbb O}_\A$ est bien fond\'ee, et consid\'erons
un arbre ~$\A=\A_1\d\A_2$ de taille~$n$.
Si $\B\in{\Bbb O}_\A$
alors $\B$ est de la forme 
$\B = \B_1\d (\B_2\d (\ \dots(\B_p\d\O)\dots\ ))$
avec $\A_1\succeq\B_1\succeq\dots\succeq\B_p$,
on lui associe le mot $\widetilde\B =\B_1\dots\B_p\in\smash{{\Bbb O}_{\A_1}^{\text{dec}}}$.
Cette association est injective, et on a clairement~: $\B\succ\C \<=> \smash{\widetilde\B\succ_{{\Bbb O}_{\A_1}^*}\widetilde\C}$.
$({\Bbb O}_{\A_1},\succ)$ est bien fond\'e par hypoth\`ese de
r\'ecurrence, donc $({\Bbb O}_{\A_1}^{\text{dec}},\smash{\succ_{{\Bbb O}_{\A_1}^*}})$ ne
contient pas de suite infinie strictement d\'ecroissante, et donc
$({\Bbb O}_{\A},\succ)$ n'en contient pas non plus.

\q{7}
Si $({\Bbb O},\succ)$ contenait une suite $(\A_n)$ strictement d\'ecroissante,
alors cette suite serait incluse dans $({\Bbb O}_{\A_0},\succ)$,
en contradiction avec~{\bf 6}.


\q{8}
On d\'emontre par r\'ecurrence sur~$n$ que l'on a les propri\'et\'es~:
$$\arbre(b,n)\in{\Bbb O},\qquad\text{et}\qquad
\forall\ m  < n,\  \arbre(b,n) \succ \arbre(b,m).$$
Le cas $n=0$ est trivial. Soit $n>0$ tel que ces propri\'et\'es sont v\'erifi\'ees pour
tous les entiers inf\'erieurs \`a~$n$. On a $n = b^x + y$ o\`u $x$ est l'exposant
maximal de~$n$, donc $\arbre(b,n) = \arbre(b,x)\d\arbre(b,y)$.
Par hypoth\`ese de r\'ecurrence, $\arbre(b,x)$ et $\arbre(b,y)$ sont des arbres
ordonn\'es, et si $\arbre(b,y) = \arbre(b,z)\d\arbre(b,t)$ alors
$z$ est l'exposant maximal de~$y$ donc $z \le x$, d'o\`u
$\arbre(b,x)\succeq\arbre(b,z)$ par hypoth\`ese de r\'ecurrence encore.
Ceci prouve que $\arbre(b,n)\in{\Bbb O}$.
Ensuite, si $m<n$ on a soit $m=0$ d'o\`u $\arbre(b,n) \succ \arbre(b,m) = \O$,
soit $m = b^{x'} + y'$ o\`u $x'$ est l'exposant maximal de~$m$, donc $x' < x$
ou $(x'=x,\ y' < y)$, ce qui implique, par hypoth\`ese de r\'ecurrence toujours,
$\arbre(b,x)\succ\arbre(b,x')$ ou 
$(\arbre(b,x)=\arbre(b,x')$ et $\arbre(b,y)\succ\arbre(b,y'))$,
donc $\arbre(b,n)\succ\arbre(b,m)$ dans les deux cas.
\sv
Remarque~: l'\'equivalence entre $>_{\N}$ et $\succ_{\Bbb O}$ restreinte
aux arbres binaires repr\'esentant des entiers en base~$b$ a d\'ej\`a \'et\'e
prouv\'ee, par un raisonnement similaire, dans la partie~{\bf 2}, question~{\bf 7}.


\q{9}
Supposons qu'il existe une suite $(g_k)$ de Goodstein infinie.
On a $\arbre(k,g_k) = \arbre(k+1,g_{k+1}+1)$ par d\'efinition,
et $\arbre(k+1,g_{k+1}+1) \succ \arbre(k+1,g_{k+1})$ d'apr\`es la question pr\'ec\'edente.
Donc la suite $(\arbre(k,g_k))$ est strictement d\'ecroissante dans~$({\Bbb O},\succ)$,
c'est impossible.
\sv
Remarque~: voyons \`a quel rang la suite de
Goodstein telle que $g_3=83$ atteint z\'ero.
On~a successivement~:
$$g_6 = 6^7-1 = 5\d6^6+\overline{555555}^6,\quad
g_7 = 5\d7^7+\overline{555554}^7,\quad
\dots,\quad
g_{11} = 5\d{11}^{11}+\overline{555550}^{11}.$$
Dans la suite, on note $K$ l'expression $r^r$ o\`u $r$ est le rang de l'entier de Goodstein consid\'er\'e.
On voit facilement que~:
$$
g_{k-1} = 5K + \overline{abcde0}^{k-1}
\=> g_{2k-1} = 5K + \overline{abcd(e-1)0}^{2k-1}
\=> \dots \=> g_{2^ek-1} = 5K + \overline{abcd00}^{2^ek-1}.
$$
En particulier, $g_{383} = 5\d383^{383} + \overline{555500}^{383}$
est le premier terme $g_k$ avec $k\ge 6$ dont l'\'ecriture en base~$k$ se termine par deux z\'eros.
Continuons~:
$$
g_{k-1} = 5K + \overline{abcd00}^{k-1}
\=> g_{k2^k-1} = 5K + \overline{abc(d-1)00}^{k2^k-1}.
$$
Donc le prochain terme apr\`es $g_{383}$ dont l'\'ecriture en base~$k$ se termine
par deux z\'eros est~:
$$g_{384\d2^{384}-1} =
5(384\d2^{384}-1)^{384\d2^{384}-1} + \overline{555400}^{384\d2^{384}-1}.$$
Le premier entier $k$ tel que l'\'ecriture de~$g_k$ en base~$k$ se termine par trois z\'eros
est d\'efini par~:
$$a =  384\d2^{384},\quad b = a2^{a},\quad c = b2^{b},\quad d = c2^{c},\quad e = d2^{d},\quad k=e-1.$$
Pour cette valeur de~$k$, on a $g_k = 5K + \overline{555000}^k$. Il ne reste plus qu'\`a grignoter patiemment
les trois 5 qui restent, avant d'attaquer le premier des cinq $K$\dots


                 %+---------------------------------+
                 %|  Un autre ordre sur les arbres  |
                 %+---------------------------------+

\SV\goodbreak
\centerline{\Gros\bf 4.  Un autre ordre sur les arbres}
\mark{4.  Un autre ordre sur les arbres}

\q{1}
{\bf Lemme :} soient $\A = \A_1\d\A_2$. Les arbres $\B$
tels que $\A\bt\B$ sont les arbres de l'une des formes suivantes~:
$$\matrix{
(1) &\B = \B_1\d(\ \dots(\B_p\d\C)\dots\ )\hfill
&\text{ avec } p\in\N,\ \A_1\bt\B_i \text{ et } \A_2\bteq\C\hfill
\cr\noalign{\smallskip}
(2) &\B = \B_1\d(\ \dots(\B_p\d(\A_1\d\D))\dots\ )
&\text{ avec } p\in\N,\ \A_1\bt\B_i \text{ et } \A_2\bt\D.
\cr
}$$
$$\A = \vcenter{\bin{$\A_1$}1em{$A_2$}}\qquad
\B =\ \vcenter{\bin{$\B_1$}10pt{\dash{-10pt}{10pt}{\bin{$\B_p$}1em{$\C$}}}}
\hskip30pt\text{ ou }
\B =\ \vcenter{\bin{$\B_1$}10pt{\dash{-11pt}{10pt}{\bin{$\B_p$}{\bin{$\A_1$}11pt{$\D$}}}}}
$$
{\bf D\'emonstration~:} on constate par r\'ecurrence sur~$p$
que si~$\B$ est donn\'e par $(1)$ ou par~$(2)$ alors on a bien $\A\bt\B$.
On d\'emontre la r\'eciproque par r\'ecurrence sur la taille~$n$ de~$\B$.
Pour $n=0$, on a $\B = \O$ qui est de la forme~$(1)$ avec
$p=0$ et $\C=\O$.
Si $n>0$ alors $\B = \B_1\d\B'$ et l'on a trois possibilit\'es.
\sv{\marge{\hskip5mm}
1. $\A_1 \bt\B_1$ et $\A \bt\B'$~: alors $\B'$
est de l'une des formes~$(1)$ ou~$(2)$, et $\B$ aussi.
\smallskip
2. $\A_1=\B_1$ et $\A_2 \bt\B'$~: alors $\B$
est de la forme~$(2)$ avec $p=0$ et $\D = \B'$.
\smallskip
3. $\A_2\bteq\B$~: alors $\B$
est de la forme~$(1)$ avec $p=0$ et $\C = \B$.
\cqfd
\sv}

{\bf Transitivit\'e de~$\bt$~:} on montre par r\'ecurrence sur~$n$
que si $\A,\B,\E$ sont des arbres dont la somme des
tailles est inf\'erieure ou \'egale \`a~$n$
tels que $\A\bt\B$ et
$\E\bt\A$, alors $\E\bt\B$. Pour $n=0$ il n'y a rien \`a
d\'emontrer. Pour $n>0$, on \'ecrit $\A = \A_1\d\A_2$,
$\E = \E_1\d\E_2$ et l'on d\'ecompose $\B$ selon
l'une des formes~$(1)$ ou~$(2)$ du lemme.
Il y a cinq cas \`a examiner, et
dans chaque cas on peut appliquer la propri\'et\'e
de transitivit\'e aux arbres consid\'er\'es
car la somme des tailles de ces arbres est inf\'erieure \`a~$n$.
\sv{\marge{\hskip15mm}
\hskip-10mm1. $\E_1 \bt\A_1$, $\E \bt\A_2$ et $\B$ est de la forme~$(1)$~:
alors $\E_1\bt\A_1\bt\B_i$ et $\E\bt\A_2\bteq\C$.
Donc $\E_1\bt\B_i$ et $\E\bt\C$,
d'o\`u $\E\bt\B$ par applications r\'ep\'et\'ees de la r\`egle 1 de la d\'efinition de~$\bt$.
\smallskip
\hskip-10mm2. $\E_1 \bt\A_1$, $\E \bt\A_2$ et $\B$ est de la forme~$(2)$~:
idem (transitivit\'e et it\'eration de la r\`egle 1).
\smallskip
\hskip-10mm3. $\E_1=\A_1$, $\E_2 \bt\A_2$ et $\B$ est de la forme~$(1)$~:
alors $\E_1\bt\B_i$ et $\E_2\bt\C$, donc $\B$ est
aussi de la forme~$(1)$ vis \`a vis de~$\E$.
\smallskip
\hskip-10mm4. $\E_1=\A_1$, $\E_2 \bt\A_2$ et $\B$ est de la forme~$(2)$~:
ici $\B$ est de la forme~$(2)$ vis \`a vis de~$\E$.
\smallskip
\hskip-10mm5. $\E_2\bteq\A$~: alors $\E_2\bteq\A\bt\B$ d'o\`u $\E_2\bt\B$
et $\E\bt\B$.
\cqfd\sv}

{\bf Irr\'eflexivit\'e~:}
montrons par r\'ecurrence sur~$n$ que si $\A$ est un arbre de taille inf\'erieure
ou \'egale \`a~$n$, alors $\A\not\bt\A$. C'est \'evident si $n=0$.
Pour $n>0$, consid\'erons un \'eventuel arbre $\A$ de taille~$n$ tel
que $\A\bt \A$. On \'ecrit
$\A = \A_1\d\A_2$,
donc $\A_1\d\A_2\bt\A_1\cdotp\A_2$, et parmi les
trois possibilit\'es donn\'ees dans la d\'efinition de~$\bt$,
les deux premi\`eres sont par hypoth\`ese de r\'ecurrence exclues car $\A_1\not\bt\A_1$
et $\A_2\not\bt\A_2$. On a aussi $\A_2\ne\A$, donc
il reste une seule pos\-si\-bi\-lit\'e~:~$\A_2\bt\A$.
Mais on a~$\A\bt\A_2$ d'apr\`es la propri\'et\'e 3 de la d\'efinition de~$\bt$,
donc $\A_2\bt\A_2$ par transitivit\'e, ce qui est impossible.
\cqfd
\sv
{\bf Ordre total~:}
Soient $\A,\B$ deux arbres binaires, on montre par r\'ecurrence
sur la somme $n$ de leurs tailles que les relations $\A\not\bt\B$
et $\B\not\bt\A$ impliquent $\A = \B$, le cas $n=0$ \'etant
comme d'habitude trivial. Pour $n>0$ un des deux arbres est non nul, donc l'autre aussi car
$\X\bt\O$ pour tout arbre~$\X$ non nul.
On \'ecrit $\A = \A_1\d\A_2$,
$\B = \B_1\d\B_2$, et l'on a les six faits
suivants~:
$$\matrix{
(1) &\A_1\not\bt\B_1\text{ ou } \A\not\bt\B_2,\qquad&
(2) &\A_1\ne\B_1    \text{ ou } \A_2\not\bt\B_2,\qquad&
(3) &\A_2\not\bteq\B,\cr\noalign{\smallskip}
(4) &\B_1\not\bt\A_1\text{ ou } \B\not\bt\A_2,\qquad&
(5) &\B_1\ne\A_1    \text{ ou } \B_2\not\bt\A_2,\qquad&
(6) &\B_2\not\bteq\A.\cr
}$$
D'apr\`es l'hypoth\`ese de r\'ecurrence, tous les couples d'arbres apparaissant
dans ces n\'egations sont comparables. $(3)$ et~$(4)$ impliquent $\A_1\bteq\B_1$,
$(1)$ et~$(6)$ impliquent $\B_1\bteq\A_1$, donc $\A_1=\B_1$
puis en reportant dans~$(2)$ et~$(5)$~: $\A_2=\B_2$,
soit finalement $\A=\B$.
\cqfd

\q{2}
On montre r\'ecurrence sur~$n$ que si $\A$ est de taille inf\'erieure
ou \'egale~\`a~$n$ et $\B$ est un sous-arbre strict de~$\A$,
alors $\A\bt\B$. Si $n=0$ il n'y a rien \`a d\'emontrer.
Si~$n>0$, soit $\A=\A_1\d\A_2$.
On a d\'ej\`a remarqu\'e que $\A\bt\A_2$,
donc si $\B$ est un sous-arbre de~$\A_2$, on
a~$\A\bt\A_2\bteq\B$ par hypoth\`ese de r\'ecurrence.
De m\^eme, si $\B$ est un sous-arbre de~$\A_1$,
alors on a~$\A_1\bteq\B$ par hypoth\`ese de r\'ecurrence, donc
il reste \`a prouver que l'on a~$\A\bt\A_1$.
\'Ecrivons $\A_1 = \A_{11}\d(\ \dots(\A_{1p}\d\O)\dots\ )$.
Alors $\A_1\bt\A_{1i}$ pour tout~$i$, donc $\A_1$ est
de la forme~$(1)$ vis \`a vis de~$\A$,
ce qui prouve que $\A\bt\A_1$.
\cqfd

\q{3}
{\bf Proposition~:} soient $\A=\A_1\d\A_2$ et $\B=\B_1\d\B_2$ deux arbres binaires
non nuls. Alors on a~:
$$\eqalign{
\A_1\bt\B_1 &\=> (\A\bt\B \<=>\rlap{$\A$}\phantom{\A_2}\bt\B_2),\cr
\A_1=\B_1   &\=> (\A\bt\B \<=>\A_2\bt\B_2),\cr
\A_1\bl\B_1 &\=> (\A\bt\B \<=>\A_2\bteq\rlap{$\B$}\phantom{\B_2}).
}$$
{\bf D\'emonstration~:}
si $\A_1\bt\B_1$ alors $\A\bt\B_2\=>\A\bt\B$ d'apr\`es la r\`egle~1,
et $\A\not\bt\B_2\=>\A_2\not\bteq\B_2\=>A\not\bt\B$ car aucune r\`egle ne s'applique \`a ce cas.
Le cas $\A_1=\B_1$ se traite de m\^eme, et le cas $\A_1\bl\B_1$ est une r\'e\'ecriture
de la r\`egle~3.\cqfd
\sv
On peut donc d\'ecider de la r\`egle \'eventuelle \`a appliquer pour comparer $\A$ et~$\B$
d\`es que l'on conna\^{\i}t l'ordre de classement de~$\A_1$ et~$\B_1$. Ceci donne l'algorithme
suivant~:
\sv
{\bfsl\cleartabs\settabs\+\hskip\leftskip\hskip5mm &\hskip5mm &\hskip5mm &\hskip5mm &\hskip5mm &\hskip5mm &\cr
\+&{\ssit compare}$(\A,\B) =$\cr
\+&&si $\A=\O$ {\it et} $\B=\O$ alors retourne {\ssf egal}\cr
\+&&sinon, si $\A=\O$ alors retourne {\ssf inf}\cr
\+&&sinon, si $\B=\O$ alors retourne {\ssf sup}\cr
\+&&sinon, {\it soient $\A_1,\A_2,\B_1,\B_2$ tels que $\A = \A_1\d\A_2$ et $\B = \B_1\d\B_2$~:}\cr
\+&&&$r :=\fct{\ssit compare}(\A_1,\B_1)$\cr
\+&&&si $r=$ {\ssf sup} alors retourne {\ssit compare}$(\A,\B_2)$\cr
\+&&&sinon, si $r=$ {\ssf egal} alors retourne {\ssit compare}$(\A_2,\B_2)$\cr
\+&&&sinon, retourne compare$(\A_2,\B)$\cr
\+&fin\cr
\sv
\+&{\ssit triangle\_noir}$(\A,\B) = (\fct{\ssit compare}(\A,\B) = \text{\ssf sup})$\cr
}
\sv
La terminaison de {\ssit compare} s'\'etablit par
r\'ecurrence sur la somme des tailles des arbres consid\'er\'es.
En ce qui concerne la complexit\'e, on montre \'egalement par r\'ecurrence
sur la somme des tailles $a,b$ de~$\A,\B$ que le nombre
d'appels \`a {\ssit compare\/} effectu\'es pour comparer $\A$ et~$\B$
est major\'e par $ab+1$.

\q{4}
Soit $\B$ un arbre binaire quelconque, on pose $s(\B) = \O\d\B$
et on montre que $s(\B)$ est le successeur de~$\B$ pour~$\bt$.
D\'ej\`a on a clairement $s(\B)\bt\B$, donc il reste \`a prouver
l'implication~:
$$\forall\ \A\in{\Bbb A}, \forall\ \B\in{\Bbb A},\
\A\bt\B\=>\A\bteq\O\d\B.$$
On d\'emontre cette propri\'et\'e\ \dots\ par r\'ecurrence sur la taille~$n$
de~$\A$. Pour $n=0$ il n'y a rien \`a d\'emontrer.
Si l'implication est vraie pour tous arbres $\A,\B$
tels que $\A$ est de taille inf\'erieure \`a~$n$, consid\'erons
un arbre~$\A$ de taille~$n$ tel que $\A\bt\B$,
arbre que l'on \'ecrit $\A = \A_1\d\A_2$~:
\sv
{\marge{\hskip5mm}
si $\A_1\ne\O$, alors $\A\bt\O\d\B$
d'apr\`es la propri\'et\'e 1 de la d\'efinition de~$\bt$.
\smallskip
si $\A_1=\O$ et $\B=\O$, alors $\A_2\bteq\O$
donc $\A\bteq\O\d\O$.
\smallskip
si $\A_1=\O$ et $\B = \B_1\d\B_2$ avec $\B_1\ne\O$,
on a $\A_2\bteq\B$ (cas 3 de la d\'efinition de~$\bt$), d'o\`u $\A\bteq\O\d\B$.
\smallskip
si $\A_1=\O$ et $\B = \O\d\B_2$,
alors on a $\A_2\bt\B_2$ (cas 2 de la d\'efinition de~$\bt$)
ou $\A_2\bteq\B$ (cas 3)~:
\par{\marge{\hskip5mm}
si $\A_2\bt\B_2$ alors $\A_2\bteq\O\d\B_2$
par hypoth\`ese de r\'ecurrence, d'o\`u $\A\bteq\O\d\B$.
\par
si $\A_2\bteq\B$ alors $\A=\O\d\A_2\bteq\O\d\B$.
\cqfd\sv}}
En conclusion~: $s_{\bt}(\B) = \O\d\B$.

\q{5}
Le proc\'ed\'e de construction des~$\A_i$ est clairement valide, et il
fournit une suite infinie strictement d\'ecroissante. Par ailleurs
la suite des longueurs des~$\A_i$ est croissante au sens large.
Enfin, $\O$ n'ayant pas de minorant ne peut appartenir \`a une suite infinie
strictement d\'ecroissante, donc $\A_i\ne\O$.
\'Ecrivons $\A_i = \B_i\d\C_i$. Parmi les trois
possibilit\'es pour avoir $\B_i\d\C_i\bt\B_{i+1}\d\C_{i+1}$
la troisi\`eme est exclue, car~:
\sv\goodbreak{\marge{\hskip5mm}
si $\C_i\bt\A_{i+1}$ alors
$\A_{i-1}\bt\A_i\bt\C_i\bt\A_{i+1}$ donc on peut remplacer
dans la suite $(\A_n)$ l'arbre $\A_i$ par $\C_i$ sans
perdre la d\'ecroissance stricte, en contradiction avec le caract\`ere minimal de~$\A_i$.
\smallskip
si $\C_i = \A_{i+1}$ alors $\A_{i+1}$ a une taille strictement
inf\'erieure \`a~$\A_i$, c'est impossible.
\sv}
On en d\'eduit que la comparaison de~$\A_i$ avec~$\A_{i+1}$ se fait
toujours sur les cas 1 ou 2, donc la suite $(\B_i)$ est d\'ecroissante au
sens large. Si elle prend une infinit\'e de valeurs distinctes, alors on peut
en extraire une suite strictement d\'ecroissante~$(\B_{i_k})$,
donc la suite $(\A_0,\dots,\A_{i_0-1},\B_{i_0},\B_{i_1},\dots\ )$
est une suite infinie strictement d\'ecroissante contredisant la
pertinence du choix de~$\A_{i_0}$. Si au contraire la suite $(\B_i)$
ne prend qu'un nombre fini de valeurs distinctes, alors \`a partir d'un certain
rang seul le cas~2 s'applique, la suite $(\C_i)$ est strictement d\'ecroissante
\`a partir de ce rang, et on conclut l\`a aussi qu'un des arbres $\A_i$
a \'et\'e mal choisi.

\q{6}
On d\'emontre par r\'ecurrence sur $n$ que si $\A$ et $\B$
sont des arbres ordonn\'es de tailles inf\'erieures ou \'egales \`a~$n$
tels que $\A\succ\B$ alors $\A\bt\B$. Il n'y a rien
\`a d\'emontrer si $n=0$, et c'est \'evident dans le cas g\'en\'eral si~$\B = \O$.
Pour $n>0$ et $\B\ne\O$ on a aussi $\A\ne\O$. \'Ecrivons
$\A = \A_1\d\A_2$
et $\B = \B_1\d(\ \dots(\B_p\d\O)\dots\ )
= \B_1\d\C$~:
\sv{\marge{\hskip5mm}
si $\A_1 = \B_1$ alors $\A_2\succ\C$,
donc par hypoth\`ese de r\'ecurrence $\A_2\bt\C$, et l'on a bien
$\A\bt\B$.
\smallskip
sinon $\A_1 \succ \B_1$, donc $\A_1\succ\B_i$ pour
tout~$i$ puisque $\B$ est ordonn\'e. On a alors, par hypoth\`ese de r\'ecurrence,
$\A_1\bt\B_i$ pour tout~$i$, ce qui prouve que $\A\bt\B$
d'apr\`es le lemme vu en question~{\bf 1}.
\par}

\q{7}
C'est \'evident.

\q{8}
On peut d\'emontrer assez facilement que si $\psi$ existe, alors~:
$$\psi((\O\d\O)\d\O) = (\O\d\O)\d\O\quad\text{et}\quad
\psi(((\O\d\O)\d\O)\d\O) = (\O\d(\O\d\O))\d\O,$$ mais le calcul
de $\psi((((\O\d\O)\d\O)\d\O)\d\O)$ est plus d\'elicat, et la d\'emonstration
de l'existence de~$\psi$ n\'ecessite d'\'elever le niveau du discours.
Nous allons donc ici pr\'esenter bri\`evement la th\'eorie des ordinaux de Cantor et en
d\'eduire une construction explicite de~$\psi$.
\sv
\centerline{\bf Nombres ordinaux}\sv
Soit $\omega$ un symbole abstrait.
On convient de repr\'esenter un arbre ordonn\'e $\A$ par une expression formelle
en~$\omega$, $\expr(\A)$, o\`u la fonction $\expr$ est d\'efinie r\'ecursivement par~:
$$\expr(\O) = 0,\qquad \expr(\A_1\d\A_2) = \omega^{\fct{\petit\ssf expr}(\A_1)} + \expr(\A_2).$$
Cette d\'efinition est copi\'ee sur celle de la fonction \erbra\ donn\'ee dans la partie~{\bf 1},
question~{\bf 5}~; on a juste remplac\'e la base $b$ utilis\'ee dans cette question par la
base abstraite~$\omega$. Par analogie avec la d\'ecomposition compl\`ete d'un entier en
base~$b$, on convient de simplifier $\omega^0$ en~$1$, $\omega^a+\dots+\omega^a$ en
$k\omega^a$ o\`u $k\in\N$ est le nombre de $\omega^a$, et de ne pas \'ecrire le z\'ero final dans une somme de plusieurs termes.
Les expressions formelles obtenues sont appel\'ees {\it nombres ordinaux}.
La figure ci-dessous pr\'esente quelques arbres ordonn\'es et les ordinaux associ\'es.
\sv
\leavevmode\hskip5mm{\advance\hsize-5mm\advance\hsize-\leftskip\hsize=0.2\hsize\leftskip=0mm\valign{\vfill#\cr
\bin{\O}{\bin{\O}8.5pt{\O}}
\sv\hskip5mm$2$
\cr
\bin{\bin{\O}8.5pt{\O}}{\O}
\sv\hskip5mm$\omega$
\cr
\bin{\bin{\O}1em{\O}}2pt{\ligne{-10pt}{10pt}{\bin{\O}1em{\O}}}
\sv\hskip5mm$\omega+1$
\cr
\bin{\bin{\O}1em{\O}}-10pt{\ligne{-9pt}{10pt}{\bin{\bin{\O}1em{\O}}{\O}}}
\sv\hskip5mm$2\omega$
\cr
\bin{\bin{\bin{\O}8.5pt{\O}}{\O}}-8pt{\O}
\sv\hskip5mm$\omega^\omega$
\cr}}
\sv
La relation d'ordre $\succ$ entre arbres ordonn\'es induit une relation d'ordre
entre nombres ordinaux, aussi not\'ee $\succ$. On a donc~:
$$0\prec1\prec2\prec\dots\prec1000^{1000}\prec\dots\prec\omega\prec\omega+1\prec\dots\prec\omega^2\prec\dots\prec\omega^3\prec\dots\prec\omega^\omega\prec\dots\prec\omega^{\omega^\omega}\prec\dots$$
Ainsi, $\omega$ appara\^{\i}t comme un ordinal infini, au sens o\`u il est plus grand
que tout nombre entier, de m\^eme que $\omega+1$, $\omega^\omega$, etc.
En fait $\omega$ est le plus petit ordinal infini, et l'arbre ordonn\'e associ\'e
\`a un ordinal est la d\'ecomposition compl\`ete de cet ordinal en base~$\omega$.
Il existe dans la th\'eorie des ensembles de Cantor d'autres ordinaux n'ayant
pas de d\'ecomposition compl\`ete en base~$\omega$, par exemple~:
$$\omega^{\omega^{\omega^{\adots}}}$$
o\`u le "nombre" d'exposants est \'egal \`a~$\omega$, mais nous n'en auront pas besoin ici.
Dans la suite de cet expos\'e, le terme "ordinal" d\'esigne donc en fait un "ordinal
repr\'esentable par un arbre ordonn\'e", et nous conviendrons de confondre un
nombre entier~$k$ avec l'ordinal fini correspondant.
\sv
\centerline{\bf D\'ecomposition euclidienne d'un ordinal infini}\sv
Soit $a = \omega^{a_1} + \dots + \omega^{a_n} + k$ un ordinal
\'ecrit comme une somme de puissances d\'ecroissantes de~$\omega$ et d'un entier~$k$.
L'exposant maximal de~$a$ est ind\'efini si $a=0$, nul si $a=k$, et \'egal \`a $a_n$ si $a$ est
un ordinal infini. En termes d'arbres ordonn\'es, si $\A$ est l'arbre ordonn\'e
associ\'e \`a~$a$, alors l'arbre ordonn\'e associ\'e \`a l'exposant maximal
de~$a$ est la branche gauche de~$\A$ lorsque $\A\ne\O$.
Si $a$ admet un exposant maximal $a_1$ et si $a_1\succ0$, alors le sur-exposant
maximal de~$a$ est par d\'efinition l'exposant maximal de~$a_1$.
Si $a_1$ est ind\'efini ou si $a_1=0$, c'est-\`a-dire si $a$ est un ordinal fini,
alors $a$ n'a pas de sur-exposant maximal.
\sv
Soit $a=\omega^{a_1} + \dots + \omega^{a_n} + k$ un ordinal infini
et $b$ son sur-exposant maximal. Comme la suite $(a_i)$ est d\'ecroissante pour~$\succ$,
il existe un entier~$p\in{[[1,n]]}$ tel que $a_1\succeq\dots\succeq a_p\succeq\omega^b\succ a_{p+1}$.
Pour $i\le p$, \'ecrivons $a_i = \omega^b + a'_i$.
La d\'ecomposition euclidienne de~$a$ est~:
$$a = \omega^{\omega^b}q + r\qquad
\text{avec  }q = \omega^{a'_1} + \dots + \omega^{a'_p}
\text{ et }r = \omega^{a_{p+1}} + \dots + \omega^{a_n} + k.$$
Dans cette d\'ecomposition, la multiplication de $\omega^{\omega^b}$ par $q$
est \`a interpr\'eter formellement, on additionne $\omega^b$ \`a chaque exposant de la d\'ecomposition
de~$q$. Cette d\'ecomposition n'est pas due \`a Euclide, mais nous l'avons appel\'ee
ainsi par analogie avec la division euclidienne des entiers. En effet, on
a par construction $0\preceq r\prec\omega^{\omega^b}$.
Remarquons aussi que nous avons $0\prec q$, et le sur-exposant maximal de~$q$,
s'il existe, est inf\'erieur ou \'egal \`a~$b$.
\sv
En termes d'arbres ordonn\'es, on obtient la d\'ecomposition euclidienne d'un
arbre $\A\succeq(\O\d\O)\d\O$ de la mani\`ere suivante~:
{\sv\marge{\hskip5mm1. }
On \'ecrit $\A = \A_1\d(\ \dots(\A_n\d(\O\d(\ \dots(\O\d\O)\dots\ )))\dots\ )$ avec $\A_i\succ\O$.
\smallskip
\enmarge{2. }On d\'ecompose $\A_1 = \B\d\A'_1$, \dots, $\A_p = \B\d\A'_p$ o\`u $p$
est le plus grand entier tel que $\A_p$ ait m\^eme branche gauche que~$\A_1$.
\smallskip
\enmarge{3. }$\B$ est l'arbre ordonn\'e associ\'e \`a~$b$, l'arbre ordonn\'e associ\'e
\`a~$q$ est $\Q = \A'_1\d(\ \dots(\A'_p\d\O)\dots\ )$ et l'arbre ordonn\'e
associ\'e \`a~$r$ est le reste de~$\A$~: $\R = \A_{p+1}\d(\ \dots(\A_n\d(\O\d(\ \dots(\O\d\O)\dots\ )))\dots\ )$.
\sv}
\centerline{\bf Concat\'enation de deux arbres}\sv
Soient $\A,\B\in{\Bbb A}$. On construit un nouvel arbre not\'e $\A::\B$
en rempla\c{c}ant dans~$\A$ le~$\O$ le plus \`a droite par~$\B$.
Formellement, $\A::\B$ est d\'efini par les relations~:
$$\O::\B = \B,\qquad (\A_1\d\A_2)::\B = \A_1\d(\A_2::\B).$$
On montre facilement par r\'ecurrence sur la taille de~$\B$ que si $\A_1\bt\A_2$
alors $\A_1::\B\bt\A_2::\B$.
\sv
\centerline{\bf La fonction~$\psi$}\sv
Soit $\A\in{\Bbb O}$ et $a$ l'ordinal repr\'esent\'e par~$\A$. On note $\psi(\A)$
l'arbre d\'efini r\'ecursivement par les relations suivantes~:
\sv{\marge{\hskip5mm}
Si $a$ est un ordinal fini alors $\psi(\A) = \A$.\smallskip
Si $a$ est un ordinal infini, soit $a=\omega^{\omega^b}q+r$ sa d\'ecomposition
euclidienne. On note $b'$, $q''$ les ordinaux suivants~:
\smallskip{\marge{\hskip5mm}
si $b$ est un ordinal fini alors $b'=b+1$, sinon $b'=b$~;\par
si $q$ est un ordinal fini alors $q''= q-1$, sinon $q''=q$.
\smallskip}
Soient $\B',\Q'',\R$ les arbres ordonn\'es associ\'es \`a $b',q'',r$.
Alors $\psi(\A) = \psi(\R)::(\psi(\B')\d\psi(\Q''))$.
\sv}
{\bf Proposition~:} la fonction $\psi$ est bien d\'efinie et elle r\'ealise
un isomorphisme entre les ordres $({\Bbb O},\succ)$ et~$({\Bbb A},\bt)$.
\sv
La d\'emonstration est scind\'ee en plusieurs \'etapes.
\sv
{\bf 1. Bonne d\'efinition de~$\psi$~:}
si $a$ est un ordinal fini alors $\psi(\A)$ est
bien d\'efini. Si $a$ est infini, alors
les arbres $\B'$, $\Q''$ et $\R$ ont strictement moins de n\oe uds
que~$\A$ et un arbre ayant z\'ero ou un n\oe ud repr\'esente un ordinal fini.
Donc, par r\'ecurrence sur la taille de~$\A$, $\psi(\A)$ est
bien d\'efini.
\sv
{\bf 2. Forme de~$\psi(\A)$~:} on montre par une r\'ecurrence imm\'ediate
sur la taille de~$\A$ que
si $\A\ne\O$ alors $\psi(\A)\ne\O$, et $\psi(\A)$ est de la forme
$\psi(\C_1)\d(\ \dots(\psi(\C_k)\d\O)\dots\ )$ o\`u chaque $\C_i$ est un arbre
ordonn\'e de taille inf\'erieure \`a celle de~$\A$ tel que $C_i=\O$ si $\A$ repr\'esente un ordinal fini, et
$\C_i\preceq\B'$ si $\A$ repr\'esente un ordinal infini avec les notations
de la d\'efinition de~$\psi$.
\sv
{\bf 3. Croissance de~$\psi$~:}
on montre par r\'ecurrence sur~$n$ que si $\A_1$ et $\A_2$ sont deux
arbres ordonn\'es de tailles inf\'erieures ou \'egales \`a~$n$
tels que $\A_1\succ \A_2$, alors $\psi(\A_1)\bt\psi(\A_2)$.
Notons $a_1,a_2$ les ordinaux associ\'es \`a~$\A_1,\A_2$ et
$a_1=\omega^{\omega^{b_1}}q_1+r_1$, $a_2=\omega^{\omega^{b_2}}q_2+r_2$
les d\'ecompositions euclidiennes \'eventuelles de $a_1$ et~$a_2$.
Pour $n=0$ il n'y a rien \`a prouver.
Si $a_1$ est fini alors $a_2$ l'est aussi donc
$\psi(\A_1)=\A_1\bt\A_2=\psi(\A_2)$ car $\bt$ et $\succ$ co\"{\i}ncident sur~${\Bbb O}$.
Si $a_1$ est infini et $a_2$ est fini, alors comme $b_1'\ne0$,
on a~:
$
(\O\d\O)\d\O
\bleq
\psi(\B_1')\d\O
\bleq
\psi(\B_1')\d\psi(\Q_1'')
\bleq
\psi(\A_1)
$,
et $(\O\d\O)\d\O$ majore strictement pour~$\bt$ tout arbre ordonn\'e repr\'esentant un ordinal fini,
d'o\`u $\psi(\A_1)\bt\psi(\A_2)$.
Supposons \`a pr\'esent $a_1$ et $a_2$ infinis. On distingue trois cas.
\sv{\marge{\hskip5mm}
Cas $b_1\succ b_2$~: alors $b'_1\succ b'_2$ donc
$\psi(\B_1')\bt\psi(\B_2')$ par hypoth\`ese de r\'ecurrence.
$\psi(\A_2)$ est de la forme $\psi(\C_1)\d(\ \dots(\psi(\C_k)\d\O)\dots\ )$
o\`u $\C_i \preceq \B'_2$ pour tout~$i$, d'o\`u $\C_i\prec\B'_1$ par transitivit\'e,
et $\psi(\C_i)\bl\psi(\B'_1)$ par hypoth\`ese de r\'ecurrence.
On en d\'eduit $\psi(\A_2)\bl\psi(\B'_1)\d\O\bleq\psi(\A_1)$.
\sv
Cas $b_1=b_2$, $q_1\succ q_2$~: alors $q''_1\succ q''_2$ donc $\psi(\Q_1'')\bt\psi(\Q_2'')$
par hypoth\`ese de r\'ecurrence. On a alors $\psi(\B_1')\d\psi(\Q_1'')\bt\psi(\B_2')\d\psi(\Q_2'')$,
puis $\psi(\B_1')\d\psi(\Q_1'')\bt\psi(\R_2)::(\psi(\B_2')\d\psi(\Q_2''))$
d'apr\`es la forme de~$\R_2$ et le fait que $r_2\prec\omega^{\omega^{b_2}}$,
d'o\`u $\psi(\A_1)\bteq\psi(\B'_1)\d\psi(\Q_1'')\bt\psi(\A_2)$.
\sv
Cas $b_1=b_2$, $q_1=q_2$, $r_1\succ r_2$~: alors $\psi(\R_1)\bt\psi(\R_2)$
par hypoth\`ese de r\'ecurrence, et l'on en d\'eduit, d'apr\`es la propri\'et\'e de croissance
de la concat\'enation~:
$\psi(\R_1)::(\psi(\B'_1)\d\psi(\Q''_1)) \bt \psi(\R_2)::(\psi(\B'_2)\d\psi(\Q''_2))$.
\sv}
{\bf 4. Bijectivit\'e de~$\psi$~:} on sait d\'ej\`a que $\psi$ est injective, puisque
strictement croissante entre deux ensembles totalement ordonn\'es. Il reste \`a prouver
que tout arbre~$\X\in{\Bbb A}$ admet un ant\'ec\'edent par~$\psi$. On proc\`ede
par r\'ecurrence sur la taille de~$\X$. Si $\X$ est l'arbre ordonn\'e associ\'e
\`a un ordinal fini alors $\X=\psi(\X)$.
Sinon, soit $\X=\X_1\d(\ \dots(\X_n\d\O)\dots\ )$, et soit $p$ le premier indice
tel que $\X_p = \max(\X_1,\dots,\X_n)$. On \'ecrit $\X=\U::(\X_1\d\V)$ et
$\U,\X_1,\V$ ont des tailles inf\'erieures \`a celle de~$\X$, donc il existe des
arbres ordonn\'es $\R,\C,\D$ tels que $\U=\psi(\R)$, $\X_1=\psi(\C)$
et $\V=\psi(\D)$. Soient $r,c,d$ les ordinaux associ\'es. Avec les notations de la
d\'efinition de~$\psi$, il existe des ordinaux $b,q$ tels que $c=b'$ et $d=q''$
car $c\succ 0$, $\X$ ne repr\'esentant pas un ordinal fini.
Par choix de~$p$ et d'apr\`es la forme des arbres $\psi(\R)$ et $\psi(\D) = \psi(\Q'')$,
$b$ majore strictement le sur-exposant maximal de~$r$ s'il existe, et $b$ majore au sens
large le sur-exposant maximal de~$q$ s'il existe, donc $\smash{\omega^{\omega^b}q+r}$
est une d\'ecomposition euclidienne valide. Soit $a$ l'ordinal ayant cette d\'ecomposition
et~$\A$ l'arbre ordonn\'e associ\'e \`a~$a$, on a $\X=\psi(\A)$.
\cqfd
\sv\centerline{\bf R\'eponse \`a la question pos\'ee}\sv
La fonction~$\psi$ construite r\'epond aux conditions de l'\'enonc\'e, et c'est la seule.
On a~:
$$\eqalign{
\psi((\O\d\O)\d\O) &= (\O\d\O)\d\O,\cr
\psi(((\O\d\O)\d\O)\d\O) &= (\O\d(\O\d\O))\d\O,\cr
\psi((((\O\d\O)\d\O)\d\O)\d\O) &= (((\O\d\O)\d\O)\d\O.\cr
}$$
\sv
{\bf D\'emonstration~:} puisque $\psi$ est un isomorphisme entre
$({\Bbb O},\succ)$ et $({\Bbb A},\bt)$, $\psi$ commute avec les fonctions
"successeur" et "borne sup\'erieure" et l'on a aussi $\psi(\O)=\O$ par
d\'efinition, donc $\psi$ est une solution au probl\`eme pos\'e.
On obtient les valeurs de~$\psi((\O\d\O)\d\O))$, etc. par application de
la d\'efinition de~$\psi$.
\sv
Supposons qu'il existe une autre solution $\psi_1\ne\psi$ et consid\'erons
${\Bbb E} = \{\A\in{\Bbb O}\text{ tq }\psi_1(\A)\ne\psi(\A)\}$.
On d\'emontre par l'absurde que $\Bbb E$ n'a pas de plus petit \'el\'ement
pour l'ordre~$\succ$~:
si $\A=\min_\succ({\Bbb E})$ alors pour tout arbre $\B\in{\Bbb O}$
tel que $\B\prec\A$, on a $\psi_1(\B) = \psi(\B)$, d'o\`u
$\psi_1(s_\succ(\B)) = s_\bt(\psi_1(\B)) =  s_\bt(\psi(\B)) = \psi(s_\succ(\B))$.
On en d\'eduit~:
$$\forall\ \B\in{\Bbb O},\ s_\succ(\B)\preceq\A\=>\psi_1(s_\succ(\B)) = \psi(s_\succ(\B)),$$
et ceci est contradictoire avec la compatibilit\'e de~$\psi$ et $\psi_1$
avec la borne sup\'erieure, car $\A$ est la borne sup\'erieure des arbres
$s_\succ(\B)$ consid\'er\'es. L'hypoth\`ese $\A=\min_\succ({\Bbb E})$ est donc
absurde, comme annonc\'e. Mais alors on obtient \`a nouveau une contradiction,
car $\Bbb E$ est un ensemble non vide sans plus petit \'el\'ement,
donc on peut construire de proche en proche une suite strictement
d\'ecroissante d'\'el\'ements de~$\Bbb E$, en contradiction avec la bonne fondation
de~$({\Bbb O},\succ)$. Tout compte fait l'existence d'une
fonction~$\psi_1\ne\psi$ est impossible.
\cqfd\sv
{\it Les auteurs de ce corrig\'e s'excusent d'avoir mis en \oe uvre une machinerie aussi lourde
pour r\'epondre \`a cette question, mais ils ont s\'ech\'e dessus pendant plusieurs jours et n'ont
pas trouv\'e de moyen plus simple pour la r\'esoudre.}


                     %+-------------------------+
                     %|  Un ordre sur les mots  |
                     %+-------------------------+

\SV\goodbreak\centerline{\Gros\bf 5.  Un ordre sur les mots}
\mark{5.  Un ordre sur les mots}
\sv
{\hskip-\leftskip\it Coquille de l'\'enonc\'e. Lire~: $\app\varphi{\N}{\N}$ strictement croissante.}
\q{1}
$(a)\=>(b)$~:
on peut prendre ${>} = {\gt}$, donc $(E,>)$ est bien fond\'e.
Supposons que $E$ contient une anticha\^{\i}ne infinie. On extrait de
cette anticha\^{\i}ne une suite $(x_i)$ sans r\'ep\'etitions, et on prolonge
$>$ en posant~:
$$(x\gt y) \<=> (x > y) \text{ ou } (\text{il existe $i > j$ tels que } x \ge x_j \text{ et }x_i \ge y).$$
V\'erifions que $\gt$ est un ordre strict.
Si $x,y,z$ sont tels que $x\gt y$ et $y\gt z$ alors il y a 4 cas~:
{\sv\marge{\hskip5mm}
$x>y$ et $y>z$~: alors $x>z$ donc $x\gt z$.
\smallskip
$x>y$, $y \ge x_j$, $x_i \ge z$, $i>j$~: alors $x \ge x_j$ et $x_i \ge z$  donc $x\gt z$.
\smallskip
$x \ge x_j$, $x_i \ge y$, $y>z$, $i>j$~: idem.
\smallskip
$x \ge x_j$, $x_i \ge y$, $y \ge x_\ell$, $x_k \ge z$, $i>j$, $k>\ell$~:
alors $x_i\ge x_\ell$ donc $k > \ell=i > j$ et $x \ge x_j$, $x_k \ge z$, d'o\`u $x\gt z$.
\sv}
En prenant $z=x$ dans la discussion pr\'ec\'edente, on constate imm\'ediatement
que les relations $x\gt y$ et $y\gt x$ sont contradictoires, donc $\gt$ est
bien un ordre strict prolongeant $>$. Pourtant $\gt$ est mal fond\'e
car la suite $(x_i)$ est strictement d\'ecroissante pour cet ordre, on a
obtenu la contradiction cherch\'ee.
\sv

$(b)\=>(c)$~: on raisonne encore par l'absurde en supposant qu'il
existe une mauvaise suite, $(x_i)$. On pose $x^0 = x_0$. Comme $x_0$ n'est major\'e
par aucun $x_i$ tel que $i>0$, on peut partitionner la suite $(x_i)_{i\ge 1}$
en deux sous-suites~: la sous-suite constitu\'ee des $x_i$ tels que $x_i < x_0$, et
la sous-suite constitu\'ee des autres $x_i$, qui sont incomparables \`a~$x_0$.
L'une de ces deux sous-suites est infinie, notons la $(x_i^1)$ et soit $x^1$
son premier terme.
On partitionne alors la sous-suite $(x_i^1)_{i\ge 1}$ en \'el\'ements inf\'erieurs \`a $x^1$ et
en \'el\'ements incomparables \`a~$x^1$, et on nomme $(x_i^2)$ celle qui est infinie
ou l'une des deux si elles sont toutes deux infinies, et $x^2$ le premier
terme de cette suite. Et ainsi de suite. On a ainsi constitu\'e une suite $(x^i)$ telle
que pour $i<j$, soit $x^i > x^j$, soit $x^i$ et $x^j$ sont incomparables, et
le cas qui a lieu est ind\'ependant de~$j$. Puisque $(E,>)$ est bien fond\'e,
la suite $(x^i)$ ne contient aucune sous-suite strictement d\'ecroissante, donc
il existe une infinit\'e d'indices $i$ tels que $x^i$ et $x^{i+1}$ sont incomparables.
L'ensemble des $x^i$ correspondants \`a ces indices constitue une anticha\^{\i}ne infinie.
\sv

$(c)\=>(a)$~: s'il existe un ordre $\gt$ mal fond\'e prolongeant $>$, soit $(x_i)$ une
suite infinie strictement d\'ecroissante pour cet ordre. Elle est bonne pour~$>$,
donc il existe $i<j$ tels que $x_i \le x_j$. Comme $x_i\gt x_j$, on a aussi
$x_i \ne x_j$, d'o\`u $x_i < x_j$ puis $x_i\lt x_j$, contradiction.
\sv

$(b)\=>(d)$~: m\^eme raisonnement que $(b)\=>(c)$, en partitionnant la
suite $(x_i^k)$ en trois sous-suites selon que $x_i^k < x^k$, $x_i^k \ge x^k$
et $x_i^k$ est incomparable \`a $x^k$.

\sv
$(d)\=>(c)$~: \'evident.

\q{2}
{\it L'\'enonc\'e est confus. Disons que $A$ est un alphabet fini ou infini ordonn\'e, que $\alpha$
d\'esigne un mot non vide dans la r\`egle $\alpha\dt\varepsilon$, et que $\alpha$
et $\beta$ d\'esignent des mots quelconques dans les deux r\`egles suivantes.
Disons aussi que \c{c}a commence \`a bien faire tous ces symboles de
relation d'ordre plus bizarres les uns que les autres et impossibles
\`a calligraphier calmement au bout de 4h de r\'eflexion, et qu'il est temps
que le probl\`eme se termine.}
\sv
{\bf Proposition~:}
soient $\alpha = a_1\dots a_n$ et $\beta=b_1\dots b_p\in A^*$.
Alors~:
$$\eqalign{
(\alpha\dteq\beta) \<=> &(\text{il existe }1\le i_1<\dots<i_p\le n\text{ tels que }a_{i_1}\ge_A b_1,\dots, a_{i_p}\ge_A b_p)\cr
&\text{\it (condition v\'erifi\'ee par convention si $p=0$)}.\cr
}$$
{\bf D\'emonstration~:} par r\'ecurrence sur~$n$.
On note $\alpha\succeq\beta$ le deuxi\`eme membre de l'\'equivalence annonc\'ee.
Pour $n=0$, les \'enonc\'es $\alpha\dteq\beta$ et $\alpha\succeq\beta$
sont \'equivalents d'apr\`es la convention adopt\'ee lorsque $\beta=\varepsilon$.
Pour $n>0$, si $\alpha\dteq\beta$ alors on a l'un des cinq cas suivants
o\`u $a,b$ d\'esignent des lettres et $\alpha',\beta'$ des mots~:
\sv{\marge{\hskip5mm}\obeylines%
$(1)\quad\alpha=\beta$,
$(2)\quad\alpha=a$ et $\beta=b$ avec $a>_A b$,
$(3)\quad\beta=\varepsilon$,
$(4)\quad\alpha = a\alpha'$, $\beta=b\beta'$ avec $a\ge_Ab$ et $\alpha'\dt\beta'$,
$(5)\quad\alpha = a\alpha'$ avec $\alpha'\dteq\beta$.
\sv\goodbreak}
Dans chaque cas on obtient $\alpha\succeq\beta$, soit directement, soit en
appliquant l'hypoth\`ese de r\'ecurrence \`a $\alpha'$.
Supposons \`a pr\'esent $\alpha\succeq\beta$ et soit $(i_1,\dots,i_p)$ une
suite strictement croissante d'indices tels que $a_{i_j}\ge_Ab_j$. Si $\alpha\ne\beta$
et $\beta\ne\varepsilon$, il faut montrer que l'un des cas $(2),(4)$ ou~$(5)$ a lieu.
Lorsque $n=1$ on a $p=1$ puisque $\beta\ne\varepsilon$, donc $a_1\ge_Ab_1$
et $a_1\ne b_1$ puisque $\alpha\ne\beta$, d'o\`u~$(1)$.
Lorsque $n>1$ et $i_1=1$, on a $\alpha=a_1\alpha'$ et $\beta=b_1\beta'$
avec $a_1\ge_Ab_1$ et $\alpha'\succeq\beta'$, donc $\alpha'\dteq\beta'$ par hypoth\`ese de r\'ecurrence,
d'o\`u~$(4)$. Enfin, lorsque $n>1$ et $i_1>1$ on a~$\alpha=a_1\alpha'$ et
$\alpha'\succeq\beta$, donc $\alpha'\dteq\beta$ par hypoth\`ese
de r\'ecurrence, d'o\`u~$(5)$.
\cqfd
\sv
{\bf $(A^*,\dt)$ est un bel ordre $\=>$ $(A,>_A)$ est un bel ordre~:}
car toute suite de lettres bonne pour $\dt_A$ est bonne pour~$>_A$.
\cqfd
\sv
{\bf $(A,>_A)$ est un bel ordre $\=>$ $(A^*,\dt)$ est un bel ordre~:}
s'il existe une suite infinie $(\alpha_n)$ de mots mauvaise pour~$\dt$ alors, comme au~{\bf 4.5}, on peut se ramener au cas o\`u $\alpha_n$
est un mot de longueur minimale parmi ceux tels que $(\alpha_0,\dots,\alpha_n)$
est le d\'ebut d'une suite mauvaise. Aucun des mots $\alpha_n$ n'est vide puisque
$\alpha_n\not\dleq\alpha_{n+1}$, on note~$a_n$ la premi\`ere lettre
de~$\alpha_n$ et $\alpha_n = a_n\beta_n$. En proc\'edant de m\^eme qu'\`a la question~$1$, on peut extraire
une suite $(a_{n_k})$ telle que l'une des trois relations a lieu~:
\sv{\marge{\hskip5mm}
1. $\forall\ k<\ell,$ $a_{n_k}>_A a_{n_\ell}$,\par
2. $\forall\ k<\ell,$ $a_{n_k}\le_A a_{n_\ell}$,\par
3. $\forall\ k<\ell,$ $a_{n_k}$ et $a_{n_\ell}$ sont incomparables.\par
}
\sv
Les cas 1. et 3. sont exclus car $(A,>_A)$ est un bel ordre.
Dans le cas~2, si la suite $(\beta_{n_k})$ est bonne alors
il existe $k<\ell$ tels que $\beta_{n_k}\dleq\beta_{n_\ell}$,
donc $n_k < n_\ell$ et $\alpha_{n_k}\dleq\alpha_{n_\ell}$,
ce qui est absurde puisque $(\alpha_n)$ est mauvaise.
Reste le cas o\`u $(\beta_{n_k})$ est mauvaise~: alors
la suite $(\alpha_0,\dots,\alpha_{{n_0}-1},\beta_{n_0},\beta_{n_1},\dots\ )$
est elle aussi mauvaise (car $\alpha_i\not\dleq\alpha_j\=>\alpha_i\not\dleq\beta_j$), en contradiction avec le choix de $\alpha_{n_0}$.
\cqfd
\SV
\centerline{\it
\vrule width 1.5cm height 2pt depth -1.6pt
\quad fin du corrig\'e\quad
\vrule width 1.5cm height 2pt depth -1.6pt
}

\bye

