summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2019-04-05 00:43:32 +0200
committerDavid A. Madore <david+git@madore.org>2019-04-05 00:43:32 +0200
commit4b111f4a5720fcadc331cc3b5185b4e503b56bce (patch)
tree8b0794f970605b5f1ca93d17df7da02dc002553e
parentdc474838b2ad1607dc077ab0d3353c77065cfc39 (diff)
downloadmitro206-4b111f4a5720fcadc331cc3b5185b4e503b56bce.tar.gz
mitro206-4b111f4a5720fcadc331cc3b5185b4e503b56bce.tar.bz2
mitro206-4b111f4a5720fcadc331cc3b5185b4e503b56bce.zip
Re-read exam.
-rw-r--r--controle-20190408.tex246
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}