More about the nim product.

1 files changed, 147 insertions, 4 deletions

diff --git a/controle-20160421.tex b/controle-20160421.tex
index 81110a0..9c09891 100644
--- a/controle-20160421.tex
+++ b/controle-20160421.tex
@@ -451,7 +451,7 @@ définie inductivement par
 \[
 \alpha\otimes\beta := \mex\Big\{(\alpha'\otimes\beta)
 \oplus (\alpha\otimes\beta') \oplus (\alpha'\otimes\beta')
-: \alpha'<\alpha, \beta'<\beta\Big\}
+: \alpha'<\alpha,\text{~et~}\beta'<\beta\Big\}
 \tag{*}
 \]
 
@@ -513,10 +513,153 @@ commutativité, et le fait que $\alpha\otimes 3 = \alpha\otimes(2\oplus
 On définit inductivement une opération $\alpha\otimes\beta$
 (\emph{produit de nim}) de deux ordinaux $\alpha,\beta$ par la
 formule (*) de l'exercice \ref{game-for-nim-product} (il n'est pas
-nécessaire d'avoir traité l'exercice en question, ni meme d'avoir lu
-autre chose que la formule (*), même s'il est permis de s'en servir).
-La notation $\oplus$ désigne la somme de nim.
+nécessaire d'avoir traité l'exercice en question, même s'il est permis
+de s'en servir), autrement dit $\alpha\otimes\beta :=
+\mex\{(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
+(\alpha'\otimes\beta') : \alpha'<\alpha, \beta'<\beta\}$ où la
+notation $\oplus$ désigne la somme de nim.
 
+(On rappelle que $\gamma = \mex S$ signifie que $\gamma\not\in S$ et
+que tout ordinal $\gamma'<\gamma$ appartient à $S$.)
+
+(1) Montrer que $\otimes$ est commutative, c'est-à-dire que
+$\beta\otimes\alpha = \alpha\otimes\beta$ quels que soient les
+ordinaux $\alpha,\beta$.
+
+\begin{corrige}
+Par induction sur $\alpha$ et $\beta$, on prouve $\beta\otimes\alpha =
+\alpha\otimes\beta$ en supposant que la même formule est vraie si l'un
+de $\alpha$ ou $\beta$ est remplacé par un ordinal strictement plus
+petit.  Or $\beta\otimes\alpha = \mex \{(\beta\otimes\alpha') \oplus
+(\beta'\otimes\alpha) \oplus (\beta'\otimes\alpha') : \alpha'<\alpha,
+\beta'<\beta\}$, et par hypothèse d'induction ceci vaut $\mex
+\{(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
+(\alpha'\otimes\beta') : \alpha'<\alpha, \beta'<\beta\} =
+\alpha\otimes\beta$.
+
+Si on préfère, on peut aussi utiliser le jeu défini dans
+l'exercice \ref{game-for-nim-product}, en remarquant qu'échanger les
+coordonnées des cases de tous les jetons ne change rien au jeu (i.e.,
+les règles sont symétriques ligne/colonne) donc ne change pas la
+fonction de Grundy.
+\end{corrige}
+
+\smallbreak
+
+(2) Montrer que $0$ est absorbant pour $\otimes$,
+c'est-à-dire $\alpha\otimes 0 = 0$ pour tout ordinal $\alpha$.
+Montrer que $1$ est neutre pour otimes, c'est-à-dire $\alpha\otimes 1
+= \alpha$ pour tout ordinal $\alpha$.
+
+\begin{corrige}
+On a $\alpha \otimes 0 = \mex \varnothing = 0$ (puisqu'il n'existe pas
+de $\beta'<0$).  Pour la seconde affirmation, par induction sur
+$\alpha$, on prouve $\alpha \otimes 1 = \alpha$ : en effet, $\alpha
+\otimes 1 = \mex \{(\alpha'\otimes 1) \oplus (\alpha\otimes 0) \oplus
+(\alpha'\otimes 0): \alpha'<\alpha\}$, et en utilisant le fait que $0$
+est aborbant pour $\otimes$ et neutre pour $\oplus$ et l'hypothèse
+d'induction, ceci vaut $\mex \{\alpha': \alpha'<\alpha\} = \mex \alpha
+= \alpha$.
+
+Si on préfère, on peut aussi utiliser le jeu défini dans
+l'exercice \ref{game-for-nim-product}, en remarquant qu'un jeton sur
+la ligne ou colonne $0$ est mort (défaussé), et que jouer sur la ligne
+ou colonne $1$ revient à jouer au jeu de nim d'après la question (2)
+de l'exercice \ref{game-for-nim-product}.
+\end{corrige}
+
+\smallbreak
+
+(3) (a) Montrer que si $\alpha\otimes\beta = \alpha\otimes\beta'$
+alors $\alpha=0$ ou bien $\beta=\beta'$ (on pourra procéder par
+contraposée).\spaceout (b) En déduire que si $\alpha'\neq\alpha$ et
+$\beta'\neq\beta$, alors $(\alpha'\otimes\beta) \oplus
+(\alpha\otimes\beta') \oplus (\alpha'\otimes\beta') \neq
+\alpha\otimes\beta$.
+
+\begin{corrige}
+(a) Si $\alpha>0$ et $\beta\neq\beta'$, supposons sans perte de
+  généralité que $\beta'<\beta$.  Alors $\alpha\otimes\beta$ est
+  le $\mex$ d'un ensemble contenant $(0\otimes\beta) \oplus
+  (\alpha\otimes\beta') \oplus (0\otimes\beta') =
+  \alpha\otimes\beta'$, donc il ne peut pas lui être égal.
+
+(b) Grâce aux propriétés de la somme de nim ($\gamma \neq \gamma'$
+  équivaut à $\gamma\oplus\gamma' \neq 0$), la condition qu'on veut
+  montrer est équivalente à : $(\alpha\otimes\beta) \oplus
+  (\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
+  (\alpha'\otimes\beta') \neq 0$.  Sous cette forme, on voit qu'il y a
+  symétrie entre $\alpha'$ et $\alpha$ et entre $\beta'$ et $\beta$ :
+  on peut donc supposer $\alpha'<\alpha$ et $\beta'<\beta$, auquel cas
+  la condition est claire par la définition même de $\otimes$.
+\end{corrige}
+
+\smallbreak
+
+(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$).
+
+\begin{corrige}
+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$ : en effet, si on avait $\lambda > \mu$, on aurait
+une contradiction en posant $\xi = \mu$ dans (a), et si on avait
+$\lambda < \mu$, on aurait une contradiction en posant $\xi = \lambda$
+dans (b).
+
+Procédons par induction pour prouver $\alpha \otimes
+(\beta\oplus\gamma) = (\alpha\otimes\beta) \oplus
+(\alpha\otimes\gamma)$ : on peut supposer cette égalité connue si l'un
+des ordinaux $\alpha,\beta,\gamma$ est remplacé par un strictement
+plus petit.
+
+(a) Si $\xi < \alpha \otimes (\beta\oplus\gamma)$, alors on peut
+écrire $\xi = (\alpha'\otimes(\beta\oplus\gamma)) \oplus
+(\alpha\otimes\delta') \oplus (\alpha'\otimes\delta')$ où
+$\alpha'<\alpha$ et $\delta' < \beta\oplus\gamma$.  La définition
+inductive de $\oplus$ permet alors d'écrire soit $\delta' =
+\beta'\oplus\gamma$ où $\beta'<\beta$, soit $\delta' =
+\beta\oplus\gamma'$ où $\gamma'<\gamma$ : par symétrie, plaçons nous
+sans perte de généralité dans le premier cas.  On a alors $\xi =
+(\alpha'\otimes (\beta\oplus\gamma)) \oplus (\alpha\otimes
+(\beta'\oplus\gamma)) \oplus (\alpha'\otimes (\beta'\oplus\gamma))$.
+Par hypothèse d'induction, on peut développer les trois termes, et
+quitte à simplifier les deux termes $\alpha'\otimes\gamma$ qui
+apparaissent, on obtient $\xi = (\alpha'\otimes\beta) \oplus
+(\alpha\otimes\beta') \oplus (\alpha'\otimes\beta') \oplus
+(\alpha\otimes\gamma)$.  Puisque la somme $(\alpha'\otimes\beta)
+\oplus (\alpha\otimes\beta') \oplus (\alpha'\otimes\beta')$ des trois
+premiers termes est différente de $\alpha\otimes\beta$
+(d'après (3)(b)), on en déduit que $\xi \neq (\alpha\otimes\beta)
+\oplus (\alpha\otimes\gamma)$, ce qu'on voulait.
+
+(b) Maintenant, si $\xi < (\alpha\otimes\beta) \oplus
+(\alpha\otimes\gamma)$, on a soit $\xi = \delta' \oplus
+(\alpha\otimes\gamma)$ avec $\delta' < \alpha\otimes\beta$, soit $\xi
+= (\alpha\otimes\beta) \oplus \varepsilon'$ avec $\varepsilon' <
+\alpha\otimes\gamma$ : par symétrie, plaçons nous sans perte de
+généralité dans le premier cas.  On peut alors écrire $\delta' =
+(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
+(\alpha'\otimes\beta')$ avec $\alpha'<\alpha$ et $\beta'<\beta$, donc
+on a : $\xi = (\alpha'\otimes\beta) \oplus (\alpha\otimes\beta')
+\oplus (\alpha'\otimes\beta') \oplus (\alpha\otimes\gamma)$.  Quitte à
+faire apparaître deux termes $\alpha'\otimes\gamma$ qui s'annulent,
+l'hypothèse d'induction permet de réécrire $\xi = (\alpha'\otimes
+(\beta\oplus\gamma)) \oplus (\alpha\otimes (\beta'\oplus\gamma))
+\oplus (\alpha'\otimes (\beta'\oplus\gamma))$.  Or $\beta'\oplus\gamma
+\neq \beta\oplus\gamma$ : en utilisant (3)(b), on a $\xi \neq \alpha
+\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).