%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt,a4paper]{article} \usepackage[francais]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} %\usepackage{ucs} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} % \usepackage{mathrsfs} \usepackage{wasysym} \usepackage{url} % \usepackage{xr-hyper} % \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} \usetikzlibrary{matrix,calc} \usepackage{hyperref} % \externaldocument{notes-mitro206}[notes-mitro206.pdf] % \theoremstyle{definition} \newtheorem{comcnt}{Tout} \newcommand\thingy{% \refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} } \newcommand\exercice{% \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{\limp}{\Longrightarrow} \newcommand{\gr}{\operatorname{gr}} \newcommand{\rk}{\operatorname{rk}} \newcommand{\fuzzy}{\mathrel{\|}} % \DeclareUnicodeCharacter{00A0}{~} % \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} \DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} % \DeclareFontFamily{U}{manual}{} \DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} \newcommand{\manfntsymbol}[1]{% {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} \newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped \newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% \hbox to0pt{\hskip-\hangindent\dbend\hfill}} % \newcommand{\spaceout}{\hskip1emplus2emminus.5em} \newif\ifcorrige \corrigetrue \newenvironment{corrige}% {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\relax\else\egroup\fi\par} % % % \begin{document} \ifcorrige \title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des jeux}} \else \title{MITRO206\\Contrôle de connaissances\\{\normalsize Théorie des jeux}} \fi \author{} \date{21 avril 2016} \maketitle %% {\footnotesize %% \immediate\write18{sh ./vc > vcline.tex} %% \begin{center} %% Git: \input{vcline.tex} %% \end{center} %% \immediate\write18{echo ' (stale)' >> vcline.tex} %% \par} \pretolerance=8000 \tolerance=50000 \vskip1truein\relax \noindent\textbf{Consignes.} 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. 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 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 % % % \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\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 permis 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} % % % \end{document}