Third exercise.

1 files changed, 111 insertions, 0 deletions

diff --git a/controle-20230417.tex b/controle-20230417.tex
index 478c1eb..1ce23ea 100644
--- a/controle-20230417.tex
+++ b/controle-20230417.tex
@@ -1,5 +1,6 @@
 %% 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}
@@ -42,6 +43,8 @@
 \newcommand{\dur}{\operatorname{dur}}
 \newcommand{\fuzzy}{\mathrel{\|}}
 %
+\newcommand{\dblunderline}[1]{\underline{\underline{#1}}}
+%
 \DeclareUnicodeCharacter{00A0}{~}
 %
 \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
@@ -485,6 +488,114 @@ non-vides), et pour la même raison que précédemment, ceci est $\leq
 \end{corrige}
 
 
+%
+%
+%
+
+\exercice
+
+Soit $G$ un graphe orienté dont l'ensemble des sommets est (au plus)
+dénombrable, et soit $x_0$ un sommet de $G$.  (Il n'y a pas d'autre
+hypothèse sur $G$, par exemple on ne suppose pas que $G$ est
+bien-fondé.)
+
+On considère le jeu suivant.  Deux joueurs s'affrontent, qu'on
+appellera \emph{le Fugueur} et \emph{le Borneur}.  Le Fugueur
+commence, après quoi ils jouent tour à tour.  En partant de $x_0$,
+chaque joueur, quand vient son tour, choisit un voisin sortant de la
+position actuelle $x$ \emph{ou bien} choisit de conserver $x$ ;
+autrement dit, il choisit un élément de $\outnb(x) \cup \{x\}$.  (Pour
+être parfaitement clair : au premier tour, le Fugueur choisit $x_1 \in
+\outnb(x_0) \cup \{x_0\}$, puis le Borneur choisit $x_2 \in
+\outnb(x_1) \cup \{x_1\}$, et ainsi de suite.)  Le jeu dure infiniment
+longtemps (manifestement, chaque joueur permettent toujours de faire
+un coup).  Au bout d'un nombre infini de coups, on considère la suite
+$(x_n)_{n\in\mathbb{N}}$ de toutes les positions traversées :
+\begin{itemize}
+\item si cette suite est d'image finie (c'est-à-dire que l'ensemble
+  $\{x_n : n\in\mathbb{N}\}$ de toutes les positions traversées est
+  fini), alors le Borneur a gagné ;
+\item sinon, le Fugueur a gagné.
+\end{itemize}
+
+(1) Montrer, en appliquant un des résultats du cours, que l'un des
+joueurs a nécessairement une stratégie gagnante (on ne demande pas de
+préciser lequel).  On pourra préalablement montrer que pour toute
+partie $F \subseteq G$, la partie $F^{\mathbb{N}} \subseteq
+G^{\mathbb{N}}$ est \emph{fermée} pour la topologie sur
+$G^{\mathbb{N}}$ produit de la topologie
+discrète\footnote{C'est-à-dire celle qui a été étudiée en cours.}, et
+en déduire une propriété de $\bigcup_{F\text{~fini~}\subseteq G}
+F^{\mathbb{N}}$ (c'est-à-dire la réunion des $F^{\mathbb{N}}$ où $F$
+parcourt toutes les parties \emph{finies} de $G$).
+
+\begin{corrige}
+Pour commencer, montrons que si $F$ est une partie de $G$ alors
+$F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée.  Ceci revient à
+montrer que son complémentaire est ouvert, autrement dit, que si
+$\dblunderline{x} \in G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$,
+alors il existe un voisinage fondamental de $\dblunderline{x}$ qui est
+inclus dans le complémentaire de $F^{\mathbb{N}}$ (autrement dit, ne
+rencontre pas $F^{\mathbb{N}}$).  Or si $\dblunderline{x} \in
+G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, c'est qu'elle a une
+valeur $x_\ell$ qui n'est pas dans $F$, et toute suite commençant par
+$x_0,\ldots,x_\ell$ n'est pas dans $F^{\mathbb{N}}$, c'est-à-dire que
+le voisinage fondamental $V_{\ell+1}(\dblunderline{x})$ est inclus
+dans le complémentaire de $F^{\mathbb{N}}$.  Ceci achève de montrer
+que $F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée.
+
+Maintenant, l'ensemble $\mathscr{F}$ des parties finies d'un ensemble
+(au plus) dénombrable, en l'occurrence, $G$, est (au plus)
+dénombrable.  Ce fait peut être tenu pour acquis, mais rappelons
+pourquoi il est vrai : en effet, si $G = \{g_i : i\in\mathbb{N}\}$,
+alors on peut par exemple énumérer $\mathscr{F}$ à travers les
+écritures binaires, ou plus précisément, $\mathscr{F} = \{F_n :
+n\in\mathbb{N}\}$ où $F_n$ désigne la partie finie
+$\{g_{i_0},\ldots,g_{i_r}\}$ lorsque $n = 2^{i_0} + \cdots + 2^{i_r}$
+avec $i_0,\ldots,i_r$ entiers naturels distincts (autrement dit, $F_0
+= \varnothing$, $F_1 = \{g_0\}$, $F_2 = \{g_1\}$, $F_3 = \{g_0,g_1\}$,
+etc.).  Peu importe le fait qu'il y ait des répétitions dans
+l'énumération $F_n$ (un ensemble surjecté par $\mathbb{N}$ est encore
+dénombrable).
+
+Ceci nous permet de dire que $\bigcup_{F\text{~fini~}\subseteq G}
+F^{\mathbb{N}}$, autrement dit $\bigcup_{F \in \mathscr{F}}
+F^{\mathbb{N}}$, est une réunion dénombrable de fermés
+dans $G^{\mathbb{N}}$.  Comme un fermé est borélien, c'est une réunion
+dénombrable de boréliens, donc c'est encore un borélien.
+
+Enfin, remarquons que dire que l'ensemble $\{x_n : n\in\mathbb{N}\}$
+est fini revient à dire qu'il est inclus un ensemble fini $F$,
+autrement dit, que la suite $\dblunderline{x} = (x_n)$ appartient à
+$F^{\mathbb{N}}$ pour un certain ensemble fini $F$, ou, ce qui revient
+au même, qu'elle appartient à $\bigcup_{F \in \mathscr{F}}
+F^{\mathbb{N}}$.
+
+On a donc affaire à un jeu de Gale-Stewart défini par l'ensemble de
+suites $A := \bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$ borélien.  Le
+théorème de détermination borélienne de Martin assure que l'un des
+joueurs a forcément une stratégie gagnante.
+\end{corrige}
+
+(2) Indépendamment de la question précédente, donner un exemple de
+couple $(G,x_0)$ pour lequel le Borneur possède une stratégie gagnante
+à ce jeu.  Donner un exemple pour lequel le Fugueur en possède une.
+(On cherchera à donner des exemples aussi simples que possibles.)
+
+\begin{corrige}
+Si $G$ est le graphe formé du seul sommet $x_0$, alors le Borneur
+gagne trivialement (la suite sera la suite constante).
+
+Si $G$ est le graphe formé des entiers naturels avec une arête $i \to
+j$ lorsque $i<j$ (autrement dit des petits entiers naturels vers les
+grands), ou même simplement $i \to i+1$, alors le Fugueur a une
+stratégie gagnante consistant à jouer de $i$ vers $i+1$, ce qui assure
+que la suite $(x_{2i+1})$ des positions choisies par le Fugueur est
+strictement croissante quoi que fasse le Borneur (il ne peut pas
+revenir en arrière), et notamment, elle n'est pas d'image finie.
+\end{corrige}
+
+
 
 %
 %