From e9b405c6c288268ff2c4c4c3bdaafe57f8623688 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 16 Apr 2024 23:43:51 +0200 Subject: Write answer key. --- controle-20240422.tex | 270 ++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 261 insertions(+), 9 deletions(-) diff --git a/controle-20240422.tex b/controle-20240422.tex index 37cf995..430adf5 100644 --- a/controle-20240422.tex +++ b/controle-20240422.tex @@ -102,7 +102,7 @@ L'usage des appareils électroniques est interdit. Durée : 2h \ifcorrige -Ce corrigé comporte \textcolor{red}{xxx} pages (page de garde incluse). +Ce corrigé comporte 6 pages (page de garde incluse). \else Cet énoncé comporte 3 pages (page de garde incluse). \fi @@ -143,13 +143,32 @@ 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 et distincts, disons $0 < g_1 < -g_2 < \cdots < g_N$ pour fixer les idées. Pour résumer : +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 @@ -169,6 +188,16 @@ 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 @@ -177,10 +206,53 @@ 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} + % % @@ -234,6 +306,19 @@ incluse dans la boule ouverte $B_\varepsilon(u) := (\emph{Indication :} s'inspirer de la note en bas de page \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 @@ -242,8 +327,39 @@ 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). -\textbf{(3)} En déduire que si $A$ est ouvert, ou bien fermé, l'un des -deux joueurs possède une stratégie gagnante au jeu qu'on a décrit. +\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 @@ -251,6 +367,25 @@ 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} + % % @@ -272,6 +407,34 @@ 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' = @@ -281,10 +444,33 @@ 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 @@ -294,12 +480,47 @@ 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\omega = +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\omega^{\gamma'} = \omega^{\gamma_s+\gamma'}$ si $\gamma'\geq -1$ (\emph{indication} : on pourra écrire $\gamma' = 1+\gamma''$). +$\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'} + @@ -309,10 +530,41 @@ 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} + % -- cgit v1.2.3