diff options
Diffstat (limited to 'controle-20190408.tex')
| -rw-r--r-- | controle-20190408.tex | 734 |
1 files changed, 734 insertions, 0 deletions
diff --git a/controle-20190408.tex b/controle-20190408.tex new file mode 100644 index 0000000..6e4da38 --- /dev/null +++ b/controle-20190408.tex @@ -0,0 +1,734 @@ +%% 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{8 avril 2019} +\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 +(cf. barème). + +\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} : exercice 1 : $9$ points ; exercice 2 : +$9$ points ; exercice 3 : $4$ points. + +\ifcorrige +Ce corrigé comporte 10 pages (page de garde incluse). +\else +Cet énoncé comporte 6 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 s'intéresse dans cet exercice à des jeux à deux joueurs (que l'on +appellera Alice et Bob) de la forme suivante : +\begin{itemize} +\item Alice et Bob sont autour d'une table sur laquelle se trouvent un + certain nombre (fini) de \emph{jetons} ; chaque jeton porte un + entier naturel qu'on appellera son \emph{type} ; il peut y avoir + plusieurs jetons de même type (par exemple, trois jetons de + type $0$, deux jetons de type $1$ et un jeton de type $1729$) ; le + nombre (fini) de jetons de jetons de chaque type constitue l'état du + jeu, et il est visible de tous ; +\item Alice et Bob jouent tour à tour, et chacun, quand vient son + tour, doit retirer un jeton de la table et le \emph{remplacer} + éventuellement par des jetons de type(s) strictement plus petit(s) : + les règles exactes de remplacement seront différentes d'une question + à l'autre, mais prendront toujours la forme « un joueur peut + remplacer un jeton de type $n$ par telle ou telle combinaison de + jetons de types $<n$ » ; dans tous les cas, un coup consiste à + retirer un unique jeton et à en poser éventuellement plusieurs ; il + y aura toujours au moins une manière de remplacer un jeton de + type $n$ donné ; +\item il n'y a aucune interaction entre les jetons, c'est-à-dire que + les remplacements permis pour un jeton de type $n$ ne dépendront que + de $n$ et pas des autres jetons présents sur la table (ni de + l'identité du joueur, ni du numéro du coup, ni de quelque autre + information) ; +\item on notera que les jetons de type $0$ ne peuvent être que retirés + (il n'y a aucun remplacement possible puisqu'il n'existe pas de + jeton de type $<0$) ; +\item le gagnant est celui qui retire le dernier jeton (puisque son + adversaire ne peut plus jouer). +\end{itemize} + +\smallskip + +Dans les questions (1) à (3), on ne fait pas d'hypothèse particulière +sur les règles de remplacement autre que celles qui sont indiquées +ci-dessus. Dans les questions (4) à (6), on traite le cas de règles +de remplacement particulières. + +\medskip + +(1) Montrer que le jeu termine toujours en temps fini. On pourra pour +cela associer judicieusement un ordinal à l'état du jeu et montrer +qu'il décroît strictement à chaque tour. + +\begin{corrige} +On associe à la position $J(n_1,\ldots,n_r)$ (définie en (2) +ci-dessous), quitte à supposer $n_1>\cdots>n_r$ l'ordinal +$\omega^{n_1} + \cdots + \omega^{n_r}$ ; ou, ce qui revient au même, +s'il y a $r_n := \#\{i : n_i = n\}$ jetons de type $n$, on considère +l'ordinal $\omega^N r_n + \cdots + \omega^2 r_2 + \omega\, r_1 + r_0$ +où $N := \max\{n_i\}$ est le plus grand type d'un jeton sur la table. +Par la comparaison des ordinaux écrits en forme normale de Cantor, cet +ordinal décroît à chaque coup (puisqu'on remplace un $\omega^n$ par +des $\omega^{n'}$ avec $n' < n$, la suite $(r_n,\ldots,r_0)$ décroît +lexicographiquement). Le jeu termine donc en temps fini. +\end{corrige} + +\medskip + +(2)(a) En notant $J(n_1,\ldots,n_r)$ l'état du jeu dans lequel $r$ +jetons se trouvent sur la table et ont les types $n_1,\ldots,n_r$ +(éventuellement répétés, p.ex. $J(0,0,0,1,1,1729)$), expliquer +pourquoi $J(n_1,\ldots,n_r)$ peut s'identifier à la somme de nim des +positions $J(n_1),\ldots,J(n_r)$ (où $J(n)$ désigne l'état du jeu +ayant un unique jeton de type $n$).\quad(b) En déduire la valeur de +Grundy $\gr J(n_1,\ldots,n_r)$ de $J(n_1,\ldots,n_r)$ en fonction de +celles des $J(n_i)$.\quad(c) Qui a une stratégie gagnante +dans une position du type $J(n,n)$ ? Expliciter une telle stratégie +en termes simples. + +(\emph{Convention :} $J()$ est le jeu nul dans lequel il ne reste plus +aucun jeton sur la table. Notamment, on a $\gr J() = 0$. On ne le +confondra pas avec $J(0)$ où il reste un jeton de type $0$.) + +\begin{corrige} +(a) Il s'agit simplement d'observer que les différents jetons + n'interagissent pas du tout. Jouer à la somme de nim de + $J(n_1),\ldots,J(n_r)$ revient à jouer sur $r$ tables différentes à + partir d'un jeton de type $n_i$ sur chacune, c'est équivalent à + jouer à $J(n_1,\ldots,n_r)$. + +(b) On en déduit que $\gr J(n_1,\ldots,n_r) = \gr(J(n_1) \oplus \cdots + \oplus J(n_r)) = \gr J(n_1) \oplus \cdots \oplus \gr J(n_r)$ (la + première égalité par (a), la seconde d'après le fait que la valeur + de Grundy d'une somme de nim est la somme de nim des valeur de + Grundy). + +(c) Le second joueur a une stratégie gagnante à $J(n,n)$ (ceci se voit + par le fait que sa valeur de Grundy vaut $0$). Cette stratégie + consiste à reproduire systématiquement les coups de son adversaire + (ce qui maintiendra un nombre pair de jetons de chaque type à la fin + de son coup). +\end{corrige} + +\medskip + +(3)(a) Pour une règle de remplacement donnée, expliquer comment se +calcule $\gr J(n)$ si on suppose connus tous les $\gr J(n')$ +pour $n'<n$.\quad(b) On rappelle que le seul remplacement possible +d'un jeton de type $0$ est de l'enlever purement et simplement : en +déduire la valeur de $\gr J(0)$ et celle de $\gr J(0,\ldots,0)$ (où il +y a $r$ jetons de type $0$). + +\begin{corrige} +(a) Puisque $\gr x$, pour une position $x$ d'un jeu combinatoire + impartial bien-fondé, vaut $\mex\{\gr y : y\in\outnb(x)\}$, on a ici + $\gr J(n) = \mex\{\gr J(n'_1,\ldots,n'_r) : J(n'_1,\ldots,n'_r) + \in\outnb J(n)\}$, c'est-à-dire $\gr J(n) = \mex\{\gr J(n'_1) \oplus + \cdots \oplus \gr J(n'_r) : J(n'_1,\ldots,n'_r)\in\outnb J(n)\}$ + d'après (2)(b) ; la règle de remplacement consiste justement à + décrire les $J(n'_1,\ldots,n'_r)\in\outnb J(n)$. + +(b) Dans le cas de $n=0$, comme $\outnb J(0) = \{J()\}$, on trouve + $\gr J(0) = \mex\{0\} = 1$, et par conséquent $\gr J(0,\ldots,0) = + 1\oplus \cdots\oplus 1$ vaut $0$ ou $1$ selon que $r$ est pair ou + impair. +\end{corrige} + +\medskip + +(4) On suppose dans cette question que la règle de remplacement est la +suivante : un joueur peut remplacer un jeton de type $n$ par un nombre +quelconque (y compris $0$) de jetons de type $n-1$. (Autrement dit, à +chaque coup, le joueur retire un jeton de type $n$ et si $n>0$ il +ajoute ensuite, optionnellement, le nombre qu'il souhaite de jetons de +type $n-1$. Par exemple, on peut remplacer un jeton de type $1729$ +par $42$ jetons de type $1728$ ; on peut aussi le retirer sans +remplacement.)\quad(a) Dans ces conditions, que vaut $\gr J(n)$ ? (On +pourra par exemple commencer par calculer $\gr J(n)$ pour $n=0,1,2,3$, +conjecturer une formule générale, et la démontrer par récurrence +sur $n$.)\quad(b) Exprimer de façon simple la stratégie gagnante du +jeu considéré dans cette question. + +\begin{corrige} +(a) On a vu en (3)(b) que $\gr J(0,\ldots,0)$ vaut $0$ ou $1$ selon + que le nombre de jetons est pair ou impair ; on en déduit que $\gr + J(1) = \mex\{0,1\} = 2$, et alors (en se rappelant que $2\oplus + 2=0$) on trouve que $\gr J(1,\ldots,1)$ vaut $0$ ou $2$ selon que le + nombre de jetons est pair ou impair ; on en déduit que $\gr J(2) = + \mex\{0,2\} = 1$, et donc $\gr J(2,\ldots,2)$ vaut $0$ ou $1$ selon + que le nombre de jetons est pair ou impair ; par conséquent, $\gr + J(3) = \mex\{0,1\} = 2$. En général on imagine facilement que $\gr + J(n)$ vaut $1$ ou $2$ selon que $n$ est pair ou impair, et ceci se + démontre par une récurrence immédiate avec exactement le même + argument qu'on vient de faire. + +(b) La valeur de Grundy de $\gr J(n_1,\ldots,n_r)$ est le XOR (= la + somme de nim) de $r$ valeurs $1$ si $r$ est le nombre de jetons de + type pair, et $r'$ valeurs $2$ si $r'$ est le nombre de jetons de + type impair : ce nombre vaut $0$, $1$, $2$ ou $3$ selon que $r$ et + $r'$ sont tous les deux pairs, que $r$ est impair et $r'$ pair, + qu'on a le contraire, ou qu'ils sont tous les deux impairs. La + stratégie gagnante consiste donc à jouer de façon que le nombre $r$ + de jetons de type pair et le nombre $r'$ de jetons de type impair + soient tous les deux pairs (de façon à annuler Grundy). +\end{corrige} + +\medskip + +(5) On suppose dans cette question que la règle de remplacement est la +suivante : un joueur peut remplacer un jeton de type $n$ par un nombre +quelconque (y compris $0$) de jetons de type $k<n$, le type $k$ +pouvant être quelconque mais doit être le même pour tous les jetons +posés. (Autrement dit, à chaque coup, le joueur retire un jeton de +type $n$ et si $n>0$ il ajoute ensuite, optionnellement, le nombre +qu'il souhaite de jetons d'un même type $k\leq n-1$. Par exemple, on +peut remplacer un jeton de type $1729$ par $42$ jetons de type $1728$ +ou $1728$ jetons de type $42$ ; on peut aussi le retirer sans +remplacement.) Dans ces conditions, que vaut $\gr J(n)$ ? (On pourra +par exemple commencer par calculer $\gr J(n)$ pour $n=0,1,2,3$, +conjecturer une formule générale, et la démontrer par récurrence +sur $n$.) + +\begin{corrige} +On a vu en (3)(b) que $\gr J(0,\ldots,0)$ vaut $0$ ou $1$ selon que le +nombre de jetons est pair ou impair ; on en déduit que $\gr J(1) = +\mex\{0,1\} = 2$, et alors (en se rappelant que $2\oplus 2=0$) on +trouve que $\gr J(1,\ldots,1)$ vaut $0$ ou $2$ selon que le nombre de +jetons est pair ou impair ; on en déduit que $\gr J(2) = \mex\{0,1,2\} += 3$ (la différence avec (4)(a) est que maintenant on peut aussi aller +en $\gr J(0,\ldots,0)$ donc $1$ apparaît dans le $\mex$), et donc $\gr +J(2,\ldots,2)$ vaut $0$ ou $3$ selon que le nombre de jetons est pair +ou impair ; par conséquent, $\gr J(3) = \mex\{0,1,2,3\} = 4$. En +général on imagine facilement que $\gr J(n)$ vaut $n+1$, et ceci se +démontre par une récurrence immédiate avec exactement le même argument +qu'on vient de faire. +\end{corrige} + +\medskip + +(6) On suppose dans cette question que la règle de remplacement est la +suivante : un joueur peut remplacer un jeton de type $n$ par un nombre +quelconque (y compris $0$) de jetons de types $<n$, qui cette fois +n'ont pas d'obligation d'être tous du même type. (Autrement dit, à +chaque coup, le joueur retire un jeton de type $n$ et si $n>0$ il +ajoute ensuite, optionnellement, le nombre qu'il souhaite de jetons de +n'importe quels types $<n$. Par exemple, on peut remplacer un jeton +de type $1729$ par $42$ jetons de type $1728$ et $666$ de type $0$ ; +on peut aussi le retirer sans remplacement.)\quad(a) Dans ces +conditions, que vaut $\gr J(n)$ ? (On pourra par exemple commencer +par calculer $\gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule +générale, et la démontrer par récurrence sur $n$.)\quad(b) Exprimer de +façon simple la stratégie gagnante du jeu considéré dans cette +question. + +\begin{corrige} +(a) On a vu en (3)(b) que $\gr J(0,\ldots,0)$ vaut $0$ ou $1$ selon + que le nombre de jetons est pair ou impair ; on en déduit que $\gr + J(1) = \mex\{0,1\} = 2$, et alors (en se rappelant que $2\oplus + 2=0$) on trouve que $\gr J(0,\ldots,0,\penalty0\relax 1,\ldots,1)$ + vaut $0$, $1$, $2$ ou $3$ selon que le nombre de jetons de chaque + type est pair ou impair (comme expliqué en (4)(b)) ; on en déduit + que $\gr J(2) = \mex\{0,1,2,3\} = 4$, et donc $\gr + J(0,\ldots,0,\penalty0\relax 1,\ldots,1,\penalty0\relax 2,\ldots,2)$ + prend exactement les valeurs entre $0$ et $7$ selon la parité des + jetons de chaque type ; par conséquent, $\gr J(3) = + \mex\{0,\ldots,7\} = 8$. En général on imagine facilement que $\gr + J(n)$ vaut $2^n$, et ceci se démontre par une récurrence immédiate + en remarquant que le $\gr J(n'_1,\ldots,n'_r)$, si les $n'_i$ + sont $<n$, peut prendre toutes les valeurs de $0$ à $2^n - 1$ selon + la parité des jetons de chaque type (donnant l'écriture binaire du + résultat). + +(b) La stratégie gagnante consiste donc à jouer de façon que le nombre + de jetons de chaque type soit pair. +\end{corrige} + + +% +% +% + +\exercice + +On définit une opération binaire $\alpha\boxplus\beta$ (appelée +« somme naturelle » ou « somme de Hessenberg ») sur les ordinaux (ici +notés $\alpha,\beta$) par la formule suivante : +\[ +\alpha \boxplus \beta = \sup\nolimits^+ \Big( \{\alpha'\boxplus\beta : +\alpha' < \alpha\} \cup \{\alpha\boxplus\beta' : \beta' < +\beta\}\Big) +\] +où on rappelle que $\sup^+ S$, si $S$ est un ensemble d'ordinaux, +désigne \emph{le plus petit ordinal strictement plus grand que tous + les éléments de $S$} (c'est aussi $\sup\{\gamma+1 : \gamma\in S\}$ +mais c'est probablement moins utile d'y penser sous cette forme). +Autrement dit, $\alpha\boxplus\beta$ désigne le plus petit ordinal qui +soit strictement supérieur à tous les $\alpha'\boxplus\beta$ pour +$\alpha'<\alpha$ ainsi qu'à tous les $\alpha\boxplus\beta'$ +pour $\beta'<\beta$. Cette définition a bien un sens par induction +bien-fondée. + +\medskip + +%% À toutes fins utiles, on signale le fait évident qu'on a $\xi = +%% \sup^+ S$ si et seulement si on a (i) $\xi$ est strictement +%% supérieur à tout élément de $S$, et (ii) tout ordinal $<\xi$ est +%% inférieur ou égal à un élément de $S$. + +À toutes fins utiles, on signale le fait évident que $\sup^+ S$ ne +change pas si on insère dans $S$ des nouveaux éléments qui sont +majorés par des éléments déjà dans $S$. + +\medskip + +(1)(a) Calculer $m\boxplus n$ pour $0\leq m\leq 5$ et $0\leq n\leq +5$.\quad(b) Conjecturer une formule générale pour $m\boxplus n$ +lorsque $m,n\in\mathbb{N}$ (c'est-à-dire +$m,n<\omega$).\quad(c) Démontrer cette formule. + +\begin{corrige} +(a)/(b) On construit le tableau de proche en proche en inscrivant dans + chaque case le plus petit entier strictement supérieur à tous les + nombres écrits plus haut dans la colonne ou plus à gauche dans la + ligne : on obtient $m\boxplus n = m + n$, et on peut imaginer que + c'est vrai en général. + +(c) Montrons que $m\boxplus n = m + n$ pour tous $m,n\in\mathbb{N}$ : + par récurrence (sur $m+n$), on peut supposer connu le fait que + $m'\boxplus n = m' + n$ pour tout $m'<m$ et $m\boxplus n' = m + n'$ + pour tout $n'<n$. On a alors $m \boxplus n = \sup^+ \big( \{m' + \boxplus n : m' < m\} \penalty0 \cup \penalty0 \{m \boxplus n' : n' + < n\}\big) = \sup^+ \big( \{m' + n : m' < m\} \penalty0 \cup + \penalty0 \{m + n' : n' < n\}\big)$ ; or l'ensemble dont on prend le + $\sup^+$ ne contient que des entiers $<m+n$ et contient $m+n-1$ donc + ce $\sup^+$ vaut $m+n$, ce qui conclut la récurrence. +\end{corrige} + +\medskip + +(2)(a) Montrer que $\boxplus$ est commutative, c'est-à-dire que +$\alpha_1\boxplus\alpha_2 = \alpha_2\boxplus\alpha_1$ quels que +soient $\alpha_1,\alpha_2$.\quad(b) Montrer que $\boxplus$ admet $0$ +pour élément neutre, c'est-à-dire que $\alpha\boxplus 0 = +0\boxplus\alpha = \alpha$ pour tout ordinal $\alpha$.\quad(c) Montrer +que si $\alpha'\leq\alpha$ et $\beta'\leq\beta$ alors +$\alpha'\boxplus\beta' \leq \alpha\boxplus\beta$, avec inégalité stricte +dans la conclusion si au moins une d'elles est stricte dans +l'hypothèse. + +\begin{corrige} +(a) Par induction transfinie sur $\alpha_1$ et $\alpha_2$, on prouve + $\alpha_2\boxplus\alpha_1 = \alpha_1\boxplus\alpha_2$ : en effet, + $\alpha_2\boxplus\alpha_1 = \sup^+ (\{\alpha_2\boxplus\beta_1: + \beta_1<\alpha_1\} \penalty0 \cup \penalty0 + \{\beta_2\boxplus\alpha_1: \beta_2<\alpha_2\})$, et par hypothèse + d'induction ceci vaut $\sup^+ (\{\beta_1\boxplus\alpha_2: + \beta_1<\alpha_1\} \penalty0 \cup \penalty0 + \{\alpha_1\boxplus\beta_2: \beta_2<\alpha_2\}) = + \alpha_1\boxplus\alpha_2$. + +(b) Par induction sur $\alpha$, on prouve $\alpha \boxplus 0 = + \alpha$ : en effet, $\alpha \boxplus 0 = \sup^+ \{\beta\boxplus 0: + \beta<\alpha\}$, et par hypothèse d'induction ceci vaut $\sup^+ + \{\beta: \beta<\alpha\} = \alpha$. Par la commutativité déjà + prouvée, $0 \boxplus \alpha$ vaut lui aussi $\alpha$. + +(c) Si $\alpha'<\alpha$ alors $\alpha'\boxplus\beta < + \alpha\boxplus\beta$ par définition même de $\alpha\boxplus\beta$, + et de même si $\beta'<\beta$ alors $\alpha\boxplus\beta' < + \alpha\boxplus\beta$. Si on a à la fois $\alpha'<\alpha$ et + $\beta'<\beta$ alors $\alpha'\boxplus\beta' < \alpha'\boxplus\beta < + \alpha\boxplus\beta$ d'après ce qu'on vient de dire. C'est + exactement ce qu'il fallait démontrer. +\end{corrige} + +\medskip + +On \underline{admettra} pour la suite que $\boxplus$ est associative, +c'est-à-dire que $(\alpha_1\boxplus\alpha_2) \boxplus \alpha_3 = +\alpha_1 \boxplus (\alpha_2\boxplus\alpha_3)$ quels que soient +$\alpha_1,\alpha_2,\alpha_3$ ; et on admettra aussi que +$\alpha_1\boxplus\cdots\boxplus\alpha_n$ est le plus petit ordinal +strictement supérieur à tous les +$\alpha_1\boxplus\cdots\boxplus\beta_i\boxplus +\cdots\boxplus\alpha_n$, où exactement un des $\alpha_i$ a été +remplacé par un ordinal $\beta_i$ strictement plus petit +(généralisation de la définition au cas de $n$ termes, analogue à un +résultat vu en cours sur les sommes de nim). + +\smallskip + +Si $\alpha$ est un ordinal et $n\geq 1$ un entier naturel, on +\underline{notera} $\alpha\boxdot n$ pour la somme naturelle $\alpha +\boxplus \cdots \boxplus \alpha$ de $n$ fois l'ordinal $\alpha$ (on +pourra aussi poser $\alpha\boxdot 0 = 0$). Dans ces conditions, il +est trivial que $(\alpha\boxdot n) \boxplus (\alpha\boxdot n') = +\alpha\boxdot (n+n')$ ; par ailleurs, on a $1\boxdot n = n$ d'après la +question (1). + +\medskip + +Considérons l'affirmation suivante : + +{\narrower\noindent\leavevmode\llap{(*) }si $\alpha = + \omega^{\gamma_1} n_1 + \cdots + \omega^{\gamma_r} n_r$ où + $\gamma_1 > \cdots > \gamma_r$ sont des ordinaux en ordre + strictement décroissant et $n_1,\ldots,n_r$ des entiers naturels non + nuls (c'est-à-dire qu'il s'agit de la forme normale de Cantor + de $\alpha$), alors on a $\alpha = (\omega^{\gamma_1} \boxdot n_1) + \boxplus \cdots \boxplus (\omega^{\gamma_r} \boxdot n_r)$\par} + +\noindent (ceci est à comparer au fait, démontré en cours, que si +$\alpha = 2^{\gamma_1} + \cdots + 2^{\gamma_r}$, où $\gamma_1 > \cdots +> \gamma_r$ sont des ordinaux en ordre strictement décroissant, +c'est-à-dire qu'il s'agit de l'écriture binaire de $\alpha$, alors on +a $\alpha = 2^{\gamma_1} \oplus \cdots \oplus 2^{\gamma_r}$). + +On pourrait démontrer (*) par induction transfinie sur $\alpha$. +Comme c'est notationnellement un peu fastidieux, on va seulement, dans +la question suivante, montrer un cas particulier assez représentatif +de l'idée générale : + +\medskip + +(3)(a) Pour $n_0,n_1 \in \mathbb{N}$, montrer que $(\omega\boxdot n_1) +\boxplus n_0 = \sup^+ \big( \{(\omega\boxdot n'_1) \boxplus n_0' : +n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \penalty0 \cup +\penalty0 \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 < +n_0\}\big)$.\quad (b) En déduire par induction transfinie sur $\alpha$ +que si $\alpha = \omega\, n_1 + n_0$ où $n_0,n_1 \in \mathbb{N}$, +alors $\alpha = (\omega \boxdot n_1) \boxplus n_0$ (ceci est un cas +particulier de (*)). + +\begin{corrige} +(a) D'après ce qu'on a admis ci-dessus, $(\omega\boxdot n_1) \boxplus + n_0$, qui est une somme naturelle de $n_1$ copies de $\omega$ et + $n_0$ fois $1$, est le plus petit ordinal strictement supérieur à + toutes les sommes naturelles obtenues en remplaçant un + des ($n_1+n_0$) termes par un terme strictement plus petit, + c'est-à-dire à tous les $(\omega\boxdot (n_1-1)) \boxplus b \boxplus + n_0$ pour $b<\omega$ (cas où on remplace un $\omega$ par $b$) et à + $(\omega\boxdot n_1) \boxplus (n_0-1)$ (cas où on remplace un $1$ + par $0$). En se rappelant que $b \boxplus n_0 = b + n_0$ (qui prend + donc toutes les valeurs $\geq n_0$) et qu'on a le droit d'insérer + dans un ensemble dont on prend le $\sup^+$ des nouveaux éléments qui + sont majorés par des éléments déjà dedans (et comme $\boxplus$ est + croissante en chaque variable d'après (2)(c)), on peut écrire + $(\omega\boxdot n_1) \boxplus n_0 = \sup^+ \big( \{(\omega\boxdot + n'_1) \boxplus n_0' : n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} + \penalty0 \cup \penalty0 \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 + < n_0\}\big)$ comme annoncé. + +(b) On procède par induction transfinie sur $\alpha = \omega n_1 + + n_0$. On veut montrer que $\alpha = (\omega \boxdot n_1) \boxplus + n_0$. Or, d'après ce qu'on vient de voir, $(\omega\boxdot n_1) + \boxplus n_0 = \sup^+ \big( \{(\omega\boxdot n'_1) \boxplus n_0' : + n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \penalty0 \cup + \penalty0 \{(\omega\boxdot n_1) \boxplus n_0' : n'_0 < n_0\}\big)$. + D'après l'hypothèse d'induction, et en utilisant le fait que les + formes normales de Cantor des ordinaux se comparent + lexicographiquement, ceci vaut encore $\sup^+ \big( \{\omega\, n'_1 + + n_0' : n'_1 < n_1 \;\hbox{et}\; n'_0 \in\mathbb{N}\} \penalty0 + \cup \penalty0 \{\omega\, n_1 + n_0' : n'_0 < n_0\}\big)$, qui est + bien $\omega\, n_1 + n_0$ comme souhaité (il s'agit précisément du + $\sup^+$ de l'ensemble des ordinaux $<\omega\, n_1 + n_0$). +\end{corrige} + +\medskip + +(4)(a) On admet maintenant l'affirmation (*) en toute généralité. En +déduire la manière dont on calcule $\alpha\boxplus\beta$ à partir des +formes normales de Cantor de $\alpha$ et $\beta$.\quad(b) En +particulier, calculer $(\omega+1)\boxplus(\omega+1)$, et comparer avec +$(\omega+1) + (\omega+1)$. + +\begin{corrige} +(a) Soient $\alpha = \omega^{\gamma_1} p_1 + \cdots + + \omega^{\gamma_r} p_r$ et $\beta = \omega^{\gamma_1} q_1 + \cdots + + \omega^{\gamma_r} q_r$ (quitte à insérer des $p_i$ et $q_i$ nuls + dans la forme normale de Cantor) avec $\gamma_1 > \cdots > + \gamma_r$. En utilisant (*), on peut écrire $\alpha = + (\omega^{\gamma_1} \boxdot p_1) \boxplus \cdots \boxplus + (\omega^{\gamma_r} \boxdot p_r)$ et $\beta = (\omega^{\gamma_1} + \boxdot q_1) \boxplus \cdots \boxplus (\omega^{\gamma_r} \boxdot + q_r)$. En utilisant la commutativité et l'associativité + de $\boxdot$ et en regroupant les puissances égales de $\omega$, on + obtient $\alpha \boxplus \beta = (\omega^{\gamma_1} \boxdot + (p_1+q_1)) \boxplus \cdots \boxplus (\omega^{\gamma_r} \boxdot + (p_r+q_r))$. Et quitte à utiliser de nouveau (*), on trouve $\alpha + \boxplus \beta = \omega^{\gamma_1} (p_1+q_1) + \cdots + + \omega^{\gamma_r} (p_r+q_r)$. On a ainsi montré que la somme + naturelle se fait en ajoutant simplement terme à terme les formes + normales de Cantor, i.e., on ajoute les chiffres (=coefficients) de + chaque puissance de $\omega$. + +(b) En particulier, $(\omega+1)\boxplus(\omega+1) = \omega\,2 + 2$ + (qui est aussi $(\omega\boxdot 2)\boxplus 2$ comme on l'a vu), alors + que $(\omega+1) + (\omega+1) = \omega + (1+\omega) + 1 = \omega + + \omega + 1 = \omega\,2 + 1$ est strictement plus petit. +\end{corrige} + +\medskip + +(La question qui suit ne fait pas appel aux questions (3) et (4).) + +(5) On considère le jeu à deux joueurs suivant : les deux joueurs +s'appellent Blaise et Roxane, et ils jouent tour à tour (on ne précise +pas qui commence) ; l'état du jeu est défini par trois ordinaux, qu'on +notera $(\alpha,\beta,\rho)$, et il est visible de tous ; les coups +possibles de Blaise consistent à diminuer strictement soit l'ordinal +$\alpha$ soit l'ordinal $\beta$ (c'est-à-dire passer de +$(\alpha,\beta,\rho)$ à $(\alpha',\beta,\rho)$ avec $\alpha'<\alpha$ +ou à $(\alpha,\beta',\rho)$ avec $\beta'<\beta$), tandis que les coups +possibles de Roxane consistent à diminuer strictement l'ordinal $\rho$ +(c'est-à-dire passer de $(\alpha,\beta,\rho)$ à $(\alpha,\beta,\rho')$ +avec $\rho'<\rho$) ; le joueur qui ne peut plus jouer a perdu. + +Montrer que, dans ce jeu, Blaise possède une stratégie gagnante +lorsque $\rho < \alpha\boxplus\beta$, que Roxane possède une stratégie +gagnante lorsque $\rho > \alpha\boxplus\beta$, et que le second joueur +possède une stratégie gagnante lorsque $\rho = \alpha\boxplus\beta$. + +\begin{corrige} +On procède par induction transfinie (sur +$\alpha\boxplus\beta\boxplus\rho$, si l'on veut) : on peut supposer la +conclusion déjà connue pour tous les $(\alpha',\beta,\rho)$, +$(\alpha,\beta',\rho)$ et $(\alpha,\beta,\rho')$ tels que dans la +question. + +Si Blaise joue en premier : si $\rho < \alpha\boxplus\beta$, alors par +définition de $\alpha\boxplus\beta$, il existe un +$\alpha'\boxplus\beta$ avec $\alpha'<\alpha$ ou $\alpha\boxplus\beta'$ +avec $\beta'<\beta$ qui majore $\rho$ (au sens large), et Blaise peut +faire le coup correspondant $(\alpha',\beta,\rho)$ ou +$(\alpha,\beta',\rho)$ auquel cas il aura une stratégie gagnante comme +second joueur par hypothèse d'induction ; si $\rho \geq +\alpha\boxplus\beta$, alors quel que soit le coup +$(\alpha',\beta,\rho)$ ou $(\alpha,\beta',\rho)$ fait par Blaise, on +aura $\rho > \alpha'\boxplus\beta$ ou $\rho > \alpha\boxplus\beta'$ +donc Roxane aura une stratégie gagnante par hypothèse d'induction. + +Si Roxane joue en premier : si $\rho > \alpha\boxplus\beta$, alors +elle peut jouer vers $(\alpha,\beta,\rho')$ avec $\rho' = +\alpha\boxplus\beta$, auquel cas elle comme second joueur aura une +stratégie gagnante par hypothèse d'induction. Si $\rho \leq +\alpha\boxplus\beta$, alors quel que soit le coup qu'elle fait, elle +arrivera à un $(\alpha,\beta,\rho')$ avec $\rho' < +\alpha\boxplus\beta$ auquel cas Blaise a une stratégie gagnante par +hypothèse d'induction. +\end{corrige} + +{\footnotesize Autrement dit, on a montré que l'addition des « nombres + (surréels) » de Conway coïncide, dans le cas particulier des + ordinaux, avec l'opération $\boxplus$ de somme naturelle.\par} + + +% +% +% + +\exercice + +Soit $n\geq 3$ un entier naturel. On considère le jeu suivant : Alice +et Bob choisissent chacun en secret un entier naturel $0\leq i\leq +n-1$ et le révèlent simultanément. Si les deux nombres sont égaux, la +partie est nulle ; sinon, le gagnant est celui qui a choisi le plus +grand, \emph{sauf} dans le cas où un joueur a choisi $n-1$ et l'autre +joueur a choisi $0$, et alors c'est celui qui a choisi $0$ qui gagne. + +(On considérera qu'un gain apporte une valeur de $+1$ à celui qui +gagne, une perte une valeur de $-1$ à celui qui perd, et qu'une partie +nulle a une valeur de $0$ pour les deux joueurs.) + +(1) De quelle sorte de jeu s'agit-il ? Écrire explicitement sa +matrice de gains dans le cas $n=5$. Pour des raisons de symétrie, +quelle est la valeur du jeu ? + +\begin{corrige} +Il s'agit d'un jeu en forme normale et à somme nulle. Pour $n=5$, la +matrice des gains d'Alice vaut : + +\begin{center} +\begin{tabular}{r|ccccc} +$\downarrow$Alice, Bob$\rightarrow$&${0}$&${1}$&${2}$&${3}$&${4}$\\\hline +${0}$&$0$&$-1$&$-1$&$-1$&$+1$\\ +${1}$&$+1$&$0$&$-1$&$-1$&$-1$\\ +${2}$&$+1$&$+1$&$0$&$-1$&$-1$\\ +${3}$&$+1$&$+1$&$+1$&$0$&$-1$\\ +${4}$&$-1$&$+1$&$+1$&$+1$&$0$\\ +\end{tabular} +\end{center} + +Pour des raisons de symétrie (la matrice étant antisymétrique, +c'est-à-dire que les deux joueurs sont dans la même situation +vis-à-vis du jeu), la valeur du gain vaut $0$. +\end{corrige} + +(2) On considère la stratégie mixte consistant à jouer chacune des +options $0$, $n-2$ et $n-1$ avec probabilité $\frac{1}{3}$ (et jamais +les autres). On l'appellera $s_0$. Si Alice joue selon cette +stratégie $s_0$ et si Bob joue l'option $i$, quel est le gain espéré +d'Alice en fonction de $i$ ? + +\begin{corrige} +Si Bob joue $0$, Alice obtient le gain espéré $\frac{1}{3}(0 + 1 - 1) += 0$. Si Bob joue une option entre $1$ et $n-3$ inclus, Alice obtient +le gain espéré $\frac{1}{3}(-1 + 1 + 1) = \frac{1}{3} > 0$. Si Bob +joue $n-2$, Alice obtient le gain espéré $\frac{1}{3}(-1 + 0 + 1) = +0$. Si Bob joue $n-1$, Alice obtient le gain espéré $\frac{1}{3}(+1 - +1 + 0) = 0$. +\end{corrige} + +(3) Pourquoi $s_0$ est-elle une stratégie optimale ? + +\begin{corrige} +Pour vérifier que $s_0$ est optimale, il s'agit de vérifier qu'elle +réalise au moins la valeur du jeu contre toute option (=stratégie +pure) de l'adversaire. C'est ce qu'on vient de faire puisque la +valeur du jeu est $0$. +\end{corrige} + +(4) Déduire de (2) qu'aucune stratégie optimale ne peut avoir une +option autre que $0$, $n-2$ ou $n-1$ dans son support. (On pourra +faire jouer une telle stratégie contre $s_0$.) + +\begin{corrige} +Si $t$ est une stratégie ayant une autre option que $0$, $n-2$ +et $n-1$ dans son support, les espérances trouvées en (2) montrent que +son espérance de gain contre $s_0$ est strictement négative +(strictement positive pour le joueur qui applique $s_0$, donc +strictement négative pour celui qui applique $t$). Donc $t$ ne peut +pas être optimale. +\end{corrige} + +(5) Montrer que la stratégie $s_0$ décrite en (2) est la seule +stratégie optimale de ce jeu. + +\begin{corrige} +On vient de voir que toute stratégie optimale $s$ a un support inclus +dans $\{0, n-2, n-1\}$. Si on appelle $p_0, p_{-2}, p_{-1}$ les +probabilités respectives de ces options dans $s$, on sait que $s$ doit +avoir une espérance de gain nulle contre $s_0$, donc contre chacune +des options pures $0$, $n-2$ et $n-1$, ce qui donne $p_{-2} = p_{-1}$, +$p_{-1} = p_0$ et $p_0 = p_{-2}$, bref, la seule possibilité est $p_0 += p_{-2} = p_{-1} = \frac{1}{3}$. +\end{corrige} + + +% +% +% +\end{document} |