diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 691 |
1 files changed, 691 insertions, 0 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 0de0d43..d51a7e7 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -5785,6 +5785,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 questions ci-dessous) : les gains d'\emph{Alice} (c'est-à-dire, la @@ -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} |