Finish exercise on nim product (prove existence of inverses).

1 files changed, 105 insertions, 33 deletions

diff --git a/controle-20160421.tex b/controle-20160421.tex
index 1e2a140..eaa536c 100644
--- a/controle-20160421.tex
+++ b/controle-20160421.tex
@@ -295,23 +295,22 @@ et on a prouvé que c'étaient bien les seuls.
 \exercice\label{game-for-nim-product}
 
 On considère le jeu suivant : une position du jeu consiste en un
-certain nombre fini de jetons placés sur un damier transfini dont les
-cases étiquetées par un couple $(\alpha,\beta)$ d'ordinaux (on dira
-que $\alpha$ est [le numéro de] la ligne de la case et $\beta$ [le
-  numéro de] la colonne).  Plusieurs jetons peuvent se trouver sur la
-même case.
+certain nombre fini de jetons placés sur un damier possiblement
+transfini dont les cases étiquetées par un couple $(\alpha,\beta)$
+d'ordinaux (on dira que $\alpha$ est la ligne de la case et $\beta$ la
+colonne).  Plusieurs jetons peuvent se trouver sur la même case.
 
 Un coup du jeu consiste à faire l'opération suivante : le joueur qui
-doit jouer choisit un jeton du jeu, disons qu'il soit sur la case
-$(\alpha,\beta)$, et il choisit aussi $\alpha' < \alpha$ (i.e., une
-ligne située plus haut) et $\beta' < \beta$ (i.e., une colonne située
-plus à gauche), il retire le jeton choisi de la case $(\alpha,\beta)$
-et le remplace par \emph{trois} jetons, sur les cases
-$(\alpha',\beta)$, $(\alpha,\beta')$ et $(\alpha',\beta')$.  (À titre
-d'exemple, si le jeu comporte un seul jeton sur la case $(42,7)$, un
-coup valable consiste à le remplacer par trois jetons, sur les cases
-$(18,7)$, $(42,5)$ et $(18,5)$.)  Le nombre de jetons présents
-augmente donc de $2$ à chaque coup joué.
+doit jouer choisit un jeton du jeu, disons sur la case
+$(\alpha,\beta)$, et il choisit aussi arbitrairement $\alpha' <
+\alpha$ (i.e., une ligne située plus haut) et $\beta' < \beta$ (i.e.,
+une colonne située plus à gauche) : il retire alors le jeton choisi de
+la case $(\alpha,\beta)$ et le remplace par \emph{trois} jetons, sur
+les cases $(\alpha',\beta)$, $(\alpha,\beta')$ et $(\alpha',\beta')$.
+(À titre d'exemple, si le jeu comporte un seul jeton sur la case
+$(42,7)$, un coup valable consiste à le remplacer par trois jetons,
+sur les cases $(18,7)$, $(42,5)$ et $(18,5)$.)  Le nombre de jetons
+présents augmente donc de $2$ à chaque coup joué.
 
 \begin{center}
 \vskip-\baselineskip
@@ -328,7 +327,7 @@ augmente donc de $2$ à chaque coup joué.
 \node[anchor=south] at (1.25,0) {$\beta'$};
 \node[anchor=south] at (2.75,0) {$\beta$};
 \end{tikzpicture}
-\\{\footnotesize (Le jeton en gris est remplacé par les trois noirs.)}
+\\{\footnotesize (Le jeton en gris remplacé par les trois noirs.)}
 \end{center}
 
 On remarquera que les jetons sur la ligne ou la colonne $0$ ne peuvent
@@ -343,8 +342,9 @@ et celui qui ne peut plus jouer a perdu.
 n'y a pas de ligne ou de colonne $0$ (on fait démarrer la numérotation
 à $1$) et il n'y a pas de défausse (les jetons disparaissent plutôt
 qu'être défaussés) : quels sont les types de coups possibles à ce
-jeu ?  On se permettra dans la suite d'utiliser librement l'une ou
-l'autre variante du jeu.
+jeu ?  (Distinguer selon que $\alpha'=0$ ou non, et selon que
+$\beta'=0$ ou non.)  On se permettra dans la suite d'utiliser
+librement l'une ou l'autre variante du jeu.
 
 \begin{corrige}
 Les jetons défaussés ne jouant aucun rôle dans le jeu, on peut les
@@ -462,10 +462,9 @@ complètement équivalents.
 \bigoplus_{i=1}^s (\alpha_i\otimes\beta_i)
 \]
 où $(\alpha_1,\beta_1),\ldots,(\alpha_s,\beta_s)$ sont les cases où se
