From 09af2d3256d2e2873b4533ef4e843a9674483b2d Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 19 Apr 2016 00:24:11 +0200 Subject: Re-read and check exam questions. --- controle-20160421.tex | 255 +++++++++++++++++++++++++++----------------------- 1 file 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} + % -- cgit v1.2.3