diff options
| -rw-r--r-- | controle-20210412.tex | 381 |
1 files changed, 381 insertions, 0 deletions
diff --git a/controle-20210412.tex b/controle-20210412.tex new file mode 100644 index 0000000..dd3f016 --- /dev/null +++ b/controle-20210412.tex @@ -0,0 +1,381 @@ +%% 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{\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{12 avril 2021} +\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. + +La longueur du sujet ne doit pas effrayer : d'une part, l'énoncé est +long parce que des rappels ont été faits et que la rédaction des +questions cherche à éviter toute ambiguïté ; d'autre part, il ne sera +pas nécessaire de tout traiter pour obtenir la totalité des points. + +\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} : chaque question numérotée aura +approximativement la même valeur (environ $1$ à $1.5$ points). + +\ifcorrige +Ce corrigé comporte \textcolor{red}{nnn} pages (page de garde incluse). +\else +Cet énoncé comporte 5 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 en forme normale, à deux joueurs, à somme nulle, +dont la matrice de gains est la suivante, où $x$ est un réel (la table +donne les gains d'Alice, qui choisit la ligne, ceux de Bob, qui +choisit la colonne, sont opposés) : + +\begin{center} +\begin{tabular}{r|rrrr} +$\downarrow$Alice, Bob$\rightarrow$&P&Q&R&S\\\hline +P&$0$&$1$&$-1$&$x$\\ +Q&$-1$&$0$&$2$&$-1$\\ +R&$1$&$-2$&$0$&$-1$\\ +S&$-x$&$1$&$1$&$0$\\ +\end{tabular} +\end{center} + +On rappelle qu'une \emph{stratégie optimale} est une stratégie mixte +qui réalise un gain espéré au moins égal à la valeur du jeu contre +toute stratégie (pure donc mixte) de l'adversaire. + +(0) Quelle est la valeur du jeu dans ce cas ? + +(1) À quelle condition sur $x$ la stratégie $\frac{1}{2}\mathrm{P} + +\frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$ (consistant à choisir P +avec probabilité $\frac{1}{2}$, et chacun de Q et R avec +probabilité $\frac{1}{4}$) est-elle optimale ? + +(2) À quelle condition sur $x$ la stratégie $\frac{1}{x+2}\mathrm{P} + +\frac{x}{x+2}\mathrm{R} + \frac{1}{x+2}\mathrm{S}$ (consistant à +choisir R avec probabilité $\frac{x}{x+2}$, et chacun de P et S avec +probabilité $\frac{1}{x+2}$) est-elle optimale ? + +(3) Donner une stratégie optimale lorsque $x\leq 0$. + +(4) Dans chacun des cas $x=0$ et $x=1$, exhiber une infinité de +stratégies optimales distinctes. + +(5) En supposant que $x$ ne soit pas un réel fixé mais \emph{tiré au + hasard} selon une loi uniforme entre $0$ et $1$ une fois que les +joueurs ont joué (autrement dit, si un joueur choisit P et l'autre S, +le joueur qui a choisi P reçoit un gain aléatoire uniforme entre +$0$ et $1$), quelle stratégie adopteriez-vous dans ce jeu ? + + +% +% +% + +\exercice + +Dans cet exercice, on va d'abord définir les ordinaux +$\varepsilon_\iota$, puis on va s'intéresser à ceux qui +sont $<\varepsilon_1$. Les parties de cet exercice sont indépendantes +à l'exception de ce qui est explicitement rappelé. + +\medskip + +\underline{Première partie.} + +On définit une fonction $\varphi$ des ordinaux vers les ordinaux par +$\varphi(\alpha) = \omega^\alpha$. On rappelle que $\varphi$ est +\emph{strictement croissante} (c'est-à-dire que si $\alpha < \beta$ +alors $\varphi(\alpha) < \varphi(\beta)$). + +(1) Rappeler pourquoi $\varphi$ est \emph{continue}, ce qui signifie +par définition la chose suivante : si $\delta$ est un ordinal limite, +alors $\lim_{\xi\to\delta} \varphi(\xi) = \varphi(\delta)$, où +$\lim_{\xi\to\delta} \varphi(\xi)$ est une notation pour +$\sup\{\varphi(\xi) : \xi < \delta\}$. + +Pour éviter de partir dans des fausses directions, il est conseillé, +jusqu'à la question (5) incluse, d'oublier la définition de $\varphi$ +et de retenir simplement que $\varphi$ est strictement croissante et +continue. + +(2) Rappeler pourquoi $\varphi(\alpha) \geq \alpha$ pour +tout $\alpha$. + +On dira qu'un ordinal $\gamma$ est un \emph{point fixe} de $\varphi$ +lorsque $\varphi(\gamma) = \gamma$. + +(3) Soit dans cette question $\alpha$ un ordinal quelconque : +considérons la suite $(\gamma_n)$ (indicée par les entiers +naturels $n$) définie par $\gamma_0 = \alpha$ et $\gamma_{n+1} = +\varphi(\gamma_n)$. Montrer que $(\gamma_n)$ est croissante +(c'est-à-dire que $m\leq n$ implique $\gamma_m \leq \gamma_n$). +Montrer que sa limite $\gamma_\omega := \lim_{n\to\omega} \gamma_n := +\sup\{\gamma_n : n \in \mathbb{N}\}$ est un point fixe de $\varphi$. +Montrer qu'il s'agit du plus petit point fixe de $\varphi$ qui +soit $\geq\alpha$ (c'est-à-dire que si $\delta$ est un point fixe +de $\varphi$ et $\delta\geq\alpha$ alors $\delta\geq\gamma_\omega$ : +on pourra pour cela montrer que $\delta\geq\gamma_n$ pour tout $n$). + +La question (3) implique notamment : \emph{pour tout ordinal $\alpha$ + il existe un point fixe de $\varphi$ qui soit $\geq\alpha$}. + +On définit maintenant $\varepsilon_\iota$ pour tout ordinal $\iota$ +par : +\begin{itemize} +\item $\varepsilon_0$ est le plus petit point fixe de $\varphi$ + (c'est-à-dire, si on veut, le plus petit point fixe qui soit $\geq + 0$) ; +\item pour $\iota+1$ ordinal successeur, $\varepsilon_{\iota+1}$ est + le plus petit point fixe de $\varphi$ qui soit $>\varepsilon_\iota$ + (c'est-à-dire, si on veut, le plus petit point fixe qui soit $\geq + (\varepsilon_\iota)+1$), +\item pour $\delta$ ordinal limite, $\varepsilon_\delta$ est + $\lim_{\xi\to\delta} \varepsilon_\xi$ (c'est-à-dire + $\sup\{\varepsilon_\xi : \xi < \delta\}$). +\end{itemize} + +(4) Montrer que $\iota \mapsto \varepsilon_\iota$ est strictement +croissante. Montrer que $\varepsilon_\delta$ est un point fixe +de $\varphi$ aussi pour $\delta$ limite (c'est vrai pour les autres +cas par la définition) : pour cela, on expliquera pourquoi +$\varphi(\lim_{\xi\to\delta} \varepsilon_\xi) = \lim_{\xi\to\delta} +\varphi(\varepsilon_\xi)$. + +(5) Montrer que tout ordinal $\gamma$ qui est un point fixe de +$\varphi$ est de la forme $\varepsilon_\iota$ pour un certain +ordinal $\iota$ (on pourra montrer qu'il existe $\iota$ tel que +$\varepsilon_\iota\geq\gamma$ puis considérer le plus petit +tel $\iota$). + +\medskip + +\underline{Deuxième partie.} + +\nobreak +On appelle $\varepsilon_0$ le plus petit ordinal tel que $\varepsilon += \omega^\varepsilon$, et $\varepsilon_1$ le suivant, c'est-à-dire le +plus petit ordinal $>\varepsilon_0$ vérifiant cette même équation +$\varepsilon = \omega^\varepsilon$ (l'existence de ces ordinaux +résulte de la première partie de cet exercice). + +On a vu en cours que les ordinaux $<\varepsilon_0$ possèdent une +représentation unique sous forme normale de Cantor itérée, et que +celle-ci permet de les comparer, de les ajouter et de les multiplier. +On va se pencher ici sur \emph{deux} systèmes différents d'écriture +des ordinaux $<\varepsilon_1$, qu'on appellera « écriture 1 » et +« écriture 2 ». + +(6) Soit $\alpha < \varepsilon_1$ un ordinal différent +de $\varepsilon_0$ : montrer que dans sa forme normale de Cantor +$\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$, tous les +exposants $\gamma_i$ sont $<\alpha$ (on pourra utiliser le fait, +démontré en (2), que $\omega^\gamma \geq \gamma$ pour tout +ordinal $\gamma$). + +On appellera \emph{écriture 1} d'un ordinal $\alpha < \varepsilon_1$ +l'écriture qui est \underline{ou bien} $\varepsilon_0$ (considéré +comme un symbole spécial), \underline{ou bien} une forme normale de +Cantor $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ où les +exposants $\gamma_s > \cdots > \gamma_1$ sont tous $<\alpha$ et +eux-mêmes écrits en écriture 1 (ceci a bien un sens par (6)). + +À titre d'exemple, $\omega^\omega\,2$ ou $\varepsilon_0$ ou bien +$\omega^{\varepsilon_0} + 1$ ou encore +$\omega^{\omega^{\varepsilon_0}+1}\,2$ sont des écritures 1. En +revanche, $\omega^{\varepsilon_0}$ n'en est pas une (elle ne vérifie +pas la contrainte sur les exposants), ni $\varepsilon_0 + 1$ (ce n'est +ni le symbole spécial $\varepsilon_0$ ni une forme normale de Cantor), +ni $(\varepsilon_0)^2$. + +(7) Il est facile de voir que cette écriture 1 permet +algorithmiquement de manipuler les ordinaux $<\varepsilon_1$ : +c'est-à-dire de les comparer, de les ajouter et de les multiplier (on +ne demande pas de le justifier, les algorithmes étant essentiellement +les mêmes que vus en cours pour les ordinaux $<\varepsilon_0$) : il +faut simplement bien se rappeler que le fait que $\varepsilon_0 = +\omega^{\varepsilon_0}$. À titre d'exemple, calculer +$\varepsilon_0\cdot \omega$ et $\varepsilon_0^2 = +\varepsilon_0\cdot\varepsilon_0$ en écriture 1. Expliquer comment +calculer $(\varepsilon_0)^\alpha$ en écriture 1 lorsque $\alpha$ est +lui-même donné en écriture 1. À titre d'exemple, écrire +$(\varepsilon_0)^{\omega 2}$ en écriture 1. + +(8) Indépendamment des questions précédentes, rappeler pourquoi tout +ordinal $\alpha$ possède une écriture unique sous la forme +$(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots + +(\varepsilon_0)^{\gamma_1}\, \xi_1$ où $\gamma_s > \cdots > \gamma_1$ +sont des ordinaux et où $\xi_s,\ldots,\xi_1$ sont des ordinaux tous +non nuls et strictement inférieurs à $\varepsilon_0$. + +(9) Indépendamment des questions précédentes, montrer que +$\varepsilon_0 + \varepsilon_1 = \varepsilon_1$ (on rappelle que +$\omega^\gamma + \omega^{\gamma'} = \omega^{\gamma'}$ lorsque $\gamma +< \gamma'$). En déduire que $\varepsilon_0 \cdot \varepsilon_1 = +\varepsilon_1$. En déduire que $(\varepsilon_0)^{\varepsilon_1} = +\varepsilon_1$. Réciproquement, montrer que si $\delta$ est un +ordinal tel que $(\varepsilon_0)^{\delta} = \delta$ alors on a aussi +$\omega^\delta = \delta$ (on pourra montrer $\delta \leq \omega^\delta +\leq \omega^{\varepsilon_0 \delta} \leq \delta$) et en déduire que +$\delta \geq \varepsilon_1$. En déduire que $\varepsilon_1$ est le +plus petit ordinal tel que $(\varepsilon_0)^{\delta} = \delta$. + +On appellera \emph{écriture 2} d'un ordinal $\alpha < \varepsilon_1$ +une écriture $(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots + +(\varepsilon_0)^{\gamma_1}\, \xi_1$ comme en (7), où les exposants +$\gamma_s > \cdots > \gamma_1$ sont tous $<\alpha$ et eux-mêmes écrits +en écriture 2, et où les $\xi_s,\ldots,\xi_1$ (qui +sont $<\varepsilon_0$) sont écrits en forme normale de Cantor itérée. + +À titre d'exemple, $\omega^\omega\,2$ (il faut sous-entendre +$(\varepsilon_0)^0$ devant, qui vaut $1$) ou $(\varepsilon_0)^2 + 1$ +ou bien $\varepsilon_0\,2 + \omega^\omega$ ou encore +$(\varepsilon_0)^{\varepsilon_0}\,\omega^\omega\,3$ sont des +écritures 2. En revanche, $\omega^{\varepsilon_0+1}$ n'en est pas une +(les puissances de $\omega$ ne peuvent apparaître qu'au sein d'une +forme normale de Cantor itérée, donc ne faisant jamais intervenir +$\varepsilon_0$). + +(10) Esquisser un algorithme permettant de convertire l'écriture 2 +d'un ordinal $<\varepsilon_1$ en écriture 1 (on utilisera la +question (7)). + +\medskip + +\underline{Troisième partie.} + +\nobreak +On aura besoin ici des définitions des ordinaux $\varepsilon_0$ et +$\varepsilon_1$ données en tête de la première partie, mais pas plus. + +On s'intéresse à un jeu de Hercule et de l'hydre qui est analogue au +jeu considéré en cours mais avec une extension : comme en cours, +l'hydre est un arbre fini enraciné, mais l'hydre a maintenant deux +types de têtes (= feuilles de l'arbre) : des têtes normales, et des +\emph{œufs} (pouvant donner naissance à de nouvelles hydres). Quand +Hercule coupe une tête $x$ normale, l'hydre se reproduit exactement +comme on l'a vu en cours, c'est-à-dire qu'elle reproduit autant +d'exemplaires qu'elle le veut de tout le sous-arbre partant du nœud +$y$ parent de $x$ dans l'arbre (ces copies étant ajoutées comme filles +du nœud $z$ parent de $y$), à condition que $y$ ne soit pas la racine +(sinon, l'hydre ne joue pas). En revanche, si Hercule coupe un œuf, +cet œuf est remplacé par une nouvelle hydre, c'est-à-dire par un +sous-arbre, arbitrairement complexe, mais ne comportant pas lui-même +d'œuf. + +(11) En associant à toute position du jeu (= tout arbre enraciné dont +certaines feuilles sont qualifiées d'œufs) un +ordinal $<\varepsilon_1$, montrer que Hercule gagne toujours, +c'est-à-dire qu'il va toujours réduire l'hydre à sa seule racine en +temps fini. + +(12) Donner un exemple de position du jeu associé à l'ordinal +$(\varepsilon_0)^{\varepsilon_0}$ par le système proposé en (11). + + +% +% +% +\end{document} |