An exercise on Goodstein sequences.

1 files changed, 129 insertions, 2 deletions

diff --git a/controle-20260622.tex b/controle-20260622.tex
index 266e314..e64e2c7 100644
--- a/controle-20260622.tex
+++ b/controle-20260622.tex
@@ -105,9 +105,9 @@ L'usage des appareils électroniques est interdit.
 Durée : 2h
 
 \ifcorrige
-Ce corrigé comporte \textcolor{red}{XXX} pages (page de garde incluse).
+Ce corrigé comporte \textcolor{red}{(à remplir)} pages (page de garde incluse).
 \else
-Cet énoncé comporte \textcolor{red}{XXX} pages (page de garde incluse).
+Cet énoncé comporte \textcolor{red}{(à remplir)} pages (page de garde incluse).
 \fi
 
 \vfill
@@ -662,4 +662,131 @@ ligne $3$).
 %
 %
 %
+
+\exercise
+
+Si $b\geq 2$ est un entier naturel, on rappelle que l'écriture en
+base $b$ d'un entier naturel $n$ est l'unique écriture
+\[
+n = b^{e_s}\, c_s + \cdots + b^{e_1}\, c_1
+\]
+où $e_s > \cdots > e_1$ (appelés les \emph{exposants} de l'écriture)
+et $1\leq c_s,\ldots,c_1\leq b-1$ (appelés les \emph{chiffres} de
+l'écriture ; on omet le chiffre $0$, mais il faut évidemment autoriser
+la somme vide pour le nombre $0$ lui-même).  On appelle
+\textbf{écriture en base $b$ itérée} l'écriture dans laquelle les
+exposants eux-mêmes sont écrits en base $b$ itérée.  Par exemple,
+l'écriture en base $2$ itérée de $38$ (dont l'écriture binaire usuelle
+est $2^5 + 2^2 + 2^1$) est :
+\[
+2^{(2^2 + 2)} + 2^2 + 2
+\]
+(en fait, si on veut être extrêmement précis, le $2$ le plus haut dans
+chaque tour d'exposants est mis pour $2^1$ où $1$ est lui-même mis ici
+pour $2^0$ ; et on n'a pas écrit les chiffres eux-mêmes, qui valent
+tous $1$).
+
+Si $n$ est un entier naturel, on définit la \textbf{suite de
+  Goodstein} partant de $n$ de la manière suivante.  Les termes de la
+suite sont indicés par les entiers naturels $b\geq 2$.  Le premier
+terme de la suite est $g_2 := n$.  Pour calculer le terme $g_{b+1}$ à
+partir de $g_b$, on effectue les opérations suivantes :
+\begin{itemize}
+\item écrire $g_b$ en base $b$ itérée, et remplacer chaque $b$ par
+  $(b+1)$ dans cette écriture (sans changer les chiffres),
+\item puis soustraire $1$.
+\end{itemize}
+
+Par exemple, à partir de $n=19$, on a $g_2 = 19$, qui s'écrit en base
+$2$ itérée comme $2^{2^2} + 2 + 1$ ; on va donc le remplacer par
+$3^{3^3} + 3 + 1 = 7\,625\,597\,484\,991$ et soustraire $1$, si bien
+que le terme suivant est $g_3 = 7\,625\,597\,484\,990$.  Le terme
+suivant sera alors obtenu à partir de $g_3 = 3^{3^3} + 3$ en
+remplaçant les $3$ par des $4$ et en soustrayant $1$, ce qui donne
+$g_4 = 4^{4^4} + 4 - 1 = 4^{4^4} + 3$ (un nombre valant environ
+$1.34\times 10^{154}$), puis on trouve $g_5 = 5^{5^5} + 2$, et ainsi
+de suite.
+
+La suite de Goodstein termine lorsqu'on atteint $0$ (si c'est le cas).
+
+\medbreak
+
+\textbf{(1)} Si $n$ est un entier naturel et $b\geq 2$, on définit un
+ordinal $f_b(n)$ de la façon suivante : écrire $n$ en base $b$ itérée
+et remplacer chaque $b$ par $\omega$ dans cette écriture (sans changer
+les chiffres).  Par exemple, $f_2(38) = f_2(2^{(2^2 + 2)} + 2^2 + 2) =
+\omega^{(\omega^\omega+\omega)} + \omega^\omega + \omega$ tandis que
+$f_3(38) = f_3(3^3 + 3^2 + 2) = \omega^\omega + \omega^2 + 2$.
+Montrer que, à $b$ fixé, la fonction $f_b$ est strictement croissante
+(c'est-à-dire : si $n<n'$ alors $f_b(n) < f_b(n')$).
+
+\begin{corrige}
+Directement par la définition, $f_b(n)$ est un ordinal écrit en forme
+normale de Cantor itérée, qui a, de plus, la propriété que tous les
+chiffres de cette écriture sont $<b$.
+
+Or les écritures en base $b$ itérée des entiers naturels se comparent
+lexicographiquement (car c'est déjà le cas des écritures en base $b$
+ordinaires) : on compare l'exposant de la plus grande puissance de $b$
+(celle écrite en premier) par le même algorithme récursivement, puis
+le chiffre correspondant, puis l'exposant suivant, etc., jusqu'à
+trouver la première différence.  C'est exactement le même algorithme
+pour la comparaison des formes normales de Cantor itérées des
+ordinaux.
+
+Autrement dit, $f_b$ définit une bijection croissante entre les
+entiers naturels et les ordinaux $<\varepsilon_0$ dont la forme
+normale de Cantor itérée n'a que des chiffres $<b$.
+\end{corrige}
+
+\medbreak
+
+\textbf{(2)} Si $(g_b)$ est une suite de Goodstein, on définit une
+suite d'ordinaux de même longueur $(\gamma_b)$ avec $\gamma_b <
+\varepsilon_0$ de la façon suivante : pour calculer $\gamma_b$, on
+écrit $g_b$ en base $b$ itérée, et remplacer chaque $b$ par $\omega$
+dans cette écriture (sans changer les chiffres).  Démontrer que
+$\gamma_{b+1} < \gamma_b$.
+
+\begin{corrige}
+La définition est donc : $\gamma_b = f_b(g_b)$.  Comme $g_{b+1} + 1$
+s'obtient en remplaçant tous les $b$ par $(b+1)$ dans l'écriture en
+base $b$ itérée de $g_b$, on a $\gamma_b = f_{b+1}(g_{b+1} + 1)$.
+Comme $\gamma_{b+1} = f_{b+1}(g_{b+1})$ et que $g_{b+1} < g_{b+1} +
+1$, par la question (1), on en déduit $\gamma_{b+1} < \gamma_b$.
+\end{corrige}
+
+\medbreak
+
+\textbf{(3)} En déduire que toute suite de Goodstein est finie.
+
+\begin{corrige}
+Si on avait une suite de Goodstein $(g_b)$ infinie, on en déduirait
+par la construction $\gamma_b = f_b(g_b)$ de la question (2) une suite
+d'ordinaux $(\gamma_b)$ infinie strictement décroissante.  Ceci n'est
+pas possible, donc toute suite de Goodstein est finie.
+\end{corrige}
+
+
+
+%
+%
+%
+
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Points bonus.}
+
+(Ceci n'est pas un exercice à résoudre mais un choix à faire.)
+
+Vous disposez de deux options : indiquez clairement sur votre copie si
+vous choisissez « Bleu » ou « Rouge ».  (Ce choix sera gardé secret.)
+
+Si au moins la moitié des participants de l'épreuve choisissent
+« Bleu », alors $0.5$ points seront ajoutés à la note de tous les
+participants.  Sinon, $0.5$ points seront ajoutés à la note seulement
+des participants qui ont choisi « Rouge »,
+
+
+%
+%
+%
 \end{document}