diff options
| -rw-r--r-- | controle-20250626.tex | 279 |
1 files changed, 146 insertions, 133 deletions
diff --git a/controle-20250626.tex b/controle-20250626.tex index 9f4b5ba..6786bed 100644 --- a/controle-20250626.tex +++ b/controle-20250626.tex @@ -153,9 +153,9 @@ Réciproquement, si $p\,\text{Pierre} + q\,\text{Papier} + r\,\text{Ciseaux}$ est une stratégie optimale d'un joueur (avec $p,q,r$ positifs de somme $1$), son gain contre les trois stratégies pures de l'adversaire (à savoir $q-r$ contre Pierre, $r-p$ contre -Papier et $p-q$ contre Ciseaux) doit être positif à chaque fois. On a -donc $q \geq r$ et $r \geq p$ et $p \geq q$, ce qui impose $p=q=r$ -donc ils valent $\frac{1}{3}$. Ceci montre que +Papier et $p-q$ contre Ciseaux) doit être au moins égal à la valeur du +jeu (soit $0$). On a donc $q \geq r$ et $r \geq p$ et $p \geq q$, ce +qui impose $p=q=r$ donc ils valent $\frac{1}{3}$. Ceci montre que $\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} + \frac{1}{3}\text{Ciseaux}$ est la seule stratégie optimale à ce jeu (quel que soit le joueur). @@ -167,12 +167,12 @@ $\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} + \frac{1}{3}\text{Ciseaux}$. \end{corrige} -\smallskip +\medskip -\textbf{(2)} On souhaite maintenant ajouter une nouvelle option au jeu -ci-dessus, c'est-à-dire qu'on considère le jeu en forme normale -(toujours symétrique et à somme nulle) défini par la matrice de -gains : +\textbf{(2)} On souhaite maintenant ajouter une nouvelle option +« Foobar » au jeu ci-dessus, c'est-à-dire qu'on considère le jeu en +forme normale (toujours symétrique et à somme nulle) défini par la +matrice de gains : \begin{center} \begin{tabular}{r|cccc} $\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar\\\hline @@ -212,7 +212,7 @@ Le profil $(M,M)$ est un équilibre de Nash lorsque $0$ est le plus grand nombre de sa colonne et le plus petit de sa ligne, c'est-à-dire exactement lorsque $x+y+z \leq 0$. -\textbf{(b)} Le profile $(\text{Foobar}, \text{Foobar})$ est un +\textbf{(b)} Le profil $(\text{Foobar}, \text{Foobar})$ est un équilibre de Nash lorsque $0$ est le plus grand nombre de sa colonne et le plus petit de sa ligne, c'est-à-dire lorsque $x,y,z$ sont tous positifs. @@ -235,19 +235,19 @@ grand nombre de sa colonne et le plus petit de sa ligne, c'est-à-dire exactement lorsque $x=0$ et $y\geq 1$ et $z\geq -1$. \end{corrige} -\smallskip +\medskip -\textbf{(3)} On reprend maintenant la matrice de gains écrite en (1), -mais cette fois les gains des deux joueurs seront \emph{égaux} au lieu -d'être opposés (ce n'est donc plus un jeu à somme nulle ! les joueurs -sont alliés et non plus adversaires). Le tableau donne la valeur du -gain commun aux deux joueurs. +\textbf{(3)} On change de jeu : on reprend maintenant la matrice de +gains écrite en (1), mais cette fois les gains des deux joueurs seront +\emph{égaux} au lieu d'être opposés (ce n'est donc plus un jeu à somme +nulle ! les joueurs sont alliés et non plus adversaires). Le tableau +donne la valeur du gain commun aux deux joueurs. \textbf{\hphantom{(3)} (a)} Montrer que les équilibres de Nash trouvés en (1) sont encore des équilibres de Nash de ce nouveau jeu.\quad\textbf{(b)} Donner au moins un équilibre de Nash différent de ceux-ci. Commenter brièvement quant à la différence de gain -éventuelle entre ces équilibres de Nash. +éventuelle entre les équilibres de Nash trouvés en (a) et (b). \begin{corrige} \textbf{(a)} En ajoutant une ligne et une colonne pour la stratégie @@ -293,10 +293,10 @@ meilleur possible ici. On considère dans cet exercice le jeu suivant : Alice et Bob ont devant eux des piles de jetons, qui représentent -l'état du jeu. Les piles sont numérotées $0$, $1$, $2$, etc. Chaque -pile contient un certain nombre fini (entier naturel) de jetons. Il -n'y a qu'un nombre fini de piles non vides (c'est-à-dire, ayant un -nombre non-nul de jetons). Pour représenter la position +l'état du jeu (= la position). Chaque pile contient un certain nombre +fini (entier naturel) de jetons. Les piles sont numérotées par des +entiers naturelles, mais il n'y en a qu'un nombre fini qui soient +non-vides (i.e., qui aient $>0$ jetons). Pour représenter la position mathématiquement, on utilisera la liste $(n_0, n_1, n_2, \ldots, n_k)$ où $n_i$ est le nombre de jetons de la pile numérotée $i$, et où ceci signifie implicitement que toutes les piles $\geq k$ sont vides. @@ -304,15 +304,20 @@ signifie implicitement que toutes les piles $\geq k$ sont vides. Un coup d'un joueur consiste à retirer \emph{exactement un} jeton d'une certaine pile $i$, de son choix, et d'ajouter \emph{autant qu'il le souhaite} (y compris $0$) jetons à chacune des piles $j<i$, y -compris plusieurs. Par exemple, à partir de la position $(0,3,2)$ on -peut notamment jouer vers $(42,1000,1)$ ou bien vers $(0,2,2)$. +compris ajouter des nombres différents à des piles différentes. Par +exemple, à partir de la position $(0,3,2)$ on peut notamment jouer +vers $(42,1000,1)$ ou bien vers $(0,2,2)$ ou encore vers +$(696\,729\,600,2,2)$. Comme d'habitude, le joueur qui ne peut pas jouer a perdu, c'est-à-dire que celui qui prend le dernier jeton a gagné. +\medskip + \textbf{(1)} Montrer que le jeu qu'on vient de définir termine -forcément en temps fini, quelle que soit la position initiale. (On -justifiera soigneusement.) +forcément en temps fini, quelle que soit la position initiale et quels +que soient les coups effectués par les joueurs. (On justifiera +soigneusement.) \begin{corrige} On associe à la position $(n_0,\ldots,n_k)$ l'ordinal $\omega^k\cdot @@ -328,14 +333,13 @@ associer a diminué strictement. Comme toute suite strictement décroissante d'ordinaux est finie, le jeu termine en temps fini, \end{corrige} -\smallskip - -Appelons « position totalement paire » une position dans laquelle le -nombre $n_i$ de jetons de chaque pile est pair. +\textbf{Définition :} Appelons « position totalement paire » une +position dans laquelle le nombre $n_i$ de jetons de chaque pile est +pair, et « position non totalement paire » une position dans laquelle +au moins un des $n_i$ est impair. \textbf{(2)} Montrer que tout coup joué depuis une position totalement -paire conduit nécessairement à une position qui n'est pas totalement -paire. +paire conduit nécessairement à une position non totalement paire. \begin{corrige} On a retiré un jeton d'une certaine pile $i$, donc si le nombre de @@ -343,19 +347,18 @@ jetons était pair avant le coup, il est devenu impair, et la position n'est plus totalement paire. \end{corrige} -\textbf{(3)} Montrer que depuis toute position qui n'est pas -totalement paire il existe au moins un coup conduisant à une position -totalement paire. +\textbf{(3)} Montrer que depuis toute position non totalement paire il +existe au moins un coup conduisant à une position totalement paire. \begin{corrige} -Si $(n_0,\ldots,n_k)$ est une position qui n'est pas totalement paire, -il existe un $n_i$ impair : soit $i$ le plus grand possible tel que -$n_i$ soit impair (tous les $n_j$ avec $j>i$ sont donc pairs). Le -coup consistant à retirer un jeton de la pile $i$ (qui passe donc à -$n_i-1$ jetons, lequel nombre est pair) et à en ajouter un à toutes -les piles $j<i$ telles que $n_j$ soit impair (qui passent donc à -$n_j+1$ jetons, lequel nombre est pair) est légal selon les règles du -jeu, et conduit à une position totalement paire. +Si $(n_0,\ldots,n_k)$ est une position non totalement paire, il existe +un $n_i$ impair : soit $i$ le plus grand possible tel que $n_i$ soit +impair (tous les $n_j$ avec $j>i$ sont donc pairs). Le coup +consistant à retirer un jeton de la pile $i$ (qui passe donc à $n_i-1$ +jetons, lequel nombre est pair) et à en ajouter un à toutes les piles +$j<i$ telles que $n_j$ soit impair (qui passent donc à $n_j+1$ jetons, +lequel nombre est pair) est légal selon les règles du jeu, et conduit +à une position totalement paire. \end{corrige} \textbf{(4)} En déduire quelles sont les positions du jeu dans @@ -368,32 +371,32 @@ Considérons la stratégie $\sigma$ consistant à jouer vers une position totalement paire si on est dans une position qui ne l'est pas (c'est possible par la question (3)) et à retirer un jeton quelconque sinon (et bien sûr, à capituler s'il n'y a plus de jeton). Le joueur qui -applique cette stratégie $\sigma$ depuis une position qui n'est pas -totalement paire va gagner : chacun de ces coups mènera à une position -totalement paire et son adversaire va forcément en sortir au coup -suivant, donc (par une récurrence immédiate) le joueur dont on parle -sera toujours face à une position qui n'est pas totalement paire, et -gagnera car le jeu ne peut pas durer indéfiniment longtemps -(question (1)). Ceci montre que les positions qui ne sont pas -totalement paires sont gagnantes pour le premier joueur (ce sont des -positions $N$) et que celles qui sont totalement paires sont gagnantes -pour le second joueur (ce sont des positions $P$). +applique cette stratégie $\sigma$ depuis une position non totalement +paire va gagner : chacun de ces coups mènera à une position totalement +paire et son adversaire va forcément en sortir au coup suivant, donc +(par une récurrence immédiate) le joueur dont on parle sera toujours +face à une position non totalement paire, et gagnera car le jeu ne +peut pas durer indéfiniment longtemps (question (1)). Ceci montre que +les positions qui ne sont pas totalement paires sont gagnantes pour le +premier joueur (ce sont des positions N) et que celles qui sont +totalement paires sont gagnantes pour le second joueur (ce sont des +positions P). Si on préfère, on peut aussi rédiger ainsi : on a vu au (1) que le graphe des positions du jeu est bien-fondé. On peut donc montrer par -induction bien-fondée sur la position $x$ que $x$ est une position $P$ +induction bien-fondée sur la position $x$ que $x$ est une position P si et seulement si elle est totalement paire. Si $x$ est totalement paire, aucun de ses voisins sortants n'est totalement pair -d'après (2), donc ils sont tous $N$ par l'hypothèse d'induction, donc -$x$ est $P$ ; et réciproquement, si $x$ est $P$, tous ses voisins sont -$N$, donc par hypothèse d'induction aucun n'est totalement pair, donc -$x$ n'est pas totalement pair par (la contraposée de) la question (3). +d'après (2), donc ils sont tous N par l'hypothèse d'induction, donc +$x$ est P ; et réciproquement, si $x$ est P, tous ses voisins sont N, +donc par hypothèse d'induction aucun n'est totalement pair, donc $x$ +n'est pas totalement pair par (la contraposée de) la question (3). Ceci conclut l'induction. \end{corrige} \textbf{(5)} Calculer, en fonction de $n$, la valeur de Grundy de la position $(n)$ (c'est-à-dire s'il n'y a que la pile numérotée $0$, et -qu'elle comporte $n$ jetons). +que celle-ci comporte $n$ jetons). \begin{corrige} On a $\gr((0)) = 0$ car c'est un puits, et $\gr((1)) = \mex\{0\} = 1$ @@ -478,24 +481,27 @@ qu'il donne la valeur de Grundy.) \end{corrige} \textbf{(10)} Démontrer cette formule. (Cette question est plus -difficile, et il peut être opportun de la garder pour la fin.) +difficile, et il peut être opportun de la garder pour la fin. On +pourra s'inspirer de la démonstration faite en cours du calcul de la +valeur de Grundy pour le jeu de nim.) \begin{corrige} On va montrer par induction transfinie sur l'ordinal $\omega^k\cdot n_k + \cdots + \omega\cdot n_1 + n_0$ associé à la position $(n_0,n_1,\ldots,n_k)$ (ou, ce qui revient essentiellement au même, par induction bien-fondée sur la position elle-même) que la formule -ci-dessus est valable. Comme $\gr((n_0,n_1,\ldots,n_k))$ est -le $\mex$ de l'ensemble $S$ des $\gr((n'_0,n'_1,\ldots,n'_k))$ où -$(n'_0,n'_1,\ldots,n'_k)$ parcourt tous les voisins sortants de -$(n_0,n_1,\ldots,n_k)$, pour montrer que $\gr((n_0,n_1,\ldots,n_k)) = -2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$, il s'agit de -vérifier (A) que $2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$ -n'est pas dans $S$ et (B) que tout nombre $r < 2^k\,(n_k\%2) + \cdots -+ 2\,(n_1\%2) + (n_0\%2)$ est dans $S$. Or par hypothèse d'induction, -les éléments de $S$ sont les $2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + -(n'_0\%2)$ avec $(n'_0,n'_1,\ldots,n'_k)$ voisin sortant de -$(n_0,n_1,\ldots,n_k)$. +ci-dessus est valable. + +Comme $\gr((n_0,n_1,\ldots,n_k))$ est le $\mex$ de l'ensemble $S$ des +$\gr((n'_0,n'_1,\ldots,n'_k))$ où $(n'_0,n'_1,\ldots,n'_k)$ parcourt +tous les voisins sortants de $(n_0,n_1,\ldots,n_k)$, pour montrer que +$\gr((n_0,n_1,\ldots,n_k)) = 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + +(n_0\%2)$, il s'agit de vérifier (A) que $2^k\,(n_k\%2) + \cdots + +2\,(n_1\%2) + (n_0\%2)$ n'est pas dans $S$ et (B) que tout nombre $r < +2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$ est dans $S$. Or par +hypothèse d'induction, les éléments de $S$ sont les $2^k\,(n'_k\%2) + +\cdots + 2\,(n'_1\%2) + (n'_0\%2)$ avec $(n'_0,n'_1,\ldots,n'_k)$ +voisin sortant de $(n_0,n_1,\ldots,n_k)$. Montrons (A) : on sait qu'un des $n'_i$ vaut $n_i-1$. Ceci assure que $(n'_i\%2) \neq (n_i\%2)$, donc par unicité des écritures binaires, @@ -506,23 +512,23 @@ diffère). Ceci conclut le (A). Montrons (B) : si $r < 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$, appelons $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$ son écriture binaire, où $b_j \in \{0,1\}$. Soit $i$ le plus grand -possible tel que $b_i \neq (n_i\%2)$ : donc forcément $b_i = -((n_i-1)\%2)$. (On prendra note du fait que $b_j = (n_j\%2)$ si $j>i$ -par maximalité de $i$.) Définissons les $n'_j$ comme suit : on pose -$n'_j = n_j$ si $j>i$, et $n'_i = n_i-1$, et enfin, pour $j<i$, on -pose $n'_j = n_j + ((n_j+b_j)\%2)$. Par construction (comme $n'_j = -n_j$ si $j>i$ et $n'_i = n_i$ et $n'_j \geq n_j$ si $j\leq i$), le +possible tel que $b_i \neq (n_i\%2)$ : alors $b_i = ((n_i-1)\%2)$. +(On prendra aussi note du fait que $b_j = (n_j\%2)$ si $j>i$ par +maximalité de $i$.) Définissons les $n'_j$ comme suit : on pose $n'_j += n_j$ si $j>i$, et $n'_i = n_i-1$, et enfin, pour $j<i$, on pose +$n'_j = n_j + ((n_j+b_j)\%2)$. Par construction (comme $n'_j = n_j$ +si $j>i$ et $n'_i = n_i$ et $n'_j \geq n_j$ si $j\leq i$), le $(n'_0,n'_1,\ldots,n'_k)$ qu'on vient de définir est bien un voisin sortant de $(n_0,n_1,\ldots,n_k)$. Par ailleurs, $(n'_j\%2) = b_j$ : en effet, pour $j>i$ cela résulte de $b_j = (n_j\%2)$ et $n'_j = n_j$ ; pour $j=i$ cela résulte de $b_i = ((n_i-1)\%2)$ et $n'_i = n_i-1$ ; et pour $j<i$ cela résulte du fait que $n'_j = n_j + ((n_j+b_j)\%2)$ est congru à $n_j + n_j + b_j$ donc à $b_j$ -modulo $2$. En comparant insérant la formule $(n'_j\%2) = b_j$ qu'on -vient de montrer dans $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$, on voit -que $r = 2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + (n'_0\%2)$. qui est -donc dans $S$. Ceci conclut le (B), donc l'induction et l'ensemble de -la démonstration. +modulo $2$. En insérant la formule $b_j = (n'_j\%2)$ qu'on vient de +montrer dans $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$, on voit que $r = +2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + (n'_0\%2)$. qui est donc +dans $S$. Ceci conclut le (B), l'induction, et l'ensemble de la +démonstration. \end{corrige} @@ -539,8 +545,9 @@ On se propose dans cet exercice de montrer qu'il existe une partie $A joueurs n'ait de stratégie gagnante). (La démonstration a été découpées en questions admettant des réponses -courtes, parfois d'une seule ligne. Aucune ne demande de raisonnement -très compliqué.) +courtes, parfois d'une seule ligne.) + +\medskip \textbf{(1)} Montrer qu'il existe une bijection $h_{\mathrm{A}}$ (resp. $h_{\mathrm{B}}$) entre $\{0,1\}^{\mathbb{N}}$ et l'ensemble @@ -614,40 +621,43 @@ l'existence d'une telle bijection —, donc il en existe un plus petit.) gothique (cet ordinal s'appelle le « cardinal du continu ») ; si on ne veut pas écrire de ‘c’ gothique on pourra, par exemple, faire un ‘c’ souligné.} $\mathfrak{c}$ l'ordinal dont on vient de justifier -l'existence (i.e., le plus petit $\gamma$ tel qu'on puisse écrire +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$). +fonction $\xi \mapsto u_\xi$, qu'on fixe dans la suite. \textbf{(4)} \textbf{(a)} 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 $x$ de $\{0,1\}^{\mathbb{N}}$ différent de tous les $v_\xi$.\quad\textbf{(b)} Si $w$ est encore un élément de -$\{0,1\}^{\mathbb{N}}$, expliquer pourquoi on peut aussi trouver $x$ -différent de $w$. +$\{0,1\}^{\mathbb{N}}$, expliquer pourquoi on peut trouver $x$ qui +soit différent de $w$ (et toujours différent des $v_\xi$). \begin{corrige} \textbf{(a)} En une ligne : $\xi \mapsto v_\xi$ n'est pas surjective par minimalité de $\mathfrak{c}$. \textbf{(b)} Si $\alpha$ est fini, il est évident qu'on peut trouver -$x$ différent de tous les $v_\xi$ et de $w$ (qui sont en nombre fini). -Si $\alpha$ est infini, alors $\alpha = 1 + \alpha$ donc on n'a qu'à -poser $v'_0 = w$ et $v'_{1+\xi} = v_\xi$ pour tout $\xi < \alpha$, et -appliquer (a). +$x$ différent de tous les $v_\xi$ et de $w$ (qui sont en nombre fini), +parce que $\{0,1\}^{\mathbb{N}}$ est infini. Si $\alpha$ est infini, +alors $\alpha = 1 + \alpha$ donc on n'a qu'à poser $v'_0 = w$ et +$v'_{1+\xi} = v_\xi$ pour tout $\xi < \alpha$, et appliquer (a), vu +que $\{v'_\xi : \xi<\alpha\} = \{v_\xi : \xi<\alpha\} \cup \{w\}$. \end{corrige} \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$). -Symétriquement, si $\tau$ est une stratégie de Bob et $z \in -\{0,1\}^{\mathbb{N}}$, on définit $z \ast \tau$ comme la confrontation -dans laquelle Alice joue les termes de la suite $z$ et Bob joue -selon $\tau$. +Alice ; i.e.,\footnote{Pour enlever le moindre doute : $\sigma \ast y$ +est la suite $(t_n)_{n\in\mathbb{N}}$ définie par récurrence par : +$t_{2m} = \sigma((t_0,\ldots,t_{2m-1}))$ et $t_{2m+1} = y_m$.} $\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$). Symétriquement, si $\tau$ est une +stratégie de Bob et $z \in \{0,1\}^{\mathbb{N}}$, on définit $z \ast +\tau$ comme la confrontation dans laquelle Alice joue les termes de la +suite $z$ et Bob joue selon $\tau$. \textbf{(5)} Si $\sigma$ est une stratégie d'Alice, expliquer en une ligne pourquoi la fonction $y \mapsto \sigma \ast y$ (de @@ -663,20 +673,22 @@ suite de ses termes impairs.) \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)(a) et (5) pourquoi il existe $y \in \{0,1\}^{\mathbb{N}}$ tel que -$\sigma \ast y$ soit différent de tous les $a_\xi$. +(4)(a) et (5) qu'il existe $y \in \{0,1\}^{\mathbb{N}}$ tel que +$\sigma \ast y$ soit différent de tous les $a_\xi$ pour $\xi<\alpha$. \begin{corrige} Pour chaque $\xi < \alpha$, si $a_\xi$ est de la forme $\sigma \ast v$, appelons $v_\xi$ le $v$ en question (qui est unique d'après (5)), et sinon, soit $v_\xi$ quelconque (par exemple la suite nulle). (Ou, si on préfère, on peut appeler $v_\xi$ la suite des termes impairs -de $a_\xi$.) D'après (4)(a), il existe $y \in \{0,1\}^{\mathbb{N}}$ -qui est différent de tous les $v_\xi$ pour $\xi < \alpha$. Alors -$\sigma \ast y$ ne peut pas être égal à $a_\xi$, car si c'était le -cas, c'est-à-dire $a_\xi = \sigma \ast y$, on aurait $\sigma \ast -v_\xi = \sigma \ast y$, donc $v_\xi = y$ par (5), contredisant la -définition de $y$. +de $a_\xi$ dans tous les cas.) + +D'après (4)(a), il existe $y \in \{0,1\}^{\mathbb{N}}$ qui est +différent de tous les $v_\xi$ pour $\xi < \alpha$. Alors $\sigma \ast +y$ ne peut pas être égal à $a_\xi$, car si c'était le cas, +c'est-à-dire $a_\xi = \sigma \ast y$, on aurait $\sigma \ast v_\xi = +\sigma \ast y$, donc $v_\xi = y$ par (5), contredisant la définition +de $y$. \end{corrige} \textbf{Supposition :} Dans les questions (7) à (9), on suppose que @@ -688,31 +700,31 @@ 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 en une -ligne 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$. -Expliquer pourquoi il existe $a_\alpha$ aussi 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$ pour $\xi<\alpha$ mais aussi du -$b_\alpha$ qu'on vient de trouver. +ligne des questions précédentes qu'il existe $b'$ qui soit de la forme +$\sigma_\alpha \ast y$ (pour un certain $y \in \{0,1\}^{\mathbb{N}}$), +mais différent de tous les $a_\xi$ pour $\xi<\alpha$. Expliquer aussi +pourquoi il existe $a'$ 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$ pour $\xi<\alpha$ et également différent du $b'$ qu'on +vient de trouver. \begin{corrige} -On pose $b_\alpha = \sigma_\alpha \ast y$, où l'existence de $y$ a été +On pose $b' = \sigma_\alpha \ast y$, où l'existence de $y$ a été prouvée en (6) (pour $\sigma = \sigma_\alpha$). -La construction de $a_\alpha$ est symétrique, il n'y a qu'à remarquer -que $z \mapsto z \ast \tau$ est injective, car si $z \ast \tau = z' -\ast \tau$, ils ont les mêmes termes pairs, donc $z = z'$, tout le -reste est presque pareil. La seule chose qui diffère est qu'on a un -élément de plus à éviter ($b_\alpha$), mais la question (4)(b) donne -justement ce point +La construction de $a'$ est symétrique, il n'y a qu'à remarquer que $z +\mapsto z \ast \tau$ est injective, car si $z \ast \tau = z' \ast +\tau$, ils ont les mêmes termes pairs, donc $z = z'$, tout le reste +est presque pareil. La seule chose qui diffère est qu'on a un élément +de plus à éviter ($b_\alpha$), mais la question (4)(b) donne justement +ce point \end{corrige} 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$ en fonction de tous -les autres paramètres. +\emph{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'$ et $b'$ en fonction de tous les autres +paramètres. \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 : @@ -720,19 +732,20 @@ les autres paramètres. \item aucun des $a_\xi$ n'est égal à aucun des $b_\zeta$ (i.e., pour tous $\xi<\mathfrak{c}$ et tout $\zeta<\mathfrak{c}$, on a $a_\xi \neq 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}}$. +\item pour tout $\xi < \mathfrak{c}$, il existe $y \in + \{0,1\}^{\mathbb{N}}$ tel que $b_\xi = \sigma_\xi \ast y$, +\item pour tout $\xi < \mathfrak{c}$, il existe $z \in + \{0,1\}^{\mathbb{N}}$ tel que $a_\xi = z \ast \tau_\xi$. \end{itemize} -(C'est tout ce qu'on aura besoin de savoir pour la suite.) +(C'est tout ce qu'on aura besoin de savoir pour les questions +suivantes.) \begin{corrige} On définit $(a_\xi)_{\xi < \mathfrak{c}}$ et $(b_\xi)_{\xi < \mathfrak{c}}$ par induction transfinie sur $\xi$ : si $(a_\xi)_{\xi - < \alpha}$ et $(b_\xi)_{\xi < \alpha}$ ont déjà été définis, alors -on choisit $a_\alpha$ et $b_\alpha$ comme l'existence a été montrée -en (7). + < \alpha}$ et $(b_\xi)_{\xi < \alpha}$ ont déjà été définis, pour +$\alpha < \mathfrak{c}$, alors on choisit $a_\alpha$ et $b_\alpha$ +comme l'existence a été montrée en (7). Pour vérifier le premier point, on distingue les cas $\xi < \zeta$ et $\zeta \leq \xi$. Dans le premier cas, la définition même de @@ -752,7 +765,7 @@ en (8). \textbf{(9)} Montrer que, quel que soit $\xi$, la stratégie $\tau_\xi$ n'est pas gagnante pour Bob au jeu $G(A)$. Montrer que la stratégie $\sigma_\xi$ n'est pas gagnante pour Alice à ce même jeu (attention, -ce n'est pas exactement symétrique vu que $A$ est l'ensemble +ce n'est pas complètement symétrique vu que $A$ est l'ensemble des $a_\alpha$). \begin{corrige} @@ -793,7 +806,7 @@ stratégie gagnante à ce jeu. \end{corrige} \textbf{(11)} Pourquoi ceci ne contredit pas les résultats vu en -cours ? +cours ? Que dire de la partie $A$ ? \begin{corrige} Les résultats du cours concernent les parties ouvertes, fermées, ou |