%% 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}