diff options
| -rw-r--r-- | controle-20160421.tex | 138 |
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} |