-trouvent les $s$ jetons (en autant de fois que nécessaire les cases
-sur lesquelles se trouvent des jetons multiples), où $\oplus$ désigne
-la somme de nim et où l'opération $\otimes$ sur les ordinaux est
-définie inductivement par
+trouvent les $s$ jetons (répétées en cas de jetons multiples), où
+$\oplus$ désigne la somme de nim, et où l'opération $\otimes$ sur les
+ordinaux est définie inductivement par
 \[
 \alpha\otimes\beta := \mex\Big\{(\alpha'\otimes\beta)
 \oplus (\alpha\otimes\beta') \oplus (\alpha'\otimes\beta')
@@ -496,7 +495,7 @@ inductive), et on a montré ce qui était demandé.
 
 (4) Calculer la valeur de $\alpha\otimes\beta$ pour $0\leq\alpha\leq
 5$ et $0\leq\beta\leq 5$.  Pour accélérer les calculs ou bien pour les
-vérifier, on pourra utiliser les résultats de
+confirmer, on pourra utiliser les résultats de
 l'exercice \ref{inductions-on-nim-product} (il n'est pas nécessaire
 d'avoir traité l'exercice en question).  On ne demande pas de
 justifier les calculs, mais on recommande de les vérifier
@@ -525,8 +524,8 @@ commutativité, et le fait que $\alpha\otimes 3 = \alpha\otimes(2\oplus
 
 \smallbreak
 
-(5) Si vous devez jouer dans la position suivante (les lignes et
-colonnes sont numérotées à partir de $1$, c'est-à-dire que la défausse
+(5) Si vous deviez jouer dans la position suivante (les lignes et
+colonnes sont numérotées à partir de $1$, autrement dit la défausse
 n'est pas figurée), quel coup feriez-vous ?
 
 \begin{center}
@@ -661,9 +660,9 @@ $\beta'\neq\beta$, alors $(\alpha'\otimes\beta) \oplus
 (4) Montrer que $\otimes$ est distributive sur $\oplus$, c'est-à-dire
 $\alpha \otimes (\beta\oplus\gamma) = (\alpha\otimes\beta) \oplus
 (\alpha\otimes\gamma)$.  Pour cela, on pourra procéder par induction
-(et remarquer que pour montrer $\lambda = \mu$ il suffit de montrer
-que (a) $\xi<\lambda$ implique $\xi\neq\mu$ et que (b) $\xi<\mu$
-implique $\xi\neq\lambda$).
+et remarquer que pour montrer $\lambda = \mu$ il suffit de montrer que
+(a) $\xi<\lambda$ implique $\xi\neq\mu$ et que (b) $\xi<\mu$ implique
+$\xi\neq\lambda$.
 
 \begin{corrige}
 Pour montrer $\lambda = \mu$ il suffit de montrer que
@@ -717,11 +716,84 @@ l'hypothèse d'induction permet de réécrire $\xi = (\alpha'\otimes
 \otimes (\beta\oplus\gamma)$, ce qu'on voulait.
 \end{corrige}
 
-%% \smallbreak
-%%
-%% On \emph{admet} que $\otimes$ est associative, c'est-à-dire
-%% $(\alpha\otimes\beta) \otimes \gamma = \alpha \otimes
-%% (\beta\otimes\gamma)$ (ce n'est pas très difficile à prouver).
+\smallbreak
+
+On \emph{admet} que $\otimes$ est associative, c'est-à-dire
+$(\alpha\otimes\beta) \otimes \gamma = \alpha \otimes
+(\beta\otimes\gamma)$ (ce n'est pas très difficile à prouver).
+
+(5) On va enfin montrer que pour tout $\alpha > 0$ il existe un
+$\alpha^*$ tel que $\alpha\otimes\alpha^* = 1$, c'est-à-dire, un
+\emph{inverse} pour le produit de nim.  Pour cela, on suppose par
+l'absurde le contraire, et on considère $\alpha$ le plus petit ordinal
+non nul qui n'a pas d'inverse, et on va arriver à une contradiction.
+Pour cela, appelons $\gamma_0 = \sup^+ \big(\{\beta :
+\beta\leq\alpha\} \cup \{\beta^* : \beta<\alpha\} \big)$ (où $\beta^*$
+désigne l'inverse de $\beta$, qu'on a supposé exister vu
+que $\beta<\alpha$) le plus petit ordinal strictement supérieur à tous
+les ordinaux $\leq\alpha$ et aux inverses des ordinaux $<\alpha$, et
+par récurrence sur l'entier naturel $n$, posons $\delta_{n+1} = \sup^+
+\big(\{\beta_1 \oplus \beta_2 : \beta_1,\beta_2<\delta_n\} \cup
+\{\beta_1 \otimes \beta_2 : \beta_1,\beta_2<\delta_n\}\big)$ le plus
+petit ordinal strictement supérieur à la somme ou au produit de nim de
+deux ordinaux strictement plus petits que $\delta_n$ (on a bien sûr
+$\delta_{n+1} \geq \delta_n$).  Soit enfin $\delta = \lim_{n\to\omega}
+\delta_n = \sup\{\delta_n : n\in\mathbb{N}\}$.\spaceout (a) Expliquer
+pourquoi si $\beta_1,\beta_2 < \delta$ alors $\beta_1\oplus\beta_2 <
+\delta$ et $\beta_1\otimes\beta_2 < \delta$.\spaceout (b) Montrer que
+si $0 < \alpha' < \alpha$ alors nécessairement $\alpha' \otimes \delta
+\geq \delta$ (dans le cas contraire, considérer le produit de $\alpha'
+\otimes \delta$ par $(\alpha')^*$ et utiliser (a)).\spaceout (c) En
+déduire que si $0 < \alpha' < \alpha$ et $\delta' < \delta$, alors
+$(\alpha'\otimes\delta) \oplus (\alpha\otimes\delta') \oplus
+(\alpha'\otimes\delta')$ est $\geq \delta$ (dans le cas contraire,
+montrer que le premier terme serait $<\delta$).  En particulier, il
+est $\neq 1$.\spaceout (d) Expliquer pourquoi si $\alpha' = 0$ alors
+$(\alpha'\otimes\delta) \oplus (\alpha\otimes\delta') \oplus
+(\alpha'\otimes\delta')$ est encore une fois $\neq 1$.\spaceout (e) En
+déduire que $\alpha\otimes\delta = 1$ et conclure.
+
+\begin{corrige}
+(a) Si $\beta < \delta$, comme $\delta$ est la borne supérieure
+  des $\delta_n$, il existe $n$ tel que $\beta < \delta_n$.  Ainsi, si
+  $\beta_1,\beta_2 < \delta$, il existe $n$ tel que $\beta_1,\beta_2 <
+  \delta_n$ (en prenant le maximum des deux $n$ obtenus), donc
+  $\beta_1\oplus\beta_2 < \delta_{n+1}$ et $\beta_1\otimes\beta_2 <
+  \delta_{n+1}$ d'après la définition de $\delta_{n+1}$, ce qui donne
+  bien $\beta_1\oplus\beta_2 < \delta$ et $\beta_1\otimes\beta_2 <
+  \delta$.
+
+(b) Si $0 < \alpha' < \alpha$ et si $\alpha' \otimes \delta < \delta$,
+  alors on a $\alpha' \otimes \delta < \delta$ et $(\alpha')^* <
+  \gamma_0 \leq \delta$ donc $(\alpha' \otimes \delta) \otimes
+  (\alpha')^* < \delta$ d'après (a).  Or $(\alpha' \otimes \delta)
+  \otimes (\alpha')^* = \delta$ par associativité, commutativité et
+  par le fait que $(\alpha')^*$ est l'inverse de $\alpha'$.
+
+(c) Si $0 < \alpha' < \alpha$ et $\delta' < \delta$, montrons que
+  $(\alpha'\otimes\delta) \oplus (\alpha\otimes\delta') \oplus
+  (\alpha'\otimes\delta')$ est $\geq\delta$.  Dans le cas contraire,
+  $\alpha'\otimes\delta$ serait la somme de nim du tout, qui
+  est $<\delta$ par hypothèse, de $\alpha\otimes\delta'$ qui
+  est $<\delta$ par (a), et de $\alpha'\otimes\delta'$ qui l'est
+  aussi ; de nouveau par (a), on aurait $\alpha'\otimes\delta <
+  \delta$, ce qui contredit (b).
+
+(d) Si $\alpha'=0$ alors $(\alpha'\otimes\delta) \oplus
+  (\alpha\otimes\delta') \oplus (\alpha'\otimes\delta') =
+  \alpha\otimes\delta' \neq 1$ puisqu'on a supposé que $\alpha$
+  n'avait pas d'inverse.
+
+(e) Par définition, $\alpha\otimes\delta$ est le plus petit ordinal
+  qui n'est pas de la forme $(\alpha'\otimes\delta) \oplus
+  (\alpha\otimes\delta') \oplus (\alpha'\otimes\delta') =
+  \alpha\otimes\delta'$ pour $\alpha'<\alpha$ et $\delta'<\delta$.  Or
+  on a montré en (c) et (d) que cette expression n'est jamais $1$, et
+  en revanche elle peut être $0$ (pour $\alpha'=\delta'=0$).  Le plus
+  petit ordinal qui n'est pas de cette forme est donc $1$ : mais on a
+  alors prouvé $\alpha\otimes\delta = 1$, ce qui contredit l'hypothèse
+  que $\alpha$ n'ait pas d'inverse.
+\end{corrige}