From 1a3036ac70527dcfce89a76f0a10cffac10361d1 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 18 Apr 2016 23:10:40 +0200
Subject: Finish exercise on nim product (prove existence of inverses).
---
controle-20160421.tex | 138 ++++++++++++++++++++++++++++++++++++++------------
1 file 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}
--
cgit v1.2.3