1 files changed, 119 insertions, 1 deletions
diff --git a/controle-20250626.tex b/controle-20250626.tex
index d5def48..c2177ca 100644
--- a/controle-20250626.tex
+++ b/controle-20250626.tex
@@ -45,6 +45,8 @@
 %
 \newcommand{\dblunderline}[1]{\underline{\underline{#1}}}
 %
+\renewcommand{\thefootnote}{\fnsymbol{footnote}}
+%
 \DeclareUnicodeCharacter{00A0}{~}
 %
 \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
@@ -124,7 +126,7 @@ Git: \input{vcline.tex}
 \exercise
 
 \textbf{(1)} On considère le jeu en forme normale symétrique à somme
-nulle défini par la matrice de gain suivante :
+nulle défini par la matrice de gains suivante :
 \begin{center}
 \begin{tabular}{r|ccc}
 $\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux\\\hline
@@ -178,6 +180,122 @@ jeu.\quad\textbf{(b)} Donner au moins un équilibre de Nash différent
 de ceux-ci.
 
 
+%
+%
+%
+
+\exercise
+
+On se propose dans cet exercice de montrer qu'il existe une partie $A
+\subseteq \{0,1\}^{\mathbb{N}}$ tel que le jeu de Gale-Stewart $G(A)
+:= G_{\{0,1\}}(A)$ ne soit pas déterminé (i.e., tel qu'aucun des deux
+joueurs n'ait de stratégie gagnante).
+
+(La démonstration a été découpées en questions admettant des réponses
+très courtes, parfois d'une seule ligne.  Aucune ne demande de
+raisonnement compliqué.)
+
+\textbf{(1)} Montrer qu'il existe une bijection $h_{\mathrm{A}}$
+(resp. $h_{\mathrm{B}}$) entre $\{0,1\}^{\mathbb{N}}$ et l'ensemble
+des stratégies d'Alice (resp. de Bob) au jeu $G(A)$.
+(\emph{Indication :} on pourra expliquer rapidement pourquoi il existe
+une bijection entre $\mathbb{N}$ et l'ensemble des positions où c'est
+à Alice, resp. à Bob, de jouer.)
+
+\textbf{(2)} On \emph{admet}\footnote{Plus généralement, on peut
+montrer qu'il existe une relation de bon ordre sur n'importe quel
+ensemble (théorème du bon ordre).} qu'il existe une relation de bon
+ordre $\preceq$ sur $\{0,1\}^{\mathbb{N}}$.  En déduire qu'il existe
+un ordinal $\gamma$ et une bijection $\xi \mapsto u_\xi$ entre
+l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$ et
+l'ensemble $\{0,1\}^{\mathbb{N}}$ (autrement dit, les $u_\xi$ sont
+deux à deux distincts et $\{u_\xi : \xi < \gamma\} =
+\{0,1\}^{\mathbb{N}}$).
+
+\textbf{(3)} Expliquer en une ligne, pourquoi il existe un plus petit
+ordinal $\gamma$ tel qu'il existe une surjection $\xi \mapsto u_\xi$
+de l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$
+sur l'ensemble $\{0,1\}^{\mathbb{N}}$.
+
+\textbf{Définition :} On notera $\mathfrak{c}$ l'ordinal dont on vient
+de justifier l'existence (i.e., le plus petit $\gamma$ tel qu'on
+puisse écrire $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ pour
+une certaine fonction $\xi \mapsto u_\xi$).
+
+\textbf{(4)} Si $(v_\xi)_{\xi<\alpha}$ sont des éléments quelconques
+de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, expliquer en
+une ligne pourquoi il existe un élément de $\{0,1\}^{\mathbb{N}}$
+différent de tous les $v_\xi$.
+
+\textbf{Définition :} Si $\sigma$ est une stratégie d'Alice au jeu
+$G(A)$ et $y \in \{0,1\}^{\mathbb{N}}$, on note $\sigma \ast y$ la
+confrontation dans laquelle Alice joue selon $\sigma$ et Bob joue
+simplement les termes successifs de $y$ (indépendamment de ce que fait
+Alice ; i.e., $\sigma \ast y$ est une suite binaire dont la suite des
+termes impairs, ceux joués par Bob, est donnée par $y$, tandis
+qu'Alice joue les termes pairs selon la stratégie $\sigma$).
+
+\textbf{(5)} Si $\sigma$ est une stratégie d'Alice, expliquer en une
+ligne pourquoi la fonction $y \mapsto \sigma \ast y$ (de
+$\{0,1\}^{\mathbb{N}}$ vers $\{0,1\}^{\mathbb{N}}$) est injective.
+
+\textbf{(6)} Si $(a_\xi)_{\xi<\alpha}$ sont des éléments quelconques
+de $\{0,1\}^{\mathbb{N}}$ où $\alpha < \mathfrak{c}$, déduire de
+(4) et (5) pourquoi il existe $y \in \{0,1\}^{\mathbb{N}}$ tel que
+$\sigma \ast y$ soit différent de tous les $a_\xi$.
+
+\textbf{Supposition :} Dans les questions (7) à (8), on suppose que
+$(\sigma_\xi)_{\xi<\mathfrak{c}}$ sont des stratégies d'Alice et
+$(\tau_\xi)_{\xi<\mathfrak{c}}$ des stratégies de Bob.  On les
+définira après la question (8), mais on n'a pas besoin d'en savoir
+plus pour l'instant.
+
+\textbf{(7)} En supposant préalablement définis des éléments
+$(a_\xi)_{\xi<\alpha}$ et $(b_\xi)_{\xi<\alpha}$ de
+$\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, déduire des
+questions précédentes qu'il existe $b_\alpha$ qui soit de la forme
+$\sigma_\alpha \ast y$ (pour un certain $y \in \{0,1\}^{\mathbb{N}}$),
+mais qui soit différent de tous les $a_\xi$ ; et, symétriquement,
+qu'il existe $a_\alpha$ qui soit de la forme $z \ast \tau_\alpha$
+(pour un certain $z \in \{0,1\}^{\mathbb{N}}$), mais différent de tous
+les $b_\xi$.
+
+On \emph{admettra} qu'il ne pose pas de problème pour
+choisir\footnote{Ceci constitue une utilisation de l'axiome du choix
+(qui a d'ailleurs déjà été utilisé dans ce qu'on a admis à la
+question (2)).}  de tels $a_\alpha$ et $b_\alpha$.
+
+\textbf{(8)} Déduire de tout ce qui précède qu'il existe $(a_\xi)_{\xi
+  < \mathfrak{c}}$ et $(b_\xi)_{\xi < \mathfrak{c}}$ tels que :
+\begin{itemize}
+\item aucun des $a_\xi$ n'est égal à aucun des $b_\zeta$,
+\item pour tout $\xi < \mathfrak{c}$, on a $b_\xi = \sigma_\xi \ast y$
+  pour un certain $y \in \{0,1\}^{\mathbb{N}}$,
+\item pour tout $\xi < \mathfrak{c}$, on a $a_\xi = z \ast \tau_\xi$
+  pour un certain $z \in \{0,1\}^{\mathbb{N}}$.
+\end{itemize}
+(C'est tout ce qu'on aura besoin de savoir pour la suite.)
+
+\textbf{Définitions :} Posons maintenant $\sigma_\xi :=
+h_{\mathrm{A}}(u_\xi)$ où $h_{\mathrm{A}}$ a été définie en (1) et
+$u_\xi$ en (3), et de même $\tau_\xi := h_{\mathrm{B}}(u_\xi)$.
+
+On pose enfin $A = \{a_\xi : \xi < \mathfrak{c}\}$ l'ensemble des
+$a_\xi$ qu'on vient de construire en (8).
+
+\textbf{(9)} Montrer que, quel que soit $\xi$, la stratégie
+$\sigma_\xi$ n'est pas gagnante pour Alice au jeu $G(A)$.  Montrer que
+la stratégie $\tau_\xi$ n'est pas gagnante pour Bob à ce même jeu
+(attention, ce n'est pas exactement symétrique vu que $A$ est
+l'ensemble des $a_\alpha$).
+
+\textbf{(10)} Déduire de tout ce qui précède que ni Alice ni Bob n'ont
+de stratégie gagnante au jeu $G(A)$.
+
+\textbf{(11)} Pourquoi ceci ne contredit pas les résultats vu en
+cours ?
+
+
 
 %
 %