From 4b111f4a5720fcadc331cc3b5185b4e503b56bce Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Fri, 5 Apr 2019 00:43:32 +0200 Subject: Re-read exam. --- controle-20190408.tex | 246 ++++++++++++++++++++++++++++---------------------- 1 file changed, 136 insertions(+), 110 deletions(-) diff --git a/controle-20190408.tex b/controle-20190408.tex index 5f4291b..6e86da7 100644 --- a/controle-20190408.tex +++ b/controle-20190408.tex @@ -87,9 +87,9 @@ dans un ordre quelconque, mais on demande de faire apparaître de façon très visible dans les copies où commence chaque exercice. La longueur du sujet ne doit pas effrayer : d'une part, l'énoncé est -long car des rappels ont été faits et que la rédaction des questions -cherche à éviter toute ambiguïté ; d'autre part, il ne sera pas -nécessaire de tout traiter pour obtenir la totalité des points +long parce que des rappels ont été faits et que la rédaction des +questions cherche à éviter toute ambiguïté ; d'autre part, il ne sera +pas nécessaire de tout traiter pour obtenir la totalité des points (cf. barème). \medbreak @@ -177,12 +177,13 @@ qu'il décroît strictement à chaque tour. On associe à la position $J(n_1,\ldots,n_r)$ (définie en (2) ci-dessous), quitte à supposer $n_1>\cdots>n_r$ l'ordinal $\omega^{n_1} + \cdots + \omega^{n_r}$ ; ou, ce qui revient au même, -s'il y a $r_n$ jetons de type $n$, on considère l'ordinal $\omega^N -r_n + \cdots + \omega^1 r_1 + r_0$ où $N$ est le plus grand type d'un -jeton sur la table. Par la comparaison des ordinaux écrits en forme -normale de Cantor, cet ordinal décroît à chaque coup (puisqu'on -remplace un $\omega^n$ par des $\omega^{n'}$ avec $n' < n$). Le jeu -termine donc en temps fini. +s'il y a $r_n := \#\{i : n_i = n\}$ jetons de type $n$, on considère +l'ordinal $\omega^N r_n + \cdots + \omega^2 r_2 + \omega\, r_1 + r_0$ +où $N := \max\{n_i\}$ est le plus grand type d'un jeton sur la table. +Par la comparaison des ordinaux écrits en forme normale de Cantor, cet +ordinal décroît à chaque coup (puisqu'on remplace un $\omega^n$ par +des $\omega^{n'}$ avec $n' < n$, la suite $(r_n,\ldots,r_0)$ décroît +lexicographiquement). Le jeu termine donc en temps fini. \end{corrige} \medskip @@ -194,17 +195,20 @@ pourquoi $J(n_1,\ldots,n_r)$ peut s'identifier à la somme de nim des positions $J(n_1),\ldots,J(n_r)$ (où $J(n)$ désigne l'état du jeu ayant un unique jeton de type $n$).\quad(b) En déduire la valeur de Grundy $\gr J(n_1,\ldots,n_r)$ de $J(n_1,\ldots,n_r)$ en fonction de -celles $\gr J(n_i)$ des $J(n_i)$.\quad(c) Qui a une stratégie gagnante +celles des $J(n_i)$.\quad(c) Qui a une stratégie gagnante dans une position du type $J(n,n)$ ? Expliciter une telle stratégie en termes simples. (\emph{Convention :} $J()$ est le jeu nul dans lequel il ne reste plus -aucun jeton. Notamment, on a $\gr J() = 0$.) +aucun jeton sur la table. Notamment, on a $\gr J() = 0$. On ne le +confondra pas avec $J(0)$ où il reste un jeton de type $0$.) \begin{corrige} (a) Il s'agit simplement d'observer que les différents jetons n'interagissent pas du tout. Jouer à la somme de nim de - $J(n_1),\ldots,J(n_r)$ revient donc à jouer à $J(n_1,\ldots,n_r)$. + $J(n_1),\ldots,J(n_r)$ revient à jouer sur $r$ tables différentes à + partir d'un jeton de type $n_i$ sur chacune, c'est équivalent à + jouer à $J(n_1,\ldots,n_r)$. (b) On en déduit que $\gr J(n_1,\ldots,n_r) = \gr(J(n_1) \oplus \cdots \oplus J(n_r)) = \gr J(n_1) \oplus \cdots \oplus \gr J(n_r)$ (la @@ -221,28 +225,26 @@ aucun jeton. Notamment, on a $\gr J() = 0$.) \medskip -(3)(a) Pour une règle de remplacement $\mathscr{R}$ donnée, en notant -par exemple $\mathscr{R}_n$ l'ensemble (non vide) de tous les -remplacements possibles d'un jeton de type $n$ (considérés comme des -suites finies d'entiers $0$ il ajoute -ensuite, optionnellement, le nombre qu'il souhaite de jetons d'un même -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 -générale, et la démontrer par récurrence sur $n$.) +quelconque (y compris $0$) de jetons de type $k0$ il ajoute ensuite, optionnellement, le nombre +qu'il souhaite de jetons d'un même 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 générale, et la démontrer par récurrence +sur $n$.) \begin{corrige} On a vu en (3)(b) que $\gr J(0,\ldots,0)$ vaut $0$ ou $1$ selon que le @@ -318,7 +321,8 @@ qu'on vient de faire. (6) On suppose dans cette question que la règle de remplacement est la suivante : un joueur peut remplacer un jeton de type $n$ par un nombre -quelconque (y compris $0$) de jetons de types $0$ il ajoute ensuite, optionnellement, le nombre qu'il souhaite de jetons de n'importe quels types $ \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 + 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)$\par} @@ -493,18 +498,20 @@ c'est-à-dire qu'il s'agit de l'écriture binaire de $\alpha$, alors on a $\alpha = 2^{\gamma_1} \oplus \cdots \oplus 2^{\gamma_r}$). On pourrait démontrer (*) par induction transfinie sur $\alpha$. -Comme c'est un peu fastidieux au niveau des notations, on va se -contenter d'un cas représentatif : +Comme c'est notationnellement un peu fastidieux, on va seulement, dans +la question suivante, montrer un cas particulier assez représentatif +de l'idée générale : \medskip -(3)(a) Si $n_1 \geq 1$, expliquer pourquoi $(\omega\boxdot n_1) +(3)(a) Pour $n_0,n_1 \in \mathbb{N}$, montrer que $(\omega\boxdot n_1) \boxplus n_0 = \sup^+ \big( \{(\omega\boxdot n'_1) \boxplus n_0' : -n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \cup\, \{(\omega\boxdot -n_1) \boxplus n_0' : n'_0 < n_0\}\big)$.\quad (b) Montrer par -induction transfinie sur $\alpha$ que si $\alpha = \omega\, n_1 + n_0$ -où $n_0,n_1 \in \mathbb{N}$, alors $\alpha = (\omega \boxdot n_1) -\boxplus n_0$. +n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \penalty0 \cup +\penalty0 \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 < +n_0\}\big)$.\quad (b) En déduire par induction transfinie sur $\alpha$ +que si $\alpha = \omega\, n_1 + n_0$ où $n_0,n_1 \in \mathbb{N}$, +alors $\alpha = (\omega \boxdot n_1) \boxplus n_0$ (ceci est un cas +particulier de (*)). \begin{corrige} (a) D'après ce qu'on a admis ci-dessus, $(\omega\boxdot n_1) \boxplus @@ -513,28 +520,31 @@ où $n_0,n_1 \in \mathbb{N}$, alors $\alpha = (\omega \boxdot n_1) toutes les sommes naturelles obtenues en remplaçant un des ($n_1+n_0$) termes par un terme strictement plus petit, c'est-à-dire à tous les $(\omega\boxdot (n_1-1)) \boxplus b \boxplus - n_0$ pour $b<\omega$ et à $(\omega\boxdot n_1) \boxplus (n_0-1)$. - En se rappelant que $b \oplus n_0 = b + n_0$ (qui prend donc toutes - les valeurs $\geq n_0$) et qu'on a le droit d'insérer dans un - ensemble dont on prend le $\sup^+$ des nouveaux éléments qui sont - majorés par des éléments déjà dedans (et comme $\boxplus$ est + n_0$ pour $b<\omega$ (cas où on remplace un $\omega$ par $b$) et à + $(\omega\boxdot n_1) \boxplus (n_0-1)$ (cas où on remplace un $1$ + par $0$). En se rappelant que $b \boxplus n_0 = b + n_0$ (qui prend + donc toutes les valeurs $\geq n_0$) et qu'on a le droit d'insérer + dans un ensemble dont on prend le $\sup^+$ des nouveaux éléments qui + sont majorés par des éléments déjà dedans (et comme $\boxplus$ est croissante en chaque variable d'après (2)(c)), on peut écrire $(\omega\boxdot n_1) \boxplus n_0 = \sup^+ \big( \{(\omega\boxdot n'_1) \boxplus n_0' : n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} - \cup\, \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 < n_0\}\big)$ - comme annoncé. + \penalty0 \cup \penalty0 \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 + < n_0\}\big)$ comme annoncé. (b) On procède par induction transfinie sur $\alpha = \omega n_1 + n_0$. On veut montrer que $\alpha = (\omega \boxdot n_1) \boxplus n_0$. Or, d'après ce qu'on vient de voir, $(\omega\boxdot n_1) \boxplus n_0 = \sup^+ \big( \{(\omega\boxdot n'_1) \boxplus n_0' : - n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \cup\, - \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 < n_0\}\big)$. D'après - l'hypothèse d'induction, et en utilisant le fait que les formes - normales de Cantor des ordinaux se comparent lexicographiquement, - ceci vaut encore $\sup^+ \big( \{\omega\, n'_1 + n_0' : n'_1 < n_1 - \;\hbox{et}\; n'_0 \in\mathbb{N}\} \cup\, \{\omega\, n_1 + n_0' : - n'_0 < n_0\}\big)$, qui est bien $\omega n_1 + n_0$ comme souhaité. + n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \penalty0 \cup + \penalty0 \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 < n_0\}\big)$. + D'après l'hypothèse d'induction, et en utilisant le fait que les + formes normales de Cantor des ordinaux se comparent + lexicographiquement, ceci vaut encore $\sup^+ \big( \{\omega\, n'_1 + + n_0' : n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \penalty0 + \cup \penalty0 \{\omega\, n_1 + n_0' : n'_0 < n_0\}\big)$, qui est + bien $\omega\, n_1 + n_0$ comme souhaité (il s'agit précisément du + $\sup^+$ de l'ensemble des ordinaux $<\omega\, n_1 + n_0$). \end{corrige} \medskip @@ -546,25 +556,35 @@ particulier, calculer $(\omega+1)\boxplus(\omega+1)$, et comparer avec $(\omega+1) + (\omega+1)$. \begin{corrige} -(a) En utilisant (*), on peut remplacer l'écriture en forme normale de - Cantor $\omega^{\gamma_1} n_1 + \cdots + \omega^{\gamma_r} n_r$ par - l'écriture analogue $(\omega^{\gamma_1} \boxdot n_1) \boxplus \cdots - \boxplus (\omega^{\gamma_r} \boxdot n_r)$ pour l'addition - naturelle ; en faisant ceci pour les deux ordinaux à ajouter, en - regroupant les puissances égales de $\omega$ et en convertissant de - nouveau en forme normale de Cantor (pour l'addition usuelle), on a - montré que la somme naturelle se fait en ajoutant simplement terme à - terme les formes normales de Cantor, i.e., on ajoute les chiffres - (=coefficients) de chaque puissance de $\omega$. +(a) Soient $\alpha = \omega^{\gamma_1} p_1 + \cdots + + \omega^{\gamma_r} p_r$ et $\beta = \omega^{\gamma_1} q_1 + \cdots + + \omega^{\gamma_r} q_r$ (quitte à insérer des $p_i$ et $q_i$ nuls + dans la forme normale de Cantor) avec $\gamma_1 > \cdots > + \gamma_r$. En utilisant (*), on peut écrire $\alpha = + (\omega^{\gamma_1} \boxdot p_1) \boxplus \cdots \boxplus + (\omega^{\gamma_r} \boxdot p_r)$ et $\beta = (\omega^{\gamma_1} + \boxdot q_1) \boxplus \cdots \boxplus (\omega^{\gamma_r} \boxdot + q_r)$. En utilisant la commutativité et l'associativité + de $\boxdot$ et en regroupant les puissances égales de $\omega$, on + obtient $\alpha \boxplus \beta = (\omega^{\gamma_1} \boxdot + (p_1+q_1)) \boxplus \cdots \boxplus (\omega^{\gamma_r} \boxdot + (p_r+q_r))$. Et quitte à utiliser de nouveau (*), on trouve $\alpha + \boxplus \beta = \omega^{\gamma_1} (p_1+q_1) + \cdots + + \omega^{\gamma_r} (p_r+q_r)$. On a ainsi montré que la somme + naturelle se fait en ajoutant simplement terme à terme les formes + normales de Cantor, i.e., on ajoute les chiffres (=coefficients) de + chaque puissance de $\omega$. (b) En particulier, $(\omega+1)\boxplus(\omega+1) = \omega\,2 + 2$ (qui est aussi $(\omega\boxdot 2)\boxplus 2$ comme on l'a vu), alors que $(\omega+1) + (\omega+1) = \omega + (1+\omega) + 1 = \omega + - \omega + 1 = \omega\,2 + 1$. + \omega + 1 = \omega\,2 + 1$ est strictement plus petit. \end{corrige} \medskip +(La question qui suit ne fait pas appel aux questions (3) et (4).) + (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 @@ -584,7 +604,7 @@ possède une stratégie gagnante lorsque $\rho = \alpha\boxplus\beta$. \begin{corrige} On procède par induction transfinie (sur -$\alpha\boxdot\beta\boxdot\rho$, si l'on veut) : on peut supposer la +$\alpha\boxplus\beta\boxplus\rho$, si l'on veut) : on peut supposer la conclusion déjà connue pour tous les $(\alpha',\beta,\rho)$, $(\alpha,\beta',\rho)$ et $(\alpha,\beta,\rho')$ tels que dans la question. @@ -594,21 +614,27 @@ définition de $\alpha\boxplus\beta$, il existe un $\alpha'\boxplus\beta$ avec $\alpha'<\alpha$ ou $\alpha\boxplus\beta'$ avec $\beta'<\beta$ qui majore $\rho$ (au sens large), et Blaise peut faire le coup correspondant $(\alpha',\beta,\rho)$ ou -$(\alpha,\beta',\rho)$ auquel cas il aura une stratégie gagnante par -hypothèse d'induction ; si $\rho \geq \alpha\boxplus\beta$, alors quel -que soit le coup $(\alpha',\beta,\rho)$ ou $(\alpha,\beta',\rho)$ fait -par Blaise, on aura $\rho > \alpha'\boxplus\beta$ ou $\rho > -\alpha\boxplus\beta'$ donc Roxane aura une stratégie gagnante. +$(\alpha,\beta',\rho)$ auquel cas il aura une stratégie gagnante comme +second joueur par hypothèse d'induction ; si $\rho \geq +\alpha\boxplus\beta$, alors quel que soit le coup +$(\alpha',\beta,\rho)$ ou $(\alpha,\beta',\rho)$ fait par Blaise, on +aura $\rho > \alpha'\boxplus\beta$ ou $\rho > \alpha\boxplus\beta'$ +donc Roxane aura une stratégie gagnante par hypothèse d'induction. Si Roxane joue en premier : si $\rho > \alpha\boxplus\beta$, alors elle peut jouer vers $(\alpha,\beta,\rho')$ avec $\rho' = -\alpha\boxplus\beta$, auquel cas elle aura une stratégie gagnante par -hypothèse d'induction. Si $\rho \leq \alpha\boxplus\beta$, alors quel -que soit le coup qu'elle fait, elle arrivera à un -$(\alpha,\beta,\rho')$ avec $\rho' < \alpha\boxplus\beta$ auquel cas -Blaise a une stratégie gagnante par hypothèse d'induction. +\alpha\boxplus\beta$, auquel cas elle comme second joueur aura une +stratégie gagnante par hypothèse d'induction. Si $\rho \leq +\alpha\boxplus\beta$, alors quel que soit le coup qu'elle fait, elle +arrivera à un $(\alpha,\beta,\rho')$ avec $\rho' < +\alpha\boxplus\beta$ auquel cas Blaise a une stratégie gagnante par +hypothèse d'induction. \end{corrige} +{\footnotesize Autrement dit, on a montré que l'addition des « nombres + (surréels) » de Conway coïncide, dans le cas particulier des + ordinaux, avec l'opération $\boxplus$ de somme naturelle.\par} + % % @@ -637,12 +663,12 @@ matrice des gains d'Alice vaut : \begin{center} \begin{tabular}{r|ccccc} -$\downarrow$Alice, Bob$\rightarrow$&$\mathtt{0}$&$\mathtt{1}$&$\mathtt{2}$&$\mathtt{3}$&$\mathtt{4}$\\\hline -$\mathtt{0}$&$0$&$-1$&$-1$&$-1$&$+1$\\ -$\mathtt{1}$&$+1$&$0$&$-1$&$-1$&$-1$\\ -$\mathtt{2}$&$+1$&$+1$&$0$&$-1$&$-1$\\ -$\mathtt{3}$&$+1$&$+1$&$+1$&$0$&$-1$\\ -$\mathtt{4}$&$-1$&$+1$&$+1$&$+1$&$0$\\ +$\downarrow$Alice, Bob$\rightarrow$&${0}$&${1}$&${2}$&${3}$&${4}$\\\hline +${0}$&$0$&$-1$&$-1$&$-1$&$+1$\\ +${1}$&$+1$&$0$&$-1$&$-1$&$-1$\\ +${2}$&$+1$&$+1$&$0$&$-1$&$-1$\\ +${3}$&$+1$&$+1$&$+1$&$0$&$-1$\\ +${4}$&$-1$&$+1$&$+1$&$+1$&$0$\\ \end{tabular} \end{center} @@ -697,8 +723,8 @@ dans $\{0, n-2, n-1\}$. Si on appelle $p_0, p_{-2}, p_{-1}$ les probabilités respectives de ces options dans $s$, on sait que $s$ doit avoir une espérance de gain nulle contre $s_0$, donc contre chacune des options pures $0$, $n-2$ et $n-1$, ce qui donne $p_{-2} = p_{-1}$, -$p_{-1} = p_0$ et $p_0 = p_{-2}$, bref, la seule possibilité est -$p_{-2} = p_{-1} = p_0 = \frac{1}{3}$. +$p_{-1} = p_0$ et $p_0 = p_{-2}$, bref, la seule possibilité est $p_0 += p_{-2} = p_{-1} = \frac{1}{3}$. \end{corrige} -- cgit v1.2.3