Write test for 2024.

1 files changed, 318 insertions, 0 deletions

diff --git a/controle-20240422.tex b/controle-20240422.tex
new file mode 100644
index 0000000..e80dece
--- /dev/null
+++ b/controle-20240422.tex
@@ -0,0 +1,318 @@
+%% 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 \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
+
+\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 antagonistes, les intérêts des deux joueurs sont
+parfaitement alignés).
+
+É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\}$).
+
+\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 strictement positifs et distincts, disons $0 < g_1 < g_2 <
+\cdots < g_N$ pour fixer les idées.  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$.
+
+\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.  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\}$.
+
+\textbf{(c)} Vérifier que les stratégies mixtes décrites 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.
+
+
+%
+%
+%
+
+\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$.
+
+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((y_i))-u| < \varepsilon$.  (Autrement dit, il existe $\ell$ tel
+que l'image du $\ell$-ième voisinage fondamental
+$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 en bas de
+page \ref{footnote-series-converges}.)
+
+\textbf{(2)} En déduire que si $U \subseteq \mathbb{R}$ est ouvert (au
+sens de la topologie usuelle des réels), 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).
+
+\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.
+
+\textbf{(4)} Montrer 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.
+
+
+%
+%
+%
+
+\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 :} pourquoi peut-on é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$).
+
+\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$.
+
+\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$.
+
+\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).
+
+\textbf{(5)} En déduire que, toujours pour $\alpha = \omega^{\gamma_s}
+n_s + \cdots + \omega^{\gamma_1} n_1$, on a $\alpha\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''$).
+
+\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$.
+
+\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$.
+
+
+
+%
+%
+%
+\end{document}