A (long) exercise on the determination of Gale-Stewart-like games defined by continuous functions.

1 files changed, 340 insertions, 1 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 9f9f8ca..43545a1 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1853,7 +1853,7 @@ d'après \ref{strategies-forall-exists-lemma}, (a) il existe un $x$ tel
 que $(x_0,\ldots,x_{i-1},x)$ ne soit pas gagnante pour Alice :
 choisissons-un tel $x$ et posons $\tau((x_0,\ldots,x_{i-1})) := x$ :
 toujours d'après \ref{strategies-forall-exists-lemma}, (b) quel que
-soit $x' \in X$, la position $(x_0,\ldots,x_{i-1},x,y)$ n'est pas
+soit $y \in X$, la position $(x_0,\ldots,x_{i-1},x,y)$ n'est pas
 gagnante pour Alice (et c'est de nouveau à Bob de jouer).  Aux points
 où $\tau$ n'a pas été défini par ce qui vient d'être dit, on le
 définit de façon arbitraire.
@@ -5217,6 +5217,345 @@ où Roxane commence (exactement analogue : Roxane choisit $(x_0,x_1)
 
 \subsection{Jeux de Gale-Stewart et détermination}
 
+\exercice
+
+On considère dans cet exercice une variante des jeux de Gale-Stewart
+où au lieu qu'un joueur « gagne » et l'autre « perde », il va leur
+être attribué un gain réel comme dans les jeux à somme nulle.  Plus
+exactement, ce type de jeu est décrit comme suit.  On fixe un ensemble
+$X$ (non vide) et une fonction $u \colon X^{\mathbb{N}} \to
+\mathbb{R}$ dite fonction de gain d'Alice (la fonction de gain de Bob
+serait $-u$).  Alice et Bob choisissent tour à tour un élément de $X$
+comme pour un jeu de Gale-Stewart, et jouent un nombre infini de
+coups, « à la fin » desquels la suite $\underline{x} =
+(x_0,x_1,x_2,\ldots)$ définit un élément $\underline{x} \in
+X^{\mathbb{N}}$.  Le gain d'Alice est alors $u(\underline{x})$ (le but
+d'Alice est de le maximiser) et le gain de Bob est $-u(\underline{x})$
+(le but de Bob est de maximiser cette quantité, c'est-à-dire de
+minimiser $u(\underline{x})$).
+
+\smallbreak
+
+(1) Expliquer pourquoi ce type de jeu peut être considéré comme une
+généralisation des jeux de Gale-Stewart.
+
+\begin{corrige}
+Si $G_X(A)$ où $A \subseteq X^{\mathbb{N}}$ est un jeu de Gale-Stewart
+défini par un sous-ensemble $A$ de $X^{\mathbb{N}}$, on peut définir
+une fonction $u \colon X^{\mathbb{N}} \to \mathbb{R}$ par
+$u(\underline{x}) = 1$ si $x\in A$ et $u(\underline{x}) = -1$
+si $x\not\in A$, c'est-à-dire utiliser la valeur $+1$ pour un gain
+d'Alice et $-1$ pour un gain de Bob.  Les buts d'Alice et de Bob dans
+le jeu défini par cette fonction sont alors exactement les mêmes que
+dans le jeu $G_X(A)$.
+\end{corrige}
+
+\smallbreak
+
+(2) On suppose désormais que $u \colon X^{\mathbb{N}} \to \mathbb{R}$
+est \emph{continue}, ce qui signifie par définition que pour tout
+$\underline{x} \in X^{\mathbb{N}}$ et tout $\varepsilon > 0$ réel, il
+existe $\ell$ tel que pour tout $y \in V_\ell(\underline{x})$ on ait
+$|u(\underline{y}) - u(\underline{x})| < \varepsilon$.  Montrer que
+quel que soit $v \in\mathbb{R}$ l'ensemble des $\underline{x}$ tels
+que $u(\underline{x}) > v$ est ouvert, et de même pour l'ensemble des
+$\underline{x}$ tels que $u(\underline{x}) < v$.
+
+\begin{corrige}
+Fixons un réel $v$.  Montrons que l'ensemble $A_v$ des $\underline{x}$
+tels que $u(\underline{x}) > v$ est ouvert.  Si $\underline{x}$ est
+dans $A_v$, i.e., vérifie $u(\underline{x}) > v$, alors la définition
+de la continuité appliquée à ce $\underline{x}$ et à $\varepsilon :=
+u(\underline{x}) - v$ assure qu'il existe $\ell$ tel que pour tout $y
+\in V_\ell(\underline{x})$ on ait $|u(\underline{y}) -
+u(\underline{x})| < \varepsilon$, et cette dernière inégalité implique
+$u(\underline{y}) > u(\underline{x}) - \varepsilon = v$, donc on a
+encore $u(\underline{y}) > v$, autrement dit $\underline{y} \in A_v$.
+On a donc montré que pour tout $\underline{x}$ dans $A_v$ il existe
+$\ell$ tel que tout $\underline{y}$ dans $V_\ell(\underline{x})$ soit
+encore dans $A_v$, c'est exactement dire que $A_v$ est ouvert.  Le cas
+de l'enesmble $B_v$ des $\underline{x}$ tels que $u(\underline{x}) <
+v$ est exactement analogue (on prendra $\varepsilon := v -
+u(\underline{x})$).
+\end{corrige}
+
+\smallbreak
+
+(3) (a) En déduire que pour tout $v$ réel, soit Alice possède une
+stratégie lui garantissant un gain $\geq v$, soit Bob possède une
+stratégie lui garantissant qu'Alice aura un gain $\leq v$
+(c'est-à-dire que lui, Bob, aura un gain $\geq -v$).\spaceout
+(b) Montrer que les deux ne peuvent se produire simultanément que pour
+\emph{au plus un} réel $v$.  Un tel $v$ s'appelle la \textbf{valeur}
+du jeu.
+
+\begin{corrige}
+(a) Quel que soit $v$ réel, on vient de voir que l'ensemble $A_v$ des
+  $\underline{x}$ tels que $u(\underline{x}) > v$ est ouvert.  La
+  détermination des jeux de Gale-Stewart ouverts
+  (théorème \ref{gale-stewart-theorem}) implique donc que soit Alice a
+  une stratégie lui garantissant de tomber dans $A_v$, c'est-à-dire un
+  gain $>v$, et \textit{a fortiori $\geq v$}, soit Bob a une stratégie
+  qui lui garantit de tomber dans le complémentaire de $A_v$,
+  c'est-à-dire garantissant qu'Alice aura un gain $\leq v$.
+
+(b) S'il existait deux réels $v' < v$ tels qu'Alice possède une
+  stratégie lui garantissant un gain $\geq v$ et que Bob possède une
+  stratégie lui garantissant qu'Alice aura un gain $\leq v'$, on
+  aurait une contradiction lorsque ces deux joueurs jouent leurs
+  stratégies respectives.
+\end{corrige}
+
+\smallbreak
+
+(4) Indépendamment de tout ce qui précède, montrer que si $w$ est un
+réel et $I_0$ et $I_1$ deux parties de $\mathbb{R}$ vérifiant (i) si
+$v \in I_0$ et $v' < v$ alors $v' \in I_0$ et de même pour $I_1$, et
+(ii) tout $v < w$ appartient à $I_0 \cup I_1$, alors en fait soit tout
+$v<w$ appartient à $I_0$ soit tout $v<w$ appartient à $I_1$.  (On
+pourra considérer à quel $I_a$ appartient $w - \frac{1}{n}$ et faire
+varier $n$.)
+
+\begin{corrige}
+Pour chaque entier $n>0$, on a $w - \frac{1}{n} \in I_0 \cup I_1$
+d'après (ii), disons donc $w - \frac{1}{n} \in I_{a(n)}$ avec $a(n)
+\in \{0,1\}$.  Soit il existe une infinité de valeurs de $n$ telles
+que $a(n)$ vaille $0$, soit $a(n)$ vaut constamment $1$ à partir d'un
+certain point — et en particulier, il existe une infinité de valeurs
+de $n$ telles que $a(n)$ vaille $1$.  Bref, dans tous les cas, il
+existe $b \in \{0,1\}$ tel que $a(n)$ prenne une infinité de fois la
+valeur $b$, c'est-à-dire $w - \frac{1}{n} \in I_b$ une infinité
+de $n$, autrement dit, pour des $n$ arbitrairement grands.  Mais si
+$v<w$, on peut trouver $n$ plus grand que $1/(w-v)$ tel que $w -
+\frac{1}{n} \in I_b$ d'après ce qu'on vient de dire, or $v <
+w-\frac{1}{n}$, et la propriété (i) montre alors que $v \in I_b$ : on
+a bien montré que tout $v<w$ appartient à $I_b$.
+\end{corrige}
+
+\smallbreak
+
+(5) On suppose désormais que $X = \{0,1\}$ (et toujours que $u$ est
+continue).  Le but de cette question est de montrer (pour $w \in
+\mathbb{R}$) que si Alice possède pour tout $v < w$ une stratégie lui
+garantissant un gain $\geq v$, alors en fait Alice possède une
+stratégie lui garantissant un gain $\geq w$ : autrement dit, si Alice
+peut se garantir n'importe quel gain $v < w$ alors elle peut se
+garantir le gain $w$ lui-même.  Pour abréger, on dira qu'une position
+est « $v$-gagnante [pour Alice] » si Alice possède une stratégie lui
+garantissant un gain $\geq v$ à partir de cette position (on notera
+qu'une position $v$-gagnante est évidemment $v'$-gagnante pour
+tout $v' < v$) ; et on dira qu'une position est « presque $w$-gagnante
+[pour Alice] » si elle est $v$-gagnante pour tout $v < w$.
+
+On cherche donc à montrer, en s'inspirant de la démonstration du
+théorème de Gale-Stewart, que si la position initiale (ou, en fait,
+une position quelconque) est presque $w$-gagnante, alors elle est
+$w$-gagnante.\spaceout (a) Montrer que si une position
+$(z_0,\ldots,z_{i-1})$ où c'est à Alice de jouer est presque
+$w$-gagnante, alors \emph{il existe} $x \in X$ (un coup d'Alice) tel
+que $(z_0,\ldots,z_{i-1},x)$ soit presque $w$-gagnante (on pourra
+utiliser (4)).\spaceout (b) Montrer que si une position
+$(z_0,\ldots,z_{i-1})$ où c'est à Bob de jouer est presque
+$w$-gagnante, alors \emph{pour tout} $x \in X$ (coup de Bob), la
+position $(z_0,\ldots,z_{i-1},x)$ est presque $w$-gagnante.\spaceout
+(c) Montrer que si $\underline{x} \in X^{\mathbb{N}}$ et
+$u(\underline{x}) < w$ alors il existe $\ell$ tel que
+$(x_0,\ldots,x_{\ell-1})$ ne soit pas presque $w$-gagnante.\spaceout
+(d) En déduire (en construisant une stratégie d'Alice qui cherche à
+rester dans des positions presque $w$-gagnantes) que si la position
+initiale est presque $w$-gagnante, alors elle est $w$-gagnante.
+
+\begin{corrige}
+(a) Si $\underline{z} := (z_0,\ldots,z_{i-1})$ est une position où
+  c'est à Alice de jouer qui est presque $w$-gagnante, elle est
+  $v$-gagnante pour tout $v < w$, autrement dit, pour chaque $v < w$,
+  Alice possède une stratégie qui lui garantit un gain $\geq v$.
+  D'après \ref{strategies-forall-exists-reformulation}, cela signifie
+  que pour chaque $v < w$, il existe un coup $x \in X$ d'Alice tel que
+  la position $\underline{z}x = (z_0,\ldots,z_{i-1},x)$ soit
+  $v$-gagnante.  Pour $x \in \{0,1\}$, soit $I_x$ l'ensemble des $v$
+  tels que la position $\underline{z}x = (z_0,\ldots,z_{i-1},x)$ soit
+  $v$-gagnante : la propriété (i) de la question (4) a été observée
+  dans la question, et la propriété (ii) est exactement la phrase
+  précédente.  On déduit de la question (4) qu'il existe $x \in
+  \{0,1\}$ tel que la position $\underline{z}x =
+  (z_0,\ldots,z_{i-1},x)$ soit $v$-gagnante pour tout $v<w$, autrement
+  dit, soit presque $w$-gagnante, ce qu'on voulait montrer.
+
+(b) Si $\underline{z} := (z_0,\ldots,z_{i-1})$ est une position où
+  c'est à Bob de jouer qui est presque $w$-gagnante, elle est
+  $v$-gagnante pour tout $v < w$, autrement dit, pour chaque $v < w$,
+  Alice possède une stratégie qui lui garantit un gain $\geq v$.
+  D'après \ref{strategies-forall-exists-reformulation}, cela signifie
+  que pour chaque $v < w$, et pour chaque coup $x \in X$ de Bob, la
+  position $\underline{z}x = (z_0,\ldots,z_{i-1},x)$ est $v$-gagnante.
+  En permutant les quantificateurs : pour chaque coup $x \in X$ de Bob
+  et pour chaque $v < w$, la position $\underline{z}x$ est
+  $v$-gagnante.  C'est bien dire que pour chaque coup $x\in X$ de Bob,
+  la position $\underline{z}x$ est presque $w$-gagnante, ce qu'on
+  voulait montrer.
+
+(c) Si $u(\underline{x}) < w$, et si $v$ est choisi tel que
+  $u(\underline{x}) < v < w$, alors par continuité de $u$
+  (cf. question (2)), il existe $\ell$ tel que $u$ soit $<v$ sur
+  $V_\ell(\underline{x})$, autrement dit, aucune confrontation qui
+  prolonge $x_0,\ldots,x_{\ell-1}$ ne peut donner un gain $\geq v$ à
+  Alice, et en particulier, la position $x_0,\ldots,x_{\ell-1}$ n'est
+  pas $v$-gagnante, donc elle n'est pas presque $w$-gagnante.
+
+(d) Si $(x_0,\ldots,x_{i-1})$ est une position où c'est à Alice de
+  jouer et qui est presque $w$-gagnante, alors d'après (a) il existe
+  un $x$ tel que $(x_0,\ldots,x_{i-1},x)$ soit presque $w$-gagnante :
+  choisissons-un tel $x$ et posons $\tau((x_0,\ldots,x_{i-1})) := x$ :
+  d'après (b), quel que soit $y \in X$, la position
+  $(x_0,\ldots,x_{i-1},x,y)$ est presque $w$-gagnante (et c'est de
+  nouveau à elle de jouer).  Aux points où $\tau$ n'a pas été défini
+  par ce qui vient d'être dit, on le définit de façon arbitraire.
+
+Si $\underline{x} = (x_0,x_1,x_2,\ldots)$ est une confrontation où
+Alice joue selon $\tau$, on voit par récurrence sur $i$ que chacune
+des positions $(x_0,\ldots,x_{i-1})$ est presque $w$-gagnante si la
+position initiale l'est : pour $i=0$ c'est l'hypothèse faite (à savoir
+que la position initiale est presque $w$-gagnante), pour les positions
+où c'est à Alice de jouer, c'est la construction de $\tau$ qui assure
+la récurrence (cf. (a) ci-dessus), et pour les positions où c'est à
+Bob de jouer, c'est la question (b) qui assure la récurrence.  Mais la
+question (c) assure qu'on a alors $u(\underline{x}) \geq w$.  On a
+donc bien défini une stratégie qui garantit à Alice un gain $\geq w$.
+\end{corrige}
+
+\smallbreak
+
+(6) (On suppose toujours que $X = \{0,1\}$ que $u$ est
+continue.)\spaceout (a) Montrer que si $u$ est bornée, alors la valeur
+du jeu existe, autrement dit, il existe $v$ tel qu'Alice possède une
+stratégie lui garantissant un gain $\geq v$ et que Bob possède une
+stratégie lui garantissant qu'Alice aura un gain $\leq v$.  (On pourra
+considérer la borne supérieure $w$ des $v$ pour lesquels Alice possède
+une stratégie lui garantissant un gain $\geq v$, et appliquer la
+question (5).)\spaceout (b) En considérant une fonction comme
+$\arctan\circ u$ ou $\tanh\circ u$, montrer qu'on peut s'affranchir de
+l'hypothèse « $u$ est bornée ».\spaceout (bonus) Déduire de ce qui
+précède que toute fonction continue $u\colon \{0,1\}^{\mathbb{N}} \to
+\mathbb{R}$ est bornée et atteint ses bornes (on pourra considérer un
+jeu où les coups de Bob sont purement et simplement ignorés).
+
+\begin{corrige}
+(a) Soit $I$ l'ensemble des $v$ pour lesquels Alice possède une
+  stratégie lui garantissant un gain $\geq v$ (i.e., pour lesquels la
+  position initiale est $v$-gagnante, dans la terminologie de (4)).
+  Si $v$ est strictement supérieur à un majorant de $u$ (qui existe
+  car $u$ est supposée bornée), il est évident qu'il est impossible
+  d'obtenir un gain $\geq v$, donc $v$ majore strictement $I$.  Si $v$
+  est strictement inférieur à un minorant de $u$, il est évident qu'il
+  est impossible de \emph{ne pas} obtenir un gain $\geq v$, donc
+  $v\in I$.  Soit $w := \sup I$, qui existe puisque $I$ est non vide
+  et majoré.  Si $v < w$, alors il existe $v' \in I$ tel que $v<v'<w$,
+  ce qui implique que $v \in I$ (puisqu'une stratégie garantissant un
+  gain $\geq v'$ garantit \textit{a fortiori} un gain $\geq v$).  On
+  voit donc qu'Alice a une stratégie lui garantissant un gain $\geq v$
+  pour tout $v < w$.  La question (5) montre alors qu'Alice a une
+  stratégie lui garantissant un gain $\geq w$.  \textit{A contrario},
+  si $v > w$, alors Alice n'a pas de stratégie lui garantissant un
+  gain $\geq v$, donc Bob a une stratégie lui garantissant qu'Alice
+  aura un gain $\leq v$ (d'après la question (3)(a)).  En appliquant
+  l'analogue pour Bob de la question (5) (qui s'en déduit en
+  échangeant les joueurs, c'est-à-dire en changeant $u$ en $-u$), Bob
+  a lui aussi une stratégie lui garantissant qu'Alice aura un
+  gain $\leq w$.  On a bien prouvé que $w$ est la valeur du jeu.
+
+(b) Si $u$ n'est plus supposée bornée, soit $\tilde u = h\circ u$ où
+  $h\colon\mathbb{R}\to\mathbb{R}$ est une fonction continue bornée et
+  strictement croissante (par exemple $\arctan$ ou $\tanh$).  Alors
+  $\tilde u$ est continue et bornée, donc la question précédente
+  montre que le jeu qu'elle définit a une valeur $\tilde w$.  Cette
+  valeur ne peut pas être strictement supérieure à toute valeur de $h$
+  (vu qu'Alice a une stratégie lui garantissant un gain $\geq\tilde
+  w$) ni strictement inférieure à toute valeur de $h$ (vu que Bob a
+  une stratégie lui garantissant qu'Alice aura un gain $\leq\tilde
+  w$).  C'est donc (en utilisant les valeurs intermédiaires) que
+  $\tilde w = h(w)$ pour un certain $w$.  Alors il est clair qu'une
+  stratégie garantissant à Alice un gain $\geq\tilde w$ dans le jeu
+  défini par $\tilde u$ lui garantit un gain $\geq w$ dans le jeu
+  défini par $u$, et de même pour Bob : ceci montre que $w$ est la
+  valeur du jeu défini par $u$.
+
+(bonus) Si $u$ est une fonction continue $\{0,1\}^{\mathbb{N}} \to
+  \mathbb{R}$, en considérant la fonction $\hat u\colon
+  \{0,1\}^{\mathbb{N}} \to \mathbb{R}$ qui ignore les coups joués par
+  Bob et calcule $u$ sur les coups joués par Alice (i.e.,
+  formellement, $\hat u(\underline{x}) = u(\check{\underline{x})}$ où
+  $\check x_i = x_{2i}$), il est clair qu'Alice a une stratégie lui
+  garantissant un gain $\geq v$ si et seulement si $u$ prend une
+  valeur $\geq v$.  Comme on vient de voir qu'il existe un plus grand
+  tel $v$ (la valeur du jeu), cela signifie bien que $u$ est bornée et
+  atteint ses bornes.
+%%
+%% Montrons que $u$ est majorée (la minoration est exactement analogue,
+%% ou s'obtient en remplaçant $u$ par $-u$).  Si ce n'est pas le cas,
+%% pour chaque $n$ entier naturel, on peut choisir un
+%% $\underline{z}_{(n)} \in X^{\mathbb{N}}$ tel que
+%% $u(\underline{z}_{(n)}) \geq n$, et on va aboutir à une contradiction.
+%%
+%% Montrons que la suite $\underline{z}_{(n)}$ possède une valeur
+%% d'adhérence, c'est-à-dire, qu'il existe $\underline{y}$ tel que
+%% $\underline{z}_{(n)}$ passe infiniment souvent dans n'importe quel
+%% voisinage fondamental de $\underline{y}$.  Pour cela, considérons le
+%% premier terme $z_{(n),0}$ de $\underline{z}_{(n)}$ : comme il
+%% appartient à $X = \{0,1\}$, il doit valoir infiniment souvent $0$ ou
+%% infiniment souvent $1$ : appelons $y_0$ une valeur qu'il prend pour
+%% une infinité de $n$.  Parmi l'ensemble des $n$ tels que $z_{(n),0} =
+%% y_0$ (on vient de s'assurer qu'il est infini), le terme $z_{(n),1}$
+%% doit lui aussi valoir infiniment souvent $0$ ou infiniment
+%% souvent $1$ : appelons $y_1$ une valeur qu'il prend pour une infinité
+%% de $n$ (autrement dit, il existe une infinité de $n$ tels que
+%% $z_{(n),0} = y_0$ \emph{et} $z_{(n),1} = y_1$).  On procède ainsi par
+%% récurrence sur $k$ : parmi l'ensemble des $n$ tels que $z_{(n),i} =
+%% y_i$ pour tout $i<k$ (dont on s'est assuré par hypothèse de récurrence
+%% qu'il est infini), le terme $z_{(n),k}$ doit lui aussi valoir
+%% infiniment souvent $0$ ou infiniment souvent $1$ : on appelle $y_k$
+%% une valeur qu'il prend pour une infinité de $n$ (autrement dit, il
+%% existe une infinité de $n$ tels que $z_{(n),i} = y_i$ pour tout $i\leq
+%% k$).  Ceci définit une suite $\underline{y} = (y_0,y_1,y_2,\ldots)$
+%% qui possède la propriété que pour tout $k$ il existe une infinité de
+%% $n$ pour lesquels $z_{(n),i} = y_i$ pour tout $i < k$ : autrement dit,
+%% $\underline{z}_{(n)}$ appartient infiniment souvent au voisinage
+%% fondamental $V_k(\underline{y})$.
+%%
+%% Or la valeur $u(\underline{y})$ est un réel, disons $<N$ pour un
+%% certain entier $N$ : par continuité de $u$ (cf. question (2)), il
+%% existe $k$ tel que $u$ soit $<N$ sur $V_k(\underline{y})$.  Notamment,
+%% si $\underline{z}_{(n)} \in V_k(\underline{y})$ alors $n < N$.  Ceci
+%% contredit le fait qu'une infinité de $\underline{z}_{(n)}$ est censée
+%% appartenir à $V_k(\underline{y})$.
+%%
+%% (De façon plus sophistiquée, on peut aussi écrire : l'espace
+%% topologique $X = \{0,1\}$ est \emph{compact} car discret et fini, donc
+%% $X^{\mathbb{N}}$ est également compact par le théorème de Tychonoff,
+%% et l'image d'un compact par une fonction continue est un compact, donc
+%% en particulier bornée dans $\mathbb{R}$.)
+\end{corrige}
+
+\smallbreak
+
+(7) Soit $u \colon \{0,1\}^{\mathbb{N}} \to \mathbb{R}$ qui à
+$(x_0,x_1,x_2,\ldots)$ associe $\sum_{i=0} x_i 2^{-i}$ (le nombre réel
+dont la représentation binaire est donnée par $0$ virgule la suite
+des $x_i$).  Vérifier que $u$ est continue et calculer la valeur du
+jeu qu'elle définit (quelle est la stratégie optimale pour Alice et
+pour Bob ?).
+
+\begin{corrige}
+(7) La fonction $u$ est continue car si $\varepsilon < 2^{-\ell-1}$
+  alors la valeur $u(\underline{x})$ est définie à $\varepsilon$ près
+  par la donnée des $\ell$ premiers termes de la
+  suite $\underline{x}$.  Il est évident qu'Alice a intérêt à ne jouer
+  que des $1$ (jouer autre chose ne ferait que diminuer son gain) et
+  Bob que des $0$.  La valeur du jeu est donc $u(0,1,0,1,0,1,\ldots) =
+  \frac{1}{2}$.
+\end{corrige}
+
+
 \subsection{Théorie de l'induction bien-fondée}
 
 \subsection{Introduction aux ordinaux}