diff options
| -rw-r--r-- | controle-20160421.tex | 198 |
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} + + % |