%% 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{\dur}{\operatorname{dur}}
\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{13 avril 2022}
\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.

\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} : \textcolor{red}{XXX}.

\ifcorrige
Ce corrigé comporte \textcolor{red}{XXX} pages (page de garde incluse).
\else
Cet énoncé comporte \textcolor{red}{XXX} 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 de nim éventuellement transfini.  (On rappelle
qu'il est défini de la manière suivante : une position du jeu est un
tuple $(\alpha_1,\ldots,\alpha_r)$ d'ordinaux, on dit qu'il y a
« $\alpha_i$ bâtonnets sur la ligne $i$ », et un coup consiste à
décroître strictement \emph{un et un seul} des $\alpha_i$, autrement
dit il existe un coup de $(\alpha_1,\ldots,\alpha_r)$ vers
$(\alpha_1,\ldots,\beta,\ldots,\alpha_r)$ où $\beta<\alpha_i$ est mis
à la place de $\alpha_i$.)

Pour chacune des positions suivantes, dire si c'est une position P
(c'est-à-dire gagnante pour le joueur qui vient de jouer) ou N
(c'est-à-dire gagnante pour le joueur qui doit jouer), et, dans ce
dernier cas, donner un coup gagnant possible pour le joueur en
question.

(a) $(1,2,3)$ (autrement dit, une ligne avec $1$ bâtonnet, une ligne
avec $2$, et une ligne avec $3$)

\begin{corrige}
On a $1 = 2^0$ et $2 = 2^1$ et $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ si
bien que $1 \oplus 2 \oplus 3 = 0$ : la valeur de Grundy de la
position est $0$, et c'est donc une position P.
\end{corrige}

(b) $(3,6,9)$

\begin{corrige}
On a $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ et $6 = 2^2 + 2^1 = 2^2 \oplus
2^1$ et $9 = 2^3 + 2^0 = 2^3 \oplus 2^0$ si bien que $3 \oplus 6
\oplus 9 = 2^3 \oplus 2^2 = 2^3 + 2^2 = 12$ : la valeur de Grundy de
la position est $12$, et c'est donc une position N.

Pour trouver un coup gagnant, c'est-à-dire un coup vers une
position P, on cherche à annuler la valeur de Grundy : autrement dit,
on cherche à remplacer le nombre $n$ de bâtonnets d'une ligne par $n
\oplus 12$, et il s'agit donc de trouver une ligne telle que $n \oplus
12 < n$.  On vérifie facilement que la seule possibilité est de
réduire la ligne ayant $9$ bâtonnets à $9 \oplus 12 = 2^2 + 2^0 = 5$
bâtonnets.  Bref, le seul coup gagnant est $(3,6,9) \to (3,6,5)$.
\end{corrige}

(c) $(\omega,\omega2,\omega3)$

\begin{corrige}
En se rappelant que $\omega = 2^{\omega}$, on a $\omega2 =
2^{\omega+1}$ et $\omega3 = 2^{\omega+1} + 2^{\omega}$ en binaire : on
a donc $\omega \oplus (\omega2) \oplus (\omega3) = 0$ : la valeur de
Grundy de la position est $0$, et c'est donc une position P.
\end{corrige}

(d) $(\omega,\omega^2,\omega^3)$

\begin{corrige}
En se rappelant de nouveau que $\omega = 2^{\omega}$, on a $\omega^2 =
2^{\omega2}$ et $\omega^3 = 2^{\omega3}$ en binaire : on a donc
$\omega \oplus \omega^2 \oplus \omega^3 = 2^{\omega3} + 2^{\omega2} +
2^\omega = \omega^3 + \omega^2 + \omega =: \gamma$ : la valeur de
Grundy de la position est $\gamma \neq 0$, et c'est cdonc une
position N.

Comme dans la question (b), on cherche à annuler la valeur de Grundy,
autrement dit remplacer le nombre $\alpha$ de bâtonnets d'une ligne
par $\alpha \oplus \gamma$ (où $\gamma = \omega^3 + \omega^2 +
\omega$, qu'il vaut mieux penser comme $2^{\omega3} \oplus 2^{\omega2}
\oplus 2^\omega$) d'une manière à ce que le résultat soit plus petit.
On vérifie facilement que la seule possibilité est de réduire la ligne
ayant $\omega^3$ bâtonnets à $\omega^3 \oplus \gamma = \omega^2 +
\omega$ bâtonnets.  Bref, le seul coup gagnant est
$(\omega,\omega^2,\omega^3) \to (\omega,\omega^2,\omega^2+\omega)$.
\end{corrige}

(e) $(\omega,\omega^\omega,\omega^{\omega^\omega})$

\begin{corrige}
En se rappelant une fois de plus que $\omega = 2^{\omega}$, on a
$\omega^\omega = (2^\omega)^\omega = 2^{\omega\times\omega} =
2^{\omega^2}$, et $\omega^{\omega^\omega} = (2^\omega)^{\omega^\omega}
= 2^{\omega\times \omega^{\omega}} = 2^{\omega^{1+\omega}} =
2^{\omega^\omega}$.  Le raisonnement est alors exactement analogue à
la question (d) (car la seule chose qui importe dans cette question
ait qu'on ait affaire à trois puissances de $2$ distinctes) : la
valeur de Grundy de la position est $\gamma := 2^{\omega^\omega} +
2^{\omega^2} + 2^\omega = \omega^{\omega^\omega} + \omega^\omega +
\omega \neq 0$ donc c'est une position N, et le seul coup gagnant est
$(\omega,\omega^\omega,\omega^{\omega^\omega}) \to
(\omega,\omega^\omega,\omega^\omega + \omega)$.
\end{corrige}

(f) $(\varepsilon_1, \varepsilon_2, \varepsilon_3)$ où $\varepsilon_0
< \varepsilon_1 < \varepsilon_2 < \varepsilon_3$ sont les quatre
premiers ordinaux\footnote{On peut définir $\varepsilon_{n+1}$ comme
  la limite, c'est-à-dire la borne supérieure, de la suite
  $(u_k)_{k<\omega}$ strictement croissante définie par $u_0 =
  (\varepsilon_n) + 1$ et $u_{k+1} = \omega^{u_k}$, c'est-à-dire $u_1
  = \omega^{(\varepsilon_n) + 1}$ et $u_2 =
  \omega^{\omega^{(\varepsilon_n) + 1}}$, etc., mais on n'aura pas
  besoin de ce fait.}  vérifiant $\varepsilon = \omega^\varepsilon$.

\begin{corrige}
Pour $i \in \{1,2,3\}$ (ou n'importe quel ordinal, en fait), on a
$\varepsilon_i = \omega^{\varepsilon_i} = (2^\omega)^{\varepsilon_i} =
2^{\omega\cdot\varepsilon_i} = 2^{\omega\cdot\omega^{\varepsilon_i}} =
2^{\omega^{1+\varepsilon_i}} = 2^{\omega^{\varepsilon_i}} =
2^{\varepsilon_i}$ (en utilisant au passage le fait, facilement
vérifié, que $1 + \rho = \rho$ quel que soit l'ordinal infini $\rho$).
Le raisonnement est alors exactement analogue aux questions (d) et (e)
(car la seule chose qui importe dans ces questions ait qu'on ait
affaire à trois puissances de $2$ distinctes) : la valeur de Grundy de
la position est $\gamma := 2^{\varepsilon_3} + 2^{\varepsilon_2} +
2^{\varepsilon_1} = \varepsilon_3 + \varepsilon_2 + \varepsilon_1 \neq
0$ donc c'est une position N, et le seul coup gagnant est
$(\varepsilon_1, \varepsilon_2, \varepsilon_3) \to (\varepsilon_1,
\varepsilon_2, \varepsilon_2 + \varepsilon_1)$.
\end{corrige}

(g) Donner un exemple de position N du jeu de nim (de préférence fini)
avec un nombre distinct de bâtonnets sur chaque ligne (i.e., les
$\alpha_i$ sont deux à deux distincts), où il existe strictement plus
qu'un coup gagnant pour le joueur qui doit jouer.  (Pour indication,
ceci est possible à partir de trois lignes de bâtonnets.)

\begin{corrige}
On cherche donc une position $(n_1,n_2,n_3)$ avec trois lignes de
bâtonnets, de valeur de Grundy $g := n_1 \oplus n_2 \oplus n_3$, telle
qu'au moins deux des trois quantités $n_i \oplus g$ soit strictement
inférieure au $n_i$ correspondant (le raisonnement étant expliqué à la
question (b)), en prenant note du fait que $n_1 \oplus g = n_2 \oplus
n_3$ et de façon analogue pour les trois autres.  On cherche donc, par
exemple, à avoir $n_1 \oplus n_3 < n_2$ et $n_1 \oplus n_2 < n_3$.
Ceci n'est pas difficile en prenant par exemple pour $n_1$ une
puissance de $2$ qui existe dans l'écriture binaire de $n_2$ et
de $n_3$ mais telle qu'en enlevant on obtient des nombres strictement
plus petits.  Par exemple, la position $(2,6,7)$ (de valeur de Grundy
$2\oplus 6\oplus 7 = 3 =: g$) admet des coups gagnants vers $(2,5,7)$
ou $(2,6,4)$ ou même $(1,6,7)$.
\end{corrige}


%
%
%

\exercice

Si $G$ est un graphe orienté bien-fondé (qu'on peut considérer comme
l'ensemble des positions d'un jeu combinatoire auquel il ne manque que
l'information, sans pertinence ici, de la position initiale), on
rappelle qu'on a défini la fonction rang
\[
\rk(x) := \sup\nolimits^+\{\rk(y) : y\in\outnb(x)\} = \sup\,\{\rk(y)+1 :
y\in\outnb(x)\}
\]
(en notant $\sup^+ S$ le plus petit ordinal strictement supérieur à
tous les ordinaux de $S$ et $\sup S$ le plus petit ordinal supérieur
ou égal à tous les ordinaux de $S$, et $\outnb(x)$ l'ensemble des
voisins sortants de $x$), et la fonction de Grundy
\[
\gr(x) := \mex\,\{\gr(y) : y\in\outnb(x)\}
\]
(où $\mex S$ désigne le plus petit ordinal qui n'est pas dans $S$),
— ces définitions ayant bien un sens par induction bien-fondée.  La
première mesure en quelque sorte la durée du jeu si les deux joueurs
coopèrent pour le faire durer aussi longtemps que possible, et la
seconde nous donne notamment l'information de quel joueur a une
stratégie gagnante.

On va maintenant définir une fonction qui mesure en quelque sorte la
durée du jeu si le joueur perdant cherche à perdre aussi lentement que
possible tandis que le joueur gagnant cherche à gagner aussi vite que
possible.  Précisément, on pose
\[
\left\{
\begin{array}{ll}
\dur(x) := \sup\,\{\dur(y)+1 : y\in\outnb(x)\}
&\;\;\text{si $\gr(x) = 0$}\\
\dur(x) := \min\,\{\dur(y)+1 : y\in\outnb(x)\text{~et~}\gr(y)=0\}
&\;\;\text{si $\gr(x) \neq 0$}\\
\end{array}
\right.
\]
(où $\min S$ désigne le plus petit ordinal de $S$, si $S$ est un
ensemble non-vide d'ordinaux).

(1) Expliquer pourquoi cette définition a bien un sens (on
prendra garde au fait que $\min\varnothing$ n'est pas défini).

\begin{corrige}
Lorsque $\gr(x) \neq 0$, il existe au moins un voisin sortant $y \in
\outnb(x)$ tel que $\gr(y) = 0$ (car le $\mex$ est la plus petite
valeur exclue: si un tel $y$ n'existait pas, le $\mex$ serait $0$) :
ceci assure que le $\min$ dans la deuxième ligne de la définition
porte toujours sur un ensemble non-vide.

En-dehors de ce fait, la définition ne pose pas de problème : le
$\sup$ d'un ensemble d'ordinaux existe toujours, et la récursivité de
la définition est légitime par induction bien-fondée, c'est-à-dire que
$\dur(x)$ peut faire appel aux valeurs de $\dur(y)$ pour des voisins
sortants $y$ de $x$.  (Le fait de faire appel à $\gr(y)$ n'est pas un
problème car on sait que $\gr$ est bien défini, et la distinction en
cas est légitime de toute manière.)
\end{corrige}

(2) Expliquer rapidement et informellement pourquoi $\dur(x)$
correspond bien à l'explication intuitive qu'on a donnée.

\begin{corrige}
Quand $x$ est une position avec $\gr(x) = 0$, c'est-à-dire une
position P, le joueur qui doit jouer est le joueur perdant (n'ayant
pas de stratégie gagnante) : il joue donc vers une position $y$ le
faisant perdre le plus lentement possible, c'est-à-dire avec $\dur(y)$
aussi grand que possible, d'où la définition $\dur(x) =
\sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ dans ce cas (le $+1$ sert à
compter le coup joué par ce joueur).

Au contraire, lorsque $\gr(x) \neq 0$, c'est-à-dire que $x$ est une
position N, le joueur qui doit jouer est le joueur gagnant : il joue
donc vers une position $y$ le faisant gagner le plus rapidement
possible, c'est-à-dire avec $\dur(y)$ aussi petit que possible parmi
les coups $x\to y$ gagnants, autrement dit ceux pour lesquels $\gr(y)
= 0$, d'où la définition $\dur(x) = \min\,\{\dur(y)+1 :
y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\}$ dans ce cas (le $+1$ sert à
compter le coup joué par ce joueur).
\end{corrige}

(3) Sur le graphe $G$ représenté ci-dessous, calculer chacune des
fonctions $\rk$, $\gr$ et $\dur$ (les lettres servent simplement à
étiqueter les sommets) :

\begin{center}\footnotesize
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (nA) at (0bp,0bp) [draw,circle] {A};
\node (nB) at (0bp,-40bp) [draw,circle] {B};
\node (nC) at (40bp,0bp) [draw,circle] {C};
\node (nD) at (40bp,-40bp) [draw,circle] {D};
\node (nE) at (80bp,0bp) [draw,circle] {E};
\node (nF) at (80bp,-40bp) [draw,circle] {F};
\node (nG) at (120bp,-40bp) [draw,circle] {G};
\draw[->] (nA) -- (nB);
\draw[->] (nA) -- (nC);
\draw[->] (nB) -- (nD);
\draw[->] (nB) to[out=315,in=225] (nG);
\draw[->] (nC) -- (nD);
\draw[->] (nC) -- (nE);
\draw[->] (nD) -- (nF);
\draw[->] (nE) -- (nF);
\draw[->] (nF) -- (nG);
\draw[->] (nE) to[out=0,in=90] (nG);
\end{tikzpicture}
\end{center}

Si on joue à partir du sommet A comme position initiale et que, comme
suggéré dans la définition de $\dur$, le joueur perdant cherche à
perdre aussi lentement que possible tandis que le joueur gagnant
cherche à gagner aussi vite que possible, quelle sera le déroulement
du jeu ?

\begin{corrige}
Les sommets ont été fort sympathiquement étiquetés dans un ordre
compatible avec le rang (tri topologique), c'est-à-dire que chaque
arête pointe vers un sommet situé strictement après dans l'ordre
alphabétique.  On effectue donc les calculs dans l'ordre alphabétique
inversé.  On trouve, pour le rang :

\begin{center}\footnotesize
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (nA) at (0bp,0bp) [draw,circle] {$4$};
\node (nB) at (0bp,-40bp) [draw,circle] {$3$};
\node (nC) at (40bp,0bp) [draw,circle] {$3$};
\node (nD) at (40bp,-40bp) [draw,circle] {$2$};
\node (nE) at (80bp,0bp) [draw,circle] {$2$};
\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
\node (nG) at (120bp,-40bp) [draw,circle] {$0$};
\draw[->] (nA) -- (nB);
\draw[->] (nA) -- (nC);
\draw[->] (nB) -- (nD);
\draw[->] (nB) to[out=315,in=225] (nG);
\draw[->] (nC) -- (nD);
\draw[->] (nC) -- (nE);
\draw[->] (nD) -- (nF);
\draw[->] (nE) -- (nF);
\draw[->] (nF) -- (nG);
\draw[->] (nE) to[out=0,in=90] (nG);
\end{tikzpicture}
\end{center}

Pour la valeur de Grundy :

\begin{center}\footnotesize
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (nA) at (0bp,0bp) [draw,circle] {$0$};
\node (nB) at (0bp,-40bp) [draw,circle] {$1$};
\node (nC) at (40bp,0bp) [draw,circle] {$1$};
\node (nD) at (40bp,-40bp) [draw,circle] {$0$};
\node (nE) at (80bp,0bp) [draw,circle] {$2$};
\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
\node (nG) at (120bp,-40bp) [draw,circle] {$0$};
\draw[->] (nA) -- (nB);
\draw[->] (nA) -- (nC);
\draw[->] (nB) -- (nD);
\draw[->] (nB) to[out=315,in=225] (nG);
\draw[->] (nC) -- (nD);
\draw[->] (nC) -- (nE);
\draw[->] (nD) -- (nF);
\draw[->] (nE) -- (nF);
\draw[->] (nF) -- (nG);
\draw[->] (nE) to[out=0,in=90] (nG);
\end{tikzpicture}
\end{center}

Et pour la fonction $\dur$ (afin de rendre le calcul plus facile à
suivre, on a entouré en double les sommets de valeur de Grundy $0$) :

\begin{center}\footnotesize
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (nA) at (0bp,0bp) [draw,double,circle] {$4$};
\node (nB) at (0bp,-40bp) [draw,circle] {$1$};
\node (nC) at (40bp,0bp) [draw,circle] {$3$};
\node (nD) at (40bp,-40bp) [draw,double,circle] {$2$};
\node (nE) at (80bp,0bp) [draw,circle] {$1$};
\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
\node (nG) at (120bp,-40bp) [draw,double,circle] {$0$};
\draw[->] (nA) -- (nB);
\draw[->] (nA) -- (nC);
\draw[->] (nB) -- (nD);
\draw[->] (nB) to[out=315,in=225] (nG);
\draw[->] (nC) -- (nD);
\draw[->] (nC) -- (nE);
\draw[->] (nD) -- (nF);
\draw[->] (nE) -- (nF);
\draw[->] (nF) -- (nG);
\draw[->] (nE) to[out=0,in=90] (nG);
\end{tikzpicture}
\end{center}

Si on joue à partir de la position A, le premier joueur, appelons-la
Alice, est en position perdante car la valeur de Grundy est nulle, et
va jouer vers C car c'est ce qui maximise la fonction $\dur$ ; son
adversaire, appelons-le Bob, joue alors vers D car c'est le seul coup
gagnant, après quoi Alice joue vers F (seul coup possible) et Bob joue
vers G.
\end{corrige}

(4) Montrer que, dans n'importe quel graphe $G$ bien-fondé, et pour
n'importe quel sommet $x$ de $G$, on a $\dur(x) \leq \rk(x)$.

\begin{corrige}
On montre par induction bien-fondée que $\dur(x) \leq \rk(x)$.  On
peut donc faire l'hypothèse qu'on sait que $\dur(y) \leq \rk(y)$ pour
tout voisin sortant $y \in \outnb(x)$ (hypothèse d'induction).  Dans
le cas où $\gr(x) = 0$, on a $\dur(x) = \sup\,\{\dur(y)+1 :
y\in\outnb(x)\}$, qui est $\leq \sup\,\{\rk(y)+1 : y\in\outnb(x)\}$
par hypothèse d'induction (il est clair qu'augmenter au sens large
tous les éléments d'un ensemble d'ordinaux augmente son $\sup$ au sens
large), et ceci vaut $\rk(x)$ par définition.  Dans le cas où $\gr(x)
\neq 0$, on a $\dur(x) = \min\,\{\dur(y)+1 :
y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \min\,\{\dur(y)+1 :
y\in\outnb(x)\} \leq \sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ de façon
évidente (en notant bien que les $\min$ portent sur des ensembles
non-vides), et pour la même raison que précédemment, ceci est $\leq
\sup\,\{\rk(y)+1 : y\in\outnb(x)\} = \rk(x)$.
\end{corrige}



%
%
%
\end{document}
