diff options
| -rw-r--r-- | controle-20190408.tex | 246 |
1 files 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 $<n$), expliquer comment on peut calculer $\gr -J(n)$ si on suppose connus tous les $\gr J(n')$ +(3)(a) Pour une règle de remplacement donnée, expliquer comment se +calcule $\gr J(n)$ si on suppose connus tous les $\gr J(n')$ pour $n'<n$.\quad(b) On rappelle que le seul remplacement possible -d'un jeton de type $0$ est de l'enlever purement et simplement (i.e., -$\mathscr{R}_0 = \{()\}$ si on veut) : en déduire la valeur de $\gr -J(0)$ et celle de $\gr J(0,\ldots,0)$ (avec, disons, $r$ jetons de -type $0$). +d'un jeton de type $0$ est de l'enlever purement et simplement : en +déduire la valeur de $\gr J(0)$ et celle de $\gr J(0,\ldots,0)$ (où il +y a $r$ jetons de type $0$). \begin{corrige} (a) Puisque $\gr x$, pour une position $x$ d'un jeu combinatoire impartial bien-fondé, vaut $\mex\{\gr y : y\in\outnb(x)\}$, on a ici - $\gr J(n) = \mex\{\gr J(y) : y\in\mathscr{R}_n\}$, c'est-à-dire $\gr - J(n) = \mex\{\gr J(n'_1) \oplus \cdots \oplus \gr J(n'_r) : - (n'_1,\ldots,n'_r)\in\mathscr{R}_n\}$ d'après (2)(b). - -(b) Dans le cas de $n=0$, on trouve $\gr J(0) = \mex\{0\} = 1$, et par - conséquent $\gr J(0,\ldots,0) = 1\oplus \cdots\oplus 1$ vaut - $0$ ou $1$ selon que $r$ est pair ou impair (si l'on veut, - $\frac{1}{2}(1+(-1)^r)$). + $\gr J(n) = \mex\{\gr J(n'_1,\ldots,n'_r) : J(n'_1,\ldots,n'_r) + \in\outnb J(n)\}$, c'est-à-dire $\gr J(n) = \mex\{\gr J(n'_1) \oplus + \cdots \oplus \gr J(n'_r) : J(n'_1,\ldots,n'_r)\in\outnb J(n)\}$ + d'après (2)(b) ; la règle de remplacement consiste justement à + décrire les $J(n'_1,\ldots,n'_r)\in\outnb J(n)$. + +(b) Dans le cas de $n=0$, comme $\outnb J(0) = \{J()\}$, on trouve + $\gr J(0) = \mex\{0\} = 1$, et par conséquent $\gr J(0,\ldots,0) = + 1\oplus \cdots\oplus 1$ vaut $0$ ou $1$ selon que $r$ est pair ou + impair. \end{corrige} \medskip @@ -277,27 +279,28 @@ jeu considéré dans cette question. somme de nim) de $r$ valeurs $1$ si $r$ est le nombre de jetons de type pair, et $r'$ valeurs $2$ si $r'$ est le nombre de jetons de type impair : ce nombre vaut $0$, $1$, $2$ ou $3$ selon que $r$ et - $r'$ sont tous les deux pairs, que $r$ est impair et $r'$ pair, le - contraire, ou qu'ils sont tous les deux impairs. La stratégie - gagnante consiste donc à jouer de façon que le nombre $r$ de jetons - de type pair et le nombre $r'$ de jetons de type impair soient tous - les deux pairs (de façon à annuler Grundy). + $r'$ sont tous les deux pairs, que $r$ est impair et $r'$ pair, + qu'on a le contraire, ou qu'ils sont tous les deux impairs. La + stratégie gagnante consiste donc à jouer de façon que le nombre $r$ + de jetons de type pair et le nombre $r'$ de jetons de type impair + soient tous les deux pairs (de façon à annuler Grundy). \end{corrige} \medskip (5) 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 type $k<n$, mais le type doit -être le même pour tous les jetons remplacés. (Autrement dit, à chaque -coup, le joueur retire un jeton de type $n$ et si $n>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 $k<n$, le type $k$ +pouvant être quelconque mais doit être le même pour tous les jetons +posés. (Autrement dit, à chaque coup, le joueur retire un jeton de +type $n$ et si $n>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$.) \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 $<n$. (Autrement dit, à +quelconque (y compris $0$) de jetons de types $<n$, qui cette fois +n'ont pas d'obligation d'être tous du même type. (Autrement dit, à chaque coup, le joueur retire un jeton de type $n$ et si $n>0$ il ajoute ensuite, optionnellement, le nombre qu'il souhaite de jetons de n'importe quels types $<n$. Par exemple, on peut remplacer un jeton @@ -364,7 +368,7 @@ On définit une opération binaire $\alpha\boxplus\beta$ (appelée notés $\alpha,\beta$) par la formule suivante : \[ \alpha \boxplus \beta = \sup\nolimits^+ \Big( \{\alpha'\boxplus\beta : -\alpha' < \alpha\} \cup\, \{\alpha\boxplus\beta' : \beta' < +\alpha' < \alpha\} \cup \{\alpha\boxplus\beta' : \beta' < \beta\}\Big) \] où on rappelle que $\sup^+ S$, si $S$ est un ensemble d'ordinaux, @@ -405,12 +409,12 @@ $m,n<\omega$).\quad(c) Démontrer cette formule. (c) Montrons que $m\boxplus n = m + n$ pour tous $m,n\in\mathbb{N}$ : par récurrence (sur $m+n$), on peut supposer connu le fait que $m'\boxplus n = m' + n$ pour tout $m'<m$ et $m\boxplus n' = m + n'$ - pour tout $n'<n$, alors $m\boxplus n$. On a alors $m \boxplus n = - \sup^+ \big( \{m' \boxplus n : m' < m\} \cup\, \{m \boxplus n' : n' - < n\}\big) = \sup^+ \big( \{m' + n : m' < m\} \cup\, \{m + n' : n' < - n\}\big)$ ; or l'ensemble dont on prend le $\sup^+$ ne contient que - des entiers $<m+n$ et contient $m+n-1$ donc ce $\sup^+$ vaut $m+n$, - ce qui conclut la récurrence. + pour tout $n'<n$. On a alors $m \boxplus n = \sup^+ \big( \{m' + \boxplus n : m' < m\} \penalty0 \cup \penalty0 \{m \boxplus n' : n' + < n\}\big) = \sup^+ \big( \{m' + n : m' < m\} \penalty0 \cup + \penalty0 \{m + n' : n' < n\}\big)$ ; or l'ensemble dont on prend le + $\sup^+$ ne contient que des entiers $<m+n$ et contient $m+n-1$ donc + ce $\sup^+$ vaut $m+n$, ce qui conclut la récurrence. \end{corrige} \medskip @@ -429,9 +433,10 @@ l'hypothèse. (a) Par induction transfinie sur $\alpha_1$ et $\alpha_2$, on prouve $\alpha_2\boxplus\alpha_1 = \alpha_1\boxplus\alpha_2$ : en effet, $\alpha_2\boxplus\alpha_1 = \sup^+ (\{\alpha_2\boxplus\beta_1: - \beta_1<\alpha_1\} \cup \{\beta_2\boxplus\alpha_1: - \beta_2<\alpha_2\})$, et par hypothèse d'induction ceci vaut $\sup^+ - (\{\beta_1\boxplus\alpha_2: \beta_1<\alpha_1\} \cup + \beta_1<\alpha_1\} \penalty0 \cup \penalty0 + \{\beta_2\boxplus\alpha_1: \beta_2<\alpha_2\})$, et par hypothèse + d'induction ceci vaut $\sup^+ (\{\beta_1\boxplus\alpha_2: + \beta_1<\alpha_1\} \penalty0 \cup \penalty0 \{\alpha_1\boxplus\beta_2: \beta_2<\alpha_2\}) = \alpha_1\boxplus\alpha_2$. @@ -455,7 +460,7 @@ l'hypothèse. 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 on admettra que +$\alpha_1,\alpha_2,\alpha_3$ ; et on admettra aussi 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 @@ -479,10 +484,10 @@ question (1). Considérons l'affirmation suivante : {\narrower\noindent\leavevmode\llap{(*) }si $\alpha = - \omega^{\gamma_1} n_1 + \cdots + \omega^{\gamma_r} n_r$ (où + \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 + 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} |