diff options
| -rw-r--r-- | controle-20230417.tex | 123 | ||||
| -rw-r--r-- | controle-20240422.tex | 576 |
2 files changed, 646 insertions, 53 deletions
diff --git a/controle-20230417.tex b/controle-20230417.tex index 34925af..fce95a1 100644 --- a/controle-20230417.tex +++ b/controle-20230417.tex @@ -76,7 +76,7 @@ \title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} \fi \author{} -\date{13 avril 2022} +\date{17 avril 2023} \maketitle \pretolerance=8000 @@ -90,6 +90,11 @@ 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. +La longueur du sujet ne doit pas effrayer : l'énoncé est long parce +que des rappels ont été faits et que la rédaction des questions +cherche à éviter toute ambiguïté. De plus, il ne sera pas nécessaire +de traiter la totalité pour avoir la note maximale. + \medbreak L'usage de tous les documents (notes de cours manuscrites ou @@ -101,7 +106,7 @@ L'usage des appareils électroniques est interdit. Durée : 2h -Barème \emph{indicatif} : \textcolor{red}{XXX}. +Barème \emph{indicatif} : $5+5+5+7$ (sur $20$) \ifcorrige Ce corrigé comporte 8 pages (page de garde incluse). @@ -256,10 +261,10 @@ 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)$. +de $n_3$ mais telle qu'en l'enlevant on obtienne 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} @@ -374,7 +379,7 @@ fonctions $\rk$, $\gr$ et $\dur$ (les lettres servent simplement à \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} - +\vskip-\baselineskip 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 @@ -409,6 +414,7 @@ inversé. On trouve, pour le rang : \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} +\vskip-\baselineskip Pour la valeur de Grundy : @@ -433,6 +439,7 @@ Pour la valeur de Grundy : \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} +\vskip-\baselineskip 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$) : @@ -458,6 +465,7 @@ suivre, on a entouré en double les sommets de valeur de Grundy $0$) : \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} +\vskip-\baselineskip 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 @@ -480,10 +488,10 @@ 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 +y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 : +y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 : +y\in\outnb(x)\}$ de façon évidente ($\min S \leq \sup S$ est clair), +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} @@ -508,9 +516,10 @@ autrement dit, il choisit un élément de $\outnb(x) \cup \{x\}$. (Pour être parfaitement clair : au premier tour, le Fugueur choisit $x_1 \in \outnb(x_0) \cup \{x_0\}$, puis le Borneur choisit $x_2 \in \outnb(x_1) \cup \{x_1\}$, et ainsi de suite.) Le jeu dure infiniment -longtemps (manifestement, chaque joueur permettent toujours de faire -un coup). Au bout d'un nombre infini de coups, on considère la suite -$(x_n)_{n\in\mathbb{N}}$ de toutes les positions traversées : +longtemps (manifestement, les règles permettent toujours à chaque +joueur de faire un coup). Au bout d'un nombre infini de coups, on +considère la suite $(x_n)_{n\in\mathbb{N}}$ de toutes les positions +traversées : \begin{itemize} \item si cette suite est d'image finie (c'est-à-dire que l'ensemble $\{x_n : n\in\mathbb{N}\}$ de toutes les positions traversées est @@ -522,21 +531,21 @@ $(x_n)_{n\in\mathbb{N}}$ de toutes les positions traversées : joueurs a nécessairement une stratégie gagnante (on ne demande pas de préciser lequel). On pourra préalablement montrer que pour toute partie $F \subseteq G$, la partie $F^{\mathbb{N}} \subseteq -G^{\mathbb{N}}$ est \emph{fermée} pour la topologie sur +G^{\mathbb{N}}$ est \emph{fermée} (pour la topologie sur $G^{\mathbb{N}}$ produit de la topologie -discrète\footnote{C'est-à-dire celle qui a été étudiée en cours.}, et -en déduire une propriété de $\bigcup_{F\text{~fini~}\subseteq G} -F^{\mathbb{N}}$ (c'est-à-dire la réunion des $F^{\mathbb{N}}$ où $F$ -parcourt toutes les parties \emph{finies} de $G$). +discrète\footnote{C'est-à-dire celle qui a été étudiée en cours.}), et +en déduire une propriété de l'ensemble +$\bigcup_{F\text{~fini~}\subseteq G} F^{\mathbb{N}}$ réunion des +$F^{\mathbb{N}}$ où $F$ parcourt toutes les parties \emph{finies} +de $G$. \begin{corrige} Pour commencer, montrons que si $F$ est une partie de $G$ alors $F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée. Ceci revient à montrer que son complémentaire est ouvert, autrement dit, que si $\dblunderline{x} \in G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, -alors il existe un voisinage fondamental de $\dblunderline{x}$ qui est -inclus dans le complémentaire de $F^{\mathbb{N}}$ (autrement dit, ne -rencontre pas $F^{\mathbb{N}}$). Or si $\dblunderline{x} \in +alors il existe un voisinage fondamental de $\dblunderline{x}$ qui ne +rencontre pas $F^{\mathbb{N}}$. Or si $\dblunderline{x} \in G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, c'est qu'elle a une valeur $x_\ell$ qui n'est pas dans $F$, et toute suite commençant par $x_0,\ldots,x_\ell$ n'est pas dans $F^{\mathbb{N}}$, c'est-à-dire que @@ -572,9 +581,11 @@ au même, qu'elle appartient à $\bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$. On a donc affaire à un jeu de Gale-Stewart défini par l'ensemble de -suites $A := \bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$ borélien. Le -théorème de détermination borélienne de Martin assure que l'un des -joueurs a forcément une stratégie gagnante. +suites $B := \bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$ borélien (ou +par son complémentaire $A := G^{\mathbb{N}} \setminus B$ si on prend +le point de vue du Fugueur). Le théorème de détermination borélienne +de Martin assure que l'un des joueurs a forcément une stratégie +gagnante. \end{corrige} (2) Indépendamment de la question précédente, donner un exemple de @@ -588,7 +599,7 @@ gagne trivialement (la suite sera la suite constante). Si $G$ est le graphe formé des entiers naturels avec une arête $i \to j$ lorsque $i<j$ (autrement dit des petits entiers naturels vers les -grands), ou même simplement $i \to i+1$, alors le Fugueur a une +grands), ou même seulement $i \to i+1$, alors le Fugueur a une stratégie gagnante consistant à jouer de $i$ vers $i+1$, ce qui assure que la suite $(x_{2i+1})$ des positions choisies par le Fugueur est strictement croissante quoi que fasse le Borneur (il ne peut pas @@ -614,8 +625,11 @@ $W$&$-1,+1$&$+1,-1$&$x,x$\\ \end{tabular} \end{center} où $x$ est un réel et, pour plus de commodité, on a écrit $U$ pour -« Pierre », $V$ pour « Papier » et $W$ pour « Ciseaux ». Le but de -l'exercice est d'étudier les équilibres de Nash de ce jeu. +« Pierre », $V$ pour « Papier » et $W$ pour « Ciseaux ». (La ligne +correspond à l'option choisie par Alice, la colonne à l'option de Bob, +et chaque case indique le gain d'Alice suivi du gain de Bob.) + +Le but de l'exercice est d'étudier les équilibres de Nash de ce jeu. (On prendra bien note, pour simplifier les raisonnements en cas, du fait que les options ont une symétrie cyclique\footnote{C'est-à-dire @@ -625,9 +639,9 @@ symétriques.) (1) Considérons le profil de stratégies mixtes dans lequel les deux joueurs choisissent chacun chaque option avec probabilité -$\frac{1}{3}$ (on rappelle que c'est ça la stratégie optimale dans le -cas à somme nulle). Pour quelle(s) valeur(s) de $x$ ce profil est-il -un équilibre de Nash ? +$\frac{1}{3}$ (c'est-à-dire la stratégie qui est optimale dans le cas +à somme nulle). Pour quelle(s) valeur(s) de $x$ ce profil est-il un +équilibre de Nash ? \begin{corrige} Pour des raisons de symétrie, si l'un des joueurs joue cette stratégie @@ -647,9 +661,9 @@ de $x$. \emph{On suppose dorénavant que $x<-1$.} (2) Existe-t-il un équilibre de Nash dans lequel Alice joue purement -$U$ (Pierre) ? (On raisonnera sur le support de la stratégie de Bob -en réponse.) En déduire tous les équilibres de Nash dans lesquels au -moins un joueur joue une stratégie pure. +$U$ ? (On raisonnera les options pouvant être dans le support de la +stratégie de Bob en réponse.) En déduire tous les équilibres de Nash +dans lesquels au moins un joueur joue une stratégie pure. \begin{corrige} Si Alice joue purement $U$, les gains de Bob pour les différentes @@ -659,18 +673,19 @@ seule option qui peut faire partie du support d'une meilleure réponse de Bob est $V$, autrement dit, si Alice joue purement $U$ dans un équilibre de Nash, Bob répond forcément purement $V$. Mais par le même raisonnement (compte tenu de la symétrie cyclique des options et -de la symétrie des joueurs), si Bob joue purement $V$, Alice répond -purement $W$. Il ne peut donc pas y avoir d'équilibre de Nash dans -lequel Alice joue purement $U$. Et de nouveau par symétrie cyclique -des options et symétrie des joueurs, il ne peut y avoir aucun -équilibre de Nash dans lequel un joueur jouerait une stratégie pure. +de la symétrie des joueurs), si Bob joue purement $V$, Alice joue $W$ +(et pas $U$ comme supposé). Il ne peut donc pas y avoir d'équilibre +de Nash dans lequel Alice joue purement $U$. Et de nouveau par +symétrie cyclique des options et symétrie des joueurs, il ne peut y +avoir aucun équilibre de Nash dans lequel un joueur jouerait une +stratégie pure. \end{corrige} (3) Dans cette question et la suivante, envisageons un équilibre de -Nash dans lequel Alice joue une stratégie mixte $pU + (1-p)V$ avec +Nash dans lequel Alice joue la stratégie mixte $pU + (1-p)V$ avec $0<p<1$. Supposons dans cette question que Bob réponde avec un une stratégie mixte ayant elle aussi $\{U,V\}$ comme support. Montrer que -$p = \frac{x+1}{2x}$ et que le gain de Bob est $\frac{x^2+1}{2x}$ ; en +$p = \frac{x+1}{2x}$ et que le gain de Bob est $\frac{x^2+1}{2x}$. En utilisant le fait que $\frac{x^2+1}{2x} < -\frac{1}{x}$ lorsque $x<-1$ (qu'on admettra pour ne pas perdre son temps en calculs inutiles), en déduire qu'un tel équilibre de Nash n'existe pas. @@ -690,13 +705,14 @@ fournit un meilleur gain espéré pour Bob, donc $\{U,V\}$ ne peut pas d'Alice. \end{corrige} -(4) Toujours en considérant un équilibre de Nash dans lequel Alice -joue une stratégie mixte $pU + (1-p)V$ avec $0<p<1$. Supposons -maintenant que Bob réponde avec un une stratégie mixte ayant -$U$ et $W$ dans son support support. Montrer que $p = \frac{2}{x+3}$ -(et que $x\neq -3$) ; en utilisant le fait que $\frac{2}{x+3} > 1$ -lorsque $-3<x<-1$ et que $\frac{2}{x+3} < 0$ lorsque $x < -3$ (qu'on -admettra aussi), en déduire qu'un tel équilibre de Nash n'existe pas. +(4) On considère toujours un équilibre de Nash dans lequel Alice joue +la stratégie mixte $pU + (1-p)V$ avec $0<p<1$. Supposons maintenant +que Bob réponde avec une stratégie mixte ayant (au moins) $U$ et $W$ +dans son support support. Montrer que $p = \frac{2}{x+3}$ (et +que $x\neq -3$) ; en utilisant le fait que $\frac{2}{x+3} > 1$ lorsque +$-3<x<-1$ et que $\frac{2}{x+3} < 0$ lorsque $x < -3$ (de nouveau, on +admettra ces faits pour ne pas perdre de temps en calculs), en déduire +qu'un tel équilibre de Nash n'existe pas. \begin{corrige} On a dit dans la question (3) que si Alice joue $pU + (1-p)V$, les @@ -728,17 +744,18 @@ on a exclu $\{U,V\}$ ; dans la question (4), on a exclu $\{U,W\}$ et $\{U,V,W\}$. Reste le cas où le support de la stratégie de Bob est $\{V,W\}$ (tandis que celui d'Alice est, on le rappelle, $\{U,V\}$). Mais quitte à effectuer une symétrie cyclique des options ($U\to W\to -V\to U$) et permuter les joueurs, cela revient au cas où le support de -la stratégie d'Alice est $\{U,V\}$ et celui de Bob est $\{U,W\}$ : -mais on a déjà exclu ce cas. Il ne reste donc aucune possibilité. +V\to U$) et échanger les joueurs, cela revient au cas où le support de +la stratégie d'Alice est $\{U,V\}$ et celui de Bob est $\{U,W\}$ : or +on a déjà exclu ce cas. Il ne reste donc aucune possibilité. \end{corrige} (6) Envisageons maintenant un équilibre de Nash dans lequel Alice joue une stratégie mixte $pU + p'V + (1-p-p')W$ avec $p>0$, $p'>0$ et $1-p-p'>0$ et Bob répond par une stratégie ayant elle aussi $\{U,V,W\}$ comme support. Écrire un système de deux équations -linéaires sur $p,p'$, justifier que ce système est non-dégéné et -conclure. +linéaires vérifié par $p,p'$, justifier que ce système est +non-dégénéré et conclure. Quels sont tous les équilibres de Nash du +jeu ? \begin{corrige} Si Alice joue $pU + p'V + (1-p-p')W$, les gains espérés de Bob pour diff --git a/controle-20240422.tex b/controle-20240422.tex new file mode 100644 index 0000000..8bab6a4 --- /dev/null +++ b/controle-20240422.tex @@ -0,0 +1,576 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\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{\|}} +% +\newcommand{\dblunderline}[1]{\underline{\underline{#1}}} +% +\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{22 avril 2024} +\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 + +\ifcorrige +Ce corrigé comporte 6 pages (page de garde incluse). +\else +Cet énoncé comporte 3 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 + +\textbf{(1)} On considère le jeu en forme normale défini par la +matrice de gain suivante : +\begin{center} +\begin{tabular}{r|cc} +$\downarrow$Alice, Bob$\rightarrow$&$X$&$Y$\\\hline +$X$&$1$&$0$\\ +$Y$&$0$&$2$\\ +\end{tabular} +\end{center} +Un seul nombre a été inscrit dans chaque case car les gains des deux +joueurs sont \emph{égaux}, et c'est ce nombre-là qui est écrit +(attention, il ne s'agit pas d'un jeu à somme nulle, au contraire : au +lieu d'être opposés, les intérêts des deux joueurs sont parfaitement +identiques). + +Étudier et déterminer tous les équilibres de Nash de ce jeu : on +commencera par considérer ceux en stratégies pures, puis par +considérer les cas où un joueur, ou l'autre, ou les deux, joue une +stratégie strictement mixte (i.e., ayant pour support $\{X,Y\}$). + +\begin{corrige} +Si Alice joue (purement) $X$, les options de Bob apportent les gains +$1$ pour $X$ et $0$ pour $Y$, dont la seule meilleure réponse de Bob +est de jouer purement $X$. De même, si Alice joue (purement) $Y$, les +options de Bob apportent les gains $0$ pour $X$ et $2$ pour $Y$, dont +la seule meilleure réponse de Bob est de jouer purement $Y$. Le rôle +des deux joueurs étant symétrique, ceci prouve que, dans un équilibre +de Nash, si l'un joue purement une des deux options, l'autre doit +jouer la même, et ceci donne bien deux équilibres de Nash, $(X,X)$ +(avec gain $1$) et $(Y,Y)$ (avec gain $2$). + +Si Alice joue une stratégie strictement mixte dans un équilibre de +Nash, on vient de voir que Bob joue $pX + (1-p)Y$, l'espérance de gain +d'Alice doit être la même pour les deux options du support de sa +stratégie, c'est-à-dire que $p = 2(1-p)$, donc $p = \frac{2}{3}$. Par +symétrie, Bob joue aussi cette stratégie, et on vérifie que ceci donne +bien un équilibre de Nash, $(\frac{2}{3}X + \frac{1}{3}Y, \; +\frac{2}{3}X + \frac{1}{3}Y)$. +\end{corrige} + +\textbf{(2)} Plus généralement, on considère un jeu de la forme +suivante : les deux joueurs ont le même ensemble d'options, notons-le +$\{X_1,\ldots,X_N\}$, et ils ont le même gain $u_A(a,b) = u_B(a,b)$ +pour $a,b\in \{X_1,\ldots,X_N\}$, et de plus ce gain vaut $0$ lorsque +$b\neq a$ et il vaut $g_i$ lorsque $a = b = X_i$, où tous les $g_i$ +sont des réels strictement positifs ($g_i > 0$). Pour résumer : +\begin{center} +\begin{tabular}{r|ccc} +$\downarrow$Alice, Bob$\rightarrow$&$X_1$&$\cdots$&$X_N$\\\hline +$X_1$&$g_1$&$\cdots$&$0$\\ +$\vdots$&$\vdots$&$\ddots$&$\vdots$\\ +$X_N$&$0$&$\cdots$&$g_N$\\ +\end{tabular} +\end{center} + +\textbf{(a)} Montrer que, dans un équilibre de Nash d'un jeu comme on +vient de le dire, si $I \subseteq \{X_1,\ldots,X_N\}$ est le +support\footnote{On rappelle que le support d'une stratégie mixte est +l'ensemble des options qu'elle choisit avec une probabilité $>0$.} de +la stratégie d'Alice, le support $J$ de la stratégie de Bob est inclus +dans $I$. (\emph{Indication :} toute option hors de $I$ apporte un +gain espéré nul, donc strictement moins bon que n'importe quelle +combinaison convexe d'options dans $I$.) En déduire par symétrie +que $I=J$. + +\begin{corrige} +Si $X_j \not\in I$, alors l'option $X_j$ apporte un gain nul à Bob, +tandis que toute option $X_i \in I$ apporte un gain strictement +positif (puisque $g_i$ est pondéré avec un coefficient strictement +positif, tout le reste étant nul). Il s'ensuit qu'une meilleure +réponse possible de Bob ne peut pas inclure $X_j$ : elle ne peut donc +inclure que des options dans $I$. Donc $J \subseteq I$. Et par +symétrie des deux joueurs, $I \subseteq J$. Donc finalement $I = J$. +\end{corrige} + +\textbf{(b)} Toujours en considérant un équilibre de Nash d'un tel +jeu, en notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie (mixte) +d'Alice, montrer que les $g_i p_i$ tels que $p_i > 0$ (c'est-à-dire +$X_i \in I$) sont tous égaux entre eux. En déduire par symétrie le +résultat analogue pour la stratégie de Bob, donc qu'elles sont égales. +En déduire qu'il existe au plus $2^N - 1$ équilibres de Nash, un pour +chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$. + +\begin{corrige} +En notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie d'Alice, pour +toute option $X_i \in J = I$ de Bob, le gain espéré de $X_i$ doit être +toujours le même. Or ce gain est $g_i p_i$. Donc tous les $g_i p_i$ +pour $X_i \in I$ sont égaux. C'est-à-dire que les $p_i$ sont +proportionnels aux $\frac{1}{g_i}$ pour $X_i \in I$ (les autres étant +nuls). Ceci détermine la stratégie d'Alice, et par symétrie c'est +aussi celle de Bob. On a donc trouvé $2^N - 1$ équilibres de Nash +potentiels : pour toute partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on +pose calcule $p_i$ comme le quotient de $\frac{1}{g_i}$ par la somme +des $\frac{1}{g_j}$ pour $X_j \in I$ si $X_i \in I$ (et $0$ sinon), et +Alice et Bob jouent chacun $p_1 X_1 + \cdots + p_N X_N$. +\end{corrige} + +\textbf{(c)} Vérifier que les stratégies mixtes trouvées en (b) sont +bien des équilibres de Nash du jeu, et conclure qu'il a exactement +$2^N - 1$ équilibres de Nash, qu'on décrira explicitement. + +\begin{corrige} +Pour chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on a bien +décrit une stratégie mixte pour chacun des deux joueurs (c'est la +même) : on a bien affaire à des réels $p_i$ positifs de somme $1$. Le +gain espéré de $X_j$ contre $p_1 X_1 + \cdots + p_N X_N$ est $0$ si +$X_j \not\in I$ et $g_j p_j$ (qui ne dépend pas de $j$) si $X_j \in +I$ : on ne peut pas faire mieux (avec une stratégie pure, donc a +fortiori avec une stratégie mixte), donc cette stratégie est bien une +meilleure réponse possible contre elle-même, et on a bien affaire à un +équilibre de Nash. + +Pour résumer : tous les équilibres de Nash sont décrits de la façon +suivante : pour une certaine partie non vide $I$ de +$\{X_1,\ldots,X_N\}$, on pose +\[ +\left\{ +\begin{array}{ll} +p_i = \frac{\textstyle 1/g_i}{\textstyle \sum_{X_j\in I}(1/g_j)}&\text{si $p_i\in I$}\\ +p_i = 0&\text{sinon} +\end{array} +\right. +\] +et les deux joueurs jouent $p_1 X_1 + \cdots + p_N X_N$ : ceci est +bien un équilibre de Nash et tous sont de cette forme (et $I$ est bien +déterminé par l'équilibre puisque c'est le support commun des +stratégies des deux joueurs, donc tous les équilibres qu'on vient de +décrire sont distincts). Il y en a donc exactement $2^N - 1$. +\end{corrige} + + +% +% +% + +\exercice + +On considère un jeu de la forme suivante. Soit $A \subseteq +\mathbb{R}$ un ensemble de réels, soit $X \subseteq \mathbb{R}$ un +ensemble \emph{fini} de réels, et soit enfin $b>1$ un réel. (Toutes +ces données sont fixées à l'avance et sont des paramètres définissant +le jeu. Ils sont supposés connus des deux joueurs.) + +Chaque joueur quand vient son tour choisit un élément $x_i \in X$ : +plus exactement, Alice choisit $x_0$, puis Bob choisit $x_1$, puis +Alice choisit $x_2$, et ainsi de suite. Il n'y a aucune contrainte +sur le choix du $x_i$ et chacun a connaissance de tous les coups +antérieurs. + +Au bout d'un nombre infini de tours, on considère le réel +\[ +u = x_0 + \frac{x_1}{b} + \frac{x_2}{b^2} + \frac{x_3}{b^3} + \cdots +\] +c'est-à-dire la somme de la série +$\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$. Cette série converge car elle +converge absolument\footnote{\label{footnote-series-converges}Preuve : +$\sum_{i=0}^{+\infty}\left|\frac{x_i}{b^i}\right| \leq +\sum_{i=0}^{+\infty}\frac{M}{b^i} = \frac{M}{1-b}$ où $M$ est un +majorant des $|x|$ pour $x\in X$, qui existe car $X$ est fini.}. Si +$u\in A$ alors Alice a gagné ; sinon, Bob a gagné. + +(Un cas particulier qu'on peut garder à l'esprit est celui où $X = +\{0,1\}$ et $b = 2$, auquel cas Alice et Bob construisent un nombre +binaire entre $0$ et $2$ en choisissant alternativement ses chiffres : +$u = x_0.x_1 x_2 x_3\cdots$ en binaire.) + +On cherche à montrer que sous certaines conditions sur $A$, l'un des +joueurs a une stratégie gagnante. + +\textbf{(1)} On considère l'application $\psi\colon X^{\mathbb{N}} \to +\mathbb{R}$ qui à une suite $\dblunderline{x} = (x_i)_{i\in\mathbb{N}} +\in X^{\mathbb{N}}$ associe $\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$. +Montrer que si $\psi(\dblunderline{x}) = u$ et $\varepsilon > 0$, +alors il existe $\ell \in \mathbb{N}$ tel que toute suite +$\dblunderline{y}$ commençant par $x_0,\ldots,x_{\ell-1}$ vérifie +$|\psi(\dblunderline{y})-u| < \varepsilon$. Autrement dit, il existe +$\ell$ tel que l'image du $\ell$-ième voisinage +fondamental\footnote{Rappel : $V_\ell(\dblunderline{x})$ est +l'ensemble des suites commençant par les $\ell$ termes +$x_0,\ldots,x_{\ell-1}$.} $V_\ell(\dblunderline{x})$ de +$\dblunderline{x}$ par $\psi$ soit incluse dans la boule ouverte +$B_\varepsilon(u) := +\mathopen]u-\varepsilon,u+\varepsilon\mathclose[$. + (\emph{Indication :} s'inspirer de la + note \ref{footnote-series-converges}.) + +\begin{corrige} +Si $\dblunderline{x}$ et $\dblunderline{y}$ coïncident sur les +termes $i<\ell$, alors $|\psi(\dblunderline{y})-u| = +|\psi(\dblunderline{y})-\dblunderline{x}| = +\left|\sum_{i=\ell}^{+\infty} \frac{x_i}{b^i}\right| \leq +\sum_{i=\ell}^{+\infty} \left|\frac{x_i}{b^i}\right| \leq +\sum_{i=\ell}^{+\infty} \frac{M}{b^i} = \frac{Mb^\ell}{1-b}$. Cette +quantité tend vers $0$ quand $\ell\to+\infty$, donc il existe $\ell$ +tel qu'elle soit $<\varepsilon$. Ceci montre bien que si +$\dblunderline{y} \in V_\ell(\dblunderline{x})$ on a +$|\psi(\dblunderline{y})-u| < \varepsilon$. +\end{corrige} + +\textbf{(2)} En déduire que si $U \subseteq \mathbb{R}$ est ouvert (au +sens de la topologie usuelle des réels\footnote{Rappel : $U \subseteq +\mathbb{R}$ est ouvert lorsque pour tout $u\in U$ il existe +$\varepsilon>0$ tel que $B_\varepsilon(u) \subseteq U$.}), alors +l'image réciproque $\psi^{-1}(U) \subseteq X^{\mathbb{N}}$ est ouverte +(au sens de la topologie produit de la topologie discrète sur +$X^{\mathbb{N}}$, qu'on a considérée en cours). + +\begin{corrige} +Supposons que $U$ soit ouvert. Si $\dblunderline{x} \in +\psi^{-1}(U)$, c'est-à-dire $\psi(\dblunderline{x}) =: u \in U$, comme +$U$ est ouvert, il existe $\varepsilon>0$ tel que $B_\varepsilon(u) +\subseteq U$, et d'après la question (1), il existe $\ell$ tel que +$\psi(V_\ell(\dblunderline{x})) \subseteq B_\varepsilon(u) \subseteq +U$, ce qui signifie $V_\ell(\dblunderline{x}) \subseteq \psi^{-1}(U)$. +On vient de montrer que tout $\dblunderline{x} \in \psi^{-1}(U)$ a un +voisinage fondamental $V_\ell(\dblunderline{x})$ inclus dans +$\psi^{-1}(U)$, c'est-à-dire que $\psi^{-1}(U)$ est ouvert. + +(Note : on a évité dans ce corrigé d'utiliser le mot « continu » car +il n'a pas été défini en cours dans le contexte d'une application de +$X^{\mathbb{N}}$ vers $\mathbb{R}$. Mais bien sûr, il est correct de +dire que $\psi$ est continue en tant qu'application entre espaces +topologiques.) +\end{corrige} + +\textbf{(3)} En déduire que si $A$ est ouvert, ou bien fermé, +dans $\mathbb{R}$, alors l'un des deux joueurs possède une stratégie +gagnante au jeu qu'on a décrit. + +\begin{corrige} +Le jeu qu'on a décrit est exactement le jeu de Gale-Stewart défini par +la partie $\psi^{-1}(A)$. Si $A$ est ouvert, alors la question (2) +montre que $\psi^{-1}(A)$ est ouvert, donc le jeu est déterminé +d'après le théorème de détermination des jeux ouverts. Si $A$ est +fermé, alors son complémentaire $\mathbb{R}\setminus A$ est ouvert, +donc la question (2) montre que $\psi^{-1}(\mathbb{R}\setminus A) = +X^{\mathbb{N}} \setminus \psi^{-1}(A)$ est ouvert, c'est-à-dire que +$\psi^{-1}(A)$ est fermé, donc le jeu est déterminé d'après le +théorème de détermination des jeux fermés. +\end{corrige} + +\textbf{(4)} Montrer aussi ce résultat lorsque $A = \mathbb{Q}$ +(autrement dit, Alice gagne si la somme $u$ de la série est +rationnelle\footnote{Merci d'avance de ne pas prétendre que +$\mathbb{Q}$ est ouvert, ni qu'il est fermé.}). Plus généralement, +montrer ce résultat lorsque $A$ est borélien. + +\begin{corrige} +L'ensemble $\mathbb{Q}$ est la réunion dénombrable des fermés $\{r\}$ +pour $r\in\mathbb{Q}$ : il est donc borélien (dans $\mathbb{R}$) ; +l'image réciproque $\psi^{-1}(\mathbb{Q})$ est donc la réunion +dénombrable des fermés $\psi^{-1}(\{r\})$ : il est donc borélien (dans +$X^{\mathbb{N}}$). D'après le théorème de détermination des jeux +boréliens, le jeu est déterminé. + +Plus généralement, l'ensemble des $B$ tels que $\psi^{-1}(B)$ soit +borélien dans $X^{\mathbb{N}}$ est une tribu (puisque $\psi^{-1}$ +préserve les réunions et intersections quelconques, ainsi que le +complémentaire) et elle contient les ouverts (puisqu'on a vu que +$\psi^{-1}(U)$ est ouvert pour $U$ ouvert). Elle contient donc les +boréliens de $\mathbb{R}$. C'est-à-dire que si $B$ est borélien +dans $\mathbb{R}$ alors $\psi^{-1}(B)$ est borélien dans +$X^{\mathbb{N}}$. D'après le théorème de détermination des jeux +boréliens, le jeu est déterminé dès que $A$ est borélien. +\end{corrige} + + +% +% +% + +\exercice + +On va développer dans cet exercice un algorithme pour calculer la +somme et le produit d'ordinaux écrits en forme normale de Cantor +(itérée). + +\textbf{(1)} On rappelle que $1 + \omega = \omega$. En déduire que si +un ordinal $\alpha$ vérifie $\alpha \geq \omega$, alors on a $1 + +\alpha = \alpha$ (\emph{indication :} justifier qu'on peut écrire +$\alpha = \omega + \beta$). En déduire que $1 + \omega^\gamma = +\omega^\gamma$ lorsque $\gamma > 0$, puis que $\omega^{\gamma_1} + +\omega^{\gamma_2} = \omega^{\gamma_2}$ lorsque $\gamma_1 < \gamma_2$, +et enfin que $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} n_2 = +\omega^{\gamma_2} n_2$ si $n_1,n_2$ sont deux entiers naturels non +nuls (et toujours avec $\gamma_1 < \gamma_2$). + +\begin{corrige} +On a vu que lorsque $\alpha_0 \leq \alpha$, il existe un unique +$\beta$ tel que $\alpha = \alpha_0 + \beta$ : en particulier, si +$\alpha \geq \omega$, on peut écrire $\alpha = \omega + \beta$, et on +en déduit que $1 + \alpha = 1 + \omega + \beta = \omega + \beta = +\alpha$. + +Or si $\gamma > 0$, c'est-à-dire $\gamma \geq 1$, on a $\omega^\gamma +\geq \omega$, et on vient de voir que ceci implique $1 + \omega^\gamma += \omega^\gamma$. + +Si $\gamma_1 < \gamma_2$, on peut écrire $\gamma_2 = \gamma_1 + +\gamma$ (cf. deux paragraphes plus haut), donc $\omega^{\gamma_1} + +\omega^{\gamma_2} = \omega^{\gamma_1} + \omega^{\gamma_1 + \gamma} = +\omega^{\gamma_1} + \omega^{\gamma_1} \, \omega^{\gamma} = +\omega^{\gamma_1} (1 + \omega^\gamma) = \omega^{\gamma_1} \, +\omega^\gamma = \omega^{\gamma_1+\gamma} = \omega^{\gamma_2}$. + +Une fois acquis que $\omega^{\gamma_1} + \omega^{\gamma_2} = +\omega^{\gamma_2}$, on a $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} +n_2 = \omega^{\gamma_1} + \cdots + \omega^{\gamma_1} + +\omega^{\gamma_2} + \cdots + \omega^{\gamma_2}$ (avec $n_1$ termes +$\omega^{\gamma_1}$ et $n_2$ termes $\omega^{\gamma_2}$), et en +utilisant de façon répétée l'égalité qu'on vient de dire, ceci vaut +$\omega^{\gamma_2} + \cdots + \omega^{\gamma_2} = \omega^{\gamma_2} +n_2$, comme annoncé. +\end{corrige} + +\textbf{(2)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots + +\omega^{\gamma_1} n_1$ (avec $\gamma_s > \cdots > \gamma_1$ et +$n_1,\ldots,n_s$ des entiers naturels non nuls) et $\alpha' = +\omega^{\gamma'_{s'}} n'_{s'} + \cdots + \omega^{\gamma'_1} n'_1$ +(idem) sont deux ordinaux écrits en forme normale de Cantor, en +utilisant les résultats de la question précédente, expliquer comment +calculer $\alpha + \alpha'$, en supposant qu'on sache +algorithmiquement comparer les $\gamma_i$ et les $\gamma'_j$. + +\begin{corrige} +On écrit $\alpha + \alpha' = \omega^{\gamma_s} n_s + \cdots + +\omega^{\gamma_1} n_1 + \omega^{\gamma'_{s'}} n'_{s'} + \cdots + +\omega^{\gamma'_1} n'_1$ et, d'après ce qu'on vient de voir, dès que +deux termes ne sont pas dans le bon ordre (i.e., si un +$\omega^{\gamma_i} n_i$ précède $\omega^{\gamma_j} n_j$ avec $\gamma_i +< \gamma_j$), alors le premier disparaît purement et simplement ; et +bien sûr, si $\gamma_i = \gamma_j$, les termes fusionnent en +$\omega^{\gamma_i} (n_i+n_j)$ par distributivité à droite. On se +retrouve donc avec l'écriture en forme normale de Cantor de $\alpha + +\alpha'$. +\end{corrige} + +\textbf{(3)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot +3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha + +\alpha'$ et $\alpha' + \alpha$. + +\begin{corrige} +Dans le sens $\alpha + \alpha'$, on a $(\omega^3\cdot 2 + \omega\cdot +3 + 5) + (\omega^2 + \omega\cdot 4) = \omega^3\cdot 2 + \omega^2 + +\omega\cdot 4$. + +Dans le sens $\alpha' + \alpha$, on a $(\omega^2 + \omega\cdot 4) + +(\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^3\cdot 2 + \omega\cdot +3 + 5$. +\end{corrige} + +\textbf{(4)} Déduire de la question (2) que si $\alpha = +\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ en forme +normale de Cantor et $k \geq 1$ est un entier naturel, alors +$\alpha\cdot k = \omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} +n_{s-1} + \cdots + \omega^{\gamma_1} n_1$ (c'est-à-dire que seul le +coefficient $n_s$ de la plus haute puissance de $\omega$ est multiplié +par $k$ ; \emph{indication} : on a $\alpha\cdot k = \alpha + \cdots + +\alpha$ avec $k$ termes identiques). + +\begin{corrige} +En écrivant $\alpha\cdot k = \alpha + \cdots + \alpha$ (qui résulte de +la distributivité à droite) et en appliquant les règles expliquées +en (2), on voit que tous les termes autres que le plus haut de tous +les termes autres que le dernier de la terme disparaissent purement et +simplement (ils sont absorbés par le terme le plus haut du $\alpha$ +suivant), donc seul subsistent $k-1$ copies de $\omega^{\gamma_s} n_s$ +plus le dernier $\alpha$, ce qui donne bien $\alpha\cdot k = +\omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} n_{s-1} + \cdots + +\omega^{\gamma_1} n_1$ comme annoncé. +\end{corrige} + +\textbf{(5)} En déduire que, toujours pour $\alpha = \omega^{\gamma_s} +n_s + \cdots + \omega^{\gamma_1} n_1$, on a $\alpha\cdot\omega = +\omega^{\gamma_s+1}$ (\emph{indication} : on pourra calculer +$\lim_{k\to\omega} \alpha \cdot k$), et plus généralement $\alpha\cdot +\omega^{\gamma'} = \omega^{\gamma_s+\gamma'}$ si $\gamma'\geq 1$ +(\emph{indication} : on pourra écrire $\gamma' = 1+\gamma''$). + +\begin{corrige} +On cherche à calculer $\alpha\cdot\omega = \lim_{k\to\omega} \alpha \cdot +k$ (rappelons que cette limite est juste une borne supérieure). Par +comparaison des formes normales de Cantor, $\omega^{\gamma_s+1}$ est +plus grand que tous les $\alpha\cdot k = \omega^{\gamma_s} n_sk + +\omega^{\gamma_{s-1}} n_{s-1} + \cdots + \omega^{\gamma_1} n_1$, donc +$\omega^{\gamma_s+1} \geq \lim_{k\to\omega} \alpha \cdot k$. Mais +inversement, la forme normale de Cantor de tout ordinal +$<\omega^{\gamma_s+1}$ commence par un terme $\leq\omega^{\gamma_s} +N$, donc majoré par $\alpha\cdot k$ pour $k$ assez grand (certainement +pour $k\geq N$) : donc $\lim_{k\to\omega} \alpha \cdot k$ ne peut pas +être $<\omega^{\gamma_s+1}$. Donc c'est exactement +$\omega^{\gamma_s+1}$, et on a prouvé $\alpha\cdot\omega = +\omega^{\gamma_s+1}$. + +Plus généralement, si $\gamma'\geq 1$, on peut écrire $\gamma' = +1+\gamma''$ comme on l'a déjà rappelé plus haut, et +$\alpha\cdot\omega^{\gamma'} = \alpha\cdot\omega^{1+\gamma''} = +\alpha\cdot\omega\omega^{\gamma''} = +\omega^{\gamma_s+1}\omega^{\gamma''} = \omega^{\gamma_s+1+\gamma''} = +\omega^{\gamma_s+\gamma'}$. +\end{corrige} + +\textbf{(6)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots + +\omega^{\gamma_1} n_1$ et $\alpha' = \omega^{\gamma'_{s'}} n'_{s'} + +\cdots + \omega^{\gamma'_1} n'_1$ sont deux ordinaux écrits en forme +normale de Cantor, en utilisant les résultats de la question +précédente, expliquer comment calculer $\alpha \cdot \alpha'$, en +supposant qu'on sache algorithmiquement comparer et ajouter les +$\gamma_i$ et les $\gamma'_j$. + +\begin{corrige} +Par distributivité à droite et comme on sait déjà calculer des sommes, +on peut se ramener au cas où $\alpha'$ est un seul terme +$\omega^{\gamma'} n'$. Par associativité, il suffit de savoir +calculer le produit par $\omega^{\gamma'}$ à droite, et par $n'$. Le +produit par $\omega^{\gamma'}$ est trivial si $\gamma'=0$ et est réglé +par la question (5) si $\gamma'>0$. Et le produit par $n'$ est réglé +par la question (4). + +Un peu plus concrètement, pour chaque terme de $\alpha'$ pour lequel +$\gamma'_j > 0$, on a $\alpha\cdot \omega^{\gamma'_j} n'_j = +\omega^{\gamma_s + \gamma'_j} n_s n_j$, et le terme fini, s'il existe +(c'est-à-dire si $\gamma'_1 = 0$) vaut $\alpha\cdot n'_1 = +\omega^{\gamma_s} n_s n'_1 + \omega^{\gamma_{s-1}} n_{s-1} + \cdots + +\omega^{\gamma_1} n_1$. Il n'y a plus qu'à ajouter tous ces termes +dans l'ordre (qui est déjà le bon, et qui donne déjà une forme normale +de Cantor, puisque $\gamma_s + \gamma'_s > \cdots + \gamma_s + +\gamma'_2 > \gamma_s > \cdots > \gamma_1$). +\end{corrige} + +\textbf{(7)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot +3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha \cdot +\alpha'$ et $\alpha' \cdot \alpha$. + +\begin{corrige} +Dans le sens $\alpha\alpha'$ on trouve $(\omega^3\cdot 2 + \omega\cdot +3 + 5) (\omega^2 + \omega\cdot 4) = \omega^5 + \omega^4\cdot 4$ (il +n'y a pas de terme fini à la fin de $\alpha'$ donc seul le premier +terme de $\alpha$ survit). + +Dans le sens $\alpha'\alpha$ on trouve $(\omega^2 + \omega\cdot 4) +(\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^5\cdot 2 + +\omega^3\cdot 3 + \omega^2\cdot 5 + \omega\cdot 4$. +\end{corrige} + + + +% +% +% +\end{document} |