%
% $Id: starpzl.tex,v 1.31 2017/04/12 21:27:51 bousch Exp $
%

\documentclass[12pt,reqno,a4paper]{amsart}
\usepackage{amsmath,amssymb,amsthm,eucal,epsf}

% Sauvons des arbres, economisons le papier
\oddsidemargin=0pt \evensidemargin=0pt \topmargin=-38pt
\textwidth=453pt \textheight=690pt

\tolerance=1000 % les mots sont plus longs en francais
% Separer les paragraphes verticalement, sans indentation
%\parindent=0pt \parskip=\smallskipamount
\parskip2pt plus 2pt

%\epsfverbosetrue % pour afficher les tailles des figures

% L'ensemble des entiers naturels
\newcommand\bN{\mathbb N}
% L'ensemble des nombres r\'eels
\newcommand\bR{\mathbb R}
% L'ensemble des quatre colonnes
\newcommand\Enscol{\mathcal C}
% Ensemble des n plus petits entiers naturels
\newcommand\intset[1]{[ #1 ]}
% Support
\newcommand\supp{\operatorname{supp}}
% L'ensemble des nombres "ronds"
\newcommand\roundset{\mathcal R}
% Inf-convolution, et fusion, de deux fonctions
\newcommand\infcv{\mathbin\square}
\newcommand\merge{\mathbin{\wedge\mkern-6mu\wedge}}
% Infimum et Supremum, avec des majuscules
\newcommand\Inf{\mathop{\rm Inf}}
\newcommand\Sup{\mathop{\rm Sup}}
\newcommand\Min{\mathop{\rm Min}}
\newcommand\Max{\mathop{\rm Max}}

\renewcommand\le{\leqslant} \renewcommand\leq{\le}
\renewcommand\ge{\geqslant} \renewcommand\geq{\ge}
\renewcommand\emptyset{\varnothing}

\numberwithin{equation}{section}
\newtheorem{proposition}{Proposition}[section]
\newtheorem{lemme}[proposition]{Lemme}
\newtheorem{theoreme}[proposition]{Th\'eor\`eme}
\renewcommand\proofname{D\'emonstration}

\begin{document}

\title{\bf La tour de Stockmeyer}
\author{Thierry Bousch}
\address{Laboratoire de Math\'ematique (UMR 8628 du CNRS), b\^at.\ 425/430,
  Universit\'e de Paris-Sud, 91405 Orsay Cedex, France}
\email{Thierry.Bousch@math.u-psud.fr}

\date{}

\keywords{Star Tower of Hanoi, Stockmeyer puzzle}

\subjclass[2010]{05C12}


\begin{abstract}
In 1994, Paul Stockmeyer proposed a four-peg variant of the Tower of
Hanoi puzzle, with three exterior pegs surrounding a central peg,
and the restriction that disks can only be moved between an exterior
peg and the central peg. He proved that it is possible to transfer
$N$ disks from an exterior peg to another with $2S_1(N)$ moves,
where $S_1(N)$ denotes the sum of the smallest $N$ integers of the
form $2^a 3^b$, and conjectured that this number could not be
decreased. This is proved in the present article.

\bigskip
\noindent
{\sc R\'esum\'e.}
En 1994, Paul Stockmeyer a propos\'e une variante \`a quatre tiges de la
Tour d'Hano\"\i, avec trois tiges ext\'erieures dispos\'ees en \'etoile
autour d'une tige centrale, et la restriction qu'on ne peut d\'eplacer
les disques qu'entre une tige ext\'erieure et la tige centrale. Il a
d\'emontr\'e qu'on peut transf\'erer $N$ disques d'une tige ext\'erieure
vers une autre en $2S_1(N)$ mouvements, o\`u $S_1(N)$ d\'esigne la somme
des $N$ plus petits entiers de la forme $2^a 3^b$, et conjectur\'e que
ce nombre ne pouvait \^etre diminu\'e. C'est ce que je d\'emontre
dans le pr\'esent article.
\end{abstract}

\maketitle

\renewcommand\contentsname{Table des mati\`eres}
\tableofcontents
%\newpage

\thispagestyle{myheadings}
\font\Rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 77 \Rms (2017), Article~B77d\hfill}
\def\thepage{}

\section{Introduction}

La {\em Tour d'Hano\"\i}, jeu math\'ematique invent\'e par Edouard Lucas
en 1883, a imm\'e\-diatement suscit\'e de nombreuses variantes, certaines
dues \`a Lucas lui-m\^eme. Cependant, la variante la plus naturelle, qui
consiste \`a modifier le nombre de tiges et rien d'autre, n'a \'et\'e
consid\'er\'ee qu'assez tard, vers 1900, par Henry Ernest Dudeney.
Comme dans le probl\`eme original, on doit transf\'erer une ``tour'' de
$N$ disques d'une tige vers une autre, en un minimum de mouvements.
Ce probl\`eme est publi\'e par Dudeney dans \cite{dudeney},
avec une esquisse de solution. Il r\'eappara{\^\i}t en 1939 parmi
les ``advanced problems'' de l'American Mathematical Monthly \cite{stewart1}.
Deux ans plus tard, en 1941, James Sutherland Frame \cite{frame} et
Bonnie Madison Stewart \cite{stewart2} d\'emontrent (ind\'ependamment)
qu'avec $h+2$ tiges ($h\ge1$), il est possible de transf\'erer $N$ disques en
\begin{equation*}
2^{E(0)} + 2^{E(1)} + \cdots + 2^{E(N-1)}
\end{equation*}
mouvements, o\`u $E(n)$ d\'esigne le plus grand entier $p$ tel que
\begin{equation*}
\frac{p(p+1)\cdots(p+h-1)}{h!} \le n,
\end{equation*}
et fournissent une proc\'edure explicite pour cela.

(Comme l'a montr\'e Andreas Hinz \cite{hinz-petr}, cette formule et
cette proc\'edure se trouvent d\'ej\`a en germe dans les \'ecrits de
Dudeney, mais sans rien qui ressemble \`a une d\'emonstration.)

En revanche, Frame et Stewart n'ont pas d\'emontr\'e que ce nombre de
mouvements \'etait le plus petit possible \cite{dunkel}. La minimalit\'e
de ce nombre constitue la {\em Conjecture de Frame--Stewart}, qui est
encore ouverte aujourd'hui, malgr\'e des r\'esultats partiels nombreux et
encourageants~: des exp\'eriences num\'eriques pouss\'ees
\cite{korf-felner}, des minorations du nombre minimum de mouvements
\cite{szegedy,chen-shen,grosu} qui approchent de mieux en mieux la
valeur conjectur\'ee, et la r\'esolution du cas de quatre tiges
\cite{bousch}.

Mais la Tour d'Hano{\"\i} peut \^etre \'etendue dans une autre direction~:
on restreint les mouvements possibles des disques, en imposant que ceux-ci
aient lieu seulement de certaines tiges vers certaines autres. On voudrait,
l\`a encore, une proc\'edure permettant de transf\'erer tous les disques
d'une tige vers une autre avec un minimum de mouvements.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL THIERRY BOUSCH}{\SMALL LA TOUR DE STOCKMEYER}

Ces variantes, avec mouvements restreints, peuvent d\'ej\`a \^etre
pos\'ees avec trois tiges, mais sont surtout int\'eressantes, et
difficiles, avec quatre tiges ou plus \cite{stockmeyer}.
Elles sont m\^eme tellement difficiles que, dans de nombreux cas, on n'a
aucune id\'ee de la strat\'egie optimale pour transf\'erer les disques,
ni du nombre minimum de mouvements. (Ce n'est pas tout \`a fait exact~:
les gens ont eu beaucoup d'id\'ees\dots mais qui ont toutes \'et\'e
r\'efut\'ees par les exp\'eriences num\'eriques~: voir la discussion dans
\cite[sections~2 et~3]{stockmeyer}.)

Paul Stockmeyer propose donc de s'int\'eresser \`a une variante
particuli\`ere, pour laquelle on a une strat\'egie de r\'esolution
qui est conjecturalement optimale, et une formule close pour
le nombre de mouvements correspondant. C'est le ``Star Puzzle''
\cite{stockmeyer}, aussi appel\'e ``Star Tower of Hanoi'' (dans
\cite[pages~251--254]{tohbook}), et qu'on pourrait aussi bien
appeler ``Tour de Stockmeyer''~: sur un plateau
se trouvent quatre tiges, dont trois (les ``tiges ext\'erieures'')
sont dispos\'ees en \'etoile autour d'une tige centrale
(voir Figure \ref{fig-etoile}). Les
disques ne peuvent se d\'eplacer que d'une tige ext\'erieure vers
la tige centrale, ou inversement. A cela s'ajoutent les r\`egles
habituelles de la Tour d'Hano\"\i~: on ne peut d\'eplacer qu'un
disque \`a la fois, d'une tige vers une autre, et sans jamais
poser un disque sur un disque plus petit.

\begin{figure}[htb]
\[ \epsfxsize=300pt \epsfbox{etoile.eps} \]
\caption{La Tour de Stockmeyer (ici avec $5$ disques)}
\label{fig-etoile}
\end{figure}

Dans cette variante, Stockmeyer d\'emontre,
par une strat\'egie de type Frame--Stewart, qu'on peut transf\'erer
$N$ disques d'une tige ext\'erieure vers une autre tige ext\'erieure
en $2S_1(N)$ mouvements, o\`u la fonction $S_1:\bN\to\bN$ est
d\'efinie par la r\'ecurrence
\begin{equation}
S_1(N) = \begin{cases}
\displaystyle \Min_{\mathstrut 0\le M<N} 2S_1(M)
              + \tfrac12 (3^{N-M}\!-1), & \hbox{si $N\ge1$,} \\
\mskip 20mu   0,                        & \hbox{si $N=0$.}
\end{cases}
\label{def-S1}
\end{equation}

En outre, il conjecture
que cette strat\'egie est optimale, c'est-\`a-dire qu'il est
impossible de transf\'erer $N$ disques d'une tige ext\'erieure vers
une autre en moins que $2S_1(N)$ mouvements.

Mais ce n'est pas tout. On sait r\'esoudre cette r\'ecurrence, avec un
r\'esultat remarquable~: comme le montre Stockmeyer, $S_1(N)$
est la somme des $N$ plus petits entiers de la forme $2^a 3^b$.
On a donc bien une formule close pour $S_1$, d'une certaine mani\`ere.
On trouvera des r\'esultats similaires, un peu plus g\'en\'eraux,
dans \cite{chappelon}.
On sait \'egalement calculer l'unique valeur de $M$ qui r\'ealise
le minimum dans \eqref{def-S1}.

Le but du pr\'esent article est de d\'emontrer que l'algorithme de
Stockmeyer est bien optimal, c'est-\`a-dire que toute mani\`ere
de d\'eplacer $N$ disques d'une tige ext\'erieure vers une autre
comporte au moins $2S_1(N)$ mouvements.

\section{Formulation de l'in\'egalit\'e principale}

Fixons tout de suite les notations, et la repr\'esentation du jeu,
en suivant \cite{bousch}.

On note $\bN=\lbrace 0,1,2,\ldots\rbrace$ l'ensemble des entiers
naturels, et pour tout entier naturel $n$, on note $\intset{n}$
l'ensemble des $n$ plus petits entiers naturels,
c.\`a.d.\ $\lbrace 0,1,\ldots,n-1\rbrace$\,;
en particulier $\intset{0}=\emptyset$.
Le symbole de Kronecker $\delta(x,y)$ est d\'efini comme $1$ si $x=y$,
et $0$ sinon; j'utiliserai \'egalement $\bar\delta(x,y)=1-\delta(x,y)$.
On notera $(x)^+$ la partie positive de $x$, c'est-\`a-dire
$\max\lbrace x,0\rbrace$.

L'ensemble des tiges (ou colonnes) sera not\'e
$\Enscol = \lbrace 0,1,2,3 \rbrace$, o\`u $0$ d\'esigne la tige centrale.
Un {\em empilement\/} (de $N$ disques sur $\Enscol$) d\'esigne une
configuration ``autoris\'ee'' du jeu, c'est-\`a-dire n'importe quelle
mani\`ere de r\'epartir les disques entre les tiges, avec
sur chaque tige les disques empil\'es par taille
d\'ecroissante. Un empilement d\'efinit une fonction (quelconque)
$\intset{N}\to\Enscol$, indiquant dans quelle colonne se trouve chaque
disque~: on identifiera l'empilement avec cette fonction.
L'ensemble de tous les empilements de $N$ disques est donc
$\Enscol^{\intset{N}}$.

Chacun des ensembles $\Enscol^{\intset{N}}$ est muni d'une structure de
graphe non-orient\'e~: deux empilements distincts ${\bf u},{\bf v}$ sont
adjacents s'il existe exactement un $k\in\intset{N}$ pour lequel
${\bf u}(k)\ne{\bf v}(k)$, l'un de ces deux nombres \'etant $0$, et de plus
${\bf u}(i)\notin\lbrace {\bf u}(k),{\bf v}(k)\rbrace$
pour tout $i<k$. Ce graphe est connexe, et la distance associ\'ee, not\'ee $d$,
donne le nombre minimum de mouvements pour passer d'un empilement \`a
un autre (en respectant les r\`egles du jeu).

J'aurai souvent \`a consid\'erer des ``multi-distances'' dans
$\Enscol^{\intset{N}}$, c'est-\`a-dire des expressions de la forme
\begin{equation*}
d({\bf u}_0,{\bf u}_1)+d({\bf u}_1,{\bf u}_2)+\cdots
+d({\bf u}_{L-1},{\bf u}_L)
\end{equation*}
(o\`u $L\ge0$), que j'\'ecrirai sous forme abr\'eg\'ee
\begin{equation*}
d({\bf u}_0,{\bf u}_1,\ldots,{\bf u}_L).
\end{equation*}

En effet, ces multi-distances s'interpr\`etent comme la longueur minimum
d'un chemin passant par les configurations
${\bf u}_0,{\bf u}_1,\ldots,{\bf u}_L\,$, dans cet ordre.

Les empilements {\em parfaits\/} (ext\'erieurs), consistant \`a mettre
tous les disques sur une m\^eme tige (ext\'erieure), ne sont pas autre
chose que les fonctions constantes (non nulles) de $\intset{N}$ dans
$\Enscol$.

On d\'efinit
la fonction $S_1:\bN\to\bN$ par la formule \eqref{def-S1}, et
on note $\alpha_1:\bN\to\bN$ ses diff\'erences finies, i.e.
\begin{equation*}
\alpha_1(n) = S_1(n+1) - S_1(n),
\end{equation*}
ce qui permet d'\'ecrire
\begin{equation*}
S_1(n) = \alpha_1(0)+\alpha_1(1)+\cdots+\alpha_1(n-1).
\end{equation*}
Comme le montre Stockmeyer \cite{stockmeyer}, la fonction $\alpha_1$
est le r\'earrangement croissant des nombres $2^a 3^b$, c'est-\`a-dire
l'unique bijection croissante de $\bN$ vers l'ensemble
\begin{equation}
\roundset = \bigl\lbrace 2^a 3^b : a,b\in\bN\rbrace
= \lbrace 1,2,3,4,6,8,9,\ldots\rbrace.
\end{equation}
Comme $\roundset$ est un mono{\"\i}de multiplicatif,
la fonction $\alpha_1$ satisfait
$\alpha_1(m+n)\le\alpha_1(m)\,\alpha_1(n)$
pour tous $m,n$. En particulier, on a toujours
\begin{equation}
\alpha_1(n) < \alpha_1(n+1) \le 2 \alpha_1(n).
\label{croissance-alpha1}
\end{equation}
Voici les premi\`eres valeurs des fonctions $S_1$ et $\alpha_1$~:
\begin{equation*}
\begin{array}{c|ccccccccccccccc}
N           & 0 & 1 & 2 & 3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 &  11 &  12 &  13 &  14 \\ \hline
S_1(N)      & 0 & 1 & 3 & 6 & 10 & 16 & 24 & 33 & 45 & 61 & 79 & 103 & 130 & 162 & 198 \\ \hline
\alpha_1(N) & 1 & 2 & 3 & 4 &  6 &  8 &  9 & 12 & 16 & 18 & 24 &  27 &  32 &  36 &  48
\end{array}
\end{equation*}
La fonction $\alpha_1$ est la suite A3586 dans OEIS \cite{sloane};
voir aussi la suite A71521.
Le nombre $N(x)$ d'entiers $\le x$ de la forme $2^a 3^b$ satisfait,
d'apr\`es Ramanujan et Pillai,
\begin{equation*}
N(x) = \frac{\log(2x)\log(3x)}{2\log 2 \log 3} + o(\log x)
\end{equation*}
pour $x$ grand (voir \cite[section~6]{moree}), ce qui entra{\^\i}ne,
pour $n$ grand,
\begin{equation*}
\log \alpha_1(n) = \sqrt{2n\log2\log3} - \tfrac12 \log 6 + o(1),
\end{equation*}
et fournit les \'equivalents
\begin{equation}
\alpha_1(n)\ \sim\ \frac{1}{\sqrt6} \,\exp \sqrt{2n\log2\log3}
\end{equation}
et
\begin{equation}
S_1(n)\ \sim\ \sqrt{\frac{n}{3\log2\log3}} \ \exp \sqrt{2n\log2\log3}
\end{equation}
Pour comparaison, on sait que le nombre minimum de mouvements dans le
{\it Reve's Puzzle} est approximativement $\sqrt{n}\,2^{\sqrt{2n}}$, mais
cette approximation n'est {\em pas\/} un \'equivalent~: voir la
discussion dans \cite[section~1]{stockmeyer}.

Il sera commode d'inclure $S_1$ dans une famille $S_0,S_1,S_2,\ldots$ de
fonctions, de la mani\`ere suivante~: pour tout entier naturel
$L\ne1$, on d\'efinit la fonction $S_L:\bN\to\bN$ par
\begin{equation}
S_L(N) = \Min_{0\le M\le N} 2S_1(M) + \tfrac{1}{2} L\,(3^{N-M}\!-1).
\label{def-SL}
\end{equation}
Notons que cette formule reste valable pour $L=1$, ce qui justifie qu'on
consid\`ere $S_1$ (d\'ej\`a d\'efinie) comme faisant partie de la famille.
Puis, on d\'efinit les fonctions $\alpha_L:\bN\to\bN$ comme les diff\'erences
finies des $S_L$~:
\begin{equation}
\alpha_L(n) = S_L(n+1) - S_L(n),
\label{def-alpha-L}
\end{equation}
ce qui permet d'\'ecrire
\begin{equation}
S_L(n) = \alpha_L(0)+\alpha_L(1)+\cdots+\alpha_L(n-1).
\end{equation}

Voici les premi\`eres valeurs des fonctions $S_L$ et $\alpha_L$~:
\begin{equation*}
\begin{array}{c|cccccccccccc}
N      & 0 & 1 & 2 &  3 &  4 &  5 &  6 &  7 &  8 &  9 &  10 &  11  \\
\hline
S_0(N) & 0 & 0 & 0 &  0 &  0 &  0 &  0 &  0 &  0 &  0 &   0 &   0  \\
S_1(N) & 0 & 1 & 3 &  6 & 10 & 16 & 24 & 33 & 45 & 61 &  79 & 103  \\
S_2(N) & 0 & 2 & 4 &  8 & 14 & 20 & 28 & 40 & 56 & 74 &  92 & 116  \\
S_3(N) & 0 & 2 & 5 &  9 & 15 & 23 & 32 & 44 & 60 & 78 & 102 & 129  \\
S_4(N) & 0 & 2 & 6 & 10 & 16 & 24 & 36 & 48 & 64 & 82 & 106 & 138  \\
S_5(N) & 0 & 2 & 6 & 11 & 17 & 25 & 37 & 52 & 68 & 86 & 110 & 142
\end{array}
\end{equation*}
%
\begin{equation*}
\begin{array}{c|cccccccccccc}
N           & 0 & 1 & 2 & 3 & 4 &  5 &  6 &  7 &  8 &  9 & 10 & 11  \\
\hline
\alpha_0(N) & 0 & 0 & 0 & 0 & 0 &  0 &  0 &  0 &  0 &  0 &  0 &  0  \\
\alpha_1(N) & 1 & 2 & 3 & 4 & 6 &  8 &  9 & 12 & 16 & 18 & 24 & 27  \\
\alpha_2(N) & 2 & 2 & 4 & 6 & 6 &  8 & 12 & 16 & 18 & 18 & 24 & 32  \\
\alpha_3(N) & 2 & 3 & 4 & 6 & 8 &  9 & 12 & 16 & 18 & 24 & 27 & 32  \\
\alpha_4(N) & 2 & 4 & 4 & 6 & 8 & 12 & 12 & 16 & 18 & 24 & 32 & 36  \\
\alpha_5(N) & 2 & 4 & 5 & 6 & 8 & 12 & 15 & 16 & 18 & 24 & 32 & 36
\end{array}
\end{equation*}

On observe sur cette table que les $\alpha_L(N)$ sont des nombres
``friables'', c'est-\`a-dire sans grands diviseurs premiers.
On constate aussi que la ligne donnant les valeurs de $\alpha_L$
s'obtient en intercalant les nombres $L,3L,9L,\ldots$ entre les valeurs
de $2\alpha_1$; je donnerai plus bas, en \eqref{alpha-L-merge},
un \'enonc\'e pr\'ecis (et une preuve) de cette propri\'et\'e.

Comme dans \cite{bousch}, la strat\'egie consiste \`a d\'emontrer,
par r\'ecurrence sur le nombre de disques $N$, des minorations sur
la fonction distance dans le graphe $\Enscol^{\intset{N}}$.
On montrera notamment que
\begin{equation}
d({\bf u},{\bf v}) \,\ge\, 2 S_1(N)
- \mkern -6mu \sum_{\substack{k\in\intset{N}\\{\bf u}(k)\ne1}}
    \mkern -6mu 2\alpha_1(k)
- \mkern -6mu \sum_{\substack{k\in\intset{N}\\{\bf v}(k)\ne3}}
    \mkern -6mu 2\alpha_1(k)
\label{minor-dist-simple}
\end{equation}
pour ${\bf u},{\bf v}:\intset{N}\to\Enscol$ deux empilements quelconques.

En particulier, en prenant pour ${\bf u},{\bf v}$ les empilements
parfaits sur les tiges $1$ et $3$, il vient $d({\bf u},{\bf v})\ge 2
S_1(N)$, et, comme on sait, d'apr\`es Stockmeyer, construire un chemin de
cette longueur, on en d\'eduit le
r\'esultat annonc\'e dans le R\'esum\'e.

Le chemin construit par Stockmeyer est donc bien un chemin
g\'eod\'esique entre $\bf u$ et $\bf v$, quel que soit $N$, comme cela
\'etait conjectur\'e. Mais il ne faudrait pas \^etre tent\'e de croire
que c'est le seul~: en g\'en\'eral, ce ne sera pas le cas. Par exemple,
avec trois disques, il existe deux chemins g\'eod\'esiques,
c'est-\`a-dire deux mani\`eres optimales de transporter une tour de
trois disques d'une tige ext\'erieure vers une autre.

Pour \'etablir l'in\'egalit\'e \eqref{minor-dist-simple},
nous devrons faire un d\'etour
et prouver des in\'egalit\'es plus g\'en\'erales, sur les
multi-distances ``alternantes''. Elles apparaissent dans la
d\'ecomposition d'une distance ordinaire $d({\bf u},{\bf v})$, ou
d'une autre multi-distance alternante, en fonction des mouvements du plus
grand disque.

Voici comment~: soient ${\bf u},{\bf v}$ les configurations parfaites
de $N$ disques sur les tiges $1,3$ (o\`u $N\ge1$), ou plus
g\'en\'eralement, n'importe quel couple d'empilements
$\intset{N}\to\Enscol$ tel que ${\bf u}(N-1)=1$ et ${\bf v}(N-1)=3$.
Dans un chemin
g\'eod\'esique $\gamma$ allant de $\bf u$ vers $\bf v$, le plus grand
disque doit aller de la tige $1$ \`a la tige $3$.
Le premier mouvement de ce disque sera de la tige $1$ vers la tige $0$,
mais ceci n'est possible que si tous les autres disques ont \'et\'e
pr\'ealablement d\'eplac\'es vers les colonnes $2$ et $3$. De m\^eme,
le dernier mouvement du plus grand disque sera de la tige $0$ vers la
tige $3$, ce qui n\'ecessite qu'\`a cet instant, tous les autres disques
soient dans les colonnes $1$ et $2$. La longueur de $\gamma$ est alors
\begin{align*}
d({\bf u},{\bf v})
&= d({\bf u}_0,{\bf u}_1)+d({\bf u}_1,{\bf u}_2)+d({\bf u}_2,{\bf u}_3)
     + d({\bf u}_3,{\bf u}_4)+d({\bf u}_4,{\bf u}_5) \\
&= 2 + d({\bf u}',{\bf u}'_1) + d({\bf u}'_1,{\bf u}'_4)
     + d({\bf u}'_4,{\bf v}')
\end{align*}
(voir Figure~\ref{fig-sldist})
o\`u les ${\bf u}'_i$ sont les empilements de $N-1$ disques obtenus en
``oubliant'' la position du plus grand disque.
Dans ce calcul, j'ai utilis\'e le fait que
$d({\bf x},{\bf y})=d({\bf x}',{\bf y}')$ si, dans les configurations
${\bf x},{\bf y}$, le plus grand disque est sur la m\^eme tige.

\begin{figure}[htb]
\[ \epsfxsize=450pt \epsfbox{sldist.eps} \]
\caption{D\'ecomposition d'une distance}
\label{fig-sldist}
\end{figure}

Le probl\`eme du calcul d'une distance $d({\bf u},{\bf v})$ sur $N$
disques se ram\`ene ainsi au probl\`eme de minimiser la multi-distance
\begin{equation*}
 d({\bf u}',{\bf s},{\bf t},{\bf v}') =
 d({\bf u}',{\bf s}) + d({\bf s},{\bf t}) + d({\bf t},{\bf v}')
\end{equation*}
sur tous les couples $({\bf s},{\bf t})$ d'\'el\'ements de
$\Enscol^{\intset{N-1}}$ pour lesquels $\supp({\bf s})\subseteq
\lbrace 2,3\rbrace$ et $\supp({\bf t})\subseteq
\lbrace 1,2\rbrace$.
Nous avons ainsi \'etabli le lemme suivant.

\begin{lemme}
Soient ${\bf u},{\bf v}:\intset{N}\to\Enscol$ des empilements de
$N$ disques (o\`u $N\ge1$) pour lesquels ${\bf u}(N-1)=1$ et
${\bf v}(N-1)=3$.
Il existe alors ${\bf s},{\bf t}:\intset{N-1}\to\Enscol$,
empilements de $N-1$ disques v\'erifiant
$\supp({\bf s})\subseteq\lbrace 2,3\rbrace$ et
$\supp({\bf t})\subseteq\lbrace 1,2\rbrace$, et tels que
\begin{equation*}
d({\bf u},{\bf v}) = 2 + d({\bf u}',{\bf s},{\bf t},{\bf v}').
\end{equation*}
\label{lemme-decomposition}
\end{lemme}

J'utiliserai par la suite une notation diagrammatique plus compacte que
celle de la Figure~\ref{fig-sldist}~: chaque configuration de $N-1$
disques (et non plus $N$) est repr\'esent\'ee verticalement, par un
empilement de quatre cases repr\'esentant les quatre tiges, de $0$ (en
haut) jusqu'\`a $3$ (en bas). Un chiffre dans la case correspondante
signifie que la tige peut contenir des disques. Les configurations
provenant de la troncature d'une configuration originale de $N$ disques
(ici ${\bf u}'$ et ${\bf v}'$) seront dessin\'ees en noir, et on
rappelera la position du disque $N-1$, si elle est connue, par un
octogone dans la case correspondante. Les autres configurations,
provenant de la d\'ecomposition donn\'ee par le lemme ci-dessus (ici
${\bf s}$ et ${\bf t}$) seront dessin\'ees en gris.
Comme pr\'ec\'edemment, on \'ecrit de gauche \`a droite les
configurations qui se succ\`edent au cours du temps.

\[ \epsfxsize=160pt \epsfbox{decompos.eps} \]

Plus g\'en\'eralement, une multi-distance $d({\bf u}_0,{\bf u}_1,
\ldots,{\bf u}_L)$ entre deux empilements ${\bf u}_0,{\bf u}_L$
sera appel\'ee {\em alternante\/}
si les empilements interm\'ediaires ${\bf u}_k$, avec $0<k<L$,
satisfont $\supp({\bf u}_k)\subseteq\lbrace2,3\rbrace$ pour
$k$ impair et $\subseteq\lbrace1,2\rbrace$ pour $k$ pair.
Au besoin, on s'autorisera \`a renum\'eroter les tiges ext\'erieures.
Il n'y a aucune contrainte sur les empilements
extr\^emes ${\bf u}_0,{\bf u}_L$.
L'alternance sera repr\'esent\'ee, comme ci-dessus, par un ``serpent'' gris
qui alterne entre les tiges $1$ et $3$.

On cherche \`a minorer une telle multi-distance alternante par une expression
qui ne d\'epende que de ${\bf u}_0$ et ${\bf u}_L$, ce qui revient
implicitement \`a minimiser sur tous les
empilements interm\'ediaires possibles, avec les contraintes de
support ci-dessus.

Il sera commode pour la suite de d\'efinir la colonne
\begin{equation}
{\mathsf p}_k = 2-(-1)^k =
\begin{cases}
1, & \text{si $k$ est pair,} \\
3, & \text{si $k$ est impair,}
\end{cases}
\end{equation}
\'el\'ement de $\Enscol$ qui donne les positions successives du ``serpent'',
et de noter ${\mathsf p}_k^N$ la configuration parfaite correspondante.

Consid\'erons d'abord le cas o\`u les configurations extr\^emes
sont les empilements parfaits ${\bf u}_0 = {\mathsf p}_0^N$ et
${\bf u}_L = {\mathsf p}_L^N$. On veut construire un chemin
``alternant'' de ${\bf u}_0$ vers ${\bf u}_L$, c'est-\`a-dire
passant par des configurations interm\'ediaires ${\bf u}_k$
de support $\subseteq\lbrace 2,{\mathsf p}_k\rbrace$, et aussi court que
possible. Pour $N\ge1$, on peut construire un tel chemin
en s'inspirant de la proc\'edure de Frame--Stewart~:
on choisit d'abord un entier $M<N$. Puis, on d\'eplace les $M$
plus petits disques de la colonne ${\mathsf p}_0=1$ vers la colonne $2$.
Ensuite, on d\'eplace $L$ fois les $N-M$ plus grands
disques alternativement entre les colonnes $1$ et $3$, ce qui produit
les configurations interm\'ediaires ${\bf u}_1,\ldots,{\bf u}_{L-1}$,
et enfin, on d\'eplace les $M$ plus petits disques de la colonne $2$
vers la colonne ${\mathsf p}_L$.
On obtient ainsi un chemin de longueur
\begin{equation*}
 4S_1(M) + L\,(3^{N-M}\!-1),
\end{equation*}
et donc $2S_L(N)$, si $M$ est bien choisi.
Est-il possible de faire mieux? Par analogie avec la conjecture de
Frame--Stewart, il para{\^\i}t naturel de penser que non. On aurait
alors la minoration suivante, pour les multi-distances alternantes
entre configurations parfaites~:
\begin{equation}
d({\bf u}_0,{\bf u}_1,\ldots,{\bf u}_L) \ge 2 S_L(N)
\label{min-mda-par}
\end{equation}
si ${\bf u}_0={\mathsf p}_0^N$, ${\bf u}_L = {\mathsf p}_L^N$, et
$\supp({\bf u}_k)\subseteq\lbrace 2,{\mathsf p}_k\rbrace$ pour $0<k<L$.
Voil\`a qui explique l'apparition des fonctions $S_L$, et
non pas seulement $S_1$, dans l'\'etude de la tour de Stockmeyer.

Il reste \`a \'etendre cette in\'egalit\'e conjecturale \`a des
configurations ${\bf u}_0,{\bf u}_L$ quelconques. Pour cela, comme
dans \cite{bousch}, on retranche au second membre une ``p\'enalit\'e''
$\beta(k)$ pour chaque disque $k$ situ\'e ``imparfaitement''
au d\'epart ou \`a l'arriv\'ee~:
\begin{equation}
d({\bf u}_0,{\bf u}_1,\ldots,{\bf u}_L) \,\ge\, 2 S_L(N)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N} \\ {\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern -14mu \beta(k)
- \mkern -15mu
  \sum_{\substack{k\in\intset{N} \\ {\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern -15mu \beta(k).
\label{min-mda-gen}
\end{equation}

J'expliquerai en \S~5 comment choisir les $\beta(k)$,
mais pour le moment, je donne simplement le th\'eor\`eme principal,
sans autre commentaire.

\begin{theoreme}
Soient $N,L$ deux entiers naturels, et ${\bf u}_0, {\bf u}_1, \ldots,
{\bf u}_L:\intset{N}\to\Enscol$ des empilements de $N$ disques v\'erifiant
$\supp({\bf u}_k)\subseteq\lbrace 2,{\mathsf p}_k\rbrace$ pour
$0<k<L$. Alors
\begin{equation*}
d({\bf u}_0,{\bf u}_1,\ldots,{\bf u}_L) \,\ge\, 2 S_L(N)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N} \\ {\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern -14mu \beta(k)
- \mkern -15mu
  \sum_{\substack{k\in\intset{N} \\ {\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern -15mu \beta(k),
\end{equation*}
o\`u on a pos\'e
\begin{equation*}
\beta(k) =
\begin{cases}
\alpha_L(k),  & \text{si\/ $k=N-1$ et\/ $L\ge2$,} \\
2\alpha_1(k), & \text{sinon.}
\end{cases}
\end{equation*}
\label{theoreme-principal}
\end{theoreme}

On verra un peu plus bas que $\alpha_L\le 2\alpha_1$, et donc
les p\'enalit\'es $\beta(k)$ v\'erifient
toujours $\alpha_L(k)\le\beta(k)\le 2\alpha_1(k)$.
Notons \'egalement que pour $L=1$, le th\'eor\`eme se r\'eduit
\`a l'in\'egalit\'e \eqref{minor-dist-simple}.
On d\'emontrera le th\'eor\`eme en \S~4, mais d'abord,
\'etablissons quelques r\'esultats pr\'eliminaires
sur les $S_L$ et $\alpha_L$.

\section{Quelques propri\'et\'es des fonctions $S_L$}

Les nombres $S_L(N)$ satisfont cinq propri\'et\'es essentielles~:
\begin{enumerate}
\item[(i)] $S_L(N)$ est croissant en $L$ et $N$\,;
\item[(ii)] $S_L(N)$ est convexe%
\footnote{Une fonction $f:\bN\to\bR$ est dite convexe (respectivement concave),
au sens discret, si ses diff\'erences finies $\Delta f(x)=f(x+1)-f(x)$
forment une fonction croissante (respectivement d\'ecroissante); ou, ce qui est
\'equivalent, si $f$ est la restriction d'une fonction $\bR\to\bR$
convexe (respectivement concave), au sens usuel.}
en $N$ (pour $L$ fix\'e);
\item[(iii)] $S_L(N)$ est concave en $L$ (pour $N$ fix\'e);
\item[(iv)] $S_L(N)$ est sur-modulaire en le couple $(L,N)$, i.e.
\begin{equation*}
S_L(N) + S_{L+1}(N+1) \,\ge\, S_L(N+1) + S_{L+1}(N)
\end{equation*}
pour tous $L,N$.
\item[(v)] Pour tout $N$ fix\'e, $S_L(N)\to 2S_1(N)$ quand $L\to\infty$.
\end{enumerate}

La propri\'et\'e (ii) revient \`a dire que $\alpha_L(N)$ est croissant
en $N$ (pour $L$ fix\'e), et la propri\'et\'e (iv) revient \`a dire
que $\alpha_L(N)$ est croissant en $L$ (pour $N$ fix\'e).

La d\'efinition \eqref{def-SL} entra{\^\i}ne imm\'ediatement que
pour tout $N$ fix\'e,
$S_L(N)$ est croissant et concave en $L$, et tend
vers $2S_1(N)$ quand $L\to\infty$, ce qui
d\'emontre (iii), (v), et la premi\`ere partie de (i).
Il reste \`a \'etablir (ii) et (iv), ainsi que la deuxi\`eme
partie de (i), c'est-\`a-dire montrer
que les $\alpha_L(N)$ sont croissants en $L$ et $N$, et positifs.

{\it Inf-convolution.}
\'Etant donn\'e deux fonctions $f,g:\bN\to\bR$,
leur {\em inf-convolution\/} $f\infcv g$ est d\'efinie comme
la plus grande fonction $h:\bN\to\bR$
telle que $h(m+n)\le f(m)+g(n)$ pour tous $m,n$.
Concr\`etement, elle est donn\'ee par la formule
\begin{equation}
(f\infcv g)\,(n)\, = \Min_{0\le m\le n} f(m)+g(n-m)
\end{equation}
pour tout $n$ entier naturel.
Comme l'inf-convolution classique (c'est-\`a-dire sur $\bR$ ou $\bR^N$,
voir par exemple~\cite{rockafellar}), cette op\'eration est
particuli\`erement int\'eressante en restriction aux fonctions
convexes (au sens discret, ici).

{\it Fusion.}
\'Etant donn\'e deux suites finies tri\'ees, c'est-\`a-dire deux entiers
naturels $m,n$ et deux fonctions croissantes $f:\intset{m}\to\bR$ et
$g:\intset{n}\to\bR$, on peut d\'efinir leur ``fusion'' $f\merge g$
comme la fonction $\intset{m+n}\to\bR$ qui est le r\'earrangement
croissant de la suite
$f(0),f(1),\ldots,f(m-1),g(0),g(1),\ldots,g(n-1)$.
Cette op\'eration intervient dans l'algorithme ``merge sort''
(tri par fusion), voir \cite[\S~5.2.4]{knuth}.
Avec quelques pr\'ecautions, on peut \'etendre cette op\'eration
\`a des suites tri\'ees infinies, c'est-\`a-dire des fonctions
croissantes $\bN\to\bR$. Je laisse au lecteur le soin de
d\'emontrer le r\'esultat suivant.

\begin{lemme}
Soient $f,g:\bN\to\bR$ deux fonctions croissantes quelconques.
Il existe exactement une fonction $h:\bN\to\bR$ ayant la propri\'et\'e
suivante~: pour tout $n\ge1$, les $n$ premiers termes du r\'earrangement
croissant de la suite
\begin{equation*}
f(0), f(1), \ldots, f(n-1), g(0), g(1), \ldots, g(n-1)
\end{equation*}
sont \'egaux \`a $h(0),h(1),\ldots,h(n-1)$ respectivement.

En outre, cette fonction est croissante.
\end{lemme}

Cette fonction sera appel\'ee {\em fusion\/} de $f$ et $g$,
et not\'ee $f\merge g$. Par exemple,
\begin{equation*}
(0,1,2,3,4,\ldots) \merge (0,2,4,6,8,\ldots) =
(0,0, 1, 2,2, 3, 4,4, 5,\ldots)
\end{equation*}

Une autre caract\'erisation de la fusion utilise
les fonctions de r\'epartition~: si $f:\bN\to\bR$ est une fonction
croissante, d\'efinissons sa fonction de r\'epartition
${\mathsf R}f:\bR\to\bN\cup\lbrace+\infty\rbrace$ par
\begin{equation*}
({\mathsf R}f)(x) = {\rm Card}\lbrace n\in\bN: f(n)<x \rbrace
= \Inf \lbrace n\in\bN: f(n)\ge x \rbrace \,;
\end{equation*}
alors $h=f\merge g$ est l'unique fonction croissante pour laquelle
${\mathsf R}h = {\mathsf R}f + {\mathsf R}g$.

De la caract\'erisation de $f\merge g$ donn\'ee par le lemme,
on d\'eduit facilement des formules explicites, comme celle-ci~:
\begin{equation}
(f\merge g)(n)\, = \Max_{0\le m\le n} \min\bigl\lbrace f(m),g(n-m)\bigr\rbrace
\end{equation}
pour tout $n$ entier naturel.

Le lemme pr\'ec\'edent implique aussi que, pour tout entier naturel $n$,
la somme des $n$ premi\`eres valeurs de $h=f\merge g$ est major\'ee par
\begin{equation*}
f(0)+f(1)+\cdots+f(m-1)+g(0)+g(1)+\cdots+g(n-m-1)
\end{equation*}
pour tout entier $m$ entre $0$ et $n$, avec \'egalit\'e pour au moins un $m$.
Autrement dit, la fonction
$n\mapsto\!\sum\limits_{k<n} h(k)$ est l'inf-convolution des fonctions
$n\mapsto\!\sum\limits_{k<n} f(k)$ et $n\mapsto\!\sum\limits_{k<n} g(k)$.
Un \'enonc\'e \'equivalent est le suivant (en notant, comme plus haut,
$\Delta$ l'op\'erateur de diff\'erence finie sur les fonctions).

\begin{lemme}
Pour $f,g:\bN\to\bR$ des fonctions convexes quelconques, on a
\begin{equation*}
\Delta\,(f\infcv g) = (\Delta f) \merge (\Delta g).
\end{equation*}
En particulier, $f\infcv g$ est convexe.
\end{lemme}

Revenons aux fonctions $S_L$. La formule \eqref{def-SL} les d\'efinit par
\begin{equation}
S_L = (2S_1) \infcv (L\Gamma),
\end{equation}
o\`u $\Gamma$ est la fonction (convexe) d\'efinie par $\Gamma(n)=(3^n-1)/2$,
et on sait d'autre part que $S_1$ est convexe (c'est-\`a-dire que
$\alpha_1$ est croissante). Il en r\'esulte, par le
lemme ci-dessus, que toutes les fonctions $S_L$ sont convexes, et la
propri\'et\'e (ii) est \'etablie. Leurs diff\'erences finies
sont donn\'ees par
\begin{equation}
\alpha_L = (2\alpha_1) \merge (L\gamma),
\label{alpha-L-merge}
\end{equation}
o\`u $\gamma$ est la fonction (croissante) donn\'ee par
$\gamma(n)=\Gamma(n+1)-\Gamma(n)=3^n$.
Mais il est clair par ailleurs que l'op\'eration $\merge$ est croissante
en ses deux arguments (pour l'ordre usuel sur les fonctions), et donc,
que la fonction $\alpha_L$ d\'epend de fa\c con croissante de $L$. Cela
\'etablit la propri\'et\'e (iv). Enfin, les fonctions $\alpha_L$ sont
visiblement positives, ce qui prouve la deuxi\`eme partie de (i).

Ceci termine la d\'emonstration des propri\'et\'es de base des $S_L(N)$
et $\alpha_L(N)$.

On peut les combiner~: par exemple, les fonctions $\alpha_L:\bN\to\bN$
forment une suite croissante qui converge simplement vers $2\alpha_1$,
ce qui montre que $\alpha_L\le 2\alpha_1$ pour tout $L$. On a aussi
$S_L\le 2S_1$, par le m\^eme argument.
Voici maintenant quelques autres propri\'et\'es des $S_L$ et $\alpha_L$,
de moindre importance.

\begin{lemme}
Pour tous $m,k$ entiers naturels, on a l'in\'egalit\'e
\begin{equation*}
\alpha_1(m+k+1)-\alpha_1(m) \ge
\Min \bigl\lbrace 3^k,\alpha_1(m) \bigr\rbrace\,.
\end{equation*}
En particulier, $\alpha_1(m) \ge 3^k$ implique
$\alpha_1(m+k+1)-\alpha_1(m) \ge 3^k$.
\label{augment-alpha}
\end{lemme}

\begin{proof}
Un \'enonc\'e \'evidemment \'equivalent est le suivant~:
pour tous $m,n,k$ entiers naturels tels que $n-m>k$, on a
$\alpha_1(n)-\alpha_1(m) \ge
\Min \bigl\lbrace 3^k,\alpha_1(m) \bigr\rbrace$.
Supposons que cet \'enonc\'e soit faux, et consid\'erons un
contre-exemple, c'est-\`a-dire un triplet $(m,n,k)$
d'entiers naturels v\'erifiant
\begin{equation*}
n-m>k, \quad
\alpha_1(n)-\alpha_1(m)<3^k, \quad
\alpha_1(n) < 2\alpha_1(m),
\end{equation*}
avec $k$ minimal.

Remarquons que $k$ ne peut pas \^etre nul, car $\alpha_1$ est
strictement croissante, et donc $k\ge1$. L'ensemble
\begin{equation*}
B = \bigl\lbrace \alpha_1(m),\alpha_1(m+1),\ldots,\alpha_1(n) \bigr\rbrace
\end{equation*}
est un sous-ensemble de $\mathcal R$ de cardinal au moins $k+2$, et il
contient au plus une puissance de $2$ car $\alpha_1(n)<2\alpha_1(m)$.
Or, tout \'el\'ement de $\mathcal R$ qui n'est pas une puissance de $2$ est
le triple d'un autre \'el\'ement de $\mathcal R$~: on peut donc \'ecrire
$B\supseteq 3A$ pour un certain sous-ensemble $A$ de $\mathcal R$ de
cardinal $k+1$.

Notons $\alpha_1(m')$ et $\alpha_1(n')$ le plus petit et le plus grand
\'el\'ement de $A$. On a
$\alpha_1(m) \le 3\alpha_1(m') \le 3\alpha_1(n') \le \alpha_1(n)$
et d'autre part $n'-m'\ge k$ puisque $A$ est de cardinal $k+1$, donc
\begin{equation*}
n'-m' > k-1, \quad
\alpha_1(n')-\alpha_1(m') < 3^{k-1}, \quad
\alpha_1(n') < 2\alpha_1(m'),
\end{equation*}
c'est-\`a-dire que le triplet $(m',n',k-1)$ serait un autre
contre-exemple, contredisant l'hypoth\`ese de minimalit\'e de $k$.
\end{proof}

La conclusion du Lemme~\ref{augment-alpha} 
est \`a rapprocher d'un r\'esultat de Mintz
\cite{mintz}, qui affirme que $\alpha_1(m)=3^k$ implique
$\alpha_1(m+k+1)=2\cdot 3^k$.

\begin{lemme}
On a l'in\'egalit\'e
\begin{equation*}
S_{L+1}(N+1) - S_L(N) \le 2\alpha_1(N)
\end{equation*}
pour tout $N$ entier naturel et $L\ge2$.
\label{lemme-augm-LN}
\end{lemme}

Pour $L=1$, cette in\'egalit\'e est probablement encore vraie, mais
ne peut pas se d\'emontrer par les m\^emes m\'ethodes, et de toute
fa\c con, je n'en aurai pas besoin.

\begin{proof}
Donnons-nous $N\ge0$ et $L\ge2$, et soit $M$ un entier entre $0$ et $N$
r\'ealisant le minimum dans la formule \eqref{def-SL}. On a donc
\begin{align*}
S_L(N) &= 2 S_1(M) + \tfrac12 L\,(3^{N-M}\!-1), \\
S_{L+1}(N+1)& \le 2 S_1(M+1) + \tfrac12 (L+1)(3^{N-M}\!-1),
\end{align*}
et par cons\'equent
\begin{equation*}
S_{L+1}(N+1)-S_L(N) \le 2\alpha_1(M) + \tfrac12(3^{N-M}\!-1).
\end{equation*}
Il suffit donc, pour prouver le lemme, de d\'emontrer que
\begin{equation}
\alpha_1(N)-\alpha_1(M) \ge \tfrac14(3^{N-M}\!-1).
\label{cond-diff-alpha}
\end{equation}
Pour $M=N$, cette condition est trivialement satisfaite.
Supposons donc $M<N$. L'expression sous le minimum dans \eqref{def-SL}
est, par hypoth\`ese, plus petite pour $M$ que pour $M+1$~:
\begin{equation*}
2 S_1(M) + \tfrac12 L\,(3^{N-M}\!-1) \le 2 S_1(M+1) + \tfrac12 L\,(3^{N-M-1}\!-1),
\end{equation*}
ce qui revient \`a dire que
\begin{equation*}
\alpha_1(M)\ge \tfrac12 L\cdot 3^{N-M-1}.
\end{equation*}
On a donc $\alpha_1(M)\ge 3^{N-M-1}$, puisque $L\ge2$.
Par le Lemme~\ref{augment-alpha}, cela entra{\^\i}ne
\begin{equation*}
\alpha_1(N)-\alpha_1(M) \ge 3^{N-M-1},
\end{equation*}
ce qui implique \'evidemment \eqref{cond-diff-alpha}.
\end{proof}

\begin{lemme}
Pour tous $L,N$ entiers naturels,
\begin{align}
S_3(N)    &=   S_1(N+1)-1,
\label{relation-S3-S1}
\\
S_{3L}(N) &\ge S_L(N+1)-L.
\label{ineg-triplement}
\end{align}
\label{lemme-triplement}
\end{lemme}

\begin{proof}
Quels que soient $L,N$ entiers naturels,
\begin{align*}
S_L(N+1) &= \Min_{M\le N+1} 2S_1(M) + \tfrac12 L\,(3^{N+1-M}\!-1) \\
&= \Min\bigl\lbrace 2S_1(N+1),
  \Min_{M\le N} 2S_1(M) + \tfrac32 L\,(3^{N-M}\!-1) + L \bigr\rbrace \\
&= \Min\bigl\lbrace 2S_1(N+1),\, S_{3L}(N)+L \bigr\rbrace,
\end{align*}
d'o\`u on d\'eduit les deux formules du lemme.
\end{proof}

\begin{lemme}
Pour tous $L,N$ entiers naturels,
\begin{equation*}
L + 2 S_{2L}(N) \ge S_L(N) + S_L(N+1).
\end{equation*}
\label{lemme-doublement}
\end{lemme}

\begin{proof}
La concavit\'e de la suite de fonctions $S_L$ permet d'\'ecrire
$2S_{2L} \ge S_L+S_{3L}$\,, ce qui, combin\'e avec \eqref{ineg-triplement},
donne le r\'esultat cherch\'e.
\end{proof}

On a en particulier la minoration
\begin{equation}
S_2(n) \ge \frac{S_1(n)+S_1(n+1)-1}{2}
\label{minoration-S2}
\end{equation}
pour tout $n$ entier naturel.

\begin{lemme}
Pour tout $n\ge4$, on a $\,\alpha_1(n+1)\le\tfrac43\alpha_1(n)$.
\label{croissance2-alpha1}
\end{lemme}

\begin{proof}
Tous les \'el\'ements de $\roundset$ autres que $1,2,4$ sont divisibles
par $3$ ou par $8$. Puisque $n\ge4$, le nombre
$R=\alpha_1(n)$, \'el\'ement de $\roundset$,
est $\ge\alpha_1(4)=6$, et donc divisible par $3$ ou $8$.
Dans le premier cas, $R'=\tfrac43 R$ est encore dans $\roundset$, et
strictement plus grand que $\alpha_1(n)$, donc $R'\ge \alpha_1(n+1)$, ce
qui est l'in\'egalit\'e cherch\'ee. Dans le second cas, on prend
$R'=\tfrac98 R$ et on applique le m\^eme argument.
\end{proof}

\section{D\'emonstration de l'in\'egalit\'e principale}

\'Ecrivons ${\mathcal D}\ge{\mathcal E}$ l'in\'egalit\'e du 
Th\'eor\`eme~\ref{theoreme-principal}.
Cette in\'egalit\'e est trivialement satisfaite
pour $L=0$, et je supposerai donc $L\ge1$ dans tout ce qui suit.

On d\'emontrera l'in\'egalit\'e par r\'ecurrence sur le nombre de disques
$N$. Pour z\'ero disque, l'in\'egalit\'e est trivialement satisfaite.
Consid\'erons maintenant le cas d'un unique disque. Pour $L=1$, on doit
montrer que
\begin{equation*}
d({\bf u}_0,{\bf u}_1)\ge 2
-2\bar\delta({\bf u}_0(0),{\mathsf p}_0)
-2\bar\delta({\bf u}_1(0),{\mathsf p}_1).
\end{equation*}
Cette in\'egalit\'e est bien satisfaite (avec \'egalit\'e) si
${\bf u}_0(0)={\mathsf p}_0$ et ${\bf u}_1(0)={\mathsf p}_1$, et
dans les autres cas, le membre de droite est n\'egatif donc \c ca marche aussi.
Pour $L\ge2$, on doit montrer que
\begin{equation*}
d({\bf u}_0,{\bf u}_1)+\cdots+d({\bf u}_{L-1},{\bf u}_L) \ge 4
-2\bar\delta({\bf u}_0(0),{\mathsf p}_0)
-2\bar\delta({\bf u}_L(0),{\mathsf p}_L),
\end{equation*}
mais ceci r\'esulte imm\'ediatement des in\'egalit\'es
\begin{align*}
d({\bf u}_0,{\bf u}_1)     &\ge 2\delta({\bf u}_0(0),{\mathsf p}_0) , \\
d({\bf u}_{L-1},{\bf u}_L) &\ge 2\delta({\bf u}_L(0),{\mathsf p}_L),
\end{align*}
qu'on v\'erifie sans peine.
L'in\'egalit\'e ${\mathcal D}\ge{\mathcal E}$ est donc valable pour $N=0,1$.

D\'esormais, on supposera $N\ge2$, et on d\'emontrera cette in\'egalit\'e
en supposant qu'elle est vraie pour tout nombre de disques plus petit.

Soient ${\bf u}'_k:\intset{N-1}\to\Enscol$ les restrictions des
fonctions ${\bf u}_k$, c'est-\`a-dire les empilements
obtenus en ``oubliant'' la position du plus grand disque.
Bien s\^ur, l'op\'eration de restriction diminue les distances
(au sens large), donc $d({\bf u}_0,\ldots,{\bf u}_L) \ge
d({\bf u}'_0,\ldots,{\bf u}'_L)$. D'autre part, on peut appliquer
aux ${\bf u}'_k$ l'hypoth\`ese de r\'ecurrence~:
\begin{equation*}
d({\bf u}'_0,\ldots,{\bf u}'_L) \,\ge\, 2 S_L(N-1)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern -14mu 2\alpha_1(k)
- \mkern -15mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern -15mu 2\alpha_1(k).
\end{equation*}
En combinant cette in\'egalit\'e avec
\begin{align*}
{\mathcal D}-{\mathcal E} &= d({\bf u}_0,\ldots,{\bf u}_L) - 2 S_L(N)
+ \mkern -14mu
  \sum_{\substack{k\in\intset{N} \\ {\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern -14mu \beta(k)
+ \mkern -15mu
  \sum_{\substack{k\in\intset{N} \\ {\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern -15mu \beta(k) \\
&\ge d({\bf u}'_0,\ldots,{\bf u}'_L) - 2 S_L(N-1)
+ \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern -14mu 2\alpha_1(k)
+ \mkern -15mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern -15mu 2\alpha_1(k) \\
&\qquad  - 2\alpha_L(N-1) +
  ( \bar\delta({\bf u}_0(N-1),{\mathsf p}_0) +
    \bar\delta({\bf u}_L(N-1),{\mathsf p}_L) ) \, \beta(N-1),
\end{align*}
on obtient
\begin{equation}
{\mathcal D}-{\mathcal E} \,\ge\, -2\alpha_L(N-1) + K\,\beta(N-1),
\label{mint-D-E}
\end{equation}
o\`u on a pos\'e
\begin{equation}
K = \bar\delta({\bf u}_0(N-1),{\mathsf p}_0) +
 \bar\delta({\bf u}_L(N-1),{\mathsf p}_L).
\label{def-K}
\end{equation}
Cet entier $K$ est le nombre d'indices $i$ dans $\lbrace 0,L\rbrace$
pour lesquels ${\bf u}_i(N-1)\ne {\mathsf p}_i$\,; il peut donc valoir
$0,1,2$. Il y a deux cas o\`u on peut conclure imm\'ediatement~:
\hfill\break
(i) Pour $K=2$, le membre de droite de \eqref{mint-D-E} est positif
puisque $\beta\ge\alpha_L$, donc
l'in\'egalit\'e ${\mathcal D}\ge{\mathcal E}$ est toujours satisfaite dans ce cas.
\hfill\break
(ii) Pour $K=L=1$, le membre de droite de \eqref{mint-D-E} est nul
car $\beta=2\alpha_1$, donc
l\`a encore ${\mathcal D}\ge{\mathcal E}$.

Nous aurons donc uniquement \`a consid\'erer le cas $K=1,L\ge2$,
ainsi que le cas $K=0$, qui feront l'objet des deux sections suivantes.

\subsection{Le cas $K=1$, avec $L\ge2$}

L'hypoth\`ese $K=1$ signifie que ${\bf u}_0(N-1)={\mathsf p}_0$
ou bien ${\bf u}_L(N-1)={\mathsf p}_L$. Les deux possibilit\'es sont
\'evidemment parfaitement sym\'etriques; dans ce qui suit, je
supposerai ${\bf u}_0(N-1)={\mathsf p}_0$ et
${\bf u}_L(N-1)\ne{\mathsf p}_L$.

Soit $a$ le plus petit indice pour lequel ${\bf u}_a(N-1)\ne{\mathsf p}_a$,
donc $0<a\le L$, et posons $b=L-a$.

Examinons d'abord le cas $a,b\ge2$, c'est-\`a-dire $2\le a\le L-2$.

On a alors ${\bf u}_k(N-1)={\mathsf p}_k$ pour $0\le k<a$
et ${\bf u}_a(N-1)=2$. Par le Lemme~\ref{lemme-decomposition},
on peut \'ecrire
\begin{equation}
d({\bf u}_k,{\bf u}_{k+1}) =
2 + d({\bf u}'_k,{\bf s}_k,{\bf t}_k,{\bf u}'_{k+1})
\label{decomp-uk}
\end{equation}
pour $0\le k<a$, o\`u les ${\bf s}_k,{\bf t}_k$ sont
des empilements de $N-1$ disques tels que
$\supp({\bf s}_k)\subseteq\lbrace 2,{\mathsf p}_{k+1}\rbrace$
et $\supp({\bf t}_k)\subseteq\lbrace 2,{\mathsf p}_k\rbrace$,
\`a l'exception de ${\bf t}_{a-1}$ dont
le support est $\subseteq\lbrace 1,3\rbrace$.
Pour $k\ge a$, on se contentera de la minoration \'evidente
$d({\bf u}_k,{\bf u}_{k+1})\ge d({\bf u}'_k,{\bf u}'_{k+1})$.
Donc,
\begin{equation*}
d({\bf u}_0, \ldots, {\bf u}_L) \ge 2a + d({\bf u}'_0,{\bf s}_0,{\bf t}_0,
{\bf u}'_1, \ldots, {\bf u}'_{a-1}, {\bf s}_{a-1}, {\bf t}_{a-1},
{\bf u}'_a, {\bf u}'_{a+1}, \ldots, {\bf u}'_L).
\end{equation*}

La multi-distance \`a droite n'est pas alternante, mais comme
le montre le diagramme ci-dessous (dessin\'e dans le cas
particulier $a=b=3$)
\[ \epsfxsize=450pt \epsfbox{dg1_22.eps} \]
on peut
la d\'ecomposer en une somme de trois multi-distances alternantes
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,
{\bf u}'_1, \ldots, {\bf u}'_{a-1}, {\bf s}_{a-1})
+ d({\bf s}_{a-1}, {\bf t}_{a-1},{\bf u}'_a)
+ d({\bf u}'_a, {\bf u}'_{a+1}, \ldots, {\bf u}'_L),
\end{equation*}
auxquelles on peut appliquer l'hypoth\`ese de r\'ecurrence~:
\begin{align*}
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,
{\bf u}'_1, \ldots, {\bf u}'_{a-1}, {\bf s}_{a-1})
&\ge 2 S_{3a-2}(N-1) - \mkern-14mu \sum_{
  \substack{k\in\intset{N-1}\\{\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern-14mu 2\alpha_1(k)
  - \mkern-30mu \sum_{
  \substack{k\in\intset{N-2}\\{\bf s}_{a-1}(k)\ne{\mathsf p}_{3a-2}}}
  \mkern-30mu 2\alpha_1(k) \\
&\qquad - \bar\delta({\bf s}_{a-1}(N-2),{\mathsf p}_{3a-2})
\,\alpha_{3a-2}(N-2),
\\
\noalign{\smallskip}
d({\bf s}_{a-1}, {\bf t}_{a-1},{\bf u}'_a)
&\ge 2 S_2(N-1) - \mkern-14mu \sum_{
  \substack{k\in\intset{N-2}\\{\bf s}_{a-1}(k)\ne2}}
  \mkern-14mu 2\alpha_1(k)
  - \mkern-10mu \sum_{
  \substack{k\in\intset{N-2}\\{\bf u}_a(k)\ne2}}
  \mkern-10mu 2\alpha_1(k) \\
&\qquad - (\bar\delta({\bf s}_{a-1}(N-2),2)+\bar\delta({\bf u}_a(N-2),2))
  \,\alpha_2(N-2),
\\
\noalign{\smallskip}
d({\bf u}'_a, {\bf u}'_{a+1}, \ldots, {\bf u}'_L)
&\ge 2 S_b(N-1) - \mkern-14mu \sum_{
  \substack{k\in\intset{N-2}\\{\bf u}_a(k)\ne{\mathsf p}_a}}
  \mkern-14mu 2\alpha_1(k)
  - \mkern-14mu \sum_{
  \substack{k\in\intset{N-1}\\{\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern-14mu 2\alpha_1(k) \\
&\qquad - \bar\delta({\bf u}_a(N-2), {\mathsf p}_a)
\,\alpha_b(N-2).
\end{align*}
On en d\'eduit
\begin{align*}
{\mathcal D}-{\mathcal E} &= d({\bf u}_0,\ldots,{\bf u}_L) - 2 S_L(N)
+ \mkern-14mu \sum_{
  \substack{k\in\intset{N}\\{\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern-14mu \beta(k)
+ \mkern-14mu \sum_{
  \substack{k\in\intset{N}\\{\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern-14mu \beta(k) \\
&\ge 2a + 2(S_{3a-2}+S_2+S_b)(N-1) - 2 S_L(N) + \alpha_L(N-1) \\
&\qquad - \mkern-10mu \sum_{k\in\intset{N-2}}\mkern-10mu
  (\bar\delta({\bf s}_{a-1}(k),{\mathsf p}_{3a-2})+\bar\delta({\bf s}_{a-1}(k),2))
  \,2\alpha_1(k) \\
&\qquad - \mkern-10mu \sum_{k\in\intset{N-2}}\mkern-10mu
  (\bar\delta({\bf u}_a(k),2)+\bar\delta({\bf u}_a(k),{\mathsf p}_a))
  \,2\alpha_1(k) \\
&\qquad - \bar\delta({\bf s}_{a-1}(N-2),{\mathsf p}_{3a-2}) \,\alpha_{3a-2}(N-2)
- \bar\delta({\bf s}_{a-1}(N-2),2) \,\alpha_2(N-2) \\
&\qquad - \bar\delta({\bf u}_a(N-2),2)\,\alpha_2(N-2)
- \bar\delta({\bf u}_a(N-2), {\mathsf p}_a)\,\alpha_b(N-2).
\end{align*}
Puisque $\supp({\bf s}_{a-1})\subseteq\lbrace 2,{\mathsf p}_{3a-2}\rbrace$
et $\supp({\bf u}_a)\subseteq\lbrace 2,{\mathsf p}_a\rbrace$,
on a, pour tout $k<N-1$,
\begin{equation*}
\bar\delta({\bf s}_{a-1}(k),{\mathsf p}_{3a-2})+\bar\delta({\bf s}_{a-1}(k),2)
= \bar\delta({\bf u}_a(k),2)+\bar\delta({\bf u}_a(k),{\mathsf p}_a) = 1,
\end{equation*}
et par suite
\begin{align*}
\bar\delta({\bf s}_{a-1}(k),{\mathsf p}_{3a-2}) \,\alpha_{3a-2}(k)
+ \bar\delta({\bf s}_{a-1}(k),2) \,\alpha_2(k)
&\le \max\lbrace \alpha_{3a-2}(k), \alpha_2(k)\rbrace ,\\
\bar\delta({\bf u}_a(k),2)\,\alpha_2(k)
+ \bar\delta({\bf u}_a(k), {\mathsf p}_a)\,\alpha_b(k)
&\le \max\lbrace \alpha_2(k), \alpha_b(k)\rbrace.
\end{align*}
Par cons\'equent
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge  2a + 2(S_{3a-2}+S_2+S_b)(N-1) - 2 S_L(N) + \alpha_L(N-1) \\
&\qquad - (2 S_1 + \alpha_{\max\lbrace 3a-2,2 \rbrace}
         + 2 S_1 + \alpha_{\max\lbrace 2,b\rbrace})(N-2) \\
&=    2a + 2(S_{3a-2}+S_2+S_b)(N-1) - 2 S_L(N) + \alpha_L(N-1) \\
&\qquad - (4 S_1 + \alpha_{3a-2}+\alpha_b)(N-2) \\
&= 2a + S_{3a-2}(N-1) + S_{3a-2}(N-2) + 2 S_2(N-1) - 4 S_1(N-2) \\
&\qquad + S_b(N-1) + S_b(N-2) - S_L(N) - S_L(N-1).
\end{align*}
Utilisons maintenant la minoration
\begin{equation}
S_{3a-2}(n) \ge S_{3a-3}(n)\ge S_{a-1}(n+1)-a+1,
\label{minor-S-3a-2}
\end{equation}
cons\'equence du Lemme~\ref{lemme-triplement}, et valable pour
tous $n\ge0$ et $a\ge1$. Il vient
\begin{align*}
{\mathcal D}-{\mathcal E} &\ge 2 + (S_{a-1}-S_L)(N) + (S_{a-1}-S_L)(N-1) \\
&\qquad + S_b(N-1) + S_b(N-2) + 2 S_2(N-1) - 4 S_1(N-2).
\end{align*}
La concavit\'e de la suite des $S_L$ entra{\^\i}ne $S_{a-1}-S_{a+b}
\ge S_1-S_{b+2}$\,. En outre, on a $S_b(n)\ge S_{b+1}(n+1)-2\alpha_1(n)$
par le Lemme~\ref{lemme-augm-LN}, donc
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2 + (S_1+S_{b+1}-S_{b+2})(N) + (S_1+S_{b+1}-S_{b+2})(N-1) \\
&\qquad - 2\alpha_1(N-1) - 2\alpha_1(N-2) + 2 S_2(N-1) - 4 S_1(N-2).
\end{align*}
La concavit\'e de la suite des $S_L$ donne aussi
$S_{b+1}-S_{b+2}\ge S_1-S_2$\,, d'o\`u
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2 + (2S_1-S_2)(N) + (2S_1-S_2)(N-1) \\
&\qquad - 2\alpha_1(N-1) - 2\alpha_1(N-2) + 2 S_2(N-1) - 4 S_1(N-2) \\
&= 2 + 2\alpha_1(N-2) -\alpha_2(N-1),
\end{align*}
et on a $\alpha_2(n)\le \alpha_3(n)=\alpha_1(n+1)$, par le
Lemme~\ref{lemme-triplement}, donc
\begin{equation*}
{\mathcal D}-{\mathcal E} \ge 2 + 2\alpha_1(N-2) - \alpha_1(N).
\end{equation*}
Mais on v\'erifie facilement, avec le
Lemme~\ref{croissance2-alpha1}, que
\begin{equation}
1 + 2\alpha_1(N-2) - \alpha_1(N) \ge 0
\label{ineg-alpha1-a2}
\end{equation}
pour tout $N\ge2$.
Ceci \'etablit l'in\'egalit\'e ${\mathcal D}\ge{\mathcal E}$
dans le cas $a,b\ge2$.

Examinons maintenant le cas $a\ge2, b=1$ (et donc $L=a+1$).

Comme le montre le diagramme
\[ \epsfxsize=400pt \epsfbox{dg1_21.eps} \]
on peut \'ecrire la multi-distance
$d({\bf u}'_0,{\bf s}_0,\ldots,{\bf t}_{a-1},{\bf u}'_a,
{\bf u}'_{a+1})$ comme somme de deux multi-distances alternantes
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1,\ldots,{\bf u}'_{a-1},
{\bf s}_{a-1}) + d({\bf s}_{a-1},{\bf t}_{a-1},{\bf u}'_a,{\bf u}'_{a+1}),
\end{equation*}
auxquelles on applique l'hypoth\`ese de r\'ecurrence.
Par un calcul similaire au pr\'ec\'edent, on obtient
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2a + 2(S_{3a-2}+S_3)(N-1) - 2 S_L(N) + \alpha_L(N-1) \\
&\qquad - (2S_1+\alpha_{\max\lbrace 3a-2,3 \rbrace})(N-2) \\
&= 2a + 2(S_{3a-2}+S_3)(N-1) - 2 S_L(N) + \alpha_L(N-1) \\
&\qquad - (2S_1+\alpha_{3a-2})(N-2) \\
&= 2a + S_{3a-2}(N-1) + S_{3a-2}(N-2) + 2 S_3(N-1) - 2 S_1(N-2) \\
&\qquad - S_L(N) - S_L(N-1),
\end{align*}
et en minorant $S_{3a-2}$ avec \eqref{minor-S-3a-2}, il vient
\begin{equation*}
{\mathcal D}-{\mathcal E} \ge 2 + (S_{a-1}-S_L)(N) + (S_{a-1}-S_L)(N-1)
 + 2 S_3(N-1) - 2 S_1(N-2).
\end{equation*}
La concavit\'e des $S_L$ implique $S_{a-1}-S_{a+1}\ge S_1-S_3$, et donc
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2 + (S_1-S_3)(N) + (S_1-S_3)(N-1) + 2 S_3(N-1) - 2 S_1(N-2) \\
&\ge 2 - \alpha_3(N-1) + S_1(N) + S_1(N-1) - 2 S_1(N-2) \\
&\ge 2 - \alpha_1(N) + \alpha_1(N-1) + 2\alpha_1(N-2),
\end{align*}
et d'apr\`es \eqref{ineg-alpha1-a2}, cette expression est positive
(on peut aussi utiliser \eqref{croissance-alpha1}).
On a donc encore ${\mathcal D}\ge{\mathcal E}$ dans le cas $a\ge2,b=1$.

A pr\'esent, consid\'erons le cas $a=1$ (et donc $L=b+1$, avec $b\ge1$).

Pour $b\ge2$, on \'ecrit la multi-distance
$d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1,
{\bf u}'_2, \ldots, {\bf u}'_L)$
\[ \epsfxsize=250pt \epsfbox{dg1_12.eps} \]
comme somme de deux multi-distances alternantes
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1) + d({\bf u}'_1,
{\bf u}'_2, \ldots, {\bf u}'_L),
\end{equation*}
auxquelles on applique l'hypoth\`ese de r\'ecurrence, et on obtient,
par des calculs similaires aux pr\'ec\'edents,
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2 + 2(S_3+S_b)(N-1) - 2 S_L(N) + \alpha_L(N-1) \\
&\qquad - (2 S_1 + \alpha_{\max\lbrace 3,b\rbrace})(N-2).
\end{align*}
Pour $b=2$, cela donne
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2 + 2(S_3+S_2)(N-1) - S_3(N) - S_3(N-1) - (2S_1+\alpha_3)(N-2) \\
&= 2 - \alpha_3(N-1) + 2 S_2(N-1) - 2 S_1(N-2) - \alpha_3(N-2) \\
&= 2 - \alpha_1(N) + 2 S_2(N-1) - 2 S_1(N-2) - \alpha_1(N-1),
\end{align*}
et on sait que $2 S_2(N-1)\ge S_1(N-1)+S_1(N)-1$, d'apr\`es
\eqref{minoration-S2}, donc
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2 - \alpha_1(N) + S_1(N-1) + S_1(N) - 1 - 2 S_1(N-2) - \alpha_1(N-1) \\
&= 1 - \alpha_1(N) + 2 \alpha_1(N-2),
\end{align*}
et cette expression, comme on l'a vu en \eqref{ineg-alpha1-a2},
est positive.

Pour $b\ge3$, on a
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2 + 2(S_3+S_b)(N-1) - S_L(N) - S_L(N-1) - (2 S_1 + \alpha_b)(N-2) \\
&= S_b(N-1) + S_b(N-2) - S_L(N) - S_L(N-1) + 2 S_1(N) - 2 S_1(N-2) \\
&= \bigl[ (S_b+2\alpha_1)(N-1)-S_{b+1}(N) \bigr]
+ \bigl[ (S_b+2\alpha_1)(N-2)-S_{b+1}(N-1) \bigr],
\end{align*}
et les deux expressions entre crochets sont positives, par le
Lemme~\ref{lemme-augm-LN}, donc ${\mathcal D}\ge{\mathcal E}$.

Pour $b=1$ (et donc $L=2$), la multi-distance
$d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1,{\bf u}'_2)$ est alternante
\[ \epsfxsize=180pt \epsfbox{dg1_11.eps} \]
et on peut lui appliquer directement l'hypoth\`ese de r\'ecurrence,
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1,{\bf u}'_2)
\ge 2 S_4(N-1) - \mkern -10mu \sum_{\substack{k\in\intset{N-1}\\{\bf u}_0(k)\ne
1}} \mkern -10mu 2\alpha_1(k)
- \mkern -10mu \sum_{\substack{k\in\intset{N-1}\\{\bf u}_2(k)\ne
1}} \mkern -10mu 2\alpha_1(k),
\end{equation*}
ce qui entra{\^\i}ne
\begin{equation*}
{\mathcal D}-{\mathcal E} \ge 2 + 2 S_4(N-1) - S_2(N) - S_2(N-1),
\end{equation*}
et le membre de droite est positif, par le Lemme~\ref{lemme-doublement}.

On a donc bien ${\mathcal D}\ge{\mathcal E}$ chaque fois que $a=1$.

Finalement, examinons le cas $b=0$ (et donc $L=a\ge2$).

Comme il n'y a aucune condition de support sur ${\bf u}_L$, il n'est plus
possible d'affirmer comme pr\'ec\'edemment que ${\bf u}_a(N-1)=2$.
La position du plus grand disque dans ${\bf u}_a$ \'etant inconnue,
il n'est plus possible de d\'ecomposer la distance $d({\bf u}_{a-1},{\bf u}_a)$
selon la formule \eqref{decomp-uk}, et on devra se contenter de la
minorer par $d({\bf u}'_{a-1},{\bf u}'_a)$. Il vient alors
\begin{equation*}
d({\bf u}_0,\ldots,{\bf u}_L) \ge 2(a-1) +
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1,\ldots,{\bf u}'_{a-2},
{\bf s}_{a-2},{\bf t}_{a-2},{\bf u}'_{a-1},{\bf u}'_a),
\end{equation*}
et la multi-distance \`a droite est alternante
\[ \epsfxsize=300pt \epsfbox{dg1_20.eps} \]
donc on peut lui appliquer
l'hypoth\`ese de r\'ecurrence,
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,\ldots,
{\bf t}_{a-2},{\bf u}'_{a-1},{\bf u}'_a)
\ge 2 S_{3a-2}(N-1)
- \mkern -14mu \sum_{\substack{k\in\intset{N-1}\\{\bf u}_0(k)\ne
{\mathsf p}_0}} \mkern -14mu 2\alpha_1(k)
- \mkern -24mu \sum_{\substack{k\in\intset{N-1}\\{\bf u}_a(k)\ne
{\mathsf p}_{3a-2}}} \mkern -24mu 2\alpha_1(k),
\end{equation*}
et par cons\'equent
\begin{equation*}
{\mathcal D}-{\mathcal E} \ge 2(a-1) + 2 S_{3a-2}(N-1) - S_a(N) - S_a(N-1).
\end{equation*}
Or on sait que $S_a(N)+S_a(N-1)\le a+2S_{2a}(N-1)$, par le 
Lemme~\ref{lemme-doublement}, donc
\begin{equation*}
{\mathcal D}-{\mathcal E} \ge a-2 + 2 (S_{3a-2}-S_{2a})(N-1),
\end{equation*}
et cette expression est visiblement positive, puisque $a\ge2$.

Nous avons ainsi \'etabli l'in\'egalit\'e ${\mathcal D}\ge{\mathcal E}$
dans tous les cas o\`u $K=1,L\ge2$.

\subsection{Le cas $K=0$}

Supposons maintenant $K=0$, et soit $E$ l'ensemble des indices $i$
dans $\lbrace 0,\ldots,L\rbrace$ pour lesquels
${\bf u}_i(N-1)\ne{\mathsf p}_i$. Par hypoth\`ese, cet ensemble
ne contient pas $0$ et $L$.

Supposons d'abord que $E$ est vide, c'est-\`a-dire que
${\bf u}_i(N-1)={\mathsf p}_i$ pour tout $i$.
(Remarquons que si $L=1$, c'est la seule possibilit\'e.)
On peut alors \'ecrire la formule \eqref{decomp-uk} pour tout $k$ dans
$\lbrace 0,\ldots,L-1\rbrace$, ce qui donne
\begin{equation*}
d({\bf u}_0,\ldots,{\bf u}_L) = 2L + d({\bf u}'_0,{\bf s}_0,\ldots,
{\bf t}_{L-1},{\bf u}'_L),
\end{equation*}
et la multi-distance \`a droite est alternante
\[ \epsfxsize=350pt \epsfbox{dg0_emp.eps} \]
donc
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,\ldots,{\bf t}_{L-1},{\bf u}'_L)
\ge 2 S_{3L}(N-1)
- \mkern-14mu \sum_{\substack{k\in\intset{N-1}\\{\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern-14mu 2\alpha_1(k)
- \mkern-15mu \sum_{\substack{k\in\intset{N-1}\\{\bf u}_L(k)\ne{\mathsf p}_{3L}}}
  \mkern-15mu 2\alpha_1(k),
\end{equation*}
ce qui donne
\begin{align*}
{\mathcal D}-{\mathcal E} &= d({\bf u}_0,\ldots,{\bf u}_L) - 2 S_L(N)
+ \mkern-14mu \sum_{\substack{k\in\intset{N}\\{\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern-14mu \beta(k)
+ \mkern-15mu \sum_{\substack{k\in\intset{N}\\{\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern-15mu \beta(k) \\
&\ge 2L + 2 S_{3L}(N-1) - 2 S_L(N),
\end{align*}
et cette quantit\'e est positive par le Lemme~\ref{lemme-triplement}.

Dans ce qui suit, on supposera $E$ non vide, et on notera $a$ et $a^*$
son plus petit et son plus grand \'el\'ement, si bien que
$0<a\le a^*<L$.
D\'efinissons \'egalement $b=a^*-a$ et $c=L-a^*$, ce qui permet
d'\'ecrire $L=a+b+c$ avec $a,c>0$ et $b\ge0$.

Le nombre ${\bf u}_k(N-1)$, c'est-\`a-dire la position du plus grand
disque dans la configuration ${\bf u}_k$, est connue pour tout $k$
dans $\lbrace 0,\ldots,a\rbrace\cup\lbrace a^*,\ldots,L\rbrace$~:
c'est la tige ${\mathsf p}_k$ si $k<a$ ou $k>a^*$, et la tige $2$ si
$k$ vaut $a$ ou $a^*$.
On peut donc utiliser la d\'ecomposition \eqref{decomp-uk} pour tout $k$ dans
$\lbrace 0,\ldots,a-1\rbrace\cup\lbrace a^*,\ldots,L-1\rbrace$, et
pour les autres valeurs de $k$, c'est-\`a-dire entre $a$ et $a^*-1$,
on utilisera la minoration \'evidente 
$d({\bf u}_k,{\bf u}_{k+1})\ge d({\bf u}'_k,{\bf u}'_{k+1})$.
Cela donne
\begin{equation}
d({\bf u}_0,\ldots,{\bf u}_L) \ge 2a + 2c +
d({\bf u}'_0,{\bf s}_0,\ldots,{\bf t}_{a-1},{\bf u}'_a,{\bf u}'_{a+1},\ldots,
{\bf u}'_{a^*}, {\bf s}_{a^*}, \ldots, {\bf t}_{L-1}, {\bf u}'_L).
\label{equation-K0}
\end{equation}
La multi-distance \`a droite ne sera pas alternante en g\'en\'eral,
et devra \^etre d\'ecompos\'ee
en fragments alternants; cette d\'ecomposition sera diff\'erente
selon que $a,b,c$ sont ``grands'' (au moins deux) ou ``petits''
(z\'ero ou un).

Notons, pour la suite, que pour $L\ge3$ on a l'in\'egalit\'e
$S_L(N)-S_{L-1}(N-1)\le 2\alpha_1(N-1)$, qui
peut se r\'ecrire
\begin{equation}
2 S_L(N) \le S_L(N) + S_{L-1}(N-1) + 2 \alpha_1(N-1).
\label{majoration-2SLN}
\end{equation}

\subsubsection{Sous-cas $a,c\ge2$}

Supposons d'abord $a,c\ge2$. Nous devrons distinguer trois
cas, selon que $b$ vaut z\'ero, un, ou au moins deux.

Pour $b\ge2$, la multi-distance \`a droite de \eqref{equation-K0}
\[ \epsfxsize=450pt \epsfbox{dg0_222.eps} \]
se d\'ecompose en
\begin{equation*}
d({\bf u}'_0,\ldots,{\bf s}_{a-1})
+ d({\bf s}_{a-1},{\bf t}_{a-1},{\bf u}'_a)
+ d({\bf u}'_a,\ldots,{\bf u}'_{a^*})
+ d({\bf u}'_{a^*},{\bf s}_{a^*},{\bf t}_{a^*})
+ d({\bf t}_{a^*},\ldots,{\bf u}'_L),
\end{equation*}
ce qui donne
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2a+2c + 2(S_{3a-2}+S_2+S_b+S_2+S_{3c-2})(N-1) - 2 S_L(N) \\
&\qquad - (2 S_1 + \alpha_{\max\lbrace 3a-2,2\rbrace}
         + 2 S_1 + \alpha_{\max\lbrace 2,b\rbrace}            \\
&\qquad\qquad
         + 2 S_1 + \alpha_{\max\lbrace b,2\rbrace}
         + 2 S_1 + \alpha_{\max\lbrace 2,3c-2\rbrace})(N-2)   \\
&= 2a+2c + 2(S_{3a-2}+S_2+S_b+S_2+S_{3c-2})(N-1) - 2 S_L(N)   \\
&\qquad - (8 S_1 + \alpha_{3a-2} + 2 \alpha_b + \alpha_{3c-2})(N-2) \\
&= 2a+2c + S_{3a-2}(N-1) + S_{3a-2}(N-2) + 2 S_b(N-2)  \\
&\qquad + 4 S_2(N-1) + S_{3c-2}(N-1) + S_{3c-2}(N-2)   \\
&\qquad - 2 S_L(N) - 8 S_1(N-2),
\end{align*}
et nous devons montrer que cette expression est positive.

Minorons $S_{3a-2}$ et $S_{3c-2}$ avec \eqref{minor-S-3a-2}, et
majorons $2S_L(N)$ avec
\eqref{majoration-2SLN}~: il vient
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + S_{a-1}(N) + S_{a-1}(N-1) + S_{c-1}(N) + S_{c-1}(N-1) \\
&\qquad - S_L(N) - S_{L-1}(N-1) - 2\alpha_1(N-1) \\
&\qquad + 2 S_b(N-2) + 4 S_2(N-1) - 8 S_1(N-2) \\
&= 4 + (S_{a-1}-S_L)(N) + (S_{a-1}-S_{L-1})(N-1) \\
&\qquad + S_{c-1}(N) + S_{c-1}(N-1) - 2\alpha_1(N-1) \\
&\qquad + 2 S_b(N-2) + 4 S_2(N-1) - 8 S_1(N-2).
\end{align*}
La concavit\'e de la suite des $S_L$ permet d'\'ecrire
$S_{a-1}-S_L\ge S_1-S_{b+c+2}$ et $S_{a-1}-S_{L-1}\ge S_1-S_{b+c+1}$,
puisque $a\ge2$, donc
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + (S_1-S_{b+c+2})(N) + (S_1-S_{b+c+1})(N-1) \\
&\qquad + S_{c-1}(N) + S_{c-1}(N-1) - 2\alpha_1(N-1) \\
&\qquad + 2 S_b(N-2) + 4 S_2(N-1) - 8 S_1(N-2) \\
&= 4 + S_1(N) + S_1(N-1) - 2\alpha_1(N-1) \\
&\qquad + (S_{c-1}-S_{b+c+2})(N) + (S_{c-1}-S_{b+c+1})(N-1) \\
&\qquad + 2 S_b(N-2) + 4 S_2(N-1) - 8 S_1(N-2).
\end{align*}
On invoque \`a nouveau la concavit\'e des $S_L$ pour dire que
$S_{c-1}-S_{b+c+2}\ge S_1-S_{b+4}$ et $S_{c-1}-S_{b+c+1}\ge S_1-S_{b+3}$,
puisque $c\ge2$, et donc
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + S_1(N) + S_1(N-1) - 2\alpha_1(N-1) \\
&\qquad + (S_1-S_{b+4})(N) + (S_1-S_{b+3})(N-1) \\
&\qquad + 2 S_b(N-2) + 4 S_2(N-1) - 8 S_1(N-2),
\end{align*}
et, comme $S_{b+4}(N)\le S_{b+3}(N-1) + 2\alpha_1(N-1)$,
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2 S_1(N) + 2 S_1(N-1) - 2\alpha_1(N-1) \\
&\qquad - 2 S_{b+3}(N-1) - 2 \alpha_1(N-1) \\
&\qquad + 2 S_b(N-2) + 4 S_2(N-1) - 8 S_1(N-2).
\end{align*}
Utilisant maintenant $S_{b+3}(N-1)\le S_{b+2}(N-2) + 2\alpha_1(N-2)$,
on obtient
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2 S_1(N) + 2 S_1(N-1) - 4\alpha_1(N-1) \\
&\qquad + 2(S_b-S_{b+2})(N-2) - 4\alpha_1(N-2) \\
&\qquad + 4 S_2(N-1) - 8 S_1(N-2).
\end{align*}
Enfin, on utilise $S_b-S_{b+2}\ge S_1-S_3$ et $2 S_2(N-1)\ge S_1(N)
+S_1(N-1)-1$, ce qui donne
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2 S_1(N) + 2 S_1(N-1) - 4\alpha_1(N-1) \\
&\qquad + 2 S_1(N-2) - 2 S_1(N-1) + 2 - 4\alpha_1(N-2) \\
&\qquad + 2 S_1(N) + 2 S_1(N-1) - 2 - 8 S_1(N-2) \\
&= 4 + 2\alpha_1(N-2) \ge 0,
\end{align*}
ce qui prouve l'in\'egalit\'e ${\mathcal D}\ge{\mathcal E}$ dans le cas $b\ge2$.

Pour $b=1$ (et donc $L=a+c+1$), la multi-distance
\`a droite de \eqref{equation-K0}
\[ \epsfxsize=425pt \epsfbox{dg0_212.eps} \]
se d\'ecompose en
\begin{equation*}
d({\bf u}'_0,\ldots,{\bf s}_{a-1})
+ d({\bf s}_{a-1},{\bf t}_{a-1},{\bf u}'_a,{\bf u}'_{a^*})
+ d({\bf u}'_{a^*},{\bf s}_{a^*},{\bf t}_{a^*})
+ d({\bf t}_{a^*},\ldots,{\bf u}'_L),
\end{equation*}
ce qui donne
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2a+2c + 2(S_{3a-2}+S_3+S_2+S_{3c-2})(N-1) - 2 S_L(N) \\
&\qquad - (6S_1 + \alpha_{3a-2} + \alpha_3 + \alpha_{3c-2})(N-2) \\
&= 2a + 2c + S_{3a-2}(N-1) + S_{3a-2}(N-2) \\
&\qquad + S_3(N-1) + S_3(N-2) + S_{3c-2}(N-1) + S_{3c-2}(N-2) \\
&\qquad + 2 S_2(N-1) - 6 S_1(N-2) - 2 S_L(N).
\end{align*}

Comme pr\'ec\'edemment, minorons $S_{3a-2}$ et $S_{3c-2}$ avec
\eqref{minor-S-3a-2}, et majorons $2S_L(N)$ avec
\eqref{majoration-2SLN}~: il vient
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + S_{a-1}(N) + S_{a-1}(N-1) + S_{c-1}(N) + S_{c-1}(N-1) \\
&\qquad + S_1(N) + S_1(N-1) - 2 + 2 S_2(N-1) - 6 S_1(N-2) \\
&\qquad - S_L(N) - S_{L-1}(N-1) - 2 \alpha_1(N-1) \\
&= 2 + (S_1 + S_{a-1}+S_{c-1}-S_L)(N) + (S_1 + S_{a-1}+S_{c-1}-S_{L-1})(N-1) \\
&\qquad + 2 S_2(N-1) - 6 S_1(N-2) - 2 \alpha_1(N-1),
\end{align*}
et les in\'egalit\'es de concavit\'e $S_{a-1}-S_{a+c+1}\ge S_1-S_{c+3}$ et
$S_{a-1}-S_{a+c}\ge S_1-S_{c+2}$ donnent
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2 + (2 S_1+S_{c-1}-S_{c+3})(N) + (2 S_1+S_{c-1}-S_{c+2})(N-1) \\
&\qquad + 2 S_2(N-1) - 2\alpha_1(N-1) - 6 S_1(N-2),
\end{align*}
puis, les in\'egalit\'es $S_{c-1}-S_{c+3}\ge S_1-S_5$ et
$S_{c-1}-S_{c+2}\ge S_1-S_4$ donnent
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2 + 3 S_1(N) + 3 S_1(N-1) - S_5(N) - S_4(N-1) \\
&\qquad + 2 S_2(N-1) - 2\alpha_1(N-1) - 6 S_1(N-2).
\end{align*}
Des majorations $S_5(N)\le (S_4+2\alpha_1)(N-1)$ et
$S_4(N-1)\le (S_3+2\alpha_1)(N-2)$, on d\'eduit
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 3 S_1(N) + S_1(N-1) + 2 S_2(N-1) \\
&\qquad - 4\alpha_1(N-1) - 4\alpha_1(N-2) - 6 S_1(N-2),
\end{align*}
et, comme $2 S_2(N-1)\ge S_1(N)+S_1(N-1)-1$, d'apr\`es \eqref{minoration-S2},
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 3 + 4 S_1(N) + 2 S_1(N-1) - 4\alpha_1(N-1) - 4\alpha_1(N-2) - 6 S_1(N-2) \\
&= 3 + 2 \alpha_1(N-2) \ge 0,
\end{align*}
ce qui prouve l'in\'egalit\'e ${\mathcal D}\ge{\mathcal E}$ dans le cas $b=1$.

Enfin, pour $b=0$ (et donc $L=a+c$), la multi-distance
\`a droite de \eqref{equation-K0}
\[ \epsfxsize=400pt \epsfbox{dg0_202.eps} \]
se d\'ecompose en
\begin{equation*}
d({\bf u}'_0,\ldots,{\bf s}_{a-1})
+ d({\bf s}_{a-1},{\bf t}_{a-1},{\bf u}'_a,{\bf s}_a,{\bf t}_a)
+ d({\bf t}_a,\ldots,{\bf u}'_L),
\end{equation*}
ce qui donne
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2a+2c + 2(S_{3a-2}+S_4+S_{3c-2})(N-1) - 2 S_L(N) \\
&\qquad - (4 S_1 + \alpha_{3a-2} + \alpha_{3c-2})(N-2) \\
&= 2a+2c + S_{3a-2}(N-1) + S_{3a-2}(N-2) + S_{3c-2}(N-1) + S_{3c-2}(N-2) \\
&\qquad + 2 S_4(N-1) - 4 S_1(N-2) - 2 S_L(N).
\end{align*}
Utilisons \`a nouveau \eqref{minor-S-3a-2} et
\eqref{majoration-2SLN}~: il vient
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + (S_{a-1}+S_{c-1}-S_L)(N) + (S_{a-1}+S_{c-1}-S_{L-1})(N-1) \\
&\qquad + 2 S_4(N-1) - 4 S_1(N-2) - 2 \alpha_1(N-1),
\end{align*}
et les in\'egalit\'es $S_{a-1}-S_{a+c}\ge S_1-S_{c+2}$ et
$S_{a-1}-S_{a+c-1}\ge S_1-S_{c+1}$, puis $S_{c-1}-S_{c+2}\ge S_1-S_4$
et $S_{c-1}-S_{c+1}\ge S_1-S_3$, donnent successivement
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + (S_1+S_{c-1}-S_{c+2})(N) + (S_1+S_{c-1}-S_{c+1})(N-1) \\
&\qquad + 2 S_4(N-1) - 4 S_1(N-2) - 2 \alpha_1(N-1) \\
&\ge 4 + (2 S_1-S_4)(N) + (2 S_1-S_3)(N-1) \\
&\qquad + 2 S_4(N-1) - 4 S_1(N-2) - 2 \alpha_1(N-1),
\end{align*}
et, comme $S_4(N)\le(S_3+2\alpha_1)(N-1)$,
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2 S_1(N) + 2 S_1(N-1) - 2 S_3(N-1) - 2\alpha_1(N-1) \\
&\qquad + 2 S_4(N-1) - 4 S_1(N-2) - 2\alpha_1(N-1) \\
&= 6 + 2 S_1(N-1) + 2 S_4(N-1) - 4 S_1(N-2) - 4 \alpha_1(N-1),
\end{align*}
et enfin, en minorant $S_4$ par $S_3$, il vient
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2 S_1(N-1) + 2 S_1(N) - 4 S_1(N-2) - 4 \alpha_1(N-1) \\
&= 4 + 4\alpha_1(N-2) - 2\alpha_1(N-1) \ge 0,
\end{align*}
puisque $\alpha_1(N-1)\le 2\alpha_1(N-2)$, d'apr\`es
\eqref{croissance-alpha1}.
On a donc \'egalement ${\mathcal D}\ge{\mathcal E}$ si $b=0$.

En r\'esum\'e, l'in\'egalit\'e ${\mathcal D}\ge{\mathcal E}$
est satisfaite dans tous les cas o\`u $a,c\ge2$.

\subsubsection{Sous-cas $a=c=1$}

Supposons maintenant $a=c=1$ (et donc $L=b+2$). On distinguera ici encore
le cas $b\ge2$ et les cas $b=0,1$.

Pour $b\ge2$, la multi-distance \`a droite de \eqref{equation-K0}
\[ \epsfxsize=320pt \epsfbox{dg0_121.eps} \]
se d\'ecompose en
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1)
+ d({\bf u}'_1,\ldots,{\bf u}'_{L-1})
+ d({\bf u}'_{L-1},{\bf s}_{L-1},{\bf t}_{L-1},{\bf u}'_L),
\end{equation*}
ce qui donne
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2(S_3 + S_b + S_3)(N-1) - 2 S_L(N) \\
&\qquad - (4S_1 + 2\alpha_{\max\lbrace b,3\rbrace})(N-2).
\end{align*}

Pour $b\ge 3$, on a
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + (4 S_3 + 2 S_b)(N-1) - 2 S_L(N) - (4 S_1 + 2\alpha_b)(N-2) \\
&= 4 + 4 S_3(N-1) + 2 S_b(N-2) - 2 S_L(N) - 4 S_1(N-2) \\
&= 4 \alpha_1(N-1) + 4 \alpha_1(N-2) + 2 S_b(N-2) - 2 S_{b+2}(N) \\
&= 2\bigl[ (S_b+2\alpha_1)(N-2) - S_{b+1}(N-1) \bigr]
  +2\bigl[ (S_{b+1}+2\alpha_1)(N-1) - S_{b+2}(N) \bigr],
\end{align*}
et les deux expressions entre crochets sont positives, par le 
Lemme~\ref{lemme-augm-LN}, donc ${\mathcal D}\ge{\mathcal E}$ si $b\ge3$.

Pour $b=2$ (et donc $L=4$), on a
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + (4 S_3 + 2 S_2)(N-1) - 2 S_4(N) - (4 S_1 + 2\alpha_3)(N-2) \\
&= 4 + 2 S_3(N-1) + 2 S_3(N-2) + 2 S_2(N-1) - 2 S_4(N) - 4 S_1(N-2),
\end{align*}
et, comme $S_4(N)\le S_3(N-1) + 2\alpha_1(N-1)$, il vient
\begin{equation}
{\mathcal D}-{\mathcal E}
\ge 2 + 2 S_1(N-1) - 4 S_1(N-2) - 4\alpha_1(N-1) + 2 S_2(N-1)
\label{minor-D-E-121}
\end{equation}
et avec l'in\'egalit\'e $1+2S_2(N-1)\ge S_1(N-1)+S_1(N)$, on en d\'eduit
\begin{equation*}
{\mathcal D}-{\mathcal E} \ge 1 + 4\alpha_1(N-2) - 3\alpha_1(N-1).
\end{equation*}
Cette expression est positive dans tous les cas o\`u
$\alpha_1(N-1)\le \tfrac43 \alpha_1(N-2)$, c'est-\`a-dire pour
tout $N\ge6$ d'apr\`es le Lemme~\ref{croissance2-alpha1}, et
pour $N=4$. Elle est \'egalement positive (nulle, en fait) pour $N=3$.
Enfin, quand $N$ vaut $2$ ou $5$, le membre de droite de
\eqref{minor-D-E-121} est positif (il vaut $0$ et $2$ respectivement).
On a donc toujours ${\mathcal D}\ge{\mathcal E}$ si $b=2$.

Pour $b=1$ (et donc $L=3$), la multi-distance
\`a droite de \eqref{equation-K0}
\[ \epsfxsize=280pt \epsfbox{dg0_111.eps} \]
se d\'ecompose en
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1,{\bf u}'_2)
+ d({\bf u}'_2,{\bf s}_2,{\bf t}_2,{\bf u}'_3),
\end{equation*}
ce qui donne
\begin{equation}
\begin{aligned}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2(S_4+S_3)(N-1) - 2 S_3(N) - (2 S_1 + \alpha_4)(N-2) \\
&= 4 + S_4(N-1) + S_4(N-2) + 2 S_1(N) - 2 S_1(N+1) - 2 S_1(N-2).
\end{aligned}
\label{minor-D-E-111}
\end{equation}
La concavit\'e des $S_L$ permet d'\'ecrire $3 S_4\ge 2S_3+S_6$, et donc
\begin{equation}
\begin{aligned}
S_4(n) &\ge \tfrac23 S_3(n) + \tfrac13 S_6(n)
\ge \tfrac 23 S_1(n+1) + \tfrac13 S_2(n+1) - \tfrac43 \\
&\ge \tfrac 23 S_1(n+1) + \tfrac16 \bigl[ S_1(n+1)+S_1(n+2)-1 \bigr] - \tfrac43 \\
&= \tfrac56 S_1(n+1) + \tfrac16 S_1(n+2) - \tfrac32
\end{aligned}
\label{minoration-S4}
\end{equation}
pour tout entier naturel $n$. Par cons\'equent,
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + \tfrac56 S_1(N) + \tfrac16 S_1(N+1) - \tfrac32
+ \tfrac56 S_1(N-1) + \tfrac16 S_1(N) - \tfrac32 \\
&\qquad + 2 S_1(N) - 2 S_1(N+1) - 2 S_1(N-2) \\
&= 1 + \tfrac56 S_1(N-1) + 3 S_1(N) - \tfrac{11}6 S_1(N+1) - 2 S_1(N-2) \\
&= 1 + 2\alpha_1(N-2) + \tfrac76 \alpha_1(N-1) - \tfrac{11}6 \alpha_1(N).
\end{align*}
On d\'eduit du Lemme~\ref{croissance2-alpha1} que cette derni\`ere
expression est positive pour tout $N\ge6$.
Elle est positive \'egalement pour $N=3,4,5$. Enfin, pour $N=2$,
le membre de droite de \eqref{minor-D-E-111} est positif
(il vaut $0$).
On a donc toujours ${\mathcal D}\ge{\mathcal E}$ si $b=1$.

Finalement, observons que le cas $b=0$ (et donc $L=2$) se ram\`ene au
cas $E=\emptyset$, d\'ej\`a trait\'e, en \'echangeant les
r\^oles des colonnes $2$ et $3$.

En r\'esum\'e, l'in\'egalit\'e ${\mathcal D}\ge{\mathcal E}$ est valable
dans tous les cas o\`u $a=c=1$.

\subsubsection{Sous-cas $a=1$, $c\ge2$}

Il reste le cas o\`u un exactement des deux nombres $a,c$ est $>1$.
Pour des raisons de sym\'etrie, il suffira d'\'etudier le cas
$a=1$, $c\ge2$.

Pour $b\ge2$, la multi-distance
\`a droite de \eqref{equation-K0}
\[ \epsfxsize=400pt \epsfbox{dg0_122.eps} \]
se d\'ecompose en
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1)
+ d({\bf u}'_1,{\bf u}'_2,\ldots,{\bf u}'_{a^*})
+ d({\bf u}'_{a^*},{\bf s}_{a^*},{\bf t}_{a^*})
+ d({\bf t}_{a^*},\ldots,{\bf u}'_L),
\end{equation*}
ce qui donne
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2a+2c + 2(S_3+S_b+S_2+S_{3c-2})(N-1) - 2 S_L(N) \\
&\qquad - (6S_1+\alpha_{\max\lbrace b,3\rbrace}+\alpha_b+\alpha_{3c-2})(N-2) \\
&= 2+2c + 2(S_3+S_b+S_2)(N-1) - 2 S_L(N)
- (6S_1+\alpha_{\max\lbrace b,3\rbrace}+\alpha_b)(N-2) \\
&\qquad + S_{3c-2}(N-1) + S_{3c-2}(N-2).
\end{align*}
Avec les in\'egalit\'es \eqref{minor-S-3a-2} et \eqref{majoration-2SLN},
il vient
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2(S_3+S_b+S_2)(N-1)
- (6S_1+\alpha_{\max\lbrace b,3\rbrace}+\alpha_b)(N-2) \\
&\qquad + (S_{c-1}-S_L)(N) + (S_{c-1}-S_{L-1})(N-1) - 2\alpha_1(N-1),
\end{align*}
et, comme $S_{c-1}-S_{1+b+c}\ge S_1-S_{b+3}$ et
$S_{c-1}-S_{b+c}\ge S_1-S_{b+2}$, on a
\begin{equation}
\begin{aligned}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2(S_3+S_b+S_2)(N-1)
- (6S_1+\alpha_{\max\lbrace b,3\rbrace}+\alpha_b)(N-2) \\
&\qquad + S_1(N) - S_{b+3}(N) + S_1(N-1) - S_{b+2}(N-1) - 2\alpha_1(N-1).
\end{aligned}
\label{minor-D-E-122}
\end{equation}

Pour $b\ge3$, cela s'\'ecrit
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2(S_3+S_2)(N-1) - 6S_1(N-2) + 2S_b(N-2) \\
&\qquad + S_1(N) - S_{b+3}(N) + S_1(N-1) - S_{b+2}(N-1) - 2\alpha_1(N-1),
\end{align*}
et, comme $S_{b+3}(N)\le(S_{b+2}+2\alpha_1)(N-1)$,
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2(S_3+S_2)(N-1) - 6S_1(N-2) + 2S_b(N-2) \\
&\qquad + S_1(N) + S_1(N-1) - 2S_{b+2}(N-1) - 4\alpha_1(N-1).
\end{align*}
Ensuite, $S_b(N-2)\ge S_{b+1}(N-1)-2\alpha_1(N-2)$ et
$S_{b+1}-S_{b+2}\ge S_1-S_2$, donc
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2(S_3+S_2)(N-1) - 6S_1(N-2) + 2S_{b+1}(N-1) - 4\alpha_1(N-2) \\
&\qquad + S_1(N) + S_1(N-1) - 2S_{b+2}(N-1) - 4\alpha_1(N-1) \\
&= 4 + 2S_3(N-1) - 6S_1(N-2) + 2S_1(N-1) - 4\alpha_1(N-2) \\
&\qquad + S_1(N) + S_1(N-1) - 4\alpha_1(N-1) \\
&= 2 + 3S_1(N) + 3S_1(N-1) - 6S_1(N-2) - 4\alpha_1(N-1) - 4\alpha_1(N-2) \\
&= 2 + 2\alpha_1(N-2) - \alpha_1(N-1),
\end{align*}
et cette expression est positive, par \eqref{croissance-alpha1}.
Ceci montre que ${\mathcal D}\ge{\mathcal E}$ si $b\ge3$.

Pour $b=2$, l'in\'egalit\'e \eqref{minor-D-E-122} s'\'ecrit
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2S_3(N-1) + 4S_2(N-1) - 6S_1(N-2) - \alpha_3(N-2) - \alpha_2(N-2) \\
&\qquad + S_1(N) + S_1(N-1) - S_5(N) - S_4(N-1) - 2\alpha_1(N-1) \\
&= 4 + S_3(N-1) + S_3(N-2) + 3S_2(N-1) + S_2(N-2) - 6S_1(N-2) \\
&\qquad + S_1(N) + S_1(N-1) - S_5(N) - S_4(N-1) - 2\alpha_1(N-1).
\end{align*}
On a $S_5(N)\le (S_4+2\alpha_1)(N-1)$
et $S_4(N-1)\le (S_3+2\alpha_1)(N-2)$, donc
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + S_3(N-1) + S_3(N-2) + 3S_2(N-1) + S_2(N-2) - 6S_1(N-2) \\
&\qquad + S_1(N) + S_1(N-1) - 2S_4(N-1) - 4\alpha_1(N-1) \\
&\ge 4 + S_3(N-1) - S_3(N-2) + 3S_2(N-1) + S_2(N-2) - 6S_1(N-2) \\
&\qquad + S_1(N) + S_1(N-1) - 4\alpha_1(N-1) - 4\alpha_1(N-2) \\
&= 4 + 3S_2(N-1) + S_2(N-2) \\
&\qquad + 2S_1(N) - 6S_1(N-2) - 4\alpha_1(N-1) - 4\alpha_1(N-2) \\
&\ge 4 + \tfrac32\bigl[ S_1(N-1)+S_1(N)-1 \bigr]
+ \tfrac12 \bigl[ S_1(N-2)+S_1(N-1)-1 \bigr] \\
&\qquad + 2S_1(N) - 6S_1(N-2) - 4\alpha_1(N-1) - 4\alpha_1(N-2) \\
&= 2 + \tfrac72 S_1(N) + 2S_1(N-1) - \tfrac{11}{2} S_1(N-2)
- 4\alpha_1(N-1) - 4\alpha_1(N-2) \\
&= 2 + \tfrac32 \alpha_1(N-2) - \tfrac12 \alpha_1(N-1),
\end{align*}
et cette expression est positive, par \eqref{croissance-alpha1}.
Ceci montre que ${\mathcal D}\ge{\mathcal E}$ si $b=2$.

Pour $b=1$ (et donc $a^*=2$ et $L=c+2$), la multi-distance
\`a droite de \eqref{equation-K0}
\[ \epsfxsize=350pt \epsfbox{dg0_112.eps} \]
se d\'ecompose en
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1)
+ d({\bf u}'_1,{\bf u}'_2,{\bf s}_2,{\bf t}_2)
+ d({\bf t}_2,\ldots,{\bf u}'_L),
\end{equation*}
ce qui donne
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2a+2c + 2(S_3+S_3+S_{3c-2})(N-1) - 2S_L(N) \\
&\qquad - (4S_1+\alpha_3+\alpha_{3c-2})(N-2) \\
&= 2+2c + 3S_3(N-1) + S_3(N-2) + S_{3c-2}(N-1) + S_{3c-2}(N-2) \\
&\qquad - 2S_L(N) - 4S_1(N-2).
\end{align*}
Avec les in\'egalit\'es \eqref{minor-S-3a-2} et \eqref{majoration-2SLN},
puis la concavit\'e des $S_L$, il vient
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 3S_1(N) + S_1(N-1) + (S_{c-1}-S_{c+2})(N) + (S_{c-1}-S_{c+1})(N-1) \\
&\qquad -2\alpha_1(N-1) - 4S_1(N-2) \\
&\ge 3S_1(N) + S_1(N-1) + (S_1-S_4)(N) + (S_1-S_3)(N-1) \\
&\qquad -2\alpha_1(N-1) - 4S_1(N-2) \\
&= 4S_1(N) + 2S_1(N-1) - S_4(N) - S_3(N-1) - 2\alpha_1(N-1) - 4S_1(N-2)
\end{align*}
et $S_4(N)\le(S_3+2\alpha_1)(N-1)$, donc
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4S_1(N) + 2S_1(N-1) - 2S_3(N-1) - 4\alpha_1(N-1) - 4S_1(N-2) \\
&= 2 + 2S_1(N) + 2S_1(N-1) - 4\alpha_1(N-1) - 4S_1(N-2) \\
&= 2 + 4\alpha_1(N-2) - 2\alpha_1(N-1),
\end{align*}
et cette expression est positive, par \eqref{croissance-alpha1}.
Ceci montre que ${\mathcal D}\ge{\mathcal E}$ si $b=1$.

Pour $b=0$ (et donc $L=c+1$), la multi-distance
\`a droite de \eqref{equation-K0}
\[ \epsfxsize=320pt \epsfbox{dg0_102.eps} \]
se d\'ecompose en
\begin{equation*}
d({\bf u}'_0,{\bf s}_0,{\bf t}_0,{\bf u}'_1,{\bf s}_1,{\bf t}_1)
+ d({\bf t}_1,\ldots,{\bf u}'_L),
\end{equation*}
ce qui donne
\begin{equation}
\begin{aligned}
{\mathcal D}-{\mathcal E}
&\ge 2a+2c + 2(S_5+S_{3c-2})(N-1) - 2S_L(N) \\
&\qquad - (2S_1 + \alpha_{\max\lbrace 5,3c-2\rbrace})(N-2).
\end{aligned}
\label{minor-D-E-102}
\end{equation}

Pour $c\ge3$, cela s'\'ecrit
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 2+2c + 2S_5(N-1) + S_{3c-2}(N-1) + S_{3c-2}(N-2) \\
&\qquad - 2S_L(N) - 2S_1(N-2).
\end{align*}
Avec les in\'egalit\'es \eqref{minor-S-3a-2} et \eqref{majoration-2SLN},
puis la concavit\'e des $S_L$, il vient
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2S_5(N-1) + (S_{c-1}-S_{c+1})(N) + (S_{c-1}-S_c)(N-1) \\
&\qquad - 2\alpha_1(N-1) - 2S_1(N-2) \\
&\ge 4 + 2S_5(N-1) + (S_2-S_4)(N) + (S_2-S_3)(N-1) \\
&\qquad - 2\alpha_1(N-1) - 2S_1(N-2).
\end{align*}

La concavit\'e des $S_L$ permet \'egalement d'\'ecrire
$3S_5\ge S_3+2S_6$, et donc
\begin{equation}
\begin{aligned}
S_5(n)
&\ge \tfrac13 S_3(n) + \tfrac23 S_6(n)
\ge \tfrac13 S_1(n+1) + \tfrac23 S_2(n+1) - \tfrac53 \\
&\ge \tfrac13 S_1(n+1) + \tfrac13 \bigl[ S_1(n+1)+S_1(n+2)-1 \bigr] - \tfrac53 \\
&= \tfrac23 S_1(n+1) + \tfrac13 S_1(n+2) - 2
\end{aligned}
\label{minoration-S5}
\end{equation}
pour tout $n$ entier naturel.
Avec ceci, et l'in\'egalit\'e $S_4(N)\le(S_3+2\alpha_1)(N-1)$, on obtient
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 4 + 2S_5(N-1) + S_2(N) + S_2(N-1) - S_4(N) - S_3(N-1) \\
&\qquad - 2\alpha_1(N-1) - 2S_1(N-2) \\
&\ge 4 + 2S_5(N-1) + S_2(N) + S_2(N-1) \\
&\qquad - 2S_3(N-1) - 4\alpha_1(N-1) - 2S_1(N-2) \\
&\ge 4 + \tfrac43 S_1(N) + \tfrac23 S_1(N+1) - 4 \\
&\qquad + \tfrac12 S_1(N) + \tfrac12 S_1(N+1) - \tfrac12
+ \tfrac12 S_1(N-1) + \tfrac12 S_1(N) - \tfrac12 \\
&\qquad -2S_1(N) + 2 - 4\alpha_1(N-1) - 2S_1(N-2) \\
&= 1 + \tfrac12 S_1(N-1) + \tfrac13 S_1(N) + \tfrac76 S_1(N+1)
- 4\alpha_1(N-1) - 2S_1(N-2) \\
&= 1 + 2\alpha_1(N-2) - \tfrac52 \alpha_1(N-1) + \tfrac76 \alpha_1(N) \\
&\ge 1 + 2\alpha_1(N-2) - \tfrac43 \alpha_1(N-1),
\end{align*}
et cette expression est positive, comme on le v\'erifie
facilement \`a l'aide du Lemme~\ref{croissance2-alpha1}.
Ceci montre que ${\mathcal D}\ge{\mathcal E}$ si $b=0, c\ge3$.

Pour $c=2$, l'in\'egalit\'e \eqref{minor-D-E-102} s'\'ecrit
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 6 + 2(S_5+S_4)(N-1) - 2S_3(N) - (2S_1+\alpha_5)(N-2) \\
&= 6 + S_5(N-1) + S_5(N-2) + 2S_4(N-1) - 2S_3(N) - 2S_1(N-2),
\end{align*}
et des minorations \eqref{minoration-S4} et \eqref{minoration-S5} on
d\'eduit
\begin{align*}
{\mathcal D}-{\mathcal E}
&\ge 6 + \tfrac23 S_1(N) + \tfrac13 S_1(N+1) - 2
+ \tfrac23 S_1(N-1) + \tfrac13 S_1(N) - 2 \\
&\qquad + \tfrac53 S_1(N) + \tfrac13 S_1(N+1) - 3
- 2S_1(N+1) + 2 - 2S_1(N-2) \\
&= 1 + \tfrac23 S_1(N-1) + \tfrac83 S_1(N) - \tfrac43 S_1(N+1) - 2S_1(N-2) \\
&= 1 + 2\alpha_1(N-2) + \tfrac43 \alpha_1(N-1) - \tfrac43 \alpha_1(N) \\
&\ge 1 + 2\alpha_1(N-2) -\tfrac43 \alpha_1(N-1),
\end{align*}
et cette expression, on l'a vu, est positive.
Ceci montre que ${\mathcal D}\ge{\mathcal E}$ si $b=0, c=2$.

Nous avons ainsi \'etabli l'in\'egalit\'e ${\mathcal D}\ge{\mathcal E}$ dans tous
les cas o\`u $K=0$. Ceci termine la preuve de la r\'ecurrence, et donc
du Th\'eor\`eme~\ref{theoreme-principal}.

\section{Pourquoi ces p\'enalit\'es?}

La d\'emonstration du Th\'eor\`eme~\ref{theoreme-principal}, on le voit,
est fastidieuse \`a cause de la disjonction de cas, mais pas vraiment
difficile. En fait, l'essentiel de la difficult\'e dans le probl\`eme
de Stockmeyer consiste \`a imaginer la ``bonne'' minoration sur les
distances entre empilements. Dans ce chapitre, je t\^acherai d'expliquer
comment je suis arriv\'e \`a cette in\'egalit\'e.

Une ``bonne'' minoration des distances doit \^etre (i) vraie, \'evidemment,
(ii) devenir une \'egalit\'e entre les empilements qui nous int\'eressent,
et, ce qui est sans doute le plus difficile \`a r\'ealiser, (iii) se pr\^eter
\`a une d\'emonstration par r\'ecurrence sur le nombre de disques.

Je me suis \'evidemment inspir\'e des m\'ethodes de l'article
\cite{bousch} pour la r\'esolution du {\it Reve's Puzzle}, mais la Tour
de Stockmeyer pr\'esente certaines particularit\'es qui font que ces
m\'ethodes ne sont pas toutes utilisables, et qu'il faut en introduire de
nouvelles.

Une diff\'erence importante est que le {\it Reve's Puzzle\/} poss\`ede
la propri\'et\'e de {\it midpoint\/} \cite{bode-hinz,korf-felner}, qui
dit qu'entre deux empilements parfaits, il existe un chemin
g\'eod\'esique sym\'etrique autour de son ar\^ete centrale, qui est
l'unique mouvement du plus grand disque.
Entre deux empilements quelconques, les choses sont plus compliqu\'ees,
mais des arguments similaires permettent de d\'ecomposer le chemin en
une ``partie gauche'' et une ``partie droite'' dont les longueurs
peuvent \^etre \'evalu\'ees par une m\^eme formule; ceci est utilis\'e
dans \cite{bousch} pour montrer l'\'equivalence entre les in\'egalit\'es
(5.3) et (5.4). Ces derni\`eres in\'egalit\'es sont plus commodes, car
elles ne d\'ependent que d'une des extr\'emit\'es du chemin~: gr\^ace \`a
\c ca, elles peuvent \^etre facilement ``monotonis\'ees'' (une
manipulation qui joue un r\^ole essentiel dans \cite{bousch}).

Il ne semble pas possible de faire quelque chose de similaire pour la
Tour de Stockmeyer~: m\^eme entre empilements parfaits (sur des tiges
ext\'erieures), le plus grand disque effectue deux mouvements, ce qui
d\'ecompose le chemin en trois parties~: une partie gauche et une partie
droite, mais aussi une partie centrale qui n'est pas de m\^eme nature.
On doit donc se contenter d'in\'egalit\'es telles que
\eqref{minor-dist-simple} ou \eqref{min-mda-gen}, qui font d\'ependre la
longueur du chemin de ses deux extr\'emit\'es.
Cette double d\'ependance complique et affaiblit beaucoup la monotonisation,
qui du coup ne para{\^\i}t plus du tout souhaitable.

D'autres diff\'erences sont que le nombre (conjecturalement) minimum de
mouvements de disques est plus compliqu\'e pour la Tour de Stockmeyer
que pour le {\it Reve's Puzzle}, et que le groupe de sym\'etrie est
plus petit. Tout cela sugg\`ere que le probl\`eme de Stockmeyer n'est
peut-\^etre pas si facile \dots

J'ai expliqu\'e en \S~2 comment on est amen\'e \`a postuler
l'in\'egalit\'e \eqref{min-mda-par} pour les multi-distances
alternantes entre configurations parfaites. Comment modifier cette
in\'egalit\'e conjecturale si les configurations ${\bf u}_0,
{\bf u}_L$ ne sont plus suppos\'ees parfaites?

On consid\'erera l'exemple suivant~: on reprend les notations de \S~2,
avec $L\ge1$, ${\bf u}_0$ et ${\bf u}_L$ sont les configurations parfaites
\`a $N$ disques
sur les tiges ${\mathsf p}_0$ et ${\mathsf p}_L$, et $\tilde{\bf u}_0,
\tilde{\bf u}_L$ les empilements obtenus \`a partir de
${\bf u}_0,{\bf u}_L$ en transf\'erant les $M$ plus petits disques
vers la tige $2$. Il est clair qu'on peut aller de ${\bf u}_0$ vers
$\tilde{\bf u}_L$ (ou de $\tilde{\bf u}_0$ vers ${\bf u}_L$) avec
$2 S_1(M) + L\,(3^{N-M}\!-1)$ mouvements de disques, et de
$\tilde{\bf u}_0$ vers $\tilde{\bf u}_L$ avec $L\,(3^{N-M}\!-1)$
mouvements de disques --- en passant, dans tous les cas, par les m\^emes
configurations interm\'ediaires ${\bf u}_1,\ldots,{\bf u}_{L-1}$.
On a donc
\begin{align*}
d({\bf u}_0,{\bf u}_1,\ldots,{\bf u}_{L-1},{\bf u}_L)
&\le 2S_1(N) ,\\
d({\bf u}_0,{\bf u}_1,\ldots,{\bf u}_{L-1},\tilde{\bf u}_L)
&\le 2S_1(N) - 2S_1(M),\\
d(\tilde{\bf u}_0,{\bf u}_1,\ldots,{\bf u}_{L-1},{\bf u}_L)
&\le 2S_1(N) - 2S_1(M),\\
d(\tilde{\bf u}_0,{\bf u}_1,\ldots,{\bf u}_{L-1},\tilde{\bf u}_L)
&\le 2S_1(N) - 4S_1(M),
\end{align*}
et il est raisonnable de supposer que ces in\'egalit\'es sont en
fait des \'egalit\'es. Si c'est le cas, on voit que la multi-distance
est diminu\'ee de
$2S_1(M) = \sum\limits_{\mkern-8mu k<M \mkern-8mu} 2\alpha_1(k)$
si les $M$
plus petits disques sont hors de la colonne ${\mathsf p}_0$ au d\'epart,
et diminu\'ee d'autant s'ils sont hors de la colonne ${\mathsf p}_L$
\`a l'arriv\'ee, ces deux effets pouvant se cumuler. Cet exemple, et
d'autres similaires, sugg\`erent la formule
\begin{equation}
d({\bf u}_0,{\bf u}_1,\ldots,{\bf u}_L) \,\ge\, 2 S_L(N)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N} \\ {\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern -14mu 2\alpha_1(k)
- \mkern -15mu
  \sum_{\substack{k\in\intset{N} \\ {\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern -15mu 2\alpha_1(k)
\label{min-mda-gen2}
\end{equation}
pour les multi-distances alternantes entre deux configurations extr\^emes
quelconques.

Cette in\'egalit\'e (conjecturale) semble donc un bon point de d\'epart
pour une d\'emon\-stration. On peut, comme en \S~4, essayer de d\'emontrer
\eqref{min-mda-gen2} par r\'ecurrence entre $N-1$ et $N$ disques, par
une disjonction de cas sur les mouvements du plus grand disque~:
cela conduit \`a un certain nombre d'in\'egalit\'es \`a d\'emontrer sur
les $S_L$, une pour chaque cas.
Beaucoup de ces in\'egalit\'es sont vraies (au moins
num\'eriquement, je n'ai pas cherch\'e \`a les prouver rigoureusement),
mais un petit nombre d'entre elles sont fausses --- et donc, cette
id\'ee de preuve ne fonctionne pas.

On pourrait envisager de d\'emontrer \eqref{min-mda-gen2} par
une r\'ecurrence entre $N-2$ et $N$ disques, mais cela n\'ecessiterait
une disjonction de cas portant sur les mouvements des deux plus grands
disques, et serait probablement tr\`es fastidieux.
Il para{\^\i}t pr\'ef\'erable de s'en tenir \`a une r\'ecurrence entre
$N-1$ et $N$ disques. La pr\'ec\'edente tentative de preuve de
\eqref{min-mda-gen2} ayant \'echou\'e de peu, on se dit qu'une toute
petite am\'elioration de cette in\'egalit\'e suffirait pour venir
\`a bout des quelques cas probl\'ematiques.

En outre, dans la r\'ecurrence appara{\^\i}t une complication technique~:
l'augmentation du terme constant $2 S_L(\cdot)$ entre $N-1$ et $N$
disques, \`a savoir $2\alpha_L(N-1)$, ne pr\'esente pas de relation
simple avec la p\'enalit\'e du plus grand disque, qui vaut
$2\alpha_1(N-1)$, lorsque $L>1$.
Cela a pour cons\'equence que les in\'egalit\'es sur $N-1$ et $N$
disques ne se raccordent pas tr\`es bien, m\^eme dans des cas qui
devraient \^etre triviaux.
En particulier, si le plus grand disque est dans la colonne $2$ au
d\'epart et \`a l'arriv\'ee, il n'a aucun int\'er\^et \`a bouger, et
$d({\bf u}_0,\ldots,{\bf u}_L)=d({\bf u}'_0,\ldots,{\bf u}'_L)$.
Cependant, la formule \eqref{min-mda-gen2} donnera des minorations
diff\'erentes pour $d({\bf u}_0,\ldots,{\bf u}_L)$ et $d({\bf
u}'_0,\ldots,{\bf u}'_L)$, ce qui n'est pas tr\`es satisfaisant.
Cela sugg\`ere que pour $L>1$ la p\'enalit\'e du plus grand disque n'est
peut-\^etre pas la bonne, et devrait \^etre $\alpha_L(N-1)$ au lieu de
$2\alpha_1(N-1)$.

Pour $L=1$, aucune am\'elioration (i.e.\ diminution) des p\'enalit\'es
n'est possible, comme on le voit en prenant pour ${\bf u}_0,{\bf u}_1$
deux configurations parfaites identiques.

En r\'esum\'e, il semble que pour $L>1$ (et $N\ge1$)
la ``bonne'' minoration des
multi-distances alternantes serait plut\^ot
\begin{equation}
\begin{aligned}
d({\bf u}_0,{\bf u}_1,\ldots,{\bf u}_L) \,\ge\, 2 S_L(N)
&-\mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern -14mu 2\alpha_1(k)
- \mkern -14mu
  \sum_{\substack{k\in\lbrace N-1\rbrace \\ {\bf u}_0(k)\ne{\mathsf p}_0}}
  \mkern -14mu \alpha_L(k) \\
&-\mkern -16mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern -16mu 2\alpha_1(k)
- \mkern -16mu
  \sum_{\substack{k\in\lbrace N-1\rbrace \\ {\bf u}_L(k)\ne{\mathsf p}_L}}
  \mkern -16mu \alpha_L(k),
\end{aligned}
\label{min-mda-gen3}
\end{equation}
in\'egalit\'e l\'eg\`erement plus fine que \eqref{min-mda-gen2} puisque la
p\'enalit\'e du plus grand disque est plus petite, et qui se comporte mieux
vis-\`a-vis de la r\'ecurrence.

Mais justement, comme c'est un \'enonc\'e plus fort, il a plus de chances
d'\^etre faux. Les arguments ci-dessus ne disent rien quant \`a la
{\em v\'eracit\'e\/} de la formule \eqref{min-mda-gen3}, seulement
que les calculs pourraient se passer mieux qu'avec \eqref{min-mda-gen2}.
Et puis, la formule \eqref{min-mda-gen3} n'a pas une tr\`es bonne
t\^ete~: elle est manifestement trop compliqu\'ee, fait jouer un r\^ole
sp\'ecial au plus grand disque, et n'inclut pas le cas $L=1$. Pourquoi
devrait-on y croire?

La raison est un argument de type {\it midpoint}, qui affirme que pour
toute valeur {\em paire\/} de $L$, on peut d\'eduire les in\'egalit\'es
\eqref{min-mda-gen3} des in\'egalit\'es \eqref{min-mda-gen2} pour la
m\^eme valeur de $L$. Pour fixer les id\'ees, examinons le cas
$L=4$. On veut montrer que toute multi-distance alternante
(\`a quatre termes) satisfait
\begin{equation*}
d({\bf u}_0,{\bf u}_1,{\bf u}_2,{\bf u}_3,{\bf u}_4) \,\ge\, 2 S_4(N)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_0(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_4(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
- K \alpha_4(N-1),
\end{equation*}
o\`u $K\in\lbrace 0,1,2\rbrace$ est d\'efini par \eqref{def-K}.
Si $K=0$, c'est-\`a-dire
${\bf u}_0(N-1)={\bf u}_4(N-1)=1$, cette in\'egalit\'e est identique
\`a \eqref{min-mda-gen2}, et il n'y a rien \`a d\'emontrer.
Si $K=2$, c'est-\`a-dire ${\bf u}_0(N-1)\ne1$ et ${\bf u}_4(N-1)\ne1$,
on \'ecrit
\begin{align*}
d({\bf u}_0,{\bf u}_1,{\bf u}_2,{\bf u}_3,{\bf u}_4)
&\ge d({\bf u}'_0,{\bf u}'_1,{\bf u}'_2,{\bf u}'_3,{\bf u}'_4) \\
&\ge
2 S_4(N-1)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_0(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_L(k)\ne1}}
  \mkern -14mu 2\alpha_1(k) \\
&=
2 S_4(N)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_0(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_L(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
- 2 \alpha_4(N-1),
\end{align*}
qui est l'in\'egalit\'e cherch\'ee.

Reste le cas $K=1$, c'est-\`a-dire que ${\bf u}_0(N-1)\ne1$ ou bien
${\bf u}_4(N-1)\ne1$. Ces deux cas \'etant sym\'etriques, je supposerai
par exemple ${\bf u}_0(N-1)=1\ne{\bf u}_4(N-1)$.
C'est ici qu'intervient la parit\'e de $L$~: on \'ecrit
\begin{align*}
d({\bf u}_0,{\bf u}_1,{\bf u}_2,{\bf u}_3,{\bf u}_4)
&= d({\bf u}_0,{\bf u}_1,{\bf u}_2) + d({\bf u}_2,{\bf u}_3,{\bf u}_4) \\
&\ge d({\bf u}_0,{\bf u}_1,{\bf u}_2) + d({\bf u}'_2,{\bf u}'_3,{\bf u}'_4) \\
&\ge \tfrac12 d({\bf u}_0,{\bf u}_1,{\bf u}_2,{\bf u}_1,{\bf u}_0) +
\tfrac12 d({\bf u}'_4,{\bf u}'_3,{\bf u}'_2,{\bf u}'_3,{\bf u}'_4).
\end{align*}
Ces deux derni\`eres multi-distances sont alternantes, donc on peut leur
appliquer la minoration \eqref{min-mda-gen2}, ce qui donne
\begin{align*}
d({\bf u}_0,{\bf u}_1,{\bf u}_2,{\bf u}_1,{\bf u}_0)
&\ge 2 S_4(N)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N} \\ {\bf u}_0(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N} \\ {\bf u}_0(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
= 2 S_4(N)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_0(k)\ne1}}
  \mkern -14mu 4\alpha_1(k),
\\
d({\bf u}'_4,{\bf u}'_3,{\bf u}'_2,{\bf u}'_3,{\bf u}'_4)
&\ge 2 S_4(N-1)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_4(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_4(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
= 2 S_4(N-1)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_4(k)\ne1}}
  \mkern -14mu 4\alpha_1(k),
\end{align*}
et par cons\'equent
\begin{equation*}
d({\bf u}_0,{\bf u}_1,{\bf u}_2,{\bf u}_3,{\bf u}_4)
\ge 2 S_4(N)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_0(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
- \mkern -14mu
  \sum_{\substack{k\in\intset{N-1} \\ {\bf u}_4(k)\ne1}}
  \mkern -14mu 2\alpha_1(k)
- \alpha_4(N-1),
\end{equation*}
qui est l'in\'egalit\'e cherch\'ee.

Cet argument s'\'etend \'evidemment \`a toute valeur paire de $L$ (et
plus g\'en\'eralement, quand le produit $KL$ est pair). Bien qu'il ne
suffise pas \`a \'etablir \eqref{min-mda-gen3} dans tous les cas, il
sugg\`ere que ces in\'egalit\'es ont de bonnes chances
d'\^etre vraies, et qu'on peut se lancer avec confiance dans une
d\'emonstration.

\bigskip

{\it Remerciements.}
Je remercie Codrut Grosu et Andreas Hinz pour leurs commentaires sur
le texte, ainsi que la correction d'un certain nombre d'erreurs.

%\newpage
\renewcommand\refname{R\'ef\'erences}
\begin{thebibliography}{xxxx}
%\addcontentsline{toc}{section}{R\'ef\'erences}

\bibitem[BH]{bode-hinz} {\sc J.-P.~Bode \& A.~M.~Hinz}, {\it Results and
open problems on the Tower of Hanoi}, Congressus Numerantium {\bf 139}
(1999), 113--122

\bibitem[Bou]{bousch} {\sc T.~Bousch}, {\it La quatri\`eme tour de
Hano\"\i}, Bulletin of the Belgian Mathematical Society Simon Stevin
{\bf 21} (2014), 895--912

\bibitem[CM]{chappelon} {\sc J.~Chappelon \& A.~Matsuura},
{\it On generalized Frame--Stewart numbers},
Discrete Mathematics {\bf 312} (2012), 830--836

\bibitem[CS]{chen-shen} {\sc X.~Chen \& J.~Shen}, {\it On the Frame--Stewart
conjecture about the Towers of Hanoi}, SIAM Journal on Computing
{\bf 33} (2004), 584--589

\bibitem[Dud]{dudeney} {\sc H.~E.~Dudeney}, {\it The Canterbury puzzles
and other curious problems}, E.~P.~Dutton, New York (1908)

\bibitem[Dun]{dunkel} {\sc O.~Dunkel}, {\it Editorial Note concerning
Advanced Problem 3918}, American Mathematical Monthly {\bf 48} (1941),
page 219

\bibitem[Gro]{grosu} {\sc C.~Grosu},
{\it A new lower bound for the Towers of Hanoi problem},
Electronic Journal of Combinatorics {\bf 23} (2016), Article~\#P1.22

\bibitem[HP]{hinz-petr} {\sc A.~M.~Hinz \& C.~Petr},
{\it Computational solution of an old Tower of Hanoi problem},
Electronic Notes in Discrete Mathematics {\bf 53} (2016), 445--458 

\bibitem[H+]{tohbook} {\sc A.~M.~Hinz, S.~Klav\v zar, U.~Milutinovi\'c \&
C.~Petr}, {\it The tower of Hanoi, myths and maths}, Birkh\"auser (2013)

\bibitem[Fra]{frame} {\sc J.~S.~Frame}, {\it Solution to Advanced
Problem 3918}, American Mathematical Monthly {\bf 48} (1941), 216--217

\bibitem[Knu]{knuth} {\sc D.~E.~Knuth}, {\it The art of computer programming,
volume 3: sorting and searching}, Addison--Wesley (1973)

\bibitem[KF]{korf-felner} {\sc R.~E.~Korf \& A.~Felner}, {\it Recent
progress in heuristic search: a case study of the four-peg towers of Hanoi
problem}, Proceedings of the twentieth international joint conference on
artificial intelligence, AAAI Press (2007), 2324--2329

\bibitem[Min]{mintz} {\sc D.~J.~Mintz}, {\it 2,3 sequence as binary
mixture}, Fibonacci Quarterly {\bf 19} (1981), 351--360

\bibitem[Mor]{moree} {\sc P.~Moree}, {\it Integers without large
prime factors: from Ramanujan to de Bruijn},
Integers {\bf 14A} (2014), Article~\#A5

\bibitem[Roc]{rockafellar} {\sc R.~T.~Rockafellar}, {\it Convex analysis},
Princeton Mathematical Series {\bf 28}, Princeton University Press (1970)

\bibitem[Slo]{sloane} {\sc N.~J.~A.~Sloane}, {The On-line Encyclopedia
of Integer Sequences}, {\tt http://oeis.org}

\bibitem[St1]{stewart1} {\sc B.~M.~Stewart}, {\it Advanced Problem 3918},
American Mathematical Monthly {\bf 46} (1939), page 363

\bibitem[St2]{stewart2} {\sc B.~M.~Stewart}, {\it Solution to
Advanced Problem 3918}, American Mathematical Monthly {\bf 48} (1941),
217--219

\bibitem[Sto]{stockmeyer} {\sc P.~K.~Stockmeyer}, {\it Variations on the
four-post Tower of Hanoi puzzle}, Congressus Numerantium {\bf 102}
(1994), 3--12

\bibitem[Sze]{szegedy} {\sc M.~Szegedy}, {\it In how many steps the
$k$-peg version of the Towers of Hanoi game can be solved?},
Lecture Notes in Computer Science {\bf 1563} (1999), 356--361

\end{thebibliography}

\end{document}
