diff options
Diffstat (limited to 'controle-20210412.tex')
| -rw-r--r-- | controle-20210412.tex | 244 |
1 files changed, 182 insertions, 62 deletions
diff --git a/controle-20210412.tex b/controle-20210412.tex index 110f494..e15403a 100644 --- a/controle-20210412.tex +++ b/controle-20210412.tex @@ -91,6 +91,9 @@ long parce que des rappels ont été faits et que la rédaction des questions cherche à éviter toute ambiguïté ; d'autre part, il ne sera pas nécessaire de tout traiter pour obtenir la totalité des points. +Les remarques en petits caractères ne font pas partie du sujet et +peuvent être ignorées. + \medbreak L'usage de tous les documents (notes de cours manuscrites ou @@ -106,7 +109,7 @@ Barème \emph{indicatif} : chaque question numérotée aura approximativement la même valeur (environ $1$ à $1.5$ points). \ifcorrige -Ce corrigé comporte \textcolor{red}{nnn} pages (page de garde incluse). +Ce corrigé comporte 10 pages (page de garde incluse). \else Cet énoncé comporte 5 pages (page de garde incluse). \fi @@ -146,7 +149,8 @@ On rappelle qu'une \emph{stratégie optimale} est une stratégie mixte qui réalise un gain espéré au moins égal à la valeur du jeu contre toute stratégie (pure donc mixte) de l'adversaire. -(0) Quelle est la valeur du jeu dans ce cas ? +\textbf{(0)} Quelle est la valeur du jeu dans ce cas ? (Ne pas faire de +calcul !) \begin{corrige} On a affaire à un jeu à somme nulle \emph{symétrique} (c'est-à-dire @@ -154,7 +158,7 @@ que sa matrice de gains est antisymétrique), donc la valeur du jeu est nulle. \end{corrige} -(1) À quelle condition sur $x$ la stratégie $\frac{1}{2}\mathrm{P} + +\textbf{(1)} À quelle condition sur $x$ la stratégie $\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$ (consistant à choisir P avec probabilité $\frac{1}{2}$, et chacun de Q et R avec probabilité $\frac{1}{4}$) est-elle optimale ? @@ -179,14 +183,14 @@ l'adversaire, il faut et il suffit donc que $\frac{x-1}{2} \geq 0$, c'est-à-dire $x\geq 1$. \end{corrige} -(2) À quelle condition sur $x$ l'expression $\frac{1}{x+2}\,\mathrm{P} + +\textbf{(2)} À quelle condition sur $x$ l'expression $\frac{1}{x+2}\,\mathrm{P} + \frac{x}{x+2}\,\mathrm{R} + \frac{1}{x+2}\,\mathrm{S}$ (consistant à choisir R avec probabilité $\frac{x}{x+2}$, et chacun de P et S avec probabilité $\frac{1}{x+2}$) définit-elle une stratégie optimale ? \begin{corrige} L'expression $\frac{1}{x+2}\,\mathrm{P} + \frac{x}{x+2}\,\mathrm{R} + -\frac{1}{x+2}\,\mathrm{S}$ définit une stratégie mixte lorsque ses +\frac{1}{x+2}\,\mathrm{S}$ définit une stratégie (mixte) lorsque ses coefficients sont positifs de somme $1$ : le fait qu'ils soient de somme $1$ est toujours vrai, et ils sont tous positifs lorsque $x\geq 0$. @@ -211,7 +215,7 @@ l'adversaire, il faut et il suffit donc que $\frac{2(1-x)}{x+2} \geq 0$, c'est-à-dire $x\leq 1$, donc finalement $0\leq x\leq 1$. \end{corrige} -(3) Donner une stratégie optimale lorsque $x\leq 0$. +\textbf{(3)} Donner une stratégie optimale lorsque $x\leq 0$. \begin{corrige} Lorsque $x\leq 0$, la stratégie pure $\mathrm{S}$ est optimale @@ -219,7 +223,7 @@ puisqu'elle réalise un gain $\geq 0$ contre toute stratégie (pure donc mixte) de l'adversaire. \end{corrige} -(4) Dans chacun des cas $x=0$ et $x=1$, exhiber une infinité de +\textbf{(4)} Dans chacun des deux cas $x=0$ et $x=1$, exhiber une infinité de stratégies optimales distinctes. \begin{corrige} @@ -240,7 +244,7 @@ encore optimale, c'est-à-dire $\frac{2+t}{6}\,\mathrm{P} + \frac{1-t}{3}\,\mathrm{S}$ pour $t\in[0;1]$. \end{corrige} -(5) En supposant que $x$ ne soit pas un réel fixé mais \emph{tiré au +\textbf{(5)} En supposant que $x$ ne soit pas un réel fixé mais \emph{tiré au hasard} selon une loi uniforme entre $0$ et $1$ une fois que les joueurs ont joué (autrement dit, si un joueur choisit P et l'autre S, le joueur qui a choisi P reçoit un gain aléatoire uniforme entre @@ -280,11 +284,12 @@ $\varphi(\alpha) = \omega^\alpha$. On rappelle que $\varphi$ est \emph{strictement croissante} (c'est-à-dire que si $\alpha < \beta$ alors $\varphi(\alpha) < \varphi(\beta)$). -(1) Rappeler pourquoi $\varphi$ est \emph{continue}, ce qui signifie +\textbf{(1)} Rappeler pourquoi $\varphi$ est \emph{continue}, ce qui signifie par définition la chose suivante : si $\delta$ est un ordinal limite, alors $\lim_{\xi\to\delta} \varphi(\xi) = \varphi(\delta)$, où $\lim_{\xi\to\delta} \varphi(\xi)$ est une notation pour -$\sup\{\varphi(\xi) : \xi < \delta\}$. +$\sup\{\varphi(\xi) : \xi < \delta\}$ lorsque $\varphi$ est +croissante. \begin{corrige} La continuité de la fonction $\varphi\colon \alpha \mapsto @@ -295,10 +300,10 @@ l'exponentiation ordinale ($\omega ^ \delta = \lim_{\xi\to\delta} Pour éviter de partir dans des fausses directions, il est conseillé, jusqu'à la question (5) incluse, d'oublier la définition de $\varphi$ -et de retenir simplement que $\varphi$ est strictement croissante et +et de retenir seulement que $\varphi$ est strictement croissante et continue. -(2) Rappeler pourquoi $\varphi(\alpha) \geq \alpha$ pour +\textbf{(2)} Rappeler pourquoi $\varphi(\alpha) \geq \alpha$ pour tout $\alpha$. \begin{corrige} @@ -321,7 +326,7 @@ contradiction.) On dira qu'un ordinal $\gamma$ est un \emph{point fixe} de $\varphi$ lorsque $\varphi(\gamma) = \gamma$. -(3) Soit dans cette question $\alpha$ un ordinal quelconque : +\textbf{(3)} Soit dans cette question $\alpha$ un ordinal quelconque : considérons la suite $(\gamma_n)$ (indicée par les entiers naturels $n$) définie par $\gamma_0 = \alpha$ et $\gamma_{n+1} = \varphi(\gamma_n)$. Montrer que $(\gamma_n)$ est croissante @@ -361,9 +366,11 @@ par : $\sup\{\varepsilon_\xi : \xi < \delta\}$). \end{itemize} -(4) Montrer que $\iota \mapsto \varepsilon_\iota$ est strictement +Cette définition a bien un sens d'après ce qu'on vient de dire. + +\textbf{(4)} Montrer que $\iota \mapsto \varepsilon_\iota$ est strictement croissante. Montrer que $\varepsilon_\delta$ est un point fixe -de $\varphi$ aussi pour $\delta$ limite (c'est vrai pour les autres +de $\varphi$ aussi pour $\delta$ limite (c'est vrai dans les autres cas par la définition) : pour cela, on expliquera pourquoi $\varphi(\lim_{\xi\to\delta} \varepsilon_\xi) = \lim_{\xi\to\delta} \varphi(\varepsilon_\xi)$. @@ -425,7 +432,7 @@ $\varphi(\varepsilon_\delta) = \varphi(\lim_{\xi\to\delta} \lim_{\xi\to\delta} \varepsilon_\xi = \varepsilon_\delta$. \end{corrige} -(5) Montrer que tout ordinal $\gamma$ qui est un point fixe de +\textbf{(5)} Montrer que tout ordinal $\gamma$ qui est un point fixe de $\varphi$ est de la forme $\varepsilon_\alpha$ pour un certain ordinal $\alpha$ (on pourra montrer qu'il existe $\alpha$ tel que $\varepsilon_\alpha\geq\gamma$ puis considérer le plus petit @@ -451,6 +458,20 @@ ces $\varepsilon_\xi$, donc on a $\varepsilon_\alpha \leq \gamma$, et on a bien prouvé $\varepsilon_\alpha = \gamma$. \end{corrige} +{\footnotesize\textit{Remarque.} On a donc démontré que la fonction + $\varphi(1,\tiret) \colon \alpha \mapsto \varepsilon_\alpha$, qui + énumère les points fixes de $\varphi(0,\tiret) = \varphi \colon + \alpha \mapsto \omega^\alpha$ strictement croissante continue, est + elle-même strictement croissante et continue. On pourrait donc + continuer le procédé et appeler $\varphi(2,\tiret)$ la fonction + énumérant les points fixes de $\varphi(1,\tiret)$ (c'est-à-dire que + $\varphi(2,0)$ est le plus petit ordinal $\zeta$ tel que $\zeta = + \varepsilon_\zeta$ puis $\varphi(2,1)$ est le suivant, etc.), « et + ainsi de suite ». Ce procédé de construction d'ordinaux s'appelle + les « fonctions de Veblen » : on peut bien sûr continuer en + définissant $\varphi(1,0,0)$ comme le premier ordinal $\delta$ tel + que $\delta = \varphi(\delta,0)$ et au-delà.\par} + \medskip \underline{Deuxième partie.} @@ -465,11 +486,11 @@ résulte de la première partie de cet exercice). On a vu en cours que les ordinaux $<\varepsilon_0$ possèdent une représentation unique sous forme normale de Cantor itérée, et que celle-ci permet de les comparer, de les ajouter et de les multiplier. -On va se pencher ici sur \emph{deux} systèmes différents d'écriture -des ordinaux $<\varepsilon_1$, qu'on appellera « écriture 1 » et -« écriture 2 ». +On va s'intéresser ici aux ordinaux $<\varepsilon_1$, et leur donner +\emph{deux} systèmes différents d'écriture, qu'on appellera +« écriture 1 » et « écriture 2 ». -(6) Soit $\alpha < \varepsilon_1$ un ordinal différent +\textbf{(6)} Soit $\alpha < \varepsilon_1$ un ordinal différent de $\varepsilon_0$ : montrer que dans sa forme normale de Cantor $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$, tous les exposants $\gamma_i$ sont $<\alpha$ (on pourra utiliser le fait, @@ -501,18 +522,20 @@ $\omega^{\omega^{\varepsilon_0}+1}\,2$ sont des écritures 1. En revanche, $\omega^{\varepsilon_0}$ n'en est pas une (elle ne vérifie pas la contrainte sur les exposants), ni $\varepsilon_0 + 1$ (ce n'est ni le symbole spécial $\varepsilon_0$ ni une forme normale de Cantor), -ni $(\varepsilon_0)^2$. +ni $\varepsilon_0\,2$, ni $(\varepsilon_0)^2$. -(7) Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$ -possède bien une écriture 1 unique. Il est facile de voir que cette -écriture 1 permet algorithmiquement de manipuler les ordinaux +\textbf{(7)} Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$ +possède bien une écriture 1 unique. Il est alors facile de voir que +cette écriture 1 permet algorithmiquement de manipuler les ordinaux $<\varepsilon_1$ : c'est-à-dire de les comparer, de les ajouter et de les multiplier (on ne demande pas de le justifier, les algorithmes étant essentiellement les mêmes que vus en cours pour les ordinaux -$<\varepsilon_0$) : il faut simplement bien se rappeler dans les -calculs intermédiaires le fait que $\varepsilon_0 = -\omega^{\varepsilon_0}$. Notamment calculer $\varepsilon_0\cdot 2$ et -$\varepsilon_0\cdot \omega$ en écriture 1. Expliquer comment calculer +$<\varepsilon_0$ sur la forme normale de Cantor : il faut simplement +bien se rappeler dans les calculs intermédiaires le fait que +$\varepsilon_0 = \omega^{\varepsilon_0}$ pour convertir +$\varepsilon_0$ en forme normale de Cantor dès qu'on en a besoin). +Calculer notamment $\varepsilon_0\cdot 2$ et $\varepsilon_0\cdot +\omega$ en écriture 1. Expliquer ensuite comment calculer $(\varepsilon_0)^\alpha$ en écriture 1 lorsque $\alpha$ est lui-même donné en écriture 1. Notamment, écrire $(\varepsilon_0)^{\omega 2}$ en écriture 1. @@ -521,15 +544,14 @@ en écriture 1. L'existence et l'unicité de l'écriture 1 résulte du (6) : donné un ordinal $<\varepsilon_1$, soit il est égal à $\varepsilon_0$, auquel cas il a une écriture 1 par définition (et celle-ci est bien unique -car on n'autorise pas de forme normale de Cantor comme -$\omega^{\varepsilon_0}$), soit on l'écrit sous forme normale de -Cantor avec des exposants strictement plus petits que lui, cette -représentation est unique, et on peut recommencer le procédé, ce qui -termine au bout d'un nombre fini d'étapes puisqu'on a affaire à des -ordinaux qui décroissent strictement. (Ou, si on préfère, on montre -par induction transfinie sur $\alpha < \varepsilon_1$ que $\alpha$ -possède une écriture 1 unique par le raisonnement qu'on vient de -dire.) +car on n'autorise pas de forme normale de Cantor pour lui), soit on +l'écrit sous forme normale de Cantor avec des exposants strictement +plus petits que lui, cette représentation est unique, et on peut +recommencer le procédé, ce qui termine au bout d'un nombre fini +d'étapes puisqu'on a affaire à des ordinaux qui décroissent +strictement. (Ou, si on préfère, on montre par induction transfinie +sur $\alpha < \varepsilon_1$ que $\alpha$ possède une écriture 1 +unique par le raisonnement qu'on vient de dire.) Calculons $\varepsilon_0\cdot 2$ en écriture 1 : il suffit de réécrire $\varepsilon_0$ comme $\omega^{\varepsilon_0}$, et alors @@ -537,7 +559,7 @@ $\omega^{\varepsilon_0}\cdot 2$ est une écriture 1 légitime (c'est bien une forme normale de Cantor dont les exposants sont tous écrits en écriture 1 et plus petit que l'ordinal donné). De même, calculons $\varepsilon_0\cdot \omega$ : pour cela, on écrit $\varepsilon_0\cdot -\omega = \omega^\varepsilon_0\cdot \omega = \omega^{\varepsilon_0+1} = +\omega = \omega^{\varepsilon_0}\cdot \omega = \omega^{\varepsilon_0+1} = \omega^{\omega^{\varepsilon_0}+1}$, ce qui est une écriture 1 légitime. @@ -552,12 +574,12 @@ laisse $\varepsilon_0$ comme résultat). Calculons $(\varepsilon_0)^{\omega 2}$ en écriture 1 : on vient de voir qu'il vaut $\omega^{\varepsilon_0\,\omega 2}$, or $\varepsilon_0\,\omega 2 = \omega^{\omega^{\varepsilon_0}+1}\,2$ comme -au-dessus, donc $(\varepsilon_0)^{\omega 2} = +ci-dessus, donc $(\varepsilon_0)^{\omega 2} = \omega^{\omega^{\omega^{\varepsilon_0}+1}\,2}$ (avec le parenthésage : $\omega^{((\omega^{((\omega^{\varepsilon_0})+1)})\cdot 2)}$). \end{corrige} -(8) Indépendamment des questions précédentes, rappeler pourquoi tout +\textbf{(8)} Indépendamment des questions précédentes, rappeler pourquoi tout ordinal $\alpha$ possède une écriture unique sous la forme $(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots + (\varepsilon_0)^{\gamma_1}\, \xi_1$ où $\gamma_s > \cdots > \gamma_1$ @@ -569,17 +591,18 @@ Il s'agit de l'écriture en base $\tau$ des ordinaux, dans le cas particulier de $\tau = \varepsilon_0$. \end{corrige} -(9) Indépendamment des questions précédentes, montrer que +\textbf{(9)} Indépendamment des questions précédentes, montrer que $\varepsilon_0 + \varepsilon_1 = \varepsilon_1$ (on rappelle que $\omega^\gamma + \omega^{\gamma'} = \omega^{\gamma'}$ lorsque $\gamma < \gamma'$). En déduire que $\varepsilon_0 \cdot \varepsilon_1 = \varepsilon_1$. En déduire que $(\varepsilon_0)^{\varepsilon_1} = \varepsilon_1$. Réciproquement, montrer que si $\delta$ est un -ordinal tel que $(\varepsilon_0)^{\delta} = \delta$ alors on a aussi -$\omega^\delta = \delta$ (on pourra montrer $\delta \leq \omega^\delta -\leq \omega^{\varepsilon_0 \delta} \leq \delta$) et en déduire que -$\delta \geq \varepsilon_1$. En déduire que $\varepsilon_1$ est le -plus petit ordinal tel que $(\varepsilon_0)^{\delta} = \delta$. +ordinal tel que $(\varepsilon_0)^{\delta} = \delta$ alors il vérifie +aussi $\omega^\delta = \delta$ (on pourra montrer $\delta \leq +\omega^\delta \leq \omega^{\varepsilon_0 \delta} = \delta$) et en +déduire que $\delta \geq \varepsilon_1$. En déduire que +$\varepsilon_1$ est le plus petit ordinal tel que +$(\varepsilon_0)^{\delta} = \delta$. \begin{corrige} On a $\varepsilon_0 + \varepsilon_1 = \omega^{\varepsilon_0} + @@ -600,7 +623,7 @@ $\gamma\mapsto\omega^\gamma$, donc toutes ces inégalités sont des égalités et notamment $\omega^\delta = \delta$. Comme $\varepsilon_1$ est le deuxième point fixe de $\gamma \mapsto \omega^\gamma$, on en déduit que soit $\delta = \varepsilon_0$ soit $\delta \geq -\varepsilon_1$ : le premier est exclu car +\varepsilon_1$ : la première possibilité est exclue car $\varepsilon_0^{\varepsilon_0} > \varepsilon_0$ (par stricte croissance de l'exponentiation ordinale en l'exposant lorsque la base est $\geq 2$), et on a donc $\delta \geq \varepsilon_1$. On a bien @@ -621,10 +644,10 @@ ou bien $\varepsilon_0\,2 + \omega^\omega$ ou encore $(\varepsilon_0)^{\varepsilon_0}\,\omega^\omega\,3$ sont des écritures 2. En revanche, $\omega^{\varepsilon_0+1}$ n'en est pas une (les puissances de $\omega$ ne peuvent apparaître qu'au sein d'une -forme normale de Cantor itérée, donc ne faisant jamais intervenir -$\varepsilon_0$). +forme normale de Cantor itérée, dont l'exposant ne fait donc jamais +intervenir $\varepsilon_0$). -(10) Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$ +\textbf{(10)} Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$ possède bien une écriture 2 unique. Esquisser un algorithme permettant de convertire l'écriture 2 d'un ordinal $<\varepsilon_1$ en écriture 1 (on utilisera la question (7)). @@ -666,19 +689,109 @@ types de têtes (= feuilles de l'arbre) : des têtes normales, et des \emph{œufs} (pouvant donner naissance à de nouvelles hydres). Quand Hercule coupe une tête $x$ normale, l'hydre se reproduit exactement comme on l'a vu en cours, c'est-à-dire qu'elle reproduit autant -d'exemplaires qu'elle le veut de tout le sous-arbre partant du nœud -$y$ parent de $x$ dans l'arbre (ces copies étant ajoutées comme filles -du nœud $z$ parent de $y$), à condition que $y$ ne soit pas la racine -(sinon, l'hydre ne joue pas). En revanche, si Hercule coupe un œuf, -cet œuf est remplacé par une nouvelle hydre, c'est-à-dire par un -sous-arbre, arbitrairement complexe, mais ne comportant pas lui-même -d'œuf. - -(11) En associant à toute position du jeu (= tout arbre enraciné dont +d'exemplaires qu'elle le veut, œufs compris, de tout le sous-arbre +partant du nœud $y$ parent de $x$ dans l'arbre (ces copies étant +ajoutées comme filles du nœud $z$ parent de $y$), à condition que $y$ +ne soit pas la racine (sinon, l'hydre ne joue pas). En revanche, si +Hercule coupe un œuf, cet œuf éclot est remplacé par une nouvelle +hydre, c'est-à-dire par un sous-arbre, arbitrairement complexe (choisi +par le joueur qui contrôle l'hydre), mais ne comportant lui-même pas +d'œuf, qui prend la place de la tête où était situé l'œuf. + +A titre d'exemple, sur le dessin suivant, où les œufs ont été +représentés par des ovales gris, selon la tête coupée par Hercule : +\begin{center} +\begin{tikzpicture}[baseline=0] +\draw[very thin] (-1.5,0) -- (1.5,0); +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node (P0) at (0,0) {}; +\node (P1) at (0,1) {}; +\node (P2) at (0,2) {}; +\node (P3) at (-1,3) {}; +\node (P4) at (1,3) {}; +\end{scope} +\begin{scope}[line width=1.5pt] +\draw (P0) -- (P1); +\draw (P1) -- (P2); +\draw (P2) -- (P3); +\draw (P2) -- (P4); +\fill[fill=gray] (P3) to[out=0,in=270] ($(P3) + (0.3,0.3)$) to[out=90,in=0] ($(P3) + (0,1.0)$) to[out=180,in=90] ($(P3) + (-0.3,0.3)$) to[out=270,in=180] (P3); +\end{scope} +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node at (P3) {}; +\end{scope} +\end{tikzpicture} +peut devenir +\begin{tikzpicture}[baseline=0] +\draw[very thin] (-1.5,0) -- (1.5,0); +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node (P0) at (0,0) {}; +\node (P1) at (0,1) {}; +\node (P2) at (0,2) {}; +\node (P3) at (-1,3) {}; +\node (P4) at (1,3) {}; +\node (P3a) at (-1.5,4) {}; +\node (P3b) at (-1,4) {}; +\node (P3c) at (-0.5,4) {}; +\node (P3aa) at (-1.75,4.5) {}; +\node (P3ab) at (-1.25,4.5) {}; +\end{scope} +\begin{scope}[line width=1.5pt] +\draw (P0) -- (P1); +\draw (P1) -- (P2); +\draw (P2) -- (P3); +\draw (P2) -- (P4); +\draw (P3) -- (P3a); +\draw (P3) -- (P3b); +\draw (P3) -- (P3c); +\draw (P3a) -- (P3aa); +\draw (P3a) -- (P3ab); +\end{scope} +\end{tikzpicture} +ou +\begin{tikzpicture}[baseline=0] +\draw[very thin] (-1.5,0) -- (1.5,0); +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node (P0) at (0,0) {}; +\node (P1) at (0,1) {}; +\node (P2) at (0,2) {}; +\node (P3a) at (-1,3) {}; +\node (P2b) at (0.5,2) {}; +\node (P3b) at (-0.25,3) {}; +\node (P2c) at (1,2) {}; +\node (P3c) at (0.5,3) {}; +\node (P2d) at (1.5,2) {}; +\node (P3d) at (1.25,3) {}; +\end{scope} +\begin{scope}[line width=1.5pt] +\draw (P0) -- (P1); +\draw (P1) -- (P2); +\draw (P1) -- (P2b); +\draw (P1) -- (P2c); +\draw (P1) -- (P2d); +\draw (P2) -- (P3a); +\draw (P2b) -- (P3b); +\draw (P2c) -- (P3c); +\draw (P2d) -- (P3d); +\fill[fill=gray] (P3a) to[out=0,in=270] ($(P3a) + (0.3,0.3)$) to[out=90,in=0] ($(P3a) + (0,1.0)$) to[out=180,in=90] ($(P3a) + (-0.3,0.3)$) to[out=270,in=180] (P3a); +\fill[fill=gray] (P3b) to[out=0,in=270] ($(P3b) + (0.3,0.3)$) to[out=90,in=0] ($(P3b) + (0,1.0)$) to[out=180,in=90] ($(P3b) + (-0.3,0.3)$) to[out=270,in=180] (P3b); +\fill[fill=gray] (P3c) to[out=0,in=270] ($(P3c) + (0.3,0.3)$) to[out=90,in=0] ($(P3c) + (0,1.0)$) to[out=180,in=90] ($(P3c) + (-0.3,0.3)$) to[out=270,in=180] (P3c); +\fill[fill=gray] (P3d) to[out=0,in=270] ($(P3d) + (0.3,0.3)$) to[out=90,in=0] ($(P3d) + (0,1.0)$) to[out=180,in=90] ($(P3d) + (-0.3,0.3)$) to[out=270,in=180] (P3d); +\end{scope} +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node at (P3a) {}; +\node at (P3b) {}; +\node at (P3c) {}; +\node at (P3d) {}; +\end{scope} +\end{tikzpicture} +\end{center} + +\textbf{(11)} En associant à toute position du jeu (= tout arbre enraciné dont certaines feuilles sont qualifiées d'œufs) un ordinal $<\varepsilon_1$, montrer que Hercule gagne toujours, c'est-à-dire qu'il va toujours réduire l'hydre à sa seule racine en -temps fini. +temps fini (quoi qu'il fasse et quoi que fasse l'hydre). \begin{corrige} À toute hydre $T$ on associe un ordinal $o(T) <\varepsilon_1$ par @@ -700,14 +813,14 @@ ce n'est pas surprenant puisque de telles tiges offrent essentiellement les mêmes possibilités à l'hydre.) \end{corrige} -(12) Donner un exemple de position du jeu associé à l'ordinal +\textbf{(12)} Donner un exemple de position du jeu associé à l'ordinal $(\varepsilon_0)^{\varepsilon_0}$ par le système proposé en (11). \begin{corrige} L'hydre suivante (dans laquelle les œufs ont été représentés par des ovales gris) : \begin{center} -\begin{tikzpicture}[baseline=0] +\begin{tikzpicture} \draw[very thin] (-1.5,0) -- (1.5,0); \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node (P0) at (0,0) {}; @@ -736,6 +849,13 @@ a la valeur $\omega^{\omega^{\varepsilon_0\,2}} = (\varepsilon_0)^{\varepsilon_0}$, comme demandé. \end{corrige} +{\footnotesize\textit{Remarque.} Pour rendre ce jeu plus intéressant, + il faudrait sans doute ajouter une règle selon laquelle Hercule ne + peut couper un œuf que s'il ne reste aucune tête non-œuf à couper, + sinon il est assez clair qu'il a intérêt à commencer par éliminer + tous les œufs. Mais cette contrainte, puisqu'elle ne concerne + qu'Hercule n'a aucune influence sur ce qu'on vient de prouver.\par} + % % |