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