diff options
Diffstat (limited to 'controle-20210412.tex')
| -rw-r--r-- | controle-20210412.tex | 887 |
1 files changed, 887 insertions, 0 deletions
diff --git a/controle-20210412.tex b/controle-20210412.tex new file mode 100644 index 0000000..8440d92 --- /dev/null +++ b/controle-20210412.tex @@ -0,0 +1,887 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{matrix,calc} +\usepackage{hyperref} +% +%\externaldocument{notes-mitro206}[notes-mitro206.pdf] +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\newcommand{\outnb}{\operatorname{outnb}} +\newcommand{\downstr}{\operatorname{downstr}} +\newcommand{\precs}{\operatorname{precs}} +\newcommand{\mex}{\operatorname{mex}} +\newcommand{\id}{\operatorname{id}} +\newcommand{\limp}{\Longrightarrow} +\newcommand{\gr}{\operatorname{gr}} +\newcommand{\rk}{\operatorname{rk}} +\newcommand{\fuzzy}{\mathrel{\|}} +% +\DeclareUnicodeCharacter{00A0}{~} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% +\begin{document} +\ifcorrige +\title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} +\else +\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} +\fi +\author{} +\date{12 avril 2021} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +La longueur du sujet ne doit pas effrayer : d'une part, l'énoncé est +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 +imprimées, feuilles d'exercices, livres) est autorisé. + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 2h + +Barème \emph{indicatif} : chaque question numérotée aura +approximativement la même valeur (environ $1$ à $1.5$ points). + +\ifcorrige +Ce corrigé comporte 10 pages (page de garde incluse). +\else +Cet énoncé comporte 5 pages (page de garde incluse). +\fi + +\vfill +{\noindent\tiny +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +On considère le jeu en forme normale, à deux joueurs, à somme nulle, +dont la matrice de gains est la suivante, où $x$ est un réel (la table +donne les gains d'Alice, qui choisit la ligne, ceux de Bob, qui +choisit la colonne, sont opposés) : + +\begin{center} +\begin{tabular}{r|rrrr} +$\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline +$\mathrm{P}$&$0$&$1$&$-1$&$x$\\ +$\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\ +$\mathrm{R}$&$1$&$-2$&$0$&$-1$\\ +$\mathrm{S}$&$-x$&$1$&$1$&$0$\\ +\end{tabular} +\end{center} + +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. + +\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 +que sa matrice de gains est antisymétrique), donc la valeur du jeu est +nulle. +\end{corrige} + +\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 ? + +\begin{corrige} +Ajoutons à la matrice des gains du jeu une ligne correspondant à la +stratégie considérée : +\begin{center} +\begin{tabular}{r|rrrr} +$\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline +$\mathrm{P}$&$0$&$1$&$-1$&$x$\\ +$\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\ +$\mathrm{R}$&$1$&$-2$&$0$&$-1$\\ +$\mathrm{S}$&$-x$&$1$&$1$&$0$\\\hline +\hbox{\vrule height12pt depth5pt width0pt}$\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$& +$0$&$0$&$0$&$\frac{x-1}{2}$\\ +\end{tabular} +\end{center} +Pour qu'elle réalise un gain au moins égal à la valeur du jeu, +c'est-à-dire $\geq 0$, contre toute stratégie (pure donc mixte) de +l'adversaire, il faut et il suffit donc que $\frac{x-1}{2} \geq 0$, +c'est-à-dire $x\geq 1$. +\end{corrige} + +\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 +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$. + +Ajoutons à la matrice des gains du jeu une ligne correspondant à la +stratégie en question : +\begin{center} +\begin{tabular}{r|rrrr} +$\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline +$\mathrm{P}$&$0$&$1$&$-1$&$x$\\ +$\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\ +$\mathrm{R}$&$1$&$-2$&$0$&$-1$\\ +$\mathrm{S}$&$-x$&$1$&$1$&$0$\\\hline +\hbox{\vrule height12pt depth5pt width0pt}$\frac{1}{x+2}\,\mathrm{P} + +\frac{x}{x+2}\,\mathrm{R} + \frac{1}{x+2}\,\mathrm{S}$& +$0$&$\frac{2(1-x)}{x+2}$&$0$&$0$\\ +\end{tabular} +\end{center} +Pour qu'elle réalise un gain au moins égal à la valeur du jeu, +c'est-à-dire $\geq 0$, contre toute stratégie (pure donc mixte) de +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} + +\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 +puisqu'elle réalise un gain $\geq 0$ contre toute stratégie (pure donc +mixte) de l'adversaire. +\end{corrige} + +\textbf{(4)} Dans chacun des deux cas $x=0$ et $x=1$, exhiber une infinité de +stratégies optimales distinctes. + +\begin{corrige} +Lorsque $x = 0$, on a trouvé deux stratégies optimales, à savoir +$\frac{1}{2}\mathrm{P} + \frac{1}{2}\mathrm{S}$ (trouvée en (2)) et +$\mathrm{S}$ (trouvée en (3)). Toute combinaison convexe de ces deux +stratégies optimales est donc encore optimale, c'est-à-dire +$\frac{t}{2}\,\mathrm{P} + \frac{2-t}{2}\,\mathrm{S}$ +pour $t\in[0;1]$. + +Lorsque $x = 1$, on a trouvé deux stratégies optimales, à savoir +$\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + +\frac{1}{4}\mathrm{R}$ (trouvée en (1)) et $\frac{1}{3}\mathrm{P} + +\frac{1}{3}\mathrm{R} + \frac{1}{3}\mathrm{S}$ (trouvée en (2)). +Toute combinaison convexe de ces deux stratégies optimales est donc +encore optimale, c'est-à-dire $\frac{2+t}{6}\,\mathrm{P} + +\frac{t}{4}\,\mathrm{Q} + \frac{4-t}{12}\,\mathrm{R} + +\frac{1-t}{3}\,\mathrm{S}$ pour $t\in[0;1]$. +\end{corrige} + +\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 +$0$ et $1$ ; cet aléa est, évidemment, indépendant de tous ceux que +les joueurs auraient pu utiliser dans la détermination de leur propre +stratégie !), quelle stratégie adopteriez-vous dans ce jeu ? + +\begin{corrige} +On cherche à maximiser le gain \emph{espéré} minimal contre toute +stratégie de l'adversaire ; mais comme $x$ est indépendant des choix +qu'ont pu faire les joueurs, on peut le remplacer par son espérance, +c'est-à-dire que le jeu considéré revient à prendre $x = \frac{1}{2}$. +D'après la question (2), une stratégie optimale est donnée par +$\frac{2}{5}\mathrm{P} + \frac{1}{5}\mathrm{R} + +\frac{2}{5}\,\mathrm{S}$. +\end{corrige} + + +% +% +% + +\exercice + +Dans cet exercice, on va d'abord définir les ordinaux +$\varepsilon_\iota$, puis on va s'intéresser à ceux qui +sont $<\varepsilon_1$. Les parties de cet exercice sont indépendantes +à l'exception de ce qui est explicitement rappelé. + +\medskip + +\underline{Première partie.} + +\nobreak +On définit une fonction $\varphi$ des ordinaux vers les ordinaux par +$\varphi(\alpha) = \omega^\alpha$. On rappelle que $\varphi$ est +\emph{strictement croissante} (c'est-à-dire que si $\alpha < \beta$ +alors $\varphi(\alpha) < \varphi(\beta)$). + +\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\}$ lorsque $\varphi$ est +croissante. + +\begin{corrige} +La continuité de la fonction $\varphi\colon \alpha \mapsto +\omega^\alpha$ fait partie de la définition inductive de +l'exponentiation ordinale ($\omega ^ \delta = \lim_{\xi\to\delta} +\omega^\xi$ si $\delta$ est limite). +\end{corrige} + +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 seulement que $\varphi$ est strictement croissante et +continue. + +\textbf{(2)} Rappeler pourquoi $\varphi(\alpha) \geq \alpha$ pour +tout $\alpha$. + +\begin{corrige} +On a vu en cours que si $\varphi$ est une fonction strictement +croissante d'un ensemble bien-ordonné vers lui-même, alors $\varphi(x) +\geq x$ pour tout $x$ : il suffit d'appliquer ce résultat à la +fonction $\varphi$. (Pour être tout à fait exact, on veut plutôt +appliquer la \emph{démonstration} de ce résultat, vu que le résultat +ne s'applique pas tel quel faute d'un ensemble bien-ordonné auquel +l'appliquer vu que les ordinaux ne constituent pas un ensemble ; mais +la démonstration s'applique exactement sans changement : on montre $x +\leq \varphi(x)$ par induction, en effet, si par l'absurde on avait +$\varphi(x) < x$, alors l'hypothèse d'induction appliquée à $y := +\varphi(x)$ donnerait $\varphi(x) \leq \varphi(\varphi(x))$, tandis +que la stricte croissance de $\varphi$ appliquée à $\varphi(x) < x$ +donnerait $\varphi(\varphi(x)) < \varphi(x)$, ce qui est une +contradiction.) +\end{corrige} + +On dira qu'un ordinal $\gamma$ est un \emph{point fixe} de $\varphi$ +lorsque $\varphi(\gamma) = \gamma$. + +\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 +(c'est-à-dire que $m\leq n$ implique $\gamma_m \leq \gamma_n$). +Montrer que sa limite $\gamma_\omega := \lim_{n\to\omega} \gamma_n := +\sup\{\gamma_n : n \in \mathbb{N}\}$ est un point fixe de $\varphi$. +Montrer qu'il s'agit du plus petit point fixe de $\varphi$ qui +soit $\geq\alpha$ (c'est-à-dire que si $\delta$ est un point fixe +de $\varphi$ et $\delta\geq\alpha$ alors $\delta\geq\gamma_\omega$ : +on pourra pour cela montrer que $\delta\geq\gamma_n$ pour tout $n$). + +\begin{corrige} +On vient de voir que $\varphi(\alpha)\geq\alpha$ pour tout $\alpha$, +ce qui montre $\gamma_{n+1}\geq\gamma_n$, donc la suite $(\gamma_n)$ +est croissante. (Si on veut vraiment faire la démonstration jusqu'au +bout : montrons que $m\leq n$ implique $\gamma_m \leq \gamma_n$ par +récurrence sur $n\geq m$ : pour $n=m$ c'est évident, et si on a +$\gamma_m \leq \gamma_n$, alors $\gamma_m \leq \gamma_n \leq +\varphi(\gamma_n) = \gamma_{n+1}$ ce qui conclut la récurrence.) + +Montrons maintenant $\varphi(\gamma_\omega) = \gamma_\omega$. Par +continuité de $\varphi$, on a $\varphi(\lim_{n\to\omega} \gamma_n) = +\lim_{n\to\omega} \varphi(\gamma_n)$ (pour être tout à fait complet +dans la démonstration de cette affirmation : $\gamma_\omega$ est par +définition le plus petit ordinal supérieur ou égal à tous les +$\gamma_n$ pour $n<\omega$, donc tout ordinal $\zeta<\gamma_\omega$ +est majoré par un $\gamma_n$ pour un certain $n<\omega$, et par +croissance de $\varphi$ on a alors $\varphi(\zeta)$ majoré par +$\varphi(\gamma_n)$, donc la borne supérieure des $\varphi(\gamma_n)$ +pour $n<\omega$ est aussi la borne supérieure des $\varphi(\zeta)$ +pour $\zeta<\gamma_\omega$ : or cette dernière borne supérieure est +$\varphi(\gamma_omega)$ par continuité de $\varphi$, ce qui montre +$\varphi(\gamma_\omega) = \lim_{n\to\omega} \varphi(\gamma_n)$), +c'est-à-dire $\varphi(\gamma_\omega) = \lim_{n\to\omega} \gamma_{1+n} += \gamma_\omega$, comme affirmé. + +Enfin, si $\delta$ est un point fixe de $\varphi$ et $\delta \geq +\alpha$, alors par récurrence sur $n$ on a $\delta \geq \gamma_n$ pour +tout $n<\omega$ (le cas $n=0$ est l'hypothèse, et $\delta \geq +\gamma_n$ implique $\varphi(\delta) \geq \varphi(\gamma_n)$ par +croissance de $\varphi$, c'est-à-dire $\delta \geq \gamma_{n+1}$), ce +qui donne $\delta \geq \gamma_\omega$ puisque $\gamma_\omega$ est la +borne supérieure des $\gamma_n$ pour $n<\omega$. +\end{corrige} + +La question (3) implique notamment : \emph{pour tout ordinal $\alpha$ + il existe un point fixe de $\varphi$ qui soit $\geq\alpha$}. + +On définit maintenant $\varepsilon_\iota$ pour tout ordinal $\iota$ +par : +\begin{itemize} +\item $\varepsilon_0$ est le plus petit point fixe de $\varphi$ + (c'est-à-dire, si on veut, le plus petit point fixe qui soit $\geq + 0$) ; +\item pour $\iota+1$ ordinal successeur, $\varepsilon_{\iota+1}$ est + le plus petit point fixe de $\varphi$ qui soit $>\varepsilon_\iota$ + (c'est-à-dire, si on veut, le plus petit point fixe qui soit $\geq + (\varepsilon_\iota)+1$), +\item pour $\delta$ ordinal limite, $\varepsilon_\delta$ est + $\lim_{\xi\to\delta} \varepsilon_\xi$ (c'est-à-dire + $\sup\{\varepsilon_\xi : \xi < \delta\}$). +\end{itemize} + +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 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)$. + +\begin{corrige} +Remarquons tout d'abord que $\varepsilon_{\iota+1}$ est le plus petit +point fixe de $\varphi$ qui soit strictement supérieur à +$\varepsilon_\iota$, et notamment $\varepsilon_{\iota+1} > +\varepsilon_\iota$, quel que soit $\iota$. + +Il est sans doute plus agréable, ensuite, de montrer que $\iota +\mapsto \varepsilon_\iota$ est croissante à partir du fait que +$\varepsilon_{\iota+1} \geq \varepsilon_\iota$ et de la continuité aux +ordinaux limites (on peut légitimement tenir ce fait pour évident vu +qu'il est sous-entendu par l'énoncé de la question en ce qu'elle +définit $\lim_{\xi\to\delta} \varepsilon_\xi$ comme +$\sup\{\varepsilon_\xi : \xi < \delta\}$). Pour cela, on montre par +induction transfinie sur $\beta$ que $\alpha \leq \beta$ implique +$\varepsilon_\alpha \leq \varepsilon_\beta$. Or si $\alpha = \beta$ +il n'y a rien à prouver, donc supposons $\alpha < \beta$. Si $\beta$ +est successeur, disons $\beta = \gamma+1$, alors $\alpha < \beta$, +signifie $\alpha \leq \gamma$, auquel cas l'hypothèse d'induction +(comme $\gamma<\beta$) donne $\varepsilon_\alpha \leq +\varepsilon_\gamma$ et d'après la remarque qu'on a faite, +$\varepsilon_\alpha \leq \varepsilon_\gamma \leq +\varepsilon_{\gamma+1} = \varepsilon_\beta$ comme on voulait. Enfin, +si $\beta$ est limite, alors $\varepsilon_\beta$ est défini comme la +borne supérieure des $\varepsilon_\xi$ pour $\xi<\beta$, mais en +particulier $\varepsilon_\alpha$ est dans cet ensemble dont on a pris +la borne supérieure, donc $\varepsilon_\alpha \leq \varepsilon_\beta$. + +Ensuite, pour passer de croissant à strictement croissant, il suffit +de dire que $\alpha < \beta$ équivaut à $\alpha+1 \leq \beta$, la +croissance donne $\varepsilon_{\alpha+1} \leq \varepsilon_\beta$, et +on a déjà remarqué $\varepsilon_\alpha < \varepsilon_{\alpha+1}$, d'où +$\varepsilon_\alpha < \varepsilon_\beta$. + +Montrons enfin que $\varepsilon_\delta$ est point fixe de $\varphi$ +pour $\delta$ limite. Le point crucial est qu'on a +$\varphi(\lim_{\xi\to\delta} \varepsilon_\xi) = \lim_{\xi\to\delta} +\varphi(\varepsilon_\xi)$ par continuité de $\varphi$ (pour etre tout +à fait complet dans la démonstration de cette affirmation : +$\varepsilon_\delta$ est par définition le plus petit ordinal +supérieur ou égal à tous les $\varepsilon_\xi$ pour $\xi<\delta$, donc +tout ordinal $\zeta<\varepsilon_\delta$ est majoré par un +$\varepsilon_\xi$ pour un certain $\xi<\delta$, et par croissance de +$\varphi$ on a alors $\varphi(\zeta)$ majoré par +$\varphi(\varepsilon_\xi)$, donc la borne supérieure des +$\varphi(\varepsilon_\xi)$ pour $\xi<\delta$ est aussi la borne +supérieure des $\varphi(\zeta)$ pour $\zeta<\varepsilon_\delta$ : or +cette dernière borne supérieure est $\varphi(\varepsilon_\delta)$ par +continuité de $\varphi$, ce qui montre $\varphi(\varepsilon_\delta) = +\lim_{\xi\to\delta} \varphi(\varepsilon_\xi)$). On montre alors +$\varphi(\varepsilon_\iota) = \varepsilon_\iota$ par induction +sur $\xi$ : le cas successeur étant contenu dans la définiton même +de $\varepsilon$, il n'y a qu'à traiter le cas limite, et on a alors +$\varphi(\varepsilon_\delta) = \varphi(\lim_{\xi\to\delta} +\varepsilon_\xi) = \lim_{\xi\to\delta} \varphi(\varepsilon_\xi) = +\lim_{\xi\to\delta} \varepsilon_\xi = \varepsilon_\delta$. +\end{corrige} + +\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 +tel $\alpha$). + +\begin{corrige} +Pour la même raison qu'en (2), on a $\varepsilon_\alpha \geq \alpha$ +pour tout $\alpha$. Donné un point fixe $\gamma$ de $\varphi$, on +sait donc qu'il existe $\alpha$ tel que $\varepsilon_\alpha \geq +\gamma$ (on vient de voir que $\alpha=\gamma$ convient). Considérons +le plus petit tel $\alpha$ : ceci a un sens car les ordinaux sont +bien-ordonnés. On veut montrer qu'on a $\varepsilon_\alpha = \gamma$. +Si $\alpha$ est successeur, disons $\alpha = \beta+1$, alors +$\varepsilon_\beta < \gamma$ par minimalité de $\alpha$, mais comme +$\gamma$ est un point fixe de $\varphi$ et que $\varepsilon_{\beta+1}$ +est le plus petit point fixe après $\varepsilon_\beta$, on doit avoir +$\varepsilon_{\beta+1} \leq \gamma$, soit $\varepsilon_\alpha \leq +\gamma$, et on a bien prouvé $\varepsilon_\alpha = \gamma$. Si +$\alpha$ est limite, en revanche, par minimalité de $\alpha$, on a +$\varepsilon_\xi < \gamma$ pour tout $\xi<\alpha$; or +$\varepsilon_\alpha$ a été défini comme la borne supérieure de +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.} + +\nobreak +On appelle $\varepsilon_0$ le plus petit ordinal tel que $\varepsilon += \omega^\varepsilon$, et $\varepsilon_1$ le suivant, c'est-à-dire le +plus petit ordinal $>\varepsilon_0$ vérifiant cette même équation +$\varepsilon = \omega^\varepsilon$ (l'existence de ces ordinaux +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 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 ». + +\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, +démontré en (2), que $\omega^\gamma \geq \gamma$ pour tout +ordinal $\gamma$). + +\begin{corrige} +Notons pour commencer que $\omega^{\gamma_i} \leq \alpha$ (ceci +résulte de la comparaison entre les formes normales de Cantor). Si on +avait $\gamma_i \geq \alpha$ alors on aurait $\alpha \geq +\omega^{\gamma_i} \geq \gamma_i \geq \alpha$ : donc en fait toutes ces +inégalités sont des égalités et $\alpha = \gamma_i = +\omega^{\gamma_i}$ est un point fixe de la fonction $\gamma \mapsto +\omega^\gamma$, ce qui, pour $\alpha < \varepsilon_1$, n'est possible +que lorsque $\alpha = \varepsilon_0$, or on a supposé le contraire. +C'est donc bien que $\gamma_i < \alpha$. +\end{corrige} + +On appellera \emph{écriture 1} d'un ordinal $\alpha < \varepsilon_1$ +l'écriture qui est \underline{ou bien} $\varepsilon_0$ (considéré +comme un symbole spécial), \underline{ou bien} une forme normale de +Cantor $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ où les +exposants $\gamma_s > \cdots > \gamma_1$ sont tous $<\alpha$ et +eux-mêmes écrits en écriture 1 (ceci a bien un sens par (6)). + +À titre d'exemple, $\omega^\omega\,2$ ou $\varepsilon_0$ ou bien +$\omega^{\varepsilon_0} + 1$ ou encore +$\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$. + +\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$ 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. + +\begin{corrige} +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 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 +$\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}+1}$, ce qui est une écriture 1 +légitime. + +Pour calculer $(\varepsilon_0)^\alpha$, on l'écrit comme +$(\omega^{\varepsilon_0})^\alpha = \omega^{\varepsilon_0\,\alpha}$, or +on vient de dire qu'on peut calculer algorithmiquement l'écriture 1 de +$\varepsilon_0\,\alpha$ en fonction de celle de $\alpha$ : en la +remplaçant dans l'exposant, on obtient alors une écriture 1 de +$\omega^{\varepsilon_0\,\alpha}$ (sauf pour $\alpha=1$ auquel cas on +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 +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} + +\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$ +sont des ordinaux et où $\xi_s,\ldots,\xi_1$ sont des ordinaux tous +non nuls et strictement inférieurs à $\varepsilon_0$. + +\begin{corrige} +Il s'agit de l'écriture en base $\tau$ des ordinaux, dans le cas +particulier de $\tau = \varepsilon_0$. +\end{corrige} + +\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 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} + +\omega^{\varepsilon_1} = \omega^{\varepsilon_1}$ car $\varepsilon_0 < +\varepsilon_1$. On en déduit $\varepsilon_0 \cdot \varepsilon_1 = +\omega^{\varepsilon_0} \cdot \omega^{\varepsilon_1} = +\omega^{\varepsilon_0 + \varepsilon_1} = \omega^{\varepsilon_1} = +\varepsilon_1$. On en déduit $(\varepsilon_0)^{\varepsilon_1} = +((\omega^{\varepsilon_0})^{\varepsilon_1} = +\omega^{\varepsilon_0\cdot\varepsilon_1} = \omega^{\varepsilon_1} = +\varepsilon_1$. + +Si $(\varepsilon_0)^{\delta} = \delta$ alors $\delta \leq +\omega^\delta \leq \omega^{\varepsilon_0 \delta} = +(\omega^{\varepsilon_0})^\delta = (\varepsilon_0)^{\delta} = \delta$ +où les deux inégalités résultent de (2) et de la croissance de +$\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$ : 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 +prouvé que $\varepsilon_1$ est le plus petit ordinal tel que +$(\varepsilon_0)^{\delta} = \delta$. +\end{corrige} + +On appellera \emph{écriture 2} d'un ordinal $\alpha < \varepsilon_1$ +une écriture $(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots + +(\varepsilon_0)^{\gamma_1}\, \xi_1$ comme en (7), où les exposants +$\gamma_s > \cdots > \gamma_1$ sont tous $<\alpha$ et eux-mêmes écrits +en écriture 2, et où les $\xi_s,\ldots,\xi_1$ (qui +sont $<\varepsilon_0$) sont écrits en forme normale de Cantor itérée. + +À titre d'exemple, $\omega^\omega\,2$ (il faut sous-entendre +$(\varepsilon_0)^0$ devant, qui vaut $1$) ou $(\varepsilon_0)^2 + 1$ +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, dont l'exposant ne fait donc jamais +intervenir $\varepsilon_0$). + +\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)). + +\begin{corrige} +L'existence et l'unicité de l'écriture 2 résulte de (8) et de +l'existence et unicité de la forme normale de Cantor itérée pour les +ordinaux $<\varepsilon_0$. + +Pour convertir de l'écriture 2 en écriture 1, on part de l'écriture 2, +on convertit chaque exposant de $(\varepsilon_0)^\gamma$ de +l'écriture 1 en écriture 2 en utilisant l'algorithme récursivement +(ceci termine bien car les exposants sont strictement plus simples, ou +plus petits comme on voudra dire). On calcule alors la valeur de +$(\varepsilon_0)^\gamma$ en partant de l'écriture 1 de $\gamma$ en +utilisant la question (7). Il ne reste alors plus qu'à distribuer à +droite les produits $(\varepsilon_0)^\gamma\cdot\xi$ avec $\xi$ écrit +comme forme normale de Cantor itérée, et enfin calculer l'expression +globale en écriture 1 (ce qui ne fait intervenir que des sommes et des +produits, qu'on sait calculer). +\end{corrige} + +{\footnotesize\textit{Remarque.} Il est aussi possible de convertir + algorithmiquement de l'écriture 1 vers l'écriture 2 : ceci passe par + calculer les $\omega^\alpha$ pour $\alpha$ donné en écriture 2.\par} + +\medskip + +\underline{Troisième partie.} + +\nobreak +On aura besoin ici des définitions des ordinaux $\varepsilon_0$ et +$\varepsilon_1$ données en tête de la première partie, mais pas plus. + +On s'intéresse à un jeu de Hercule et de l'hydre qui est analogue au +jeu considéré en cours mais avec une extension : comme en cours, +l'hydre est un arbre fini enraciné, mais l'hydre a maintenant deux +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, œ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 (quoi qu'il fasse et quoi que fasse l'hydre). + +\begin{corrige} +À toute hydre $T$ on associe un ordinal $o(T) <\varepsilon_1$ par +récurrence sur la profondeur de l'arbre, de la façon suivante : si $T$ +est un œuf, alors on pose $o(T) = \varepsilon_0$ ; sinon, si +$T_1,\ldots,T_r$ sont les sous-arbres ayant pour racine les fils de la +racine, triés de façon que $o(T_1) \geq \cdots \geq o(T_r)$, alors on +pose $o(T) = \omega^{o(T_1)} + \cdots + \omega^{o(T_r)}$. Exactement +les mêmes démonstrations que dans le cours tiennent, il faut +simplement ajouter la clause suivante : si $T$ est un œuf et $T'$ est +une hydre sans œuf, alors $o(T') < \varepsilon_0 = o(T)$, donc en +remplaçant l'œuf par une hydre sans œuf quelconque, on fait +strictement décroître l'ordinal. + +(Remarquons que, comme $\varepsilon_0 = \omega^{\varepsilon_0}$, une +tige de longueur arbitraire se finissant par un œuf a toujours la même +valeur $\varepsilon_0$ avec ce système : ce n'est pas un problème, et +ce n'est pas surprenant puisque de telles tiges offrent +essentiellement les mêmes possibilités à l'hydre.) +\end{corrige} + +\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} +\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); +\fill[fill=gray] (P4) to[out=0,in=270] ($(P4) + (0.3,0.3)$) to[out=90,in=0] ($(P4) + (0,1.0)$) to[out=180,in=90] ($(P4) + (-0.3,0.3)$) to[out=270,in=180] (P4); +\end{scope} +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node at (P3) {}; +\node at (P4) {}; +\end{scope} +\end{tikzpicture} +\end{center} +a la valeur $\omega^{\omega^{\varepsilon_0\,2}} = +\omega^{(\omega^{\varepsilon_0})^2} = \omega^{\varepsilon_0^2} = +(\omega^{\varepsilon_0})^{\varepsilon_0} = +(\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} + + +% +% +% +\end{document} |