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}