Continue writing exam.

1 files changed, 111 insertions, 3 deletions

diff --git a/controle-20190408.tex b/controle-20190408.tex
index 65e25a0..1a9e36d 100644
--- a/controle-20190408.tex
+++ b/controle-20190408.tex
@@ -206,7 +206,7 @@ ajoute ensuite, optionnellement, le nombre qu'il souhaite de jetons de
 type $n-1$.  Par exemple, on peut remplacer un jeton de type $1729$
 par $42$ jetons de type $1728$ ; on peut aussi le retirer sans
 remplacement.)\quad(a) Dans ces conditions, que vaut $\gr J(n)$ ?  (On
-pourra par exemple commencer par calculer $gr J(n)$ pour $n=0,1,2,3$,
+pourra par exemple commencer par calculer $\gr J(n)$ pour $n=0,1,2,3$,
 conjecturer une formule générale, et la démontrer par récurrence
 sur $n$.)\quad(b) Exprimer de façon simple la stratégie gagnante du
 jeu considéré dans cette question.
@@ -223,7 +223,7 @@ type $k\leq n-1$.  Par exemple, on peut remplacer un jeton de
 type $1729$ par $42$ jetons de type $1728$ ou $1728$ jetons de
 type $42$ ; on peut aussi le retirer sans remplacement.)  Dans ces
 conditions, que vaut $\gr J(n)$ ?  (On pourra par exemple commencer
-par calculer $gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule
+par calculer $\gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule
 générale, et la démontrer par récurrence sur $n$.)
 
 \medskip
@@ -237,7 +237,7 @@ n'importe quels types $<n$.  Par exemple, on peut remplacer un jeton
 de type $1729$ par $42$ jetons de type $1728$ et $666$ de type $0$ ;
 on peut aussi le retirer sans remplacement.)\quad(a) Dans ces
 conditions, que vaut $\gr J(n)$ ?  (On pourra par exemple commencer
-par calculer $gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule
+par calculer $\gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule
 générale, et la démontrer par récurrence sur $n$.)\quad(b) Exprimer de
 façon simple la stratégie gagnante du jeu considéré dans cette
 question.
@@ -246,4 +246,112 @@ question.
 %
 %
 %
