summaryrefslogtreecommitdiffstats
path: root/controle-20160421.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-04-19 00:24:11 +0200
committerDavid A. Madore <david+git@madore.org>2016-04-19 00:24:11 +0200
commit09af2d3256d2e2873b4533ef4e843a9674483b2d (patch)
treea52205eb67ce773dd4efcf286ea9a91f657ce70b /controle-20160421.tex
parent1a3036ac70527dcfce89a76f0a10cffac10361d1 (diff)
downloadmitro206-09af2d3256d2e2873b4533ef4e843a9674483b2d.tar.gz
mitro206-09af2d3256d2e2873b4533ef4e843a9674483b2d.tar.bz2
mitro206-09af2d3256d2e2873b4533ef4e843a9674483b2d.zip
Re-read and check exam questions.upload-20160421exam-20160421
Diffstat (limited to 'controle-20160421.tex')
-rw-r--r--controle-20160421.tex255
1 files changed, 138 insertions, 117 deletions
diff --git a/controle-20160421.tex b/controle-20160421.tex
index eaa536c..8720f49 100644
--- a/controle-20160421.tex
+++ b/controle-20160421.tex
@@ -97,6 +97,10 @@ est précisé. Ils pourront être traités 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 de l'énoncé ne doit pas décourager : les exercices ont été
+formulés de manière à rappeler le contexte et certaines notions du
+cours.
+
Il n'est pas nécessaire de faire des réponses longues. Notamment, si
certaines réponses sont très semblables à des exercices déjà traités
en cours, on pourra donner une justification lapidaire, mais on
@@ -199,11 +203,13 @@ v - 0p_U - 4p_V &\leq 0\;\;\text{(Y)}\\
On peut l'écrire sous forme normale en réécrivant $v = v_+ - v_-$ avec
$v_+,v_- \geq 0$, mais on gagne un petit peu en remarquant que $v$
sera forcément positif puisque tous les gains du tableau le sont, donc
-on peut ajouter la contrainte $v \geq 0$. Une application de
-l'algorithme du simplexe donne finalement l'optimum $v = 2$ atteint
-pour $p_U = \frac{2}{3}$ et $p_V = \frac{1}{3}$, avec pour le dual
-$q_X = \frac{1}{2}$ et $q_Y = \frac{1}{2}$ (les inégalités (X) et (Y)
-sont toutes les deux saturées).
+on peut ajouter la contrainte $v \geq 0$. Pour la même raison, on
+peut transformer la contrainte d'égalité $p_U + p_V = 1$ en
+l'inégalité $p_U + p_V \leq 1$. Une application de l'algorithme du
+simplexe donne finalement l'optimum $v = 2$ atteint pour $p_U =
+\frac{2}{3}$ et $p_V = \frac{1}{3}$, avec pour le dual $q_X =
+\frac{1}{2}$ et $q_Y = \frac{1}{2}$ (les inégalités (X) et (Y) sont
+toutes les deux saturées).
Autrement dit, Alice joue les options U et V avec probabilités
$\frac{1}{3}$ et $\frac{2}{3}$, Bob réplique avec les options X et Y
@@ -222,17 +228,17 @@ somme $1$) sont les poids des deux options d'Alice (=probabilités
qu'elle les joue), et $q_X,q_Y$ (positifs, également de somme $1$) les
poids des deux options de Bob. On va discuter selon le support des
stratégies (i.e., selon les ensembles d'options qui ont un poids
-strictement positif).\spaceout (a) Pour commencer, quels sont les
-équilibres de Nash évidents en stratégies pures ? Expliquer pourquoi
-ce sont bien les seuls équilibres de Nash où l'un des deux joueurs a
-une stratégie pure.\spaceout (b) Calculer ce que doivent valoir $p_U$
-et $p_V$ dans un équilibre de Nash où $q_X > 0$ et $q_Y > 0$ (i.e.,
-les options X et Y de Bob sont dans le support), et ce que doivent
-valoir $q_X$ et $q_Y$ dans un équilibre de Nash où $p_U > 0$ et $p_V >
-0$ (i.e., les options U et V d'Alice sont dans le support). Ces
-contraintes donnent-elles effectivement un équilibre de
-Nash ?\spaceout (c) Conclure quant à l'ensemble des équilibres de Nash
-du jeu considéré.
+strictement positif).\spaceout (a) Quels sont les équilibres de Nash
+évidents en stratégies pures ? Expliquer pourquoi ce sont bien les
+seuls équilibres de Nash où l'un des deux joueurs a une stratégie
+pure.\spaceout (b) Calculer ce que doivent valoir $p_U$ et $p_V$ dans
+un équilibre de Nash où $q_X > 0$ et $q_Y > 0$ (i.e., les options X et
+Y de Bob sont dans le support), et ce que doivent valoir $q_X$ et
+$q_Y$ dans un équilibre de Nash où $p_U > 0$ et $p_V > 0$ (i.e., les
+options U et V d'Alice sont dans le support). Ces contraintes
+donnent-elles effectivement un équilibre de Nash ?\spaceout
+(c) Conclure quant à l'ensemble des équilibres de Nash du jeu
+considéré.
\begin{corrige}
(a) Deux équilibres de Nash sont évidents : si Alice joue (purement) U
@@ -255,7 +261,7 @@ donnent forcément le même gain, car si l'une d'elle donnait un gain
strictement supérieure à l'autre, Bob aurait intérêt à augmenter le
poids $q$ correspondant et améliorerait ainsi strictement sa réponse.
Autrement dit, l'espérance de gain contre la stratégie pure X,
-c'est-à-dire $6 p_U$, est égale à l'espérance de gain contre la
+c'est-à-dire $3 p_U$, est égale à l'espérance de gain contre la
stratégie pure Y, soit $p_U + 4 p_V$. On a donc $3 p_U = p_U + 4
p_V$, et comme aussi $p_U + p_V = 1$ on trouve $(p_U, p_V) =
(\frac{1}{3}, \frac{2}{3})$ en résolvant le système (soit la même
@@ -268,15 +274,17 @@ raisonnement). De même, si $p_U > 0$ et $p_V > 0$, on a $3 q_X + q_Y
Bref, on a un équilibre de Nash \emph{potentiel} donné par $(p_U,p_V,
q_X,q_Y) = (\frac{2}{3}, \frac{1}{3}, \frac{1}{2}, \frac{1}{2})$,
c'est-à-dire exactement le même profil que dans la question (3) quand
-les joueurs étaient adversaires. Pourtant, aucun des deux joueurs n'a
-(strictement) intérêt à changer unilatéralement sa stratégie puisque
-les deux options qui se présentent à lui sont indifférentes (elles ont
-le même gain espéré) compte tenu du comportement de l'autre. On a
-donc bien trouvé un troisième équilibre de Nash.
+les joueurs étaient adversaires. Ceci peut surprendre, mais le fait
+est qu'aucun des deux joueurs n'a (strictement) intérêt à changer
+unilatéralement sa stratégie puisque les deux options qui se
+présentent à lui sont indifférentes (elles ont le même gain espéré)
+compte tenu du comportement de l'autre. On a donc bien trouvé un
+troisième équilibre de Nash.
(c) Pour résumer, on a trois équilibres de Nash récapitulés par le
tableau (triés par ordre de gain espéré décroissant) :
\begin{center}
+\vskip-\baselineskip
\begin{tabular}{cc|cc|c}
$p_U$&$p_V$&$q_X$&$q_Y$&gain\\\hline
$0$&$1$&$0$&$1$&$4$\\
@@ -297,8 +305,9 @@ et on a prouvé que c'étaient bien les seuls.
On considère le jeu suivant : une position du jeu consiste en un
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.
+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 sans effet particulier (ils s'empilent).
Un coup du jeu consiste à faire l'opération suivante : le joueur qui
doit jouer choisit un jeton du jeu, disons sur la case
@@ -307,10 +316,9 @@ $(\alpha,\beta)$, et il choisit aussi arbitrairement $\alpha' <
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é.
+(Par exemple, un coup valable consiste à remplacer un jeton sur la
+case $(42,7)$ par trois sur les cases $(18,7)$, $(42,5)$ et $(18,5)$.)
+Le nombre de jetons augmente donc de $2$ à chaque coup.
\begin{center}
\vskip-\baselineskip
@@ -324,8 +332,8 @@ présents augmente donc de $2$ à chaque coup joué.
\end{scope}
\node[anchor=east] at (0,-0.75) {$\alpha'$};
\node[anchor=east] at (0,-1.75) {$\alpha$};
-\node[anchor=south] at (1.25,0) {$\beta'$};
-\node[anchor=south] at (2.75,0) {$\beta$};
+\node[anchor=south] at (1.25,-0.1) {$\beta'$};
+\node[anchor=south] at (2.75,-0.1) {$\beta$};
\end{tikzpicture}
\\{\footnotesize (Le jeton en gris remplacé par les trois noirs.)}
\end{center}
@@ -336,11 +344,13 @@ dire que cette ligne et cette colonne $0$ sont la « défausse » des
jetons. Le jeu se termine lorsque chacun des jetons est sur la ligne
ou la colonne $0$ (=dans la défausse), car il n'est alors plus
possible de jouer. Les joueurs (Alice et Bob) jouent à tour de rôle
-et celui qui ne peut plus jouer a perdu.
+et le premier qui ne peut plus jouer a perdu.
+
+\smallbreak
(0) Décrire brièvement le jeu complètement équivalent dans lequel il
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
+à $1$), c'est-à-dire pas de défausse (les jetons disparaissent plutôt
qu'être défaussés) : quels sont les types de coups possibles à ce
jeu ? (Distinguer selon que $\alpha'=0$ ou non, et selon que
$\beta'=0$ ou non.) On se permettra dans la suite d'utiliser
@@ -385,15 +395,15 @@ les chiffres de la forme normale de Cantor sont la somme des chiffres
correspondants de $\alpha$ et de $\beta$.\spaceout (b) En déduire que
le jeu considéré dans cet exercice termine toujours en temps fini.
(On pourra par exemple considérer la somme des $\omega^\gamma$ où
-$\gamma$ parcourt les $h(\alpha,\beta)$ des cases où il y a un jeton,
-dans l'ordre décroissant.)
+$\gamma$ parcourt, dans l'ordre décroissant, les valeurs
+$h(\alpha,\beta)$ pour les cases $(\alpha,\beta)$ où il y a un jeton.)
\begin{corrige}
(a) Si on pose $h(\alpha,\beta) = \omega^{\max(\alpha,\beta)} +
\omega^{\min(\alpha,\beta)}$ et si $\alpha' < \alpha$, alors soit
- $\max(\alpha,\beta) < \max(\alpha',\beta)$ soit $\max(\alpha,\beta)
- = \max(\alpha',\beta)$ et alors $\min(\alpha,\beta) <
- \min(\alpha',\beta)$, et dans les deux cas $h(\alpha',\beta) <
+ $\max(\alpha',\beta) < \max(\alpha,\beta)$ soit $\max(\alpha',\beta)
+ = \max(\alpha,\beta)$ et alors $\min(\alpha',\beta) <
+ \min(\alpha,\beta)$ : dans les deux cas, $h(\alpha',\beta) <
h(\alpha,\beta)$ par comparaison des formes normales de Cantor.
Comme la fonction $h$ est symétrique en ses deux arguments, on a
aussi $h(\alpha,\beta') < h(\alpha,\beta)$ si $\beta' < \beta$.
@@ -408,26 +418,28 @@ h(\alpha,\beta)$. Comme la fonction $h$ est symétrique en ses deux
arguments, on a aussi $h(\alpha,\beta') < h(\alpha,\beta)$ si $\beta'
< \beta$.
+{\footnotesize
(\emph{Remarque :} En fait, la fonction $\boxplus$, aussi appelée
-« somme naturelle » sur les ordinaux, est plus naturelle dans ce
+« somme naturelle » sur les ordinaux, est plus adaptée dans ce
contexte, parce qu'on peut se convaincre que $\alpha \boxplus \beta =
\sup^+ \big( \{\alpha'\boxplus\beta : \alpha' < \alpha\} \cup\,
\{\alpha\boxplus\beta' : \beta' < \beta\}\big)$, c'est-à-dire qu'elle
-est justement la « plus petite » fonction strictement croissante en
-chacun de ses arguments. On comparera cette définition avec $\alpha
-\oplus \beta = \mex \big( \{\alpha'\oplus\beta : \alpha' < \alpha\}
-\cup\, \{\alpha\oplus\beta' : \beta' < \beta\}\big)$. En revanche,
+est justement la plus petite fonction strictement croissante en chacun
+de ses arguments. On comparera cette définition avec $\alpha \oplus
+\beta = \mex \big( \{\alpha'\oplus\beta : \alpha' < \alpha\} \cup\,
+\{\alpha\oplus\beta' : \beta' < \beta\}\big)$. En revanche,
l'addition usuelle ne convient pas, parce que $\alpha'+\beta$ peut
être égal à $\alpha+\beta$ même si $\alpha'<\alpha$, par exemple
$1+\omega = 0+\omega$.)
+\par}
(b) À une position du jeu ayant $s$ jetons sur les
cases $(\alpha_i,\beta_i)$ (pour $i=1,\ldots,s$) on peut associer
l'ordinal $\omega^{\gamma_1} + \cdots + \omega^{\gamma_s}$ où les
$\gamma_i := h(\alpha_i,\beta_i)$ ont été triés de façon à avoir
-$\gamma_1 > \cdots > \gamma_s$ (donc, quitte à regrouper les mêmes
-puissances, à avoir une forme normale de Cantor). Un coup consistae à
-remplacer un terme $\omega^{\gamma_i}$ par une somme de
+$\gamma_1 \geq \cdots \geq \gamma_s$ (donc, quitte à regrouper les
+mêmes puissances, à avoir une forme normale de Cantor). Un coup
+consiste à remplacer un terme $\omega^{\gamma_i}$ par une somme de
$\omega^{\gamma'}$ pour des $\gamma' < \gamma_i$ vu que
$h(\alpha',\beta) < h(\alpha,\beta)$ et $h(\alpha,\beta') <
h(\alpha,\beta)$ et \textit{a fortiori} $h(\alpha',\beta') <
@@ -498,28 +510,28 @@ inductive), et on a montré ce qui était demandé.
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
+détailler les calculs, mais on recommande de les vérifier
soigneusement.
\begin{corrige}
-En calculant un peu plus loin que ce qui était demandé, on trouve :
+En procédant inductivement, on trouve :
{\[
-\begin{array}{c|cccccccccccccccc}
-\otimes&0&1&2&3&4&5&6&7\\\hline
-0&0&0&0&0&0&0&0&0\\
-1&0&1&2&3&4&5&6&7\\
-2&0&2&3&1&8&10&11&9\\
-3&0&3&1&2&12&15&13&14\\
-4&0&4&8&12&6&2&14&10\\
-5&0&5&10&15&2&7&8&13\\
-6&0&6&11&13&14&8&5&3\\
-7&0&7&9&14&10&13&3&4\\
+\begin{array}{c|cccccccccccccc}
+\otimes&0&1&2&3&4&5\\\hline
+0&0&0&0&0&0&0\\
+1&0&1&2&3&4&5\\
+2&0&2&3&1&8&10\\
+3&0&3&1&2&12&15\\
+4&0&4&8&12&6&2\\
+5&0&5&10&15&2&7\\
\end{array}
\]}
(pour simplifier les calculs, on peut notamment utiliser la
commutativité, et le fait que $\alpha\otimes 3 = \alpha\otimes(2\oplus
1) = (\alpha\otimes 2) \oplus \alpha$ et de même $\alpha\otimes 5 =
-\alpha\otimes(4\oplus 1) = (\alpha\otimes 4) \oplus \alpha$).
+\alpha\otimes(4\oplus 1) = (\alpha\otimes 4) \oplus \alpha$ ; si on
+n'a pas l'habitude de calculer des sommes de nim, le mieux est sans
+doute de tout écrire en binaire, quitte à reconvertir ensuite).
\end{corrige}
\smallbreak
@@ -556,7 +568,7 @@ n'est pas figurée), quel coup feriez-vous ?
La valeur de Grundy est $(1\otimes 1) \oplus (2\otimes 2) \oplus
(3\otimes 3) \oplus (4\otimes 4) \oplus (5\otimes 5) = 1 \oplus 3
\oplus 2 \oplus 6 \oplus 7 = 1$, et on veut l'annuler. Plusieurs
-coups gagnants sont possibles, par exemple : retirer le jeton en
+coups sont possibles pour y arriver, par exemple : retirer le jeton en
$(1,1)$ (c'est-à-dire jouer $(\alpha,\beta,\alpha',\beta') =
(1,1,0,0)$) ; ou bien, remonter le jeton $(3,3)$ en $(1,3)$
(c'est-à-dire jouer $(\alpha,\beta,\alpha',\beta') = (3,3,1,0)$) ; ou
@@ -609,8 +621,8 @@ fonction de Grundy.
(2) Montrer que $0$ est absorbant pour $\otimes$,
c'est-à-dire $\alpha\otimes 0 = 0$ pour tout ordinal $\alpha$.
-Montrer que $1$ est neutre pour otimes, c'est-à-dire $\alpha\otimes 1
-= \alpha$ pour tout ordinal $\alpha$.
+Montrer que $1$ est neutre pour $\otimes$, soit $\alpha\otimes 1 =
+\alpha$ pour tout ordinal $\alpha$.
\begin{corrige}
On a $\alpha \otimes 0 = \mex \varnothing = 0$ (puisqu'il n'existe pas
@@ -619,8 +631,7 @@ $\alpha$, on prouve $\alpha \otimes 1 = \alpha$ : en effet, $\alpha
\otimes 1 = \mex \{(\alpha'\otimes 1) \oplus (\alpha\otimes 0) \oplus
(\alpha'\otimes 0): \alpha'<\alpha\}$, et en utilisant le fait que $0$
est aborbant pour $\otimes$ et neutre pour $\oplus$ et l'hypothèse
-d'induction, ceci vaut $\mex \{\alpha': \alpha'<\alpha\} = \mex \alpha
-= \alpha$.
+d'induction, ceci vaut $\mex \{\alpha': \alpha'<\alpha\} = \alpha$.
Si on préfère, on peut aussi utiliser le jeu défini dans
l'exercice \ref{game-for-nim-product}, en remarquant qu'un jeton sur
@@ -631,28 +642,24 @@ de l'exercice \ref{game-for-nim-product}.
\smallbreak
-(3) (a) Montrer que si $\alpha\otimes\beta = \alpha\otimes\beta'$
-alors $\alpha=0$ ou bien $\beta=\beta'$ (on pourra procéder par
-contraposée).\spaceout (b) En déduire que si $\alpha'\neq\alpha$ et
-$\beta'\neq\beta$, alors $(\alpha'\otimes\beta) \oplus
-(\alpha\otimes\beta') \oplus (\alpha'\otimes\beta') \neq
-\alpha\otimes\beta$.
+(3) (b) Montrer que si $\alpha'\neq\alpha$ et $\beta'\neq\beta$, alors
+$(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
+(\alpha'\otimes\beta') \neq \alpha\otimes\beta$.\spaceout (a) En
+déduire que si $\alpha\otimes\beta = \alpha\otimes\beta'$ alors
+$\alpha=0$ ou bien $\beta=\beta'$.
\begin{corrige}
-(a) Si $\alpha>0$ et $\beta\neq\beta'$, supposons sans perte de
- généralité que $\beta'<\beta$. Alors $\alpha\otimes\beta$ est
- le $\mex$ d'un ensemble contenant $(0\otimes\beta) \oplus
- (\alpha\otimes\beta') \oplus (0\otimes\beta') =
- \alpha\otimes\beta'$, donc il ne peut pas lui être égal.
-
-(b) Grâce aux propriétés de la somme de nim ($\gamma \neq \gamma'$
+(a) Grâce aux propriétés de la somme de nim ($\gamma \neq \gamma'$
équivaut à $\gamma\oplus\gamma' \neq 0$), la condition qu'on veut
montrer est équivalente à : $(\alpha\otimes\beta) \oplus
(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
(\alpha'\otimes\beta') \neq 0$. Sous cette forme, on voit qu'il y a
symétrie entre $\alpha'$ et $\alpha$ et entre $\beta'$ et $\beta$ :
on peut donc supposer $\alpha'<\alpha$ et $\beta'<\beta$, auquel cas
- la condition est claire par la définition même de $\otimes$.
+ la propriété est claire par la définition même de $\otimes$ comme
+ un $\mex$.
+
+(b) C'est le cas particulier du (a) lorsque $\alpha'=0$.
\end{corrige}
\smallbreak
@@ -662,21 +669,20 @@ $\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$.
+$\xi\neq\lambda$. (Et on rappelle que si $\xi < \mex S$ alors $\xi\in
+S$.)
\begin{corrige}
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$ : en effet, si on avait $\lambda > \mu$, on aurait
-une contradiction en posant $\xi = \mu$ dans (a), et si on avait
-$\lambda < \mu$, on aurait une contradiction en posant $\xi = \lambda$
-dans (b).
+$\xi\neq\lambda$ : en effet, la contraposée de (a) est que
+$\mu\geq\lambda$, et la contraposée de (b) est que $\lambda\geq\mu$.
Procédons par induction pour prouver $\alpha \otimes
(\beta\oplus\gamma) = (\alpha\otimes\beta) \oplus
-(\alpha\otimes\gamma)$ : on peut supposer cette égalité connue si l'un
-des ordinaux $\alpha,\beta,\gamma$ est remplacé par un strictement
-plus petit.
+(\alpha\otimes\gamma)$ : on peut supposer cette égalité connue si au
+moins l'un des ordinaux $\alpha,\beta,\gamma$ est remplacé par un
+strictement plus petit.
(a) Si $\xi < \alpha \otimes (\beta\oplus\gamma)$, alors on peut
écrire $\xi = (\alpha'\otimes(\beta\oplus\gamma)) \oplus
@@ -695,7 +701,7 @@ apparaissent, on obtient $\xi = (\alpha'\otimes\beta) \oplus
(\alpha\otimes\gamma)$. Puisque la somme $(\alpha'\otimes\beta)
\oplus (\alpha\otimes\beta') \oplus (\alpha'\otimes\beta')$ des trois
premiers termes est différente de $\alpha\otimes\beta$
-(d'après (3)(b)), on en déduit que $\xi \neq (\alpha\otimes\beta)
+(d'après (3)(a)), on en déduit que $\xi \neq (\alpha\otimes\beta)
\oplus (\alpha\otimes\gamma)$, ce qu'on voulait.
(b) Maintenant, si $\xi < (\alpha\otimes\beta) \oplus
@@ -712,7 +718,7 @@ faire apparaître deux termes $\alpha'\otimes\gamma$ qui s'annulent,
l'hypothèse d'induction permet de réécrire $\xi = (\alpha'\otimes
(\beta\oplus\gamma)) \oplus (\alpha\otimes (\beta'\oplus\gamma))
\oplus (\alpha'\otimes (\beta'\oplus\gamma))$. Or $\beta'\oplus\gamma
-\neq \beta\oplus\gamma$ : en utilisant (3)(b), on a $\xi \neq \alpha
+\neq \beta\oplus\gamma$ : en utilisant (3)(a), on a $\xi \neq \alpha
\otimes (\beta\oplus\gamma)$, ce qu'on voulait.
\end{corrige}
@@ -725,24 +731,25 @@ $(\alpha\otimes\beta) \otimes \gamma = \alpha \otimes
(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'
+l'absurde le contraire, et on considère $\alpha$ le \emph{plus petit}
+ordinal non nul qui n'a pas d'inverse, et on va arriver à une
+contradiction. Pour cela, appelons $\gamma_0 = \sup^+ \big(\{\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 à $\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 nim 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
@@ -764,20 +771,20 @@ déduire que $\alpha\otimes\delta = 1$ et conclure.
\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'$.
+ alors comme $(\alpha')^* < \gamma_0 \leq \delta$, on a
+ $(\alpha')^*\otimes (\alpha' \otimes \delta) < \delta$ d'après (a).
+ Or $(\alpha')^* \otimes (\alpha' \otimes \delta) = \delta$ par
+ associativité et par le fait que $(\alpha')^*$ est l'inverse
+ de $\alpha'$ : contradiction.
(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).
+ $\gamma := (\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
+ de $\gamma$, 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') =
@@ -795,6 +802,20 @@ déduire que $\alpha\otimes\delta = 1$ et conclure.
que $\alpha$ n'ait pas d'inverse.
\end{corrige}
+\smallbreak
+
+{\footnotesize
+\emph{Remarque :} On a donc vu que les ordinaux, pour les opérations
+$\oplus$ et $\otimes$, i.e., les « nimbres », forment donc un
+\emph{corps} commutatif, corps dit de « caractéristique $2$ »
+car $1\oplus 1 = 0$. Un raisonnement assez semblable à celui fait
+en (5) permettrait de montrer, en outre, que ce corps est
+« algébriquement clos », c'est-à-dire que tout polynôme non constant y
+a une racine. Les entiers naturels strictement inférieurs
+à $2^{2^r}$, quant à eux, forment le corps fini ayant ce nombre
+d'éléments.)
+\par}
+
%