%% 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{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}\smallskip\noindent\textbf{\thecomcnt.} } \newcommand\exercice{% \refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} \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{\dur}{\operatorname{dur}} \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\par\smallbreak\else\egroup\par\fi} % % % \begin{document} \ifcorrige \title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} \else \title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} \fi \author{} \date{13 avril 2022} \maketitle \pretolerance=8000 \tolerance=50000 \vskip1truein\relax \noindent\textbf{Consignes.} Les exercices sont totalement 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. \medbreak L'usage de tous les documents (notes de cours manuscrites ou imprimées, feuilles d'exercices, livres) est autorisé. L'usage des appareils électroniques est interdit. \medbreak Durée : 2h Barème \emph{indicatif} : \textcolor{red}{XXX}. \ifcorrige Ce corrigé comporte \textcolor{red}{XXX} pages (page de garde incluse). \else Cet énoncé comporte \textcolor{red}{XXX} pages (page de garde incluse). \fi \vfill {\noindent\tiny \immediate\write18{sh ./vc > vcline.tex} Git: \input{vcline.tex} \immediate\write18{echo ' (stale)' >> vcline.tex} \par} \pagebreak % % % \exercice On considère le jeu de nim éventuellement transfini. (On rappelle qu'il est défini de la manière suivante : une position du jeu est un tuple $(\alpha_1,\ldots,\alpha_r)$ d'ordinaux, on dit qu'il y a « $\alpha_i$ bâtonnets sur la ligne $i$ », et un coup consiste à décroître strictement \emph{un et un seul} des $\alpha_i$, autrement dit il existe un coup de $(\alpha_1,\ldots,\alpha_r)$ vers $(\alpha_1,\ldots,\beta,\ldots,\alpha_r)$ où $\beta<\alpha_i$ est mis à la place de $\alpha_i$.) Pour chacune des positions suivantes, dire si c'est une position P (c'est-à-dire gagnante pour le joueur qui vient de jouer) ou N (c'est-à-dire gagnante pour le joueur qui doit jouer), et, dans ce dernier cas, donner un coup gagnant possible pour le joueur en question. (a) $(1,2,3)$ (autrement dit, une ligne avec $1$ bâtonnet, une ligne avec $2$, et une ligne avec $3$) \begin{corrige} On a $1 = 2^0$ et $2 = 2^1$ et $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ si bien que $1 \oplus 2 \oplus 3 = 0$ : la valeur de Grundy de la position est $0$, et c'est donc une position P. \end{corrige} (b) $(3,6,9)$ \begin{corrige} On a $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ et $6 = 2^2 + 2^1 = 2^2 \oplus 2^1$ et $9 = 2^3 + 2^0 = 2^3 \oplus 2^0$ si bien que $3 \oplus 6 \oplus 9 = 2^3 \oplus 2^2 = 2^3 + 2^2 = 12$ : la valeur de Grundy de la position est $12$, et c'est donc une position N. Pour trouver un coup gagnant, c'est-à-dire un coup vers une position P, on cherche à annuler la valeur de Grundy : autrement dit, on cherche à remplacer le nombre $n$ de bâtonnets d'une ligne par $n \oplus 12$, et il s'agit donc de trouver une ligne telle que $n \oplus 12 < n$. On vérifie facilement que la seule possibilité est de réduire la ligne ayant $9$ bâtonnets à $9 \oplus 12 = 2^2 + 2^0 = 5$ bâtonnets. Bref, le seul coup gagnant est $(3,6,9) \to (3,6,5)$. \end{corrige} (c) $(\omega,\omega2,\omega3)$ \begin{corrige} En se rappelant que $\omega = 2^{\omega}$, on a $\omega2 = 2^{\omega+1}$ et $\omega3 = 2^{\omega+1} + 2^{\omega}$ en binaire : on a donc $\omega \oplus (\omega2) \oplus (\omega3) = 0$ : la valeur de Grundy de la position est $0$, et c'est donc une position P. \end{corrige} (d) $(\omega,\omega^2,\omega^3)$ \begin{corrige} En se rappelant de nouveau que $\omega = 2^{\omega}$, on a $\omega^2 = 2^{\omega2}$ et $\omega^3 = 2^{\omega3}$ en binaire : on a donc $\omega \oplus \omega^2 \oplus \omega^3 = 2^{\omega3} + 2^{\omega2} + 2^\omega = \omega^3 + \omega^2 + \omega =: \gamma$ : la valeur de Grundy de la position est $\gamma \neq 0$, et c'est cdonc une position N. Comme dans la question (b), on cherche à annuler la valeur de Grundy, autrement dit remplacer le nombre $\alpha$ de bâtonnets d'une ligne par $\alpha \oplus \gamma$ (où $\gamma = \omega^3 + \omega^2 + \omega$, qu'il vaut mieux penser comme $2^{\omega3} \oplus 2^{\omega2} \oplus 2^\omega$) d'une manière à ce que le résultat soit plus petit. On vérifie facilement que la seule possibilité est de réduire la ligne ayant $\omega^3$ bâtonnets à $\omega^3 \oplus \gamma = \omega^2 + \omega$ bâtonnets. Bref, le seul coup gagnant est $(\omega,\omega^2,\omega^3) \to (\omega,\omega^2,\omega^2+\omega)$. \end{corrige} (e) $(\omega,\omega^\omega,\omega^{\omega^\omega})$ \begin{corrige} En se rappelant une fois de plus que $\omega = 2^{\omega}$, on a $\omega^\omega = (2^\omega)^\omega = 2^{\omega\times\omega} = 2^{\omega^2}$, et $\omega^{\omega^\omega} = (2^\omega)^{\omega^\omega} = 2^{\omega\times \omega^{\omega}} = 2^{\omega^{1+\omega}} = 2^{\omega^\omega}$. Le raisonnement est alors exactement analogue à la question (d) (car la seule chose qui importe dans cette question ait qu'on ait affaire à trois puissances de $2$ distinctes) : la valeur de Grundy de la position est $\gamma := 2^{\omega^\omega} + 2^{\omega^2} + 2^\omega = \omega^{\omega^\omega} + \omega^\omega + \omega \neq 0$ donc c'est une position N, et le seul coup gagnant est $(\omega,\omega^\omega,\omega^{\omega^\omega}) \to (\omega,\omega^\omega,\omega^\omega + \omega)$. \end{corrige} (f) $(\varepsilon_1, \varepsilon_2, \varepsilon_3)$ où $\varepsilon_0 < \varepsilon_1 < \varepsilon_2 < \varepsilon_3$ sont les quatre premiers ordinaux\footnote{On peut définir $\varepsilon_{n+1}$ comme la limite, c'est-à-dire la borne supérieure, de la suite $(u_k)_{k<\omega}$ strictement croissante définie par $u_0 = (\varepsilon_n) + 1$ et $u_{k+1} = \omega^{u_k}$, c'est-à-dire $u_1 = \omega^{(\varepsilon_n) + 1}$ et $u_2 = \omega^{\omega^{(\varepsilon_n) + 1}}$, etc., mais on n'aura pas besoin de ce fait.} vérifiant $\varepsilon = \omega^\varepsilon$. \begin{corrige} Pour $i \in \{1,2,3\}$ (ou n'importe quel ordinal, en fait), on a $\varepsilon_i = \omega^{\varepsilon_i} = (2^\omega)^{\varepsilon_i} = 2^{\omega\cdot\varepsilon_i} = 2^{\omega\cdot\omega^{\varepsilon_i}} = 2^{\omega^{1+\varepsilon_i}} = 2^{\omega^{\varepsilon_i}} = 2^{\varepsilon_i}$ (en utilisant au passage le fait, facilement vérifié, que $1 + \rho = \rho$ quel que soit l'ordinal infini $\rho$). Le raisonnement est alors exactement analogue aux questions (d) et (e) (car la seule chose qui importe dans ces questions ait qu'on ait affaire à trois puissances de $2$ distinctes) : la valeur de Grundy de la position est $\gamma := 2^{\varepsilon_3} + 2^{\varepsilon_2} + 2^{\varepsilon_1} = \varepsilon_3 + \varepsilon_2 + \varepsilon_1 \neq 0$ donc c'est une position N, et le seul coup gagnant est $(\varepsilon_1, \varepsilon_2, \varepsilon_3) \to (\varepsilon_1, \varepsilon_2, \varepsilon_2 + \varepsilon_1)$. \end{corrige} (g) Donner un exemple de position N du jeu de nim (de préférence fini) avec un nombre distinct de bâtonnets sur chaque ligne (i.e., les $\alpha_i$ sont deux à deux distincts), où il existe strictement plus qu'un coup gagnant pour le joueur qui doit jouer. (Pour indication, ceci est possible à partir de trois lignes de bâtonnets.) \begin{corrige} On cherche donc une position $(n_1,n_2,n_3)$ avec trois lignes de bâtonnets, de valeur de Grundy $g := n_1 \oplus n_2 \oplus n_3$, telle qu'au moins deux des trois quantités $n_i \oplus g$ soit strictement inférieure au $n_i$ correspondant (le raisonnement étant expliqué à la question (b)), en prenant note du fait que $n_1 \oplus g = n_2 \oplus n_3$ et de façon analogue pour les trois autres. On cherche donc, par exemple, à avoir $n_1 \oplus n_3 < n_2$ et $n_1 \oplus n_2 < n_3$. Ceci n'est pas difficile en prenant par exemple pour $n_1$ une puissance de $2$ qui existe dans l'écriture binaire de $n_2$ et de $n_3$ mais telle qu'en enlevant on obtient des nombres strictement plus petits. Par exemple, la position $(2,6,7)$ (de valeur de Grundy $2\oplus 6\oplus 7 = 3 =: g$) admet des coups gagnants vers $(2,5,7)$ ou $(2,6,4)$ ou même $(1,6,7)$. \end{corrige} % % % \exercice Si $G$ est un graphe orienté bien-fondé (qu'on peut considérer comme l'ensemble des positions d'un jeu combinatoire auquel il ne manque que l'information, sans pertinence ici, de la position initiale), on rappelle qu'on a défini la fonction rang \[ \rk(x) := \sup\nolimits^+\{\rk(y) : y\in\outnb(x)\} = \sup\,\{\rk(y)+1 : y\in\outnb(x)\} \] (en notant $\sup^+ S$ le plus petit ordinal strictement supérieur à tous les ordinaux de $S$ et $\sup S$ le plus petit ordinal supérieur ou égal à tous les ordinaux de $S$, et $\outnb(x)$ l'ensemble des voisins sortants de $x$), et la fonction de Grundy \[ \gr(x) := \mex\,\{\gr(y) : y\in\outnb(x)\} \] (où $\mex S$ désigne le plus petit ordinal qui n'est pas dans $S$), — ces définitions ayant bien un sens par induction bien-fondée. La première mesure en quelque sorte la durée du jeu si les deux joueurs coopèrent pour le faire durer aussi longtemps que possible, et la seconde nous donne notamment l'information de quel joueur a une stratégie gagnante. On va maintenant définir une fonction qui mesure en quelque sorte la durée du jeu si le joueur perdant cherche à perdre aussi lentement que possible tandis que le joueur gagnant cherche à gagner aussi vite que possible. Précisément, on pose \[ \left\{ \begin{array}{ll} \dur(x) := \sup\,\{\dur(y)+1 : y\in\outnb(x)\} &\;\;\text{si $\gr(x) = 0$}\\ \dur(x) := \min\,\{\dur(y)+1 : y\in\outnb(x)\text{~et~}\gr(y)=0\} &\;\;\text{si $\gr(x) \neq 0$}\\ \end{array} \right. \] (où $\min S$ désigne le plus petit ordinal de $S$, si $S$ est un ensemble non-vide d'ordinaux). (1) Expliquer pourquoi cette définition a bien un sens (on prendra garde au fait que $\min\varnothing$ n'est pas défini). \begin{corrige} Lorsque $\gr(x) \neq 0$, il existe au moins un voisin sortant $y \in \outnb(x)$ tel que $\gr(y) = 0$ (car le $\mex$ est la plus petite valeur exclue: si un tel $y$ n'existait pas, le $\mex$ serait $0$) : ceci assure que le $\min$ dans la deuxième ligne de la définition porte toujours sur un ensemble non-vide. En-dehors de ce fait, la définition ne pose pas de problème : le $\sup$ d'un ensemble d'ordinaux existe toujours, et la récursivité de la définition est légitime par induction bien-fondée, c'est-à-dire que $\dur(x)$ peut faire appel aux valeurs de $\dur(y)$ pour des voisins sortants $y$ de $x$. (Le fait de faire appel à $\gr(y)$ n'est pas un problème car on sait que $\gr$ est bien défini, et la distinction en cas est légitime de toute manière.) \end{corrige} (2) Expliquer rapidement et informellement pourquoi $\dur(x)$ correspond bien à l'explication intuitive qu'on a donnée. \begin{corrige} Quand $x$ est une position avec $\gr(x) = 0$, c'est-à-dire une position P, le joueur qui doit jouer est le joueur perdant (n'ayant pas de stratégie gagnante) : il joue donc vers une position $y$ le faisant perdre le plus lentement possible, c'est-à-dire avec $\dur(y)$ aussi grand que possible, d'où la définition $\dur(x) = \sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ dans ce cas (le $+1$ sert à compter le coup joué par ce joueur). Au contraire, lorsque $\gr(x) \neq 0$, c'est-à-dire que $x$ est une position N, le joueur qui doit jouer est le joueur gagnant : il joue donc vers une position $y$ le faisant gagner le plus rapidement possible, c'est-à-dire avec $\dur(y)$ aussi petit que possible parmi les coups $x\to y$ gagnants, autrement dit ceux pour lesquels $\gr(y) = 0$, d'où la définition $\dur(x) = \min\,\{\dur(y)+1 : y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\}$ dans ce cas (le $+1$ sert à compter le coup joué par ce joueur). \end{corrige} (3) Sur le graphe $G$ représenté ci-dessous, calculer chacune des fonctions $\rk$, $\gr$ et $\dur$ (les lettres servent simplement à étiqueter les sommets) : \begin{center}\footnotesize \begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] \node (nA) at (0bp,0bp) [draw,circle] {A}; \node (nB) at (0bp,-40bp) [draw,circle] {B}; \node (nC) at (40bp,0bp) [draw,circle] {C}; \node (nD) at (40bp,-40bp) [draw,circle] {D}; \node (nE) at (80bp,0bp) [draw,circle] {E}; \node (nF) at (80bp,-40bp) [draw,circle] {F}; \node (nG) at (120bp,-40bp) [draw,circle] {G}; \draw[->] (nA) -- (nB); \draw[->] (nA) -- (nC); \draw[->] (nB) -- (nD); \draw[->] (nB) to[out=315,in=225] (nG); \draw[->] (nC) -- (nD); \draw[->] (nC) -- (nE); \draw[->] (nD) -- (nF); \draw[->] (nE) -- (nF); \draw[->] (nF) -- (nG); \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} Si on joue à partir du sommet A comme position initiale et que, comme suggéré dans la définition de $\dur$, le joueur perdant cherche à perdre aussi lentement que possible tandis que le joueur gagnant cherche à gagner aussi vite que possible, quelle sera le déroulement du jeu ? \begin{corrige} Les sommets ont été fort sympathiquement étiquetés dans un ordre compatible avec le rang (tri topologique), c'est-à-dire que chaque arête pointe vers un sommet situé strictement après dans l'ordre alphabétique. On effectue donc les calculs dans l'ordre alphabétique inversé. On trouve, pour le rang : \begin{center}\footnotesize \begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] \node (nA) at (0bp,0bp) [draw,circle] {$4$}; \node (nB) at (0bp,-40bp) [draw,circle] {$3$}; \node (nC) at (40bp,0bp) [draw,circle] {$3$}; \node (nD) at (40bp,-40bp) [draw,circle] {$2$}; \node (nE) at (80bp,0bp) [draw,circle] {$2$}; \node (nF) at (80bp,-40bp) [draw,circle] {$1$}; \node (nG) at (120bp,-40bp) [draw,circle] {$0$}; \draw[->] (nA) -- (nB); \draw[->] (nA) -- (nC); \draw[->] (nB) -- (nD); \draw[->] (nB) to[out=315,in=225] (nG); \draw[->] (nC) -- (nD); \draw[->] (nC) -- (nE); \draw[->] (nD) -- (nF); \draw[->] (nE) -- (nF); \draw[->] (nF) -- (nG); \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} Pour la valeur de Grundy : \begin{center}\footnotesize \begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] \node (nA) at (0bp,0bp) [draw,circle] {$0$}; \node (nB) at (0bp,-40bp) [draw,circle] {$1$}; \node (nC) at (40bp,0bp) [draw,circle] {$1$}; \node (nD) at (40bp,-40bp) [draw,circle] {$0$}; \node (nE) at (80bp,0bp) [draw,circle] {$2$}; \node (nF) at (80bp,-40bp) [draw,circle] {$1$}; \node (nG) at (120bp,-40bp) [draw,circle] {$0$}; \draw[->] (nA) -- (nB); \draw[->] (nA) -- (nC); \draw[->] (nB) -- (nD); \draw[->] (nB) to[out=315,in=225] (nG); \draw[->] (nC) -- (nD); \draw[->] (nC) -- (nE); \draw[->] (nD) -- (nF); \draw[->] (nE) -- (nF); \draw[->] (nF) -- (nG); \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} Et pour la fonction $\dur$ (afin de rendre le calcul plus facile à suivre, on a entouré en double les sommets de valeur de Grundy $0$) : \begin{center}\footnotesize \begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] \node (nA) at (0bp,0bp) [draw,double,circle] {$4$}; \node (nB) at (0bp,-40bp) [draw,circle] {$1$}; \node (nC) at (40bp,0bp) [draw,circle] {$3$}; \node (nD) at (40bp,-40bp) [draw,double,circle] {$2$}; \node (nE) at (80bp,0bp) [draw,circle] {$1$}; \node (nF) at (80bp,-40bp) [draw,circle] {$1$}; \node (nG) at (120bp,-40bp) [draw,double,circle] {$0$}; \draw[->] (nA) -- (nB); \draw[->] (nA) -- (nC); \draw[->] (nB) -- (nD); \draw[->] (nB) to[out=315,in=225] (nG); \draw[->] (nC) -- (nD); \draw[->] (nC) -- (nE); \draw[->] (nD) -- (nF); \draw[->] (nE) -- (nF); \draw[->] (nF) -- (nG); \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} Si on joue à partir de la position A, le premier joueur, appelons-la Alice, est en position perdante car la valeur de Grundy est nulle, et va jouer vers C car c'est ce qui maximise la fonction $\dur$ ; son adversaire, appelons-le Bob, joue alors vers D car c'est le seul coup gagnant, après quoi Alice joue vers F (seul coup possible) et Bob joue vers G. \end{corrige} (4) Montrer que, dans n'importe quel graphe $G$ bien-fondé, et pour n'importe quel sommet $x$ de $G$, on a $\dur(x) \leq \rk(x)$. \begin{corrige} On montre par induction bien-fondée que $\dur(x) \leq \rk(x)$. On peut donc faire l'hypothèse qu'on sait que $\dur(y) \leq \rk(y)$ pour tout voisin sortant $y \in \outnb(x)$ (hypothèse d'induction). Dans le cas où $\gr(x) = 0$, on a $\dur(x) = \sup\,\{\dur(y)+1 : y\in\outnb(x)\}$, qui est $\leq \sup\,\{\rk(y)+1 : y\in\outnb(x)\}$ par hypothèse d'induction (il est clair qu'augmenter au sens large tous les éléments d'un ensemble d'ordinaux augmente son $\sup$ au sens large), et ceci vaut $\rk(x)$ par définition. Dans le cas où $\gr(x) \neq 0$, on a $\dur(x) = \min\,\{\dur(y)+1 : y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \min\,\{\dur(y)+1 : y\in\outnb(x)\} \leq \sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ de façon évidente (en notant bien que les $\min$ portent sur des ensembles non-vides), et pour la même raison que précédemment, ceci est $\leq \sup\,\{\rk(y)+1 : y\in\outnb(x)\} = \rk(x)$. \end{corrige} % % % \end{document}