diff options
| -rw-r--r-- | notes-mitro206.tex | 50 |
1 files changed, 44 insertions, 6 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 15ac029..7d5f1b3 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -1304,7 +1304,7 @@ $A$, Alice \textbf{gagne}, sinon c'est Bob (la partie n'est jamais nulle). Dans ce contexte, les suites finies d'éléments de $X$ s'appellent les -\textbf{positions} (y compris la suite vide, qui peut s'appeler +\textbf{positions} (y compris la suite vide $()$, qui peut s'appeler position initiale) de $G_X(A)$, ou de $G_X$ vu que $A$ n'intervient pas ici ; leur ensemble $\bigcup_{\ell=0}^{+\infty} X^\ell$ s'appelle parfois l'\textbf{arbre} du jeu $G_X$. Une \textbf{partie} ou @@ -1324,10 +1324,10 @@ $\big(\bigcup_{\ell=0}^{+\infty} X^{2\ell}\big) \to X$ Lorsque dans une partie (confrontation) $x_0,x_1,x_2,\ldots$ de $G_X$ on a $\varsigma((x_0,\ldots,x_{i-1})) = x_i$ pour chaque $i$ pair (y -compris $\varsigma(()) = x_0$), on dit qu'Alice a joué la partie selon -la stratégie $\varsigma$ ; de même, lorsque -$\tau((x_0,\ldots,x_{i-1})) = x_i$ pour chaque $i$ impair, on dit que -Bob a joué la partie selon la stratégie $\tau$. +compris $\varsigma(()) = x_0$ en notant $()$ la suite vide), on dit +qu'Alice a joué la partie selon la stratégie $\varsigma$ ; de même, +lorsque $\tau((x_0,\ldots,x_{i-1})) = x_i$ pour chaque $i$ impair, on +dit que Bob a joué la partie selon la stratégie $\tau$. Si $\varsigma$ et $\tau$ sont deux stratégies pour Alice et Bob respectivement, on définit $\varsigma \ast \tau$ comme la partie jouée @@ -1340,9 +1340,47 @@ pour Alice est dite \textbf{gagnante} (dans $G_X(A)$) lorsque Alice gagne toute partie où elle joue selon $\varsigma$. La stratégie $\tau$ pour Bob est dite \textbf{gagnante} lorsque Bob gagne toute partie où il joue selon $\tau$. Lorsque l'un ou l'autre joueur a une -stratégig gagnante, le jeu est dit \textbf{déterminé}. +stratégie gagnante, le jeu est dit \textbf{déterminé}. \end{defn} +\thingy Il peut arriver qu'on ait envie d'échanger les rôles d'Alice +et Bob, c'est-à-dire soit de faire commencer la partie à Bob, soit de +définir le jeu par l'ensemble $B$ des suites qui font gagner Bob (et +qui est simplement $X^{\mathbb{N}} \setminus A$), soit les deux. Il +va de soi que ceci ne pose aucune difficulté, il faudra juste le +signaler le cas échéant. + +\smallbreak + +La proposition suivante est presque triviale et signifie qu'Alice (qui +doit jouer) possède une stratégie gagnante si et seulement si elle +peut jouer un coup $x$ qui l'amène à une position d'où elle (Alice) a +une stratégie gagnante, et Bob en possède une si et seulement si +n'importe quel coup $x$ joué par Alice amène à une position d'où il +(Bob) a une stratégie gagnante : +\begin{prop} +Soit $X$ un ensemble et $A \subseteq X^{\mathbb{N}}$. Pour $x \in X$, +on notera $x^{\$} A$ l'ensemble des suites $(x_1,x_2,x_3,\ldots) \in +X^{\mathbb{N}}$ telles que $(x,x_1,x_2,\ldots) \in A$ (autrement dit, +l'image réciproque de $A$ par l'application $X^{\mathbb{N}} \to +X^{\mathbb{N}}$ qui insère un $x$ en début de la suite). + +Dans le jeu de Gale-Stewart $G_X(A)$ : +\begin{itemize} +\item Alice (premier joueur) possède une stratégie gagnante si et + seulement si il existe $x \in X$ tel qu'elle (=Alice) possède une + stratégie gagnante en jouant en second dans le jeu de Gale-Stewart + défini par le sous-ensemble $x^{\$} A$ ; +\item Bob (second joueur) possède une stratégie gagnante si et + seulement si pour tout $x \in X$ il (=Bob) possède une stratégie + gagnante en jouant en premier dans le jeu de Gale-Stewart défini par + le sous-ensemble $x^{\$} A$. +\end{itemize} +\end{prop} +\begin{proof} +\textcolor{red}{...} +\end{proof} + % |