From 8ea916c312f489069dd3927b49b9e02092752355 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 2 Feb 2017 15:49:34 +0100
Subject: Copy exercises from last year's exam to course notes.

---
 notes-mitro206.tex | 691 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 691 insertions(+)

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 0de0d43..d51a7e7 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -5784,6 +5784,175 @@ multiplication peut même être définie entre un nombre réel et [la
 
 \exercice
 
+Alice joue contre Bob un jeu dans lequel elle choisit une option parmi
+deux possibles appelées U et V, et Bob choisit une option parmi deux
+appelées X et Y (les modalités du choix varient selon les questions
+ci-dessous) : les gains d'\emph{Alice} (c'est-à-dire, la fonction
+qu'elle cherche à maximiser) sont donnés par le tableau ci-dessous, en
+fonction de son choix (colonne de gauche) et de celui de Bob (ligne du
+haut) :
+
+\begin{center}
+\begin{tabular}{r|ccc}
+$\downarrow$A, B$\rightarrow$&X&Y\\\hline
+U&$3$&$1$\\
+V&$0$&$4$\\
+\end{tabular}
+\end{center}
+
+\smallbreak
+
+(1) On suppose que Bob fait son choix \emph{après} Alice, et en
+connaissant le choix d'Alice, et qu'il cherche à minimiser le gain
+d'Alice (i.e., le gain de Bob est l'opposé de celui d'Alice).  Comment
+Alice a-t-elle intérêt à jouer et comment Bob répondra-t-il ?  Quelle
+est le gain d'Alice dans ce cas ?
+
+\begin{corrige}
+Si Alice choisit U, Bob répondra par Y et le gain d'Alice sera $1$ ;
+si Alice choisit V, Bob répondra par X et le gain d'Alice sera $0$.
+Comme Alice veut maximiser son gain, elle a intérêt à choisir U, et
+Bob répondra par Y, et le gain d'Alice sera $1$ dans ce cas.
+\end{corrige}
+
+\smallbreak
+
+(2) On suppose maintenant que Bob fait son choix \emph{avant} Alice,
+et qu'Alice connaîtra le choix de Bob ; on suppose toujours que Bob
+cherche à minimiser le gain d'Alice.  Que fera Bob et comment Alice
+répondra-t-elle ?  Quelle est le gain d'Alice dans ce cas ?
+
+\begin{corrige}
+Si Bob choisit X, Alice répondra par U et le gain d'Alice sera $3$ ;
+si Bob choisit Y, Alice répondra par V et le gain d'Alice sera $4$.
+Comme Bob veut minimiser le gain d'Alice, il a intérêt à choisir X, et
+Alice répondra par U, et le gain d'Alice sera $3$ dans ce cas.
+\end{corrige}
+
+\smallbreak
+
+(3) On suppose qu'Alice et Bob font leur choix séparément, sans
+connaître le choix de l'autre, et toujours que Bob cherche à minimiser
+le gain d'Alice.  Comment ont-ils intérêt à faire leurs choix ?  Quel
+est le gain (espéré) d'Alice dans ce cas ?
+
+\begin{corrige}
+On a affaire à un jeu à somme nulle écrit en forme normale :
+l'algorithme \ref{zero-sum-games-by-linear-programming-algorithm} nous
+indique qu'on obtient la stratégie optimale d'Alice en résolvant le
+problème de programmation linéaire suivant :
+\[
+\left\{
+\begin{aligned}
+\text{maximiser\ }v&\text{\ avec}\\
+p_U \geq 0\;, \;\; p_V \geq 0&\\
+p_U + p_V &= 1\\
+v - 3p_U - 0p_V &\leq 0\;\;\text{(X)}\\
+v - 1p_U - 4p_V &\leq 0\;\;\text{(Y)}\\
+\end{aligned}
+\right.
+\]
+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$.  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
+de façon équiprobable, et le gain espéré d'Alice est $2$, qui est la
+valeur du jeu à somme nulle en forme normale considéré ici.
+\end{corrige}
+
+\smallbreak
+
+(4) On suppose maintenant que Bob cherche à \emph{maximiser} le gain
+d'Alice (i.e., il n'est plus son adversaire comme dans les questions
+(1), (2) et (3), mais son allié).  On cherche à déterminer quels sont
+les équilibres de Nash possibles.  On notera $(p_U,p_V, q_X,q_Y)$ un
+profil de stratégies mixtes général, où $p_U,p_V$ (positifs de
+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) 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
+  et Bob joue (purement) X, aucun n'a intérêt à changer puisque $3$
+  est maximum sur la ligne et sur la colonne ; si Alice joue
+  (purement) V et Bob joue (purement) Y, aucun n'a intérêt à changer
+  puisque $4$ est maximum sur la ligne et sur la colonne.  Les gains
+  d'Alice (et de Bob) dans chacun de ces cas sont donc $3$ et $4$
+  respectivement.
+
+Il s'agit là de l'ensemble des équilibres de Nash où l'un des deux
+joueurs a une stratégie pure : par exemple, si Alice joue purement U,
+Bob ne peut que répondre par purement X puisque le gain $3$ est
+strictement plus grand que tout autre gain sur la ligne (i.e., donner
+un poids non nul à une autre option de Bob ne pourrait que diminuer le
+gain).
+
+(b) Si $q_X > 0$ et $q_Y > 0$, les stratégies pures X et Y de Bob
+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 $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
+stratégie mixte que trouvée en (3), ce qui n'est pas un hasard vu que
+le signe des gains de Bob n'est pas du tout intervenu dans le
+raisonnement).  De même, si $p_U > 0$ et $p_V > 0$, on a $3 q_X + q_Y
+= 4 q_Y$, et comme aussi $q_X + q_Y = 1$ on trouve $(q_X, q_Y) =
+(\frac{1}{2}, \frac{1}{2})$ en résolvant le système (même remarque).
+
+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.  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$\\
+$1$&$0$&$1$&$0$&$3$\\
+$\frac{2}{3}$&$\frac{1}{3}$&$\frac{1}{2}$&$\frac{1}{2}$&$2$\\
+\end{tabular}
+\end{center}
+et on a prouvé que c'étaient bien les seuls.
+\end{corrige}
+
+%
+%
+%
+
+\exercice
+
 Alice joue contre Bob un jeu dans lequel elle choisit une option parmi
 trois possibles appelées U, V et W, et Bob choisit une option parmi
 trois appelées X, Y et Z (les modalités du choix varient selon les
@@ -6971,6 +7140,528 @@ représentation binaire.  Ceci démontre donc la conjecture.
 \end{corrige}
 
 
+%
+%
+%
+
+\exercice\label{game-for-nim-product}
+
+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 [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
+$(\alpha,\beta)$, et il choisit aussi arbitrairement $\alpha' <
+\alpha$ (i.e., une ligne située plus haut) et $\beta' < \beta$ (i.e.,
+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')$.
+(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
+\begin{tikzpicture}
+\draw[step=.5cm,help lines] (0,-2) grid (3.5,0);
+\begin{scope}[every node/.style={circle,fill,inner sep=1.2mm}]
+\node at (1.25,-0.75) {};
+\node at (1.25,-1.75) {};
+\node at (2.75,-0.75) {};
+\node[fill=gray] at (2.75,-1.75) {};
+\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.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}
+
+On remarquera que les jetons sur la ligne ou la colonne $0$ ne peuvent
+plus être retirés ou servir de quelque manière que ce soit : on pourra
+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 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$), 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
+librement l'une ou l'autre variante du jeu.
+
+\begin{corrige}
+Les jetons défaussés ne jouant aucun rôle dans le jeu, on peut les
+ignorer et obtenir un jeu équivalent.  Les lignes et les colonnes sont
+alors numérotés par des ordinaux non nuls, c'est-à-dire $\geq 1$.  Les
+quatre types de coups possibles dans ce jeu, selon que $\alpha'$ et/ou
+$\beta'$ vaut $0$, sont alors :
+\begin{itemize}
+\item simplement retirer un jeton de la case $(\alpha,\beta)$ [cas où
+  $\alpha' = 0$ et $\beta' = 0$],
+\item déplacer un jeton de la case $(\alpha,\beta)$ vers une case
+  $(\alpha,\beta')$ plus à gauche (i.e., $\beta' < \beta$) dans la
+  ligne [cas où $\alpha' = 0$ et $\beta' \neq 0$],
+\item déplacer un jeton de la case $(\alpha,\beta)$ vers une case
+  $(\alpha',\beta)$ plus haut (i.e., $\alpha' < \alpha$) dans la
+  colonne [cas où $\alpha' \neq 0$ et $\beta' = 0$],
+\item remplacer un jeton de la case $(\alpha,\beta)$ par un jeton sur
+  une case $(\alpha,\beta')$ plus à gauche dans la ligne, un autre sur
+  une case $(\alpha',\beta)$ plus haut dans la colonne, et un
+  troisième sur la case $(\alpha',\beta')$ à l'intersection de la
+  nouvelle ligne et de la nouvelle colonne, comme dans le jeu
+  d'origine [cas où $\alpha' \neq 0$ et $\beta' \neq 0$].
+\end{itemize}
+\vskip-\baselineskip\vskip-\baselineskip
+\end{corrige}
+
+\smallbreak
+
+(1) (a) Montrer qu'il existe une fonction $h(\alpha,\beta)$ de deux
+ordinaux $\alpha,\beta$ et à valeurs ordinales qui soit strictement
+croissante en chaque variable (c'est-à-dire que si $\alpha' < \alpha$
+alors $h(\alpha',\beta) < h(\alpha,\beta)$ et que si $\beta' < \beta$
+alors $h(\alpha,\beta') < h(\alpha,\beta)$).  Pour cela, on pourra,
+comme on préfère, poser $h(\alpha,\beta) = \omega^{\max(\alpha,\beta)}
++ \omega^{\min(\alpha,\beta)}$ ou bien $h(\alpha,\beta) =
+\alpha\boxplus\beta$ où $\alpha\boxplus\beta$ désigne l'ordinal dont
+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, 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)$ : 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$.
+
+Si on préfère poser $h(\alpha,\beta) = \alpha\boxplus\beta$, et si
+$\alpha' < \alpha$, le chiffre correspondant à la plus haute puissance
+de $\omega$ qui diffère est strictement plus petit dans la forme
+normale de Cantor de $\alpha'$ que celui de $\alpha$, et cette
+affirmation est encore vraie lorsqu'on ajoute chiffre à chiffre la
+forme normale de Cantor de $\beta$, donc on a bien $h(\alpha',\beta) <
+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 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,
+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 \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') <
+h(\alpha,\beta)$ si $\alpha'<\alpha$ et $\beta'<\beta$.  Ceci fait
+donc décroître strictement l'ordinal en question, et en particulier,
+la partie doit terminer en temps fini.
+\end{corrige}
+
+(2) Dans le cas particulier où il n'y a qu'une ligne de jetons
+(numérotée $1$ ; ou bien deux lignes numérotées $0$ et $1$ si on garde
+la défausse), expliquer pourquoi le jeu est simplement une
+reformulation du jeu de nim.
+
+\begin{corrige}
+Un coup joué sur un jeton de la ligne $1$ consiste simplement soit à
+le retirer soit à le déplacer vers une colonne plus à gauche ; on peut
+identifier la position ayant $n_i$ jetons sur la case $(1,\alpha_i)$ à
+un partie de nim ayant $n_i$ lignes avec $\alpha_i$ allumettes : le
+coup consistant à déplacer un jeton de la case $\alpha_i$ vers la case
+$\alpha_i' < \alpha_i$ peut se voir comme un coup de nim consistant à
+diminuer le nombre d'allumettes de la ligne qui en a $\alpha_i$ pour
+qu'il en reste $\alpha'_i$ ; et le fait de retirer un jeton sur la
+case $(1,\alpha_i)$ comme le coup de nim consistant à retirer toutes
+les allumettes de la ligne correspondante.  Les jeux sont donc
+complètement équivalents.
+\end{corrige}
+
+\smallbreak
+
+(3) Montrer que la valeur de Grundy d'un état quelconque du jeu vaut
+\[
+\bigoplus_{i=1}^s (\alpha_i\otimes\beta_i)
+\]
+où $(\alpha_1,\beta_1),\ldots,(\alpha_s,\beta_s)$ sont les cases où se
+trouvent les $s$ jetons (répétées en cas de jetons multiples), où
+$\oplus$ désigne la somme de nim, et où l'opération $\otimes$ sur les
+ordinaux est définie inductivement par
+\[
+\alpha\otimes\beta := \mex\Big\{(\alpha'\otimes\beta)
+\oplus (\alpha\otimes\beta') \oplus (\alpha'\otimes\beta')
+: \alpha'<\alpha,\text{~et~}\beta'<\beta\Big\}
+\tag{*}
+\]
+
+\begin{corrige}
+Il n'y a aucune interaction entre les jetons dans le jeu.  En
+particulier, jouer à une somme de nim de deux positions du jeu
+considéré dans cet exercice revient au même que de jouer à la position
+ayant la réunion de ces deux ensembles de jetons.  Si on note
+$u_{\alpha,\beta}$ la position du jeu ayant un unique jeton sur la
+case $(\alpha,\beta)$, on déduit de \ref{summary-of-grundy-theory} que
+la valeur de Grundy d'un état quelconque du jeu vaut
+$\bigoplus_{i=1}^s \gr(u_{\alpha_i,\beta_i})$.  Or
+$\gr(u_{\alpha,\beta})$ est le plus petit ordinal qui n'est pas de la
+forme $\gr(z)$ pour $z$ une position voisine sortante
+de $u_{\alpha,\beta}$, et d'après ce qu'on vient de dire, on obtient
+exactement $\gr(u_{\alpha,\beta}) = \mex\big\{\gr(u_{\alpha',\beta})
+\oplus \gr(u_{\alpha,\beta'}) \oplus \gr(u_{\alpha',\beta'}) :
+\alpha'<\alpha, \beta'<\beta\big\}$, c'est-à-dire bien
+$\gr(u_{\alpha,\beta}) = \alpha\otimes\beta$ (même définition
+inductive), et on a montré ce qui était demandé.
+\end{corrige}
+
+\smallbreak
+
+(4) Calculer la valeur de $\alpha\otimes\beta$ pour $0\leq\alpha\leq
+5$ et $0\leq\beta\leq 5$.  Pour accélérer les calculs ou bien pour les
+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
+détailler les calculs, mais on recommande de les vérifier
+soigneusement.
+
+\begin{corrige}
+En procédant inductivement, on trouve :
+{\[
+\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$ ; 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
+
+(5) Si vous deviez jouer dans la position suivante (les lignes et
+colonnes sont numérotées à partir de $1$, autrement dit la défausse
+n'est pas figurée), quel coup feriez-vous ?
+
+\begin{center}
+\vskip-\baselineskip
+\begin{tikzpicture}
+\draw[step=.5cm,help lines] (0,-2.5) grid (2.5,0);
+\begin{scope}[every node/.style={circle,fill,inner sep=1.2mm}]
+\node at (0.25,-0.25) {};
+\node at (0.75,-0.75) {};
+\node at (1.25,-1.25) {};
+\node at (1.75,-1.75) {};
+\node at (2.25,-2.25) {};
+\end{scope}
+\node[anchor=east] at (0,-0.25) {$1$};
+\node[anchor=east] at (0,-0.75) {$2$};
+\node[anchor=east] at (0,-1.25) {$3$};
+\node[anchor=east] at (0,-1.75) {$4$};
+\node[anchor=east] at (0,-2.25) {$5$};
+\node[anchor=south] at (0.25,0) {$1$};
+\node[anchor=south] at (0.75,0) {$2$};
+\node[anchor=south] at (1.25,0) {$3$};
+\node[anchor=south] at (1.75,0) {$4$};
+\node[anchor=south] at (2.25,0) {$5$};
+\end{tikzpicture}
+\end{center}
+
+\begin{corrige}
+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 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
+encore, remplacer le jeton $(5,5)$ par trois jetons en $(4,5)$,
+$(5,4)$ et $(4,4)$ (c'est-à-dire jouer $(\alpha,\beta,\alpha',\beta')
+= (5,5,4,4)$).
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice\label{inductions-on-nim-product}
+
+On définit inductivement une opération $\alpha\otimes\beta$
+(\emph{produit de nim}) de deux ordinaux $\alpha,\beta$ par
+$\alpha\otimes\beta := \mex\{(\alpha'\otimes\beta) \oplus
+(\alpha\otimes\beta') \oplus (\alpha'\otimes\beta') : \alpha'<\alpha,
+\beta'<\beta\}$ (autrement dit, par la formule (*) de
+l'exercice \ref{game-for-nim-product} ; il n'est pas nécessaire
+d'avoir traité l'exercice en question, même s'il est possible de s'en
+servir).  La notation $\oplus$ désigne la somme de nim.  On rappelle
+par ailleurs que $\gamma = \mex S$ signifie que $\gamma\not\in S$ et
+que tout ordinal $\gamma'<\gamma$ appartient à $S$.
+
+(1) Montrer que $\otimes$ est commutative, c'est-à-dire que
+$\beta\otimes\alpha = \alpha\otimes\beta$ quels que soient les
+ordinaux $\alpha,\beta$.
+
+\begin{corrige}
+Par induction sur $\alpha$ et $\beta$, on prouve $\beta\otimes\alpha =
+\alpha\otimes\beta$ en supposant que la même formule est vraie si l'un
+de $\alpha$ ou $\beta$ est remplacé par un ordinal strictement plus
+petit.  Or $\beta\otimes\alpha = \mex \{(\beta\otimes\alpha') \oplus
+(\beta'\otimes\alpha) \oplus (\beta'\otimes\alpha') : \alpha'<\alpha,
+\beta'<\beta\}$ (en utilisant la commutativité de $\oplus$), et par
+hypothèse d'induction ceci vaut $\mex
+\{(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
+(\alpha'\otimes\beta') : \alpha'<\alpha, \beta'<\beta\} =
+\alpha\otimes\beta$.
+
+Si on préfère, on peut aussi utiliser le jeu défini dans
+l'exercice \ref{game-for-nim-product}, en remarquant qu'échanger les
+coordonnées des cases de tous les jetons ne change rien au jeu (i.e.,
+les règles sont symétriques ligne/colonne) donc ne change pas la
+fonction de Grundy.
+\end{corrige}
+
+\smallbreak
+
+(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$, soit $\alpha\otimes 1 =
+\alpha$ pour tout ordinal $\alpha$.
+
+\begin{corrige}
+On a $\alpha \otimes 0 = \mex \varnothing = 0$ (puisqu'il n'existe pas
+de $\beta'<0$).  Pour la seconde affirmation, par induction sur
+$\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\} = \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
+la ligne ou colonne $0$ est mort (défaussé), et que jouer sur la ligne
+ou colonne $1$ revient à jouer au jeu de nim d'après la question (2)
+de l'exercice \ref{game-for-nim-product}.
+\end{corrige}
+
+\smallbreak
+
+(3) (a) 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 (b) En
+déduire que si $\alpha\otimes\beta = \alpha\otimes\beta'$ alors
+$\alpha=0$ ou bien $\beta=\beta'$.
+
+\begin{corrige}
+(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 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
+
+(4) Montrer que $\otimes$ est distributive sur $\oplus$, c'est-à-dire
+$\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$.  (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, 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 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
+(\alpha\otimes\delta') \oplus (\alpha'\otimes\delta')$ où
+$\alpha'<\alpha$ et $\delta' < \beta\oplus\gamma$.  La définition
+inductive de $\oplus$ permet alors d'écrire soit $\delta' =
+\beta'\oplus\gamma$ où $\beta'<\beta$, soit $\delta' =
+\beta\oplus\gamma'$ où $\gamma'<\gamma$ : par symétrie, plaçons nous
+sans perte de généralité dans le premier cas.  On a alors $\xi =
+(\alpha'\otimes (\beta\oplus\gamma)) \oplus (\alpha\otimes
+(\beta'\oplus\gamma)) \oplus (\alpha'\otimes (\beta'\oplus\gamma))$.
+Par hypothèse d'induction, on peut développer les trois termes, et
+quitte à simplifier les deux termes $\alpha'\otimes\gamma$ qui
+apparaissent, on obtient $\xi = (\alpha'\otimes\beta) \oplus
+(\alpha\otimes\beta') \oplus (\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)(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
+(\alpha\otimes\gamma)$, on a soit $\xi = \delta' \oplus
+(\alpha\otimes\gamma)$ avec $\delta' < \alpha\otimes\beta$, soit $\xi
+= (\alpha\otimes\beta) \oplus \varepsilon'$ avec $\varepsilon' <
+\alpha\otimes\gamma$ : par symétrie, plaçons nous sans perte de
+généralité dans le premier cas.  On peut alors écrire $\delta' =
+(\alpha'\otimes\beta) \oplus (\alpha\otimes\beta') \oplus
+(\alpha'\otimes\beta')$ avec $\alpha'<\alpha$ et $\beta'<\beta$, donc
+on a : $\xi = (\alpha'\otimes\beta) \oplus (\alpha\otimes\beta')
+\oplus (\alpha'\otimes\beta') \oplus (\alpha\otimes\gamma)$.  Quitte à
+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)(a), on a $\xi \neq \alpha
+\otimes (\beta\oplus\gamma)$, ce qu'on voulait.
+\end{corrige}
+
+\smallbreak
+
+On \emph{admet} que $\otimes$ est associative, c'est-à-dire
+$(\alpha\otimes\beta) \otimes \gamma = \alpha \otimes
+(\beta\otimes\gamma)$ (ce n'est pas très difficile à prouver).
+
+(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 \emph{plus petit}
+ordinal non nul qui n'a pas d'inverse, et on va arriver à une
+contradiction.  Pour cela, appelons $\delta_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
+(\alpha'\otimes\delta')$ est $\geq \delta$ (dans le cas contraire,
+montrer que le premier terme serait $<\delta$).  En particulier, il
+est $\neq 1$.\spaceout (d) Expliquer pourquoi si $\alpha' = 0$ alors
+$(\alpha'\otimes\delta) \oplus (\alpha\otimes\delta') \oplus
+(\alpha'\otimes\delta')$ est encore une fois $\neq 1$.\spaceout (e) En
+déduire que $\alpha\otimes\delta = 1$ et conclure.
+
+\begin{corrige}
+(a) Si $\beta < \delta$, comme $\delta$ est la borne supérieure
+  des $\delta_n$, il existe $n$ tel que $\beta < \delta_n$.  Ainsi, si
+  $\beta_1,\beta_2 < \delta$, il existe $n$ tel que $\beta_1,\beta_2 <
+  \delta_n$ (en prenant le maximum des deux $n$ obtenus), donc
+  $\beta_1\oplus\beta_2 < \delta_{n+1}$ et $\beta_1\otimes\beta_2 <
+  \delta_{n+1}$ d'après la définition de $\delta_{n+1}$, ce qui donne
+  bien $\beta_1\oplus\beta_2 < \delta$ et $\beta_1\otimes\beta_2 <
+  \delta$.
+
+(b) Si $0 < \alpha' < \alpha$ et si $\alpha' \otimes \delta < \delta$,
+  alors comme $(\alpha')^* < \delta_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
+  $\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') =
+  \alpha\otimes\delta' \neq 1$ puisqu'on a supposé que $\alpha$
+  n'avait pas d'inverse.
+
+(e) Par définition, $\alpha\otimes\delta$ est le plus petit ordinal
+  qui n'est pas de la forme $(\alpha'\otimes\delta) \oplus
+  (\alpha\otimes\delta') \oplus (\alpha'\otimes\delta')$ pour
+  $\alpha'<\alpha$ et $\delta'<\delta$.  Or
+  on a montré en (c) et (d) que cette expression n'est jamais $1$, et
+  en revanche elle peut être $0$ (pour $\alpha'=\delta'=0$).  Le plus
+  petit ordinal qui n'est pas de cette forme est donc $1$ : mais on a
+  alors prouvé $\alpha\otimes\delta = 1$, ce qui contredit l'hypothèse
+  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}
+
+
 
 \setbox0=\vbox\bgroup
 \subsection{Notions sur les combinatoires partisans à information parfaite}
-- 
cgit v1.2.3