+
+\exercice
+
+On définit une opération binaire $\alpha\boxplus\beta$ (appelée
+« somme naturelle » ou « somme de Hessenberg ») sur les ordinaux (ici
+notés $\alpha,\beta$) par la formule suivante :
+\[
+\alpha \boxplus \beta = \sup\nolimits^+ \Big( \{\alpha'\boxplus\beta :
+\alpha' < \alpha\} \cup\, \{\alpha\boxplus\beta' : \beta' <
+\beta\}\Big)
+\]
+où on rappelle que $\sup^+ S$, si $S$ est un ensemble d'ordinaux,
+désigne \emph{le plus petit ordinal strictement plus grand que tous
+  les éléments de $S$} (c'est aussi $\sup\{\gamma+1 : \gamma\in S\}$
+mais c'est probablement moins utile d'y penser sous cette forme).
+Autrement dit, $\alpha\boxplus\beta$ désigne le plus petit ordinal qui
+soit strictement supérieur à tous les $\alpha'\boxplus\beta$ pour
+$\alpha'<\alpha$ ainsi qu'à tous les $\alpha\boxplus\beta'$
+pour $\beta'<\beta$.  Cette définition a bien un sens par induction
+bien-fondée.
+
+\medskip
+
+(1)(a) Calculer $m\boxplus n$ pour $0\leq m\leq 5$ et $0\leq n\leq
+5$.\quad(b) Conjecturer une formule générale pour $m\boxplus n$
+lorsque $m,n\in\mathbb{N}$ (c'est-à-dire
+$m,n<\omega$).\quad(c) Démontrer cette formule.
+
+\medskip
+
+(2)(a) Montrer que $\boxplus$ est commutative, c'est-à-dire que
+$\alpha\boxplus\beta = \beta\boxplus\alpha$ quels que
+soient $\alpha,\beta$.\quad(b) Montrer que $\boxplus$ admet $0$ pour
+élément neutre, c'est-à-dire que $\alpha\boxplus 0 = 0\boxplus\alpha =
+\alpha$ pour tout ordinal $\alpha$.
+
+\medskip
+
+On \underline{admettra} pour la suite que $\boxplus$ est associative,
+c'est-à-dire que $(\alpha_1\boxplus\alpha_2) \boxplus \alpha_3 =
+\alpha_1 \boxplus (\alpha_2\boxplus\alpha_3)$ quels que soient
+$\alpha_1,\alpha_2,\alpha_3$, et que
+$\alpha_1\boxplus\cdots\boxplus\alpha_n$ est le plus petit ordinal
+strictement supérieur à tous les
+$\alpha_1\boxplus\cdots\boxplus\beta_i\boxplus
+\cdots\boxplus\alpha_n$, où exactement un des $\alpha_i$ a été
+remplacé par un ordinal $\beta_i$ strictement plus petit
+(généralisation de la définition au cas de $n$ termes).
+
+\smallskip
+
+Si $\alpha$ est un ordinal et $n\geq 1$ un entier naturel, on
+\underline{notera} $\alpha\boxdot n$ pour la somme naturelle $\alpha
+\boxplus \cdots \boxplus \alpha$ de $n$ fois l'ordinal $\alpha$ (on
+pourra aussi poser $\alpha\boxdot 0 = 0$).  Dans ces conditions, il
+est trivial que $(\alpha\boxdot n) \boxplus (\alpha\boxdot n') =
+\alpha\boxdot (n+n')$.
+
+\medskip
+
+(3) Montrer par induction transfinie sur $\alpha$ que si $\alpha =
+\omega^{\gamma_1} n_1 + \cdots + \omega^{\gamma_r} n_r$ (où $\gamma_1
+> \cdots > \gamma_r$ sont des ordinaux en ordre strictement
+décroissant et $n_1,\ldots,n_r$ des entiers naturels non nuls ;
+c'est-à-dire qu'il s'agit de la forme normale de Cantor de $\alpha$)
+alors on a $\alpha = (\omega^{\gamma_1} \boxdot n_1) \boxplus \cdots
+\boxplus (\omega^{\gamma_r} \boxdot n_r)$.
+
+\emph{Indication :} On imitera de près la démonstration du fait donné
+en cours que si $\alpha = 2^{\gamma_1} + \cdots + 2^{\gamma_r}$ (où
+$\gamma_1 > \cdots > \gamma_r$ sont des ordinaux en ordre strictement
+décroissant ; c'est-à-dire qu'il s'agit de la l'écriture binaire
+de $\alpha$) alors on a $\alpha = 2^{\gamma_1} \oplus \cdots \oplus
+2^{\gamma_r}$.  Il n'y a pas grand-chose à modifier à part remplacer
+$\mex$ par $\sup^+$ aux endroits utiles.  (Cette question est un peu
+longue, mais il est possible de traiter la suite en l'admettant.)
+
+\medskip
+
+(4)(a) En déduire la manière dont on calcule $\alpha\boxplus\beta$ à
+partir des formes normales de Cantor de
+$\alpha$ et $\beta$.\quad(b) En particulier, calculer
+$(\omega+1)\boxplus(\omega+1)$, et comparer avec $(\omega+1) +
+(\omega+1)$.
+
+\medskip
+
+(5) On considère le jeu à deux joueurs suivant : les deux joueurs
+s'appellent Blaise et Roxane, et ils jouent tour à tour (on ne précise
+pas qui commence) ; l'état du jeu est défini par trois ordinaux, qu'on
+notera $(\alpha,\beta,\rho)$, et il est visible de tous ; les coups
+possibles de Blaise consistent à diminuer strictement soit l'ordinal
+$\alpha$ soit l'ordinal $\beta$ (c'est-à-dire passer de
+$(\alpha,\beta,\rho)$ à $(\alpha',\beta,\rho)$ avec $\alpha'<\alpha$
+ou à $(\alpha,\beta',\rho)$ avec $\beta'<\beta$), tandis que les coups
+possibles de Roxane consistent à diminuer strictement l'ordinal $\rho$
+(c'est-à-dire passer de $(\alpha,\beta,\rho)$ à $(\alpha,\beta,\rho')$
+avec $\rho'<\rho$) ; le joueur qui ne peut plus jouer a perdu.
+
+Montrer que, dans ce jeu, Blaise possède une stratégie gagnante
+lorsque $\rho > \alpha\boxplus\beta$, que Roxane possède une stratégie
+gagnante lorsque $\rho < \alpha\boxplus\beta$, et que le second joueur
+possède une stratégie gagnante lorsque $\rho = \alpha\boxplus\beta$.
+
+
+%
+%
+%
 \end{document}