Continue exercise on nim multiplication.

1 files changed, 167 insertions, 31 deletions

diff --git a/controle-20160421.tex b/controle-20160421.tex
index d77b957..9edff71 100644
--- a/controle-20160421.tex
+++ b/controle-20160421.tex
@@ -33,19 +33,15 @@
 \refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
 \renewcommand{\qedsymbol}{\smiley}
 %
+\newcommand{\outnb}{\operatorname{outnb}}
+\newcommand{\downstr}{\operatorname{downstr}}
+\newcommand{\precs}{\operatorname{precs}}
+\newcommand{\mex}{\operatorname{mex}}
 \newcommand{\id}{\operatorname{id}}
-\newcommand{\Frac}{\operatorname{Frac}}
-\newcommand{\degtrans}{\operatorname{deg.tr}}
-\newcommand{\Frob}{\operatorname{Frob}}
-\newcommand{\alg}{\operatorname{alg}}
-\newcommand{\sep}{\operatorname{sep}}
-\newcommand{\Gal}{\operatorname{Gal}}
-\newcommand{\Fix}{\operatorname{Fix}}
-\newcommand{\Hom}{\operatorname{Hom}}
-\newcommand{\Divis}{\operatorname{Div}}
-\newcommand{\divis}{\operatorname{div}}
-\newcommand{\Pic}{\operatorname{Pic}}
-\newcommand{\ord}{\operatorname{ord}}
+\newcommand{\limp}{\Longrightarrow}
+\newcommand{\gr}{\operatorname{gr}}
+\newcommand{\rk}{\operatorname{rk}}
+\newcommand{\fuzzy}{\mathrel{\|}}
 %
 \DeclareUnicodeCharacter{00A0}{~}
 %
@@ -96,19 +92,33 @@
 
 \noindent\textbf{Consignes.}
 
-Les exercices sont complètement indépendants.  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.
+Les exercices sont indépendants sauf dans la mesure où le contraire
+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.
 
-Il n'est pas nécessaire de faire des réponses longues.
+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
+prendra bien soin de souligner tout ce qui diffère.
+
+\medbreak
 
 L'usage de tous les documents (notes de cours manuscrites ou
 imprimées, feuilles d'exercices, livres) est autorisé.
 
 L'usage des calculatrices électroniques est interdit.
 
+\medbreak
+
 Durée : 3h
 
+\medbreak
+
+Barème indicatif : chaque question a approximativement la même valeur.
+Il ne sera pas nécessaire de tout traiter pour avoir le maximum des
+points.
+
 \pagebreak
 
 
@@ -193,7 +203,7 @@ 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 saturées).
+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
@@ -217,7 +227,7 @@ strictement positif).\spaceout (a) Pour commencer, quels sont les
 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 dovient
+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
@@ -285,21 +295,23 @@ et on a prouvé que c'étaient bien les seuls.
 \exercice
 
 On considère le jeu suivant : une position du jeu consiste en un
-certain nombre (fini) de jetons placés sur un damier 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).
+certain nombre fini de jetons placés sur un damier 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.
 
 Un coup du jeu consiste à faire l'opération suivante : le joueur qui
 doit jouer choisit un jeton du jeu, disons qu'il soit sur la case
-$(\alpha,\beta)$, et il choisit aussi $\alpha' < \alpha$ et $\beta' <
-\beta$, il retire 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é.
+$(\alpha,\beta)$, et il choisit aussi $\alpha' < \alpha$ (i.e., une
+ligne située plus haut) et $\beta' < \beta$ (i.e., une colonne située
+plus à gauche), il retire 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é.
 
 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
@@ -313,7 +325,8 @@ et celui qui ne peut plus jouer a perdu.
 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
 qu'être défaussés) : quels sont les types de coups possibles à ce
-jeu ?
+jeu ?  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
@@ -337,8 +350,131 @@ $\beta'$ vaut $0$, sont alors :
   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 les $h(\alpha,\beta)$ des cases où il y a un jeton,
+dans l'ordre décroissant.)
+
+\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) <
+  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$.
+
+(\emph{Remarque :} En fait, la fonction $\boxplus$, aussi appelée
+« somme naturelle » sur les ordinaux, est plus naturelle 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$.)
+
+(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
+$\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 (en autant de fois que nécessaire les cases
+sur lesquelles se trouvent des 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, \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}
+
+
 
 
 %