diff options
| -rw-r--r-- | controle-20230417.tex | 111 |
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} + + % % |