Séminaire Lotharingien de Combinatoire 77 (2017), Article B77d

LA TOUR DE STOCKMEYER

THIERRY BOUSCH

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.

Résumé. En 1994, Paul Stockmeyer a proposé une variante à quatre tiges de la Tour d’Hanoï, avec trois tiges extérieures disposées en étoile autour d’une tige centrale, et la restriction qu’on ne peut déplacer les disques qu’entre une tige extérieure et la tige centrale. Il a démontré qu’on peut transférer N disques d’une tige extérieure vers une autre en 2S_{1}(N) mouvements, où S_{1}(N) désigne la somme des N plus petits entiers de la forme 2^{a}3^{b}, et conjecturé que ce nombre ne pouvait être diminué. C’est ce que je démontre dans le présent article.

Table des matières

1. Introduction

2. Formulation de l’inégalité principale 3 3. Quelques propriétés des fonctions S_{L} 8 4. Démonstration de l’inégalité principale 12 4.1. Le cas K = 1, avec L ⩾ 2 13 4.2. Le cas K = 0 17 5. Pourquoi ces pénalités? 27 Références 30

1. Introduction

La Tour d’Hanoï, jeu mathématique inventé par Edouard Lucas en 1883, a immédiatement suscité de nombreuses variantes, certaines dues à Lucas lui-même. Cependant, la variante la plus naturelle, qui consiste à modifier le nombre de tiges et rien d’autre, n’a été considérée qu’assez tard, vers 1900, par Henry Ernest Dudeney. Comme dans le problème original, on doit transférer une “tour” de N disques d’une tige vers une autre, en un minimum de mouvements. Ce problème est publié par Dudeney dans [Dud], avec une esquisse de solution. Il réapparaît en 1939 parmi les “advanced problems” de l’American Mathematical Monthly [St1]. Deux ans plus tard, en 1941, James Sutherland Frame

2010 Mathematics Subject Classification. 05C12. Key words and phrases. Star Tower of Hanoi, Stockmeyer puzzle.

[Fra] et Bonnie Madison Stewart [St2] démontrent (indépendamment) qu’avec h + 2 tiges (h ⩾ 1), il est possible de transférer N disques en

2^{E(0)} + 2^{E(1)} + ⋯ + 2^{E(N−1)}

mouvements, où E(n) désigne le plus grand entier p tel que

\frac{p(p + 1) ⋯ (p + h − 1)}{h!} ⩽ n,

et fournissent une procédure explicite pour cela.

(Comme l’a montré Andreas Hinz [HP], cette formule et cette procédure se trouvent déjà en germe dans les écrits de Dudeney, mais sans rien qui ressemble à une démonstration.)

En revanche, Frame et Stewart n’ont pas démontré que ce nombre de mouvements était le plus petit possible [Dun]. La minimalité de ce nombre constitue la Conjecture de Frame–Stewart, qui est encore ouverte aujourd’hui, malgré des résultats partiels nombreux et encourageants : des expériences numériques poussées [KF], des minorations du nombre minimum de mouvements [Sze, CS, Gro] qui approchent de mieux en mieux la valeur conjecturée, et la résolution du cas de quatre tiges [Bou].

Mais la Tour d’Hanoï peut être étendue 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à encore, une procédure permettant de transférer tous les disques d’une tige vers une autre avec un minimum de mouvements.

Ces variantes, avec mouvements restreints, peuvent déjà être posées avec trois tiges, mais sont surtout intéressantes, et difficiles, avec quatre tiges ou plus [Sto]. Elles sont même tellement difficiles que, dans de nombreux cas, on n’a aucune idée de la stratégie optimale pour transférer les disques, ni du nombre minimum de mouvements. (Ce n’est pas tout à fait exact : les gens ont eu beaucoup d’idées… mais qui ont toutes été réfutées par les expériences numériques : voir la discussion dans [Sto, sections 2 et 3].)

Paul Stockmeyer propose donc de s’intéresser à une variante particulière, pour laquelle on a une stratégie de résolution qui est conjecturalement optimale, et une formule close pour le nombre de mouvements correspondant. C’est le “Star Puzzle” [Sto], aussi appelé “Star Tower of Hanoi” (dans [H+, pages 251–254]), et qu’on pourrait aussi bien appeler “Tour de Stockmeyer” : sur un plateau se trouvent quatre tiges, dont trois (les “tiges extérieures”) sont disposées en étoile autour d’une tige centrale (voir Figure 1). Les disques ne peuvent se déplacer que d’une tige extérieure vers la tige centrale, ou inversement. A cela s’ajoutent les règles habituelles de la Tour d’Hanoï : on ne peut déplacer qu’un disque à la fois, d’une tige vers une autre, et sans jamais poser un disque sur un disque plus petit.

Dans cette variante, Stockmeyer démontre, par une stratégie de type Frame–Stewart, qu’on peut transférer N disques d’une tige extérieure vers une autre tige extérieure en 2S_{1}(N) mouvements, où la fonction S_{1} : ℕ → ℕ est définie par la récurrence

S_{1}(N) = \begin{cases}Min_{0⩽M<N} 2S_{1}(M) + \frac{1}{2}(3^{N−M} − 1), & si N ⩾ 1, \\ 0, & si N = 0. \end{cases}  (1.1)

En outre, il conjecture que cette stratégie est optimale, c’est-à-dire qu’il est impossible de transférer N disques d’une tige extérieure vers une autre en moins que 2S_{1}(N) mouvements.

Figure 1. La Tour de Stockmeyer (ici avec 5 disques)

Mais ce n’est pas tout. On sait résoudre cette récurrence, avec un résultat 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ère. On trouvera des résultats similaires, un peu plus généraux, dans [CM]. On sait également calculer l’unique valeur de M qui réalise le minimum dans (1.1).

Le but du présent article est de démontrer que l’algorithme de Stockmeyer est bien optimal, c’est-à-dire que toute manière de déplacer N disques d’une tige extérieure vers une autre comporte au moins 2S_{1}(N) mouvements.

2. Formulation de l’inégalité principale

Fixons tout de suite les notations, et la représentation du jeu, en suivant [Bou].

On note ℕ = {0, 1, 2, …} l’ensemble des entiers naturels, et pour tout entier naturel n, on note [n] l’ensemble des n plus petits entiers naturels, c.à.d. {0, 1, …, n − 1}; en particulier [0] = ∅. Le symbole de Kronecker δ(x, y) est défini comme 1 si x = y, et 0 sinon; j’utiliserai également δ̄(x, y) = 1 − δ(x, y). On notera (x)^{+} la partie positive de x, c’est-à-dire max{x, 0}.

L’ensemble des tiges (ou colonnes) sera noté 𝒞 = {0, 1, 2, 3}, où 0 désigne la tige centrale. Un empilement (de N disques sur 𝒞) désigne une configuration “autorisée” du jeu, c’est-à-dire n’importe quelle manière de répartir les disques entre les tiges, avec sur chaque tige les disques empilés par taille décroissante. Un empilement définit une fonction (quelconque) [N] → 𝒞, 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 𝒞^{[N]}.

Chacun des ensembles 𝒞^{[N]} est muni d’une structure de graphe non-orienté : deux empilements distincts u, v sont adjacents s’il existe exactement un k ∈ [N] pour lequel u(k) ≠ v(k), l’un de ces deux nombres étant 0, et de plus u(i) ∉ {u(k), v(k)} pour tout i < k. Ce graphe est connexe, et la distance associée, notée d, donne le nombre minimum de mouvements pour passer d’un empilement à un autre (en respectant les règles du jeu).

J’aurai souvent à considérer des “multi-distances” dans 𝒞^{[N]}, c’est-à-dire des expressions de la forme

d(u_{0}, u_{1}) + d(u_{1}, u_{2}) + ⋯ + d(u_{L−1}, u_{L})

(où L ⩾ 0), que j’écrirai sous forme abrégée

d(u_{0}, u_{1}, …, u_{L}).

En effet, ces multi-distances s’interprètent comme la longueur minimum d’un chemin passant par les configurations u_{0}, u_{1}, …, u_{L}, dans cet ordre.

Les empilements parfaits (extérieurs), consistant à mettre tous les disques sur une même tige (extérieure), ne sont pas autre chose que les fonctions constantes (non nulles) de [N] dans 𝒞.

On définit la fonction S_{1} : ℕ → ℕ par la formule (1.1), et on note α_{1} : ℕ → ℕ ses différences finies, i.e.

α_{1}(n) = S_{1}(n + 1) − S_{1}(n),

ce qui permet d’écrire

S_{1}(n) = α_{1}(0) + α_{1}(1) + ⋯ + α_{1}(n − 1).

Comme le montre Stockmeyer [Sto], la fonction α_{1} est le réarrangement croissant des nombres 2^{a}3^{b}, c’est-à-dire l’unique bijection croissante de ℕ vers l’ensemble

ℛ = {2^{a}3^{b} : a, b ∈ ℕ} = {1, 2, 3, 4, 6, 8, 9, …}.  (2.1)

Comme ℛ est un monoïde multiplicatif, la fonction α_{1} satisfait α_{1}(m + n) ⩽ α_{1}(m) α_{1}(n) pour tous m, n. En particulier, on a toujours

α_{1}(n) < α_{1}(n + 1) ⩽ 2α_{1}(n).  (2.2)

Voici les premières valeurs des fonctions S_{1} et α_{1} :

\begin{matrix}N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ S_{1}(N) & 0 & 1 & 3 & 6 & 10 & 16 & 24 & 33 & 45 & 61 & 79 & 103 & 130 & 162 & 198 \\ α_{1}(N) & 1 & 2 & 3 & 4 & 6 & 8 & 9 & 12 & 16 & 18 & 24 & 27 & 32 & 36 & 48 \end{matrix}

La fonction α_{1} est la suite A3586 dans OEIS [Slo]; voir aussi la suite A71521. Le nombre N(x) d’entiers ⩽ x de la forme 2^{a}3^{b} satisfait, d’après Ramanujan et Pillai,

N(x) = \frac{log(2x) log(3x)}{2 log 2 log 3} + o(log x)

pour x grand (voir [Mor, section 6]), ce qui entraîne, pour n grand,

log α_{1}(n) = \sqrt{2n log 2 log 3} − \frac{1}{2} log 6 + o(1),

et fournit les équivalents

α_{1}(n) ∼ \frac{1}{\sqrt{6}} exp \sqrt{2n log 2 log 3}  (2.3)

et

S_{1}(n) ∼ \sqrt{\frac{n}{3 log 2 log 3}} exp \sqrt{2n log 2 log 3}  (2.4)

Pour comparaison, on sait que le nombre minimum de mouvements dans le Reve’s Puzzle est approximativement \sqrt{n} 2^{\sqrt{2n}}, mais cette approximation n’est pas un équivalent : voir la discussion dans [Sto, section 1].

Il sera commode d’inclure S_{1} dans une famille S_{0}, S_{1}, S_{2}, … de fonctions, de la manière suivante : pour tout entier naturel L ≠ 1, on définit la fonction S_{L} : ℕ → ℕ par

S_{L}(N) = Min_{0⩽M⩽N} 2S_{1}(M) + \frac{1}{2}L (3^{N−M} − 1).  (2.5)

Notons que cette formule reste valable pour L = 1, ce qui justifie qu’on considère S_{1} (déjà définie) comme faisant partie de la famille. Puis, on définit les fonctions α_{L} : ℕ → ℕ comme les différences finies des S_{L} :

α_{L}(n) = S_{L}(n + 1) − S_{L}(n),  (2.6)

ce qui permet d’écrire

S_{L}(n) = α_{L}(0) + α_{L}(1) + ⋯ + α_{L}(n − 1).  (2.7)

Voici les premières valeurs des fonctions S_{L} et α_{L} :

\begin{matrix}N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 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{matrix}

\begin{matrix}N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ α_{0}(N) & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ α_{1}(N) & 1 & 2 & 3 & 4 & 6 & 8 & 9 & 12 & 16 & 18 & 24 & 27 \\ α_{2}(N) & 2 & 2 & 4 & 6 & 6 & 8 & 12 & 16 & 18 & 18 & 24 & 32 \\ α_{3}(N) & 2 & 3 & 4 & 6 & 8 & 9 & 12 & 16 & 18 & 24 & 27 & 32 \\ α_{4}(N) & 2 & 4 & 4 & 6 & 8 & 12 & 12 & 16 & 18 & 24 & 32 & 36 \\ α_{5}(N) & 2 & 4 & 5 & 6 & 8 & 12 & 15 & 16 & 18 & 24 & 32 & 36 \end{matrix}

On observe sur cette table que les α_{L}(N) sont des nombres “friables”, c’est-à-dire sans grands diviseurs premiers. On constate aussi que la ligne donnant les valeurs de α_{L} s’obtient en intercalant les nombres L, 3L, 9L, … entre les valeurs de 2α_{1}; je donnerai plus bas, en (3.4), un énoncé précis (et une preuve) de cette propriété.

Comme dans [Bou], la stratégie consiste à démontrer, par récurrence sur le nombre de disques N, des minorations sur la fonction distance dans le graphe 𝒞^{[N]}. On montrera notamment que

d(u, v) ⩾ 2S_{1}(N) − ∑_{\begin{matrix}k∈[N] \\ u(k)≠1 \end{matrix}}2α_{1}(k) − ∑_{\begin{matrix}k∈[N] \\ v(k)≠3 \end{matrix}}2α_{1}(k)  (2.8)

pour u, v : [N] → 𝒞 deux empilements quelconques.

En particulier, en prenant pour u, v les empilements parfaits sur les tiges 1 et 3, il vient d(u, v) ⩾ 2S_{1}(N), et, comme on sait, d’après Stockmeyer, construire un chemin de cette longueur, on en déduit le résultat annoncé dans le Résumé.

Le chemin construit par Stockmeyer est donc bien un chemin géodésique entre u et v, quel que soit N, comme cela était conjecturé. Mais il ne faudrait pas être tenté de croire que c’est le seul : en général, ce ne sera pas le cas. Par exemple, avec trois disques, il existe deux chemins géodésiques, c’est-à-dire deux manières optimales de transporter une tour de trois disques d’une tige extérieure vers une autre.

Pour établir l’inégalité (2.8), nous devrons faire un détour et prouver des inégalités plus générales, sur les multi-distances “alternantes”. Elles apparaissent dans la décomposition d’une distance ordinaire d(u, v), ou d’une autre multi-distance alternante, en fonction des mouvements du plus grand disque.

Voici comment : soient u, v les configurations parfaites de N disques sur les tiges 1, 3 (où N ⩾ 1), ou plus généralement, n’importe quel couple d’empilements [N] → 𝒞 tel que u(N − 1) = 1 et v(N − 1) = 3. Dans un chemin géodésique γ allant de u vers v, le plus grand disque doit aller de la tige 1 à 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 été préalablement déplacés vers les colonnes 2 et 3. De même, le dernier mouvement du plus grand disque sera de la tige 0 vers la tige 3, ce qui nécessite qu’à cet instant, tous les autres disques soient dans les colonnes 1 et 2. La longueur de γ est alors

d(u, v) = d(u_{0}, u_{1}) + d(u_{1}, u_{2}) + d(u_{2}, u_{3}) + d(u_{3}, u_{4}) + d(u_{4}, u_{5})
= 2 + d(u′, u′_{1}) + d(u′_{1}, u′_{4}) + d(u′_{4}, v′)

(voir Figure 2) où les u′_{i} sont les empilements de N − 1 disques obtenus en “oubliant” la position du plus grand disque. Dans ce calcul, j’ai utilisé le fait que d(x, y) = d(x′, y′) si, dans les configurations x, y, le plus grand disque est sur la même tige.

Figure 2. Décomposition d’une distance

Le problème du calcul d’une distance d(u, v) sur N disques se ramène ainsi au problème de minimiser la multi-distance

d(u′, s, t, v′) = d(u′, s) + d(s, t) + d(t, v′)

sur tous les couples (s, t) d’éléments de 𝒞^{[N−1]} pour lesquels supp(s) ⊆ {2, 3} et supp(t) ⊆ {1, 2}. Nous avons ainsi établi le lemme suivant.

Lemme 2.1. Soient u, v : [N] → 𝒞 des empilements de N disques (où N ⩾ 1) pour lesquels u(N − 1) = 1 et v(N − 1) = 3. Il existe alors s, t : [N − 1] → 𝒞, empilements de N − 1 disques vérifiant supp(s) ⊆ {2, 3} et supp(t) ⊆ {1, 2}, et tels que

d(u, v) = 2 + d(u′, s, t, v′).

J’utiliserai par la suite une notation diagrammatique plus compacte que celle de la Figure 2 : chaque configuration de N − 1 disques (et non plus N) est représentée verticalement, par un empilement de quatre cases représentant les quatre tiges, de 0 (en haut) jusqu’à 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 u′ et v′) seront dessinées 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écomposition donnée par le lemme ci-dessus (ici s et t) seront dessinées en gris. Comme précédemment, on écrit de gauche à droite les configurations qui se succèdent au cours du temps.

Plus généralement, une multi-distance d(u_{0}, u_{1}, …, u_{L}) entre deux empilements u_{0}, u_{L} sera appelée alternante si les empilements intermédiaires u_{k}, avec 0 < k < L, satisfont supp(u_{k}) ⊆ {2, 3} pour k impair et ⊆ {1, 2} pour k pair. Au besoin, on s’autorisera à renuméroter les tiges extérieures. Il n’y a aucune contrainte sur les empilements extrêmes u_{0}, u_{L}. L’alternance sera représentée, comme ci-dessus, par un “serpent” gris qui alterne entre les tiges 1 et 3.

On cherche à minorer une telle multi-distance alternante par une expression qui ne dépende que de u_{0} et u_{L}, ce qui revient implicitement à minimiser sur tous les empilements intermédiaires possibles, avec les contraintes de support ci-dessus.

Il sera commode pour la suite de définir la colonne

p_{k} = 2 − (−1)^{k} = \begin{cases}1, & si k est pair, \\ 3, & si k est impair, \end{cases}  (2.9)

élément de 𝒞 qui donne les positions successives du “serpent”, et de noter p_{k}^{N} la configuration parfaite correspondante.

Considérons d’abord le cas où les configurations extrêmes sont les empilements parfaits u_{0} = p_{0}^{N} et u_{L} = p_{L}^{N}. On veut construire un chemin “alternant” de u_{0} vers u_{L}, c’est-à-dire passant par des configurations intermédiaires u_{k} de support ⊆ {2, p_{k}}, et aussi court que possible. Pour N ⩾ 1, on peut construire un tel chemin en s’inspirant de la procédure de Frame–Stewart : on choisit d’abord un entier M < N. Puis, on déplace les M plus petits disques de la colonne p_{0} = 1 vers la colonne 2. Ensuite, on déplace L fois les N − M plus grands disques alternativement entre les colonnes 1 et 3, ce qui produit les configurations intermédiaires u_{1}, …, u_{L−1}, et enfin, on déplace les M plus petits disques de la colonne 2 vers la colonne p_{L}. On obtient ainsi un chemin de longueur

4S_{1}(M) + L (3^{N−M} − 1),

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ît naturel de penser que non. On aurait alors la minoration suivante, pour les multi-distances alternantes entre configurations parfaites :

d(u_{0}, u_{1}, …, u_{L}) ⩾ 2S_{L}(N)  (2.10)

si u_{0} = p_{0}^{N}, u_{L} = p_{L}^{N}, et supp(u_{k}) ⊆ {2, p_{k}} pour 0 < k < L. Voilà qui explique l’apparition des fonctions S_{L}, et non pas seulement S_{1}, dans l’étude de la tour de Stockmeyer.

Il reste à étendre cette inégalité conjecturale à des configurations u_{0}, u_{L} quelconques. Pour cela, comme dans [Bou], on retranche au second membre une “pénalité” β(k) pour chaque disque k situé “imparfaitement” au départ ou à l’arrivée :

d(u_{0}, u_{1}, …, u_{L}) ⩾ 2S_{L}(N) − ∑_{\begin{matrix}k∈[N] \\ u_{0}(k)≠p_{0} \end{matrix}} β(k) − ∑_{\begin{matrix}k∈[N] \\ u_{L}(k)≠p_{L} \end{matrix}} β(k).  (2.11)

J’expliquerai en § 5 comment choisir les β(k), mais pour le moment, je donne simplement le théorème principal, sans autre commentaire.

Théorème 2.2. Soient N, L deux entiers naturels, et u_{0}, u_{1}, …, u_{L} : [N] → 𝒞 des empilements de N disques vérifiant supp(u_{k}) ⊆ {2, p_{k}} pour 0 < k < L. Alors

d(u_{0}, u_{1}, …, u_{L}) ⩾ 2S_{L}(N) − ∑_{\begin{matrix}k∈[N] \\ u_{0}(k)≠p_{0} \end{matrix}} β(k) − ∑_{\begin{matrix}k∈[N] \\ u_{L}(k)≠p_{L} \end{matrix}} β(k),

où on a posé

β(k) = \begin{cases}α_{L}(k), & si k = N − 1 et L ⩾ 2, \\ 2α_{1}(k), & sinon. \end{cases}

On verra un peu plus bas que α_{L} ⩽ 2α_{1}, et donc les pénalités β(k) vérifient toujours α_{L}(k) ⩽ β(k) ⩽ 2α_{1}(k). Notons également que pour L = 1, le théorème se réduit à l’inégalité (2.8). On démontrera le théorème en § 4, mais d’abord, établissons quelques résultats préliminaires sur les S_{L} et α_{L}.

3. Quelques propriétés des fonctions S_{L}

Les nombres S_{L}(N) satisfont cinq propriétés essentielles :

(i) S_{L}(N) est croissant en L et N ; (ii) S_{L}(N) est convexe^{1} en N (pour L fixé); (iii) S_{L}(N) est concave en L (pour N fixé); (iv) S_{L}(N) est sur-modulaire en le couple (L, N), i.e.

S_{L}(N) + S_{L+1}(N + 1) ⩾ S_{L}(N + 1) + S_{L+1}(N)

pour tous L, N.

(v) Pour tout N fixé, S_{L}(N) → 2S_{1}(N) quand L → ∞.

La propriété (ii) revient à dire que α_{L}(N) est croissant en N (pour L fixé), et la propriété (iv) revient à dire que α_{L}(N) est croissant en L (pour N fixé).

La définition (2.5) entraîne immédiatement que pour tout N fixé, S_{L}(N) est croissant et concave en L, et tend vers 2S_{1}(N) quand L → ∞, ce qui démontre (iii), (v), et la première partie de (i). Il reste à établir (ii) et (iv), ainsi que la deuxième partie de (i), c’est-à-dire montrer que les α_{L}(N) sont croissants en L et N, et positifs.

Inf-convolution. Étant donné deux fonctions f, g : ℕ → ℝ, leur inf-convolution f □ g est définie comme la plus grande fonction h : ℕ → ℝ telle que h(m + n) ⩽ f(m) + g(n) pour tous m, n. Concrètement, elle est donnée par la formule

(f □ g) (n) = Min_{0⩽m⩽n} f(m) + g(n − m)  (3.1)

pour tout n entier naturel. Comme l’inf-convolution classique (c’est-à-dire sur ℝ ou ℝ^{N}, voir par exemple [Roc]), cette opération est particulièrement intéressante en restriction aux fonctions convexes (au sens discret, ici).

1Une fonction f : ℕ → ℝ est dite convexe (respectivement concave), au sens discret, si ses différences finies Δf(x) = f(x + 1) − f(x) forment une fonction croissante (respectivement décroissante); ou, ce qui est équivalent, si f est la restriction d’une fonction ℝ → ℝ convexe (respectivement concave), au sens usuel.

Fusion. Étant donné deux suites finies triées, c’est-à-dire deux entiers naturels m, n et deux fonctions croissantes f : [m] → ℝ et g : [n] → ℝ, on peut définir leur “fusion” f ∧∧ g comme la fonction [m + n] → ℝ qui est le réarrangement croissant de la suite f(0), f(1), …, f(m − 1), g(0), g(1), …, g(n − 1). Cette opération intervient dans l’algorithme “merge sort” (tri par fusion), voir [Knu, § 5.2.4]. Avec quelques précautions, on peut étendre cette opération à des suites triées infinies, c’est-à-dire des fonctions croissantes ℕ → ℝ. Je laisse au lecteur le soin de démontrer le résultat suivant.

Lemme 3.1. Soient f, g : ℕ → ℝ deux fonctions croissantes quelconques. Il existe exactement une fonction h : ℕ → ℝ ayant la propriété suivante : pour tout n ⩾ 1, les n premiers termes du réarrangement croissant de la suite

f(0), f(1), …, f(n − 1), g(0), g(1), …, g(n − 1)

sont égaux à h(0), h(1), …, h(n − 1) respectivement.

En outre, cette fonction est croissante.

Cette fonction sera appelée fusion de f et g, et notée f ∧∧ g. Par exemple,

(0, 1, 2, 3, 4, …) ∧∧ (0, 2, 4, 6, 8, …) = (0, 0, 1, 2, 2, 3, 4, 4, 5, …)

Une autre caractérisation de la fusion utilise les fonctions de répartition : si f : ℕ → ℝ est une fonction croissante, définissons sa fonction de répartition Rf : ℝ → ℕ ∪ {+∞} par

(Rf)(x) = Card{n ∈ ℕ : f(n) < x} = Inf{n ∈ ℕ : f(n) ⩾ x};

alors h = f ∧∧ g est l’unique fonction croissante pour laquelle Rh = Rf + Rg.

De la caractérisation de f ∧∧ g donnée par le lemme, on déduit facilement des formules explicites, comme celle-ci :

(f ∧∧ g)(n) = Max_{0⩽m⩽n} min{f(m), g(n − m)}  (3.2)

pour tout n entier naturel.

Le lemme précédent implique aussi que, pour tout entier naturel n, la somme des n premières valeurs de h = f ∧∧ g est majorée par

f(0) + f(1) + ⋯ + f(m − 1) + g(0) + g(1) + ⋯ + g(n − m − 1)

pour tout entier m entre 0 et n, avec égalité pour au moins un m. Autrement dit, la fonction n ↦ ∑_{k<n} h(k) est l’inf-convolution des fonctions n ↦ ∑_{k<n} f(k) et n ↦ ∑_{k<n} g(k). Un

énoncé équivalent est le suivant (en notant, comme plus haut, Δ l’opérateur de différence finie sur les fonctions).

Lemme 3.2. Pour f, g : ℕ → ℝ des fonctions convexes quelconques, on a

Δ (f □ g) = (Δf) ∧∧ (Δg).

En particulier, f □ g est convexe.

Revenons aux fonctions S_{L}. La formule (2.5) les définit par

S_{L} = (2S_{1}) □ (LΓ),  (3.3)

où Γ est la fonction (convexe) définie par Γ(n) = (3^{n} − 1)/2, et on sait d’autre part que S_{1} est convexe (c’est-à-dire que α_{1} est croissante). Il en résulte, par le lemme ci-dessus, que toutes les fonctions S_{L} sont convexes, et la propriété (ii) est établie. Leurs différences finies sont données par

α_{L} = (2α_{1}) ∧∧ (Lγ),  (3.4)

où γ est la fonction (croissante) donnée par γ(n) = Γ(n + 1) − Γ(n) = 3^{n}. Mais il est clair par ailleurs que l’opération ∧∧ est croissante en ses deux arguments (pour l’ordre usuel sur les fonctions), et donc, que la fonction α_{L} dépend de façon croissante de L. Cela établit la propriété (iv). Enfin, les fonctions α_{L} sont visiblement positives, ce qui prouve la deuxième partie de (i).

Ceci termine la démonstration des propriétés de base des S_{L}(N) et α_{L}(N).

On peut les combiner : par exemple, les fonctions α_{L} : ℕ → ℕ forment une suite croissante qui converge simplement vers 2α_{1}, ce qui montre que α_{L} ⩽ 2α_{1} pour tout L. On a aussi S_{L} ⩽ 2S_{1}, par le même argument. Voici maintenant quelques autres propriétés des S_{L} et α_{L}, de moindre importance.

Lemme 3.3. Pour tous m, k entiers naturels, on a l’inégalité

α_{1}(m + k + 1) − α_{1}(m) ⩾ Min{3^{k}, α_{1}(m)} .

En particulier, α_{1}(m) ⩾ 3^{k} implique α_{1}(m + k + 1) − α_{1}(m) ⩾ 3^{k}.

Démonstration. Un énoncé évidemment équivalent est le suivant : pour tous m, n, k entiers naturels tels que n − m > k, on a α_{1}(n) − α_{1}(m) ⩾ Min{3^{k}, α_{1}(m)}. Supposons que cet énoncé soit faux, et considérons un contre-exemple, c’est-à-dire un triplet (m, n, k) d’entiers naturels vérifiant

n − m > k, α_{1}(n) − α_{1}(m) < 3^{k}, α_{1}(n) < 2α_{1}(m),

avec k minimal.

Remarquons que k ne peut pas être nul, car α_{1} est strictement croissante, et donc k ⩾ 1. L’ensemble

B = {α_{1}(m), α_{1}(m + 1), …, α_{1}(n)}

est un sous-ensemble de ℛ de cardinal au moins k +2, et il contient au plus une puissance de 2 car α_{1}(n) < 2α_{1}(m). Or, tout élément de ℛ qui n’est pas une puissance de 2 est le triple d’un autre élément de ℛ : on peut donc écrire B ⊇ 3A pour un certain sous-ensemble A de ℛ de cardinal k + 1.

Notons α_{1}(m′) et α_{1}(n′) le plus petit et le plus grand élément de A. On a α_{1}(m) ⩽ 3α_{1}(m′) ⩽ 3α_{1}(n′) ⩽ α_{1}(n) et d’autre part n′ − m′ ⩾ k puisque A est de cardinal k + 1, donc

n′ − m′ > k − 1, α_{1}(n′) − α_{1}(m′) < 3^{k−1}, α_{1}(n′) < 2α_{1}(m′),

c’est-à-dire que le triplet (m′, n′, k − 1) serait un autre contre-exemple, contredisant l’hypothèse de minimalité de k. □

La conclusion du Lemme 3.3 est à rapprocher d’un résultat de Mintz [Min], qui affirme que α_{1}(m) = 3^{k} implique α_{1}(m + k + 1) = 2 · 3^{k}.

Lemme 3.4. On a l’inégalité

S_{L+1}(N + 1) − S_{L}(N) ⩽ 2α_{1}(N)

pour tout N entier naturel et L ⩾ 2.

Pour L = 1, cette inégalité est probablement encore vraie, mais ne peut pas se démontrer par les mêmes méthodes, et de toute façon, je n’en aurai pas besoin.

Démonstration. Donnons-nous N ⩾ 0 et L ⩾ 2, et soit M un entier entre 0 et N réalisant le minimum dans la formule (2.5). On a donc

S_{L}(N) = 2S_{1}(M) + \frac{1}{2}L (3^{N−M} − 1),
S_{L+1}(N + 1) ⩽ 2S_{1}(M + 1) + \frac{1}{2}(L + 1)(3^{N−M} − 1),

et par conséquent

S_{L+1}(N + 1) − S_{L}(N) ⩽ 2α_{1}(M) + \frac{1}{2}(3^{N−M} − 1).

Il suffit donc, pour prouver le lemme, de démontrer que

α_{1}(N) − α_{1}(M) ⩾ \frac{1}{4}(3^{N−M} − 1).  (3.5)

Pour M = N, cette condition est trivialement satisfaite. Supposons donc M < N. L’expression sous le minimum dans (2.5) est, par hypothèse, plus petite pour M que pour M + 1 :

2S_{1}(M) + \frac{1}{2}L (3^{N−M} − 1) ⩽ 2S_{1}(M + 1) + \frac{1}{2}L (3^{N−M−1}− 1),

ce qui revient à dire que

α_{1}(M) ⩾ \frac{1}{2}L · 3^{N−M−1}.

On a donc α_{1}(M) ⩾ 3^{N−M−1}, puisque L ⩾ 2. Par le Lemme 3.3, cela entraîne

α_{1}(N) − α_{1}(M) ⩾ 3^{N−M−1},

ce qui implique évidemment (3.5). □

Lemme 3.5. Pour tous L, N entiers naturels,

S_{3}(N) = S_{1}(N + 1) − 1,  (3.6)
S_{3L}(N) ⩾ S_{L}(N + 1) − L.  (3.7)

Démonstration. Quels que soient L, N entiers naturels,

S_{L}(N + 1) = Min_{M⩽N+1} 2S_{1}(M) + \frac{1}{2}L (3^{N+1−M} − 1)

= Min\{2S_{1}(N + 1), Min_{M⩽N} 2S_{1}(M) + \frac{3}{2}L (3^{N−M} − 1) + L\}

= Min{2S_{1}(N + 1), S_{3L}(N) + L},

d’où on déduit les deux formules du lemme. □

Lemme 3.6. Pour tous L, N entiers naturels,

L + 2S_{2L}(N) ⩾ S_{L}(N) + S_{L}(N + 1).

Démonstration. La concavité de la suite de fonctions S_{L} permet d’écrire 2S_{2L} ⩾ S_{L}+S_{3L}, ce qui, combiné avec (3.7), donne le résultat cherché. □

On a en particulier la minoration

S_{2}(n) ⩾ \frac{S_{1}(n) + S_{1}(n + 1) − 1}{2}  (3.8)

pour tout n entier naturel.

Lemme 3.7. Pour tout n ⩾ 4, on a α_{1}(n + 1) ⩽ \frac{4}{3}α_{1}(n).

Démonstration. Tous les éléments de ℛ autres que 1, 2, 4 sont divisibles par 3 ou par 8. Puisque n ⩾ 4, le nombre R = α_{1}(n), élément de ℛ, est ⩾ α_{1}(4) = 6, et donc divisible par 3 ou 8. Dans le premier cas, R′ = \frac{4}{3}R est encore dans ℛ, et strictement plus grand que α_{1}(n), donc R′ ⩾ α_{1}(n + 1), ce qui est l’inégalité cherchée. Dans le second cas, on prend R′ = \frac{9}{8}R et on applique le même argument. □

4. Démonstration de l’inégalité principale

Écrivons 𝒟 ⩾ ℰ l’inégalité du Théorème 2.2. Cette inégalité est trivialement satisfaite pour L = 0, et je supposerai donc L ⩾ 1 dans tout ce qui suit.

On démontrera l’inégalité par récurrence sur le nombre de disques N. Pour zéro disque, l’inégalité est trivialement satisfaite. Considérons maintenant le cas d’un unique disque. Pour L = 1, on doit montrer que

d(u_{0}, u_{1}) ⩾ 2 − 2δ̄(u_{0}(0), p_{0}) − 2δ̄(u_{1}(0), p_{1}).

Cette inégalité est bien satisfaite (avec égalité) si u_{0}(0) = p_{0} et u_{1}(0) = p_{1}, et dans les autres cas, le membre de droite est négatif donc ça marche aussi. Pour L ⩾ 2, on doit montrer que

d(u_{0}, u_{1}) + ⋯ + d(u_{L−1}, u_{L}) ⩾ 4 − 2δ̄(u_{0}(0), p_{0}) − 2δ̄(u_{L}(0), p_{L}),

mais ceci résulte immédiatement des inégalités

d(u_{0}, u_{1}) ⩾ 2δ(u_{0}(0), p_{0}),
d(u_{L−1}, u_{L}) ⩾ 2δ(u_{L}(0), p_{L}),

qu’on vérifie sans peine. L’inégalité 𝒟 ⩾ ℰ est donc valable pour N = 0, 1.

Désormais, on supposera N ⩾ 2, et on démontrera cette inégalité en supposant qu’elle est vraie pour tout nombre de disques plus petit.

Soient u′_{k} : [N − 1] → 𝒞 les restrictions des fonctions u_{k}, c’est-à-dire les empilements obtenus en “oubliant” la position du plus grand disque. Bien sûr, l’opération de restriction diminue les distances (au sens large), donc d(u_{0}, …, u_{L}) ⩾ d(u′_{0}, …, u′_{L}). D’autre part, on peut appliquer aux u′_{k} l’hypothèse de récurrence :

d(u′_{0}, …, u′_{L}) ⩾ 2S_{L}(N − 1) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠p_{0} \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−1] \\ u_{L}(k)≠p_{L} \end{matrix}} 2α_{1}(k).

En combinant cette inégalité avec

𝒟 − ℰ = d(u_{0}, …, u_{L}) − 2S_{L}(N) + ∑_{\begin{matrix}k∈[N] \\ u_{0}(k)≠p_{0} \end{matrix}} β(k) + ∑_{\begin{matrix}k∈[N] \\ u_{L}(k)≠p_{L} \end{matrix}} β(k)

⩾ d(u′_{0}, …, u′_{L}) − 2S_{L}(N − 1) + ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠p_{0} \end{matrix}} 2α_{1}(k) + ∑_{\begin{matrix}k∈[N−1] \\ u_{L}(k)≠p_{L} \end{matrix}} 2α_{1}(k)

− 2α_{L}(N − 1) + (δ̄(u_{0}(N − 1), p_{0}) + δ̄(u_{L}(N − 1), p_{L})) β(N − 1),

on obtient

𝒟 − ℰ ⩾ −2α_{L}(N − 1) + K β(N − 1),  (4.1)

où on a posé

K = δ̄(u_{0}(N − 1), p_{0}) + δ̄(u_{L}(N − 1), p_{L}).  (4.2)

Cet entier K est le nombre d’indices i dans {0, L} pour lesquels u_{i}(N − 1) ≠ p_{i}; il peut donc valoir 0, 1, 2. Il y a deux cas où on peut conclure immédiatement :

(i) Pour K = 2, le membre de droite de (4.1) est positif puisque β ⩾ α_{L}, donc l’inégalité 𝒟 ⩾ ℰ est toujours satisfaite dans ce cas. (ii) Pour K = L = 1, le membre de droite de (4.1) est nul car β = 2α_{1}, donc là encore 𝒟 ⩾ ℰ.

Nous aurons donc uniquement à considérer le cas K = 1, L ⩾ 2, ainsi que le cas K = 0, qui feront l’objet des deux sections suivantes.

4.1. Le cas K = 1, avec L ⩾ 2. L’hypothèse K = 1 signifie que u_{0}(N − 1) = p_{0} ou bien u_{L}(N − 1) = p_{L}. Les deux possibilités sont évidemment parfaitement symétriques; dans ce qui suit, je supposerai u_{0}(N − 1) = p_{0} et u_{L}(N − 1) ≠ p_{L}.

Soit a le plus petit indice pour lequel u_{a}(N − 1) ≠ p_{a}, donc 0 < a ⩽ L, et posons b = L − a.

Examinons d’abord le cas a, b ⩾ 2, c’est-à-dire 2 ⩽ a ⩽ L − 2.

On a alors u_{k}(N − 1) = p_{k} pour 0 ⩽ k < a et u_{a}(N − 1) = 2. Par le Lemme 2.1, on peut écrire

d(u_{k}, u_{k+1}) = 2 + d(u′_{k}, s_{k}, t_{k}, u′_{k+1})  (4.3)

pour 0 ⩽ k < a, où les s_{k}, t_{k} sont des empilements de N − 1 disques tels que supp(s_{k}) ⊆ {2, p_{k+1}} et supp(t_{k}) ⊆ {2, p_{k}}, à l’exception de t_{a−1} dont le support est ⊆ {1, 3}. Pour k ⩾ a, on se contentera de la minoration évidente d(u_{k}, u_{k+1}) ⩾ d(u′_{k}, u′_{k+1}). Donc,

d(u_{0}, …, u_{L}) ⩾ 2a + d(u′_{0}, s_{0}, t_{0}, u′_{1}, …, u′_{a−1}, s_{a−1}, t_{a−1}, u′_{a}, u′_{a+1}, …, u′_{L}).

La multi-distance à droite n’est pas alternante, mais comme le montre le diagramme ci-dessous (dessiné dans le cas particulier a = b = 3)

on peut la décomposer en une somme de trois multi-distances alternantes

d(u′_{0}, s_{0}, t_{0}, u′_{1}, …, u′_{a−1}, s_{a−1}) + d(s_{a−1}, t_{a−1}, u′_{a}) + d(u′_{a}, u′_{a+1}, …, u′_{L}),

auxquelles on peut appliquer l’hypothèse de récurrence :

d(u′_{0}, s_{0}, t_{0}, u′_{1}, …, u′_{a−1}, s_{a−1}) ⩾ 2S_{3a−2}(N − 1) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠p_{0} \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−2] \\ s_{a−1}(k)≠p_{3a−2} \end{matrix}} 2α_{1}(k)

− δ̄(s_{a−1}(N − 2), p_{3a−2}) α_{3a−2}(N − 2),
d(s_{a−1}, t_{a−1}, u′_{a}) ⩾ 2S_{2}(N − 1) − ∑_{\begin{matrix}k∈[N−2] \\ s_{a−1}(k)≠2 \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−2] \\ u_{a}(k)≠2 \end{matrix}}2α_{1}(k)

− (δ̄(s_{a−1}(N − 2), 2) + δ̄(u_{a}(N − 2), 2)) α_{2}(N − 2),

d(u′_{a}, u′_{a+1}, …, u′_{L}) ⩾ 2S_{b}(N − 1) − ∑_{\begin{matrix}k∈[N−2] \\ u_{a}(k)≠p_{a} \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−1] \\ u_{L}(k)≠p_{L} \end{matrix}} 2α_{1}(k)

− δ̄(u_{a}(N − 2), p_{a}) α_{b}(N − 2).

14 THIERRY BOUSCH

On en déduit

𝒟 − ℰ = d(u_{0}, …, u_{L}) − 2S_{L}(N) + ∑_{\begin{matrix}k∈[N] \\ u_{0}(k)≠p_{0} \end{matrix}} β(k) + ∑_{\begin{matrix}k∈[N] \\ u_{L}(k)≠p_{L} \end{matrix}} β(k)
⩾ 2a + 2(S_{3a−2} + S_{2} + S_{b})(N − 1) − 2S_{L}(N) + α_{L}(N − 1)

− ∑_{k∈[N−2]} (δ̄(s_{a−1}(k), p_{3a−2}) + δ̄(s_{a−1}(k), 2)) 2α_{1}(k)

− ∑_{k∈[N−2]} (δ̄(u_{a}(k), 2) + δ̄(u_{a}(k), p_{a})) 2α_{1}(k)

− δ̄(s_{a−1}(N − 2), p_{3a−2}) α_{3a−2}(N − 2) − δ̄(s_{a−1}(N − 2), 2) α_{2}(N − 2) − δ̄(u_{a}(N − 2), 2) α_{2}(N − 2) − δ̄(u_{a}(N − 2), p_{a}) α_{b}(N − 2).

Puisque supp(s_{a−1}) ⊆ {2, p_{3a−2}} et supp(u_{a}) ⊆ {2, p_{a}}, on a, pour tout k < N − 1,

δ̄(s_{a−1}(k), p_{3a−2}) + δ̄(s_{a−1}(k), 2) = δ̄(u_{a}(k), 2) + δ̄(u_{a}(k), p_{a}) = 1,

et par suite

δ̄(s_{a−1}(k), p_{3a−2}) α_{3a−2}(k) + δ̄(s_{a−1}(k), 2) α_{2}(k) ⩽ max{α_{3a−2}(k), α_{2}(k)},
δ̄(u_{a}(k), 2) α_{2}(k) + δ̄(u_{a}(k), p_{a}) α_{b}(k) ⩽ max{α_{2}(k), α_{b}(k)}.

Par conséquent

𝒟 − ℰ ⩾ 2a + 2(S_{3a−2} + S_{2} + S_{b})(N − 1) − 2S_{L}(N) + α_{L}(N − 1)
− (2S_{1} + α_{max{3a−2,2}} + 2S_{1} + α_{max{2,b}})(N − 2)
= 2a + 2(S_{3a−2} + S_{2} + S_{b})(N − 1) − 2S_{L}(N) + α_{L}(N − 1)
− (4S_{1} + α_{3a−2} + α_{b})(N − 2)

= 2a + S_{3a−2}(N − 1) + S_{3a−2}(N − 2) + 2S_{2}(N − 1) − 4S_{1}(N − 2)

+ S_{b}(N − 1) + S_{b}(N − 2) − S_{L}(N) − S_{L}(N − 1).

Utilisons maintenant la minoration

S_{3a−2}(n) ⩾ S_{3a−3}(n) ⩾ S_{a−1}(n + 1) − a + 1,  (4.4)

conséquence du Lemme 3.5, et valable pour tous n ⩾ 0 et a ⩾ 1. Il vient

𝒟 − ℰ ⩾ 2 + (S_{a−1} − S_{L})(N) + (S_{a−1} − S_{L})(N − 1)
+ S_{b}(N − 1) + S_{b}(N − 2) + 2S_{2}(N − 1) − 4S_{1}(N − 2).

La concavité de la suite des S_{L} entraîne S_{a−1} − S_{a+b} ⩾ S_{1} − S_{b+2} . En outre, on a S_{b}(n) ⩾ S_{b+1}(n + 1) − 2α_{1}(n) par le Lemme 3.4, donc

𝒟 − ℰ ⩾ 2 + (S_{1} + S_{b+1} − S_{b+2})(N) + (S_{1} + S_{b+1} − S_{b+2})(N − 1)
− 2α_{1}(N − 1) − 2α_{1}(N − 2) + 2S_{2}(N − 1) − 4S_{1}(N − 2).

La concavité de la suite des S_{L} donne aussi S_{b+1} − S_{b+2} ⩾ S_{1} − S_{2} , d’où

𝒟 − ℰ ⩾ 2 + (2S_{1} − S_{2})(N) + (2S_{1} − S_{2})(N − 1)
− 2α_{1}(N − 1) − 2α_{1}(N − 2) + 2S_{2}(N − 1) − 4S_{1}(N − 2)
= 2 + 2α_{1}(N − 2) − α_{2}(N − 1),

et on a α_{2}(n) ⩽ α_{3}(n) = α_{1}(n + 1), par le Lemme 3.5, donc 𝒟 − ℰ ⩾ 2 + 2α_{1}(N − 2) − α_{1}(N).

LA TOUR DE STOCKMEYER 15

Mais on vérifie facilement, avec le Lemme 3.7, que

1 + 2α_{1}(N − 2) − α_{1}(N) ⩾ 0  (4.5)

pour tout N ⩾ 2. Ceci établit l’inégalité 𝒟 ⩾ ℰ dans le cas a, b ⩾ 2.

Examinons maintenant le cas a ⩾ 2, b = 1 (et donc L = a + 1).

Comme le montre le diagramme

on peut écrire la multi-distance d(u′_{0}, s_{0}, …, t_{a−1}, u′_{a}, u′_{a+1}) comme somme de deux multidistances alternantes

d(u′_{0}, s_{0}, t_{0}, u′_{1}, …, u′_{a−1}, s_{a−1}) + d(s_{a−1}, t_{a−1}, u′_{a}, u′_{a+1}),

auxquelles on applique l’hypothèse de récurrence. Par un calcul similaire au précédent, on obtient

𝒟 − ℰ ⩾ 2a + 2(S_{3a−2} + S_{3})(N − 1) − 2S_{L}(N) + α_{L}(N − 1)
− (2S_{1} + α_{max{3a−2,3}})(N − 2)
= 2a + 2(S_{3a−2} + S_{3})(N − 1) − 2S_{L}(N) + α_{L}(N − 1)
− (2S_{1} + α_{3a−2})(N − 2)
= 2a + S_{3a−2}(N − 1) + S_{3a−2}(N − 2) + 2S_{3}(N − 1) − 2S_{1}(N − 2)
− S_{L}(N) − S_{L}(N − 1),

et en minorant S_{3a−2} avec (4.4), il vient

𝒟 − ℰ ⩾ 2 + (S_{a−1} − S_{L})(N) + (S_{a−1} − S_{L})(N − 1) + 2S_{3}(N − 1) − 2S_{1}(N − 2). La concavité des S_{L} implique S_{a−1} − S_{a+1} ⩾ S_{1} − S_{3}, et donc

𝒟 − ℰ ⩾ 2 + (S_{1} − S_{3})(N) + (S_{1} − S_{3})(N − 1) + 2S_{3}(N − 1) − 2S_{1}(N − 2)
⩾ 2 − α_{3}(N − 1) + S_{1}(N) + S_{1}(N − 1) − 2S_{1}(N − 2)
⩾ 2 − α_{1}(N) + α_{1}(N − 1) + 2α_{1}(N − 2),

et d’après (4.5), cette expression est positive (on peut aussi utiliser (2.2)). On a donc encore 𝒟 ⩾ ℰ dans le cas a ⩾ 2, b = 1.

A présent, considérons le cas a = 1 (et donc L = b + 1, avec b ⩾ 1).

Pour b ⩾ 2, on écrit la multi-distance d(u′_{0}, s_{0}, t_{0}, u′_{1}, u′_{2}, …, u′_{L})

comme somme de deux multi-distances alternantes d(u′_{0}, s_{0}, t_{0}, u′_{1}) + d(u′_{1}, u′_{2}, …, u′_{L}),

16 THIERRY BOUSCH

auxquelles on applique l’hypothèse de récurrence, et on obtient, par des calculs similaires aux précédents,

𝒟 − ℰ ⩾ 2 + 2(S_{3} + S_{b})(N − 1) − 2S_{L}(N) + α_{L}(N − 1)
− (2S_{1} + α_{max{3,b}})(N − 2).

Pour b = 2, cela donne

𝒟 − ℰ ⩾ 2 + 2(S_{3} + S_{2})(N − 1) − S_{3}(N) − S_{3}(N − 1) − (2S_{1} + α_{3})(N − 2)
= 2 − α_{3}(N − 1) + 2S_{2}(N − 1) − 2S_{1}(N − 2) − α_{3}(N − 2)
= 2 − α_{1}(N) + 2S_{2}(N − 1) − 2S_{1}(N − 2) − α_{1}(N − 1),

et on sait que 2S_{2}(N − 1) ⩾ S_{1}(N − 1) + S_{1}(N) − 1, d’après (3.8), donc

𝒟 − ℰ ⩾ 2 − α_{1}(N) + S_{1}(N − 1) + S_{1}(N) − 1 − 2S_{1}(N − 2) − α_{1}(N − 1)
= 1 − α_{1}(N) + 2α_{1}(N − 2),

et cette expression, comme on l’a vu en (4.5), est positive.

Pour b ⩾ 3, on a

𝒟 − ℰ ⩾ 2 + 2(S_{3} + S_{b})(N − 1) − S_{L}(N) − S_{L}(N − 1) − (2S_{1} + α_{b})(N − 2)
= S_{b}(N − 1) + S_{b}(N − 2) − S_{L}(N) − S_{L}(N − 1) + 2S_{1}(N) − 2S_{1}(N − 2)
= [(S_{b} + 2α_{1})(N − 1) − S_{b+1}(N)] + [(S_{b} + 2α_{1})(N − 2) − S_{b+1}(N − 1)],

et les deux expressions entre crochets sont positives, par le Lemme 3.4, donc 𝒟 ⩾ ℰ. Pour b = 1 (et donc L = 2), la multi-distance d(u′_{0}, s_{0}, t_{0}, u′_{1}, u′_{2}) est alternante

et on peut lui appliquer directement l’hypothèse de récurrence,

d(u′_{0}, s_{0}, t_{0}, u′_{1}, u′_{2}) ⩾ 2S_{4}(N − 1) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠1 \end{matrix}}2α_{1}(k) − ∑_{\begin{matrix}k∈[N−1] \\ u_{2}(k)≠1 \end{matrix}}2α_{1}(k),

ce qui entraîne

𝒟 − ℰ ⩾ 2 + 2S_{4}(N − 1) − S_{2}(N) − S_{2}(N − 1),

et le membre de droite est positif, par le Lemme 3.6.

On a donc bien 𝒟 ⩾ ℰ chaque fois que a = 1.

Finalement, examinons le cas b = 0 (et donc L = a ⩾ 2).

Comme il n’y a aucune condition de support sur u_{L}, il n’est plus possible d’affirmer comme précédemment que u_{a}(N −1) = 2. La position du plus grand disque dans u_{a} étant inconnue, il n’est plus possible de décomposer la distance d(u_{a−1}, u_{a}) selon la formule (4.3), et on devra se contenter de la minorer par d(u′_{a−1}, u′_{a}). Il vient alors

d(u_{0}, …, u_{L}) ⩾ 2(a − 1) + d(u′_{0}, s_{0}, t_{0}, u′_{1}, …, u′_{a−2}, s_{a−2}, t_{a−2}, u′_{a−1}, u′_{a}), et la multi-distance à droite est alternante

donc on peut lui appliquer l’hypothèse de récurrence,

d(u′_{0}, s_{0}, …, t_{a−2}, u′_{a−1}, u′_{a}) ⩾ 2S_{3a−2}(N − 1) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠p_{0} \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−1] \\ u_{a}(k)≠p_{3a−2} \end{matrix}} 2α_{1}(k),

et par conséquent

𝒟 − ℰ ⩾ 2(a − 1) + 2S_{3a−2}(N − 1) − S_{a}(N) − S_{a}(N − 1).

Or on sait que S_{a}(N) + S_{a}(N − 1) ⩽ a + 2S_{2a}(N − 1), par le Lemme 3.6, donc

𝒟 − ℰ ⩾ a − 2 + 2(S_{3a−2} − S_{2a})(N − 1),

et cette expression est visiblement positive, puisque a ⩾ 2.

Nous avons ainsi établi l’inégalité 𝒟 ⩾ ℰ dans tous les cas où K = 1, L ⩾ 2.

4.2. Le cas K = 0. Supposons maintenant K = 0, et soit E l’ensemble des indices i dans {0, …, L} pour lesquels u_{i}(N − 1) ≠ p_{i}. Par hypothèse, cet ensemble ne contient pas 0 et L.

Supposons d’abord que E est vide, c’est-à-dire que u_{i}(N − 1) = p_{i} pour tout i. (Remarquons que si L = 1, c’est la seule possibilité.) On peut alors écrire la formule (4.3) pour tout k dans {0, …, L − 1}, ce qui donne

d(u_{0}, …, u_{L}) = 2L + d(u′_{0}, s_{0}, …, t_{L−1}, u′_{L}),

et la multi-distance à droite est alternante

donc

d(u′_{0}, s_{0}, …, t_{L−1}, u′_{L}) ⩾ 2S_{3L}(N − 1) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠p_{0} \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−1] \\ u_{L}(k)≠p_{3L} \end{matrix}} 2α_{1}(k),

ce qui donne

𝒟 − ℰ = d(u_{0}, …, u_{L}) − 2S_{L}(N) + ∑_{\begin{matrix}k∈[N] \\ u_{0}(k)≠p_{0} \end{matrix}} β(k) + ∑_{\begin{matrix}k∈[N] \\ u_{L}(k)≠p_{L} \end{matrix}} β(k)

⩾ 2L + 2S_{3L}(N − 1) − 2S_{L}(N),

et cette quantité est positive par le Lemme 3.5.

Dans ce qui suit, on supposera E non vide, et on notera a et a^{∗} son plus petit et son plus grand élément, si bien que 0 < a ⩽ a^{∗} < L. Définissons également b = a^{∗} − a et c = L − a^{∗}, ce qui permet d’écrire L = a + b + c avec a, c > 0 et b ⩾ 0.

Le nombre u_{k}(N −1), c’est-à-dire la position du plus grand disque dans la configuration u_{k}, est connue pour tout k dans {0, …, a} ∪ {a^{∗}, …, L} : c’est la tige p_{k} si k < a ou k > a^{∗}, et la tige 2 si k vaut a ou a^{∗}. On peut donc utiliser la décomposition (4.3) pour tout k dans {0, …, a − 1} ∪ {a^{∗}, …, L − 1}, et pour les autres valeurs de k, c’est-à-dire entre a et a^{∗} − 1, on utilisera la minoration évidente d(u_{k}, u_{k+1}) ⩾ d(u′_{k}, u′_{k+1}). Cela donne

d(u_{0}, …, u_{L}) ⩾ 2a + 2c + d(u′_{0}, s_{0}, …, t_{a−1}, u′_{a}, u′_{a+1}, …, u′_{a^{∗}}, s_{a^{∗}}, …, t_{L−1}, u′_{L}). (4.6)

La multi-distance à droite ne sera pas alternante en général, et devra être décomposée en fragments alternants; cette décomposition sera différente selon que a, b, c sont “grands” (au moins deux) ou “petits” (zéro ou un).

Notons, pour la suite, que pour L ⩾ 3 on a l’inégalité S_{L}(N)−S_{L−1}(N−1) ⩽ 2α_{1}(N−1), qui peut se récrire

2S_{L}(N) ⩽ S_{L}(N) + S_{L−1}(N − 1) + 2α_{1}(N − 1).  (4.7)

4.2.1. Sous-cas a, c ⩾ 2. Supposons d’abord a, c ⩾ 2. Nous devrons distinguer trois cas, selon que b vaut zéro, un, ou au moins deux.

Pour b ⩾ 2, la multi-distance à droite de (4.6)

se décompose en

d(u′_{0}, …, s_{a−1}) + d(s_{a−1}, t_{a−1}, u′_{a}) + d(u′_{a}, …, u′_{a^{∗}}) + d(u′_{a^{∗}}, s_{a^{∗}}, t_{a^{∗}}) + d(t_{a^{∗}}, …, u′_{L}),

ce qui donne

𝒟 − ℰ ⩾ 2a + 2c + 2(S_{3a−2} + S_{2} + S_{b} + S_{2} + S_{3c−2})(N − 1) − 2S_{L}(N)
− (2S_{1} + α_{max{3a−2,2}} + 2S_{1} + α_{max{2,b}}
+ 2S_{1} + α_{max{b,2}} + 2S_{1} + α_{max{2,3c−2}})(N − 2)
= 2a + 2c + 2(S_{3a−2} + S_{2} + S_{b} + S_{2} + S_{3c−2})(N − 1) − 2S_{L}(N)
− (8S_{1} + α_{3a−2} + 2α_{b} + α_{3c−2})(N − 2)
= 2a + 2c + S_{3a−2}(N − 1) + S_{3a−2}(N − 2) + 2S_{b}(N − 2)
+ 4S_{2}(N − 1) + S_{3c−2}(N − 1) + S_{3c−2}(N − 2)
− 2S_{L}(N) − 8S_{1}(N − 2),

et nous devons montrer que cette expression est positive.

Minorons S_{3a−2} et S_{3c−2} avec (4.4), et majorons 2S_{L}(N) avec (4.7) : il vient

𝒟 − ℰ ⩾ 4 + S_{a−1}(N) + S_{a−1}(N − 1) + S_{c−1}(N) + S_{c−1}(N − 1)
− S_{L}(N) − S_{L−1}(N − 1) − 2α_{1}(N − 1)
+ 2S_{b}(N − 2) + 4S_{2}(N − 1) − 8S_{1}(N − 2)
= 4 + (S_{a−1} − S_{L})(N) + (S_{a−1} − S_{L−1})(N − 1)
+ S_{c−1}(N) + S_{c−1}(N − 1) − 2α_{1}(N − 1)
+ 2S_{b}(N − 2) + 4S_{2}(N − 1) − 8S_{1}(N − 2).

La concavité de la suite des S_{L} permet d’écrire S_{a−1} − S_{L} ⩾ S_{1} − S_{b+c+2} et S_{a−1} − S_{L−1} ⩾ S_{1} − S_{b+c+1}, puisque a ⩾ 2, donc

𝒟 − ℰ ⩾ 4 + (S_{1} − S_{b+c+2})(N) + (S_{1} − S_{b+c+1})(N − 1)
+ S_{c−1}(N) + S_{c−1}(N − 1) − 2α_{1}(N − 1)
+ 2S_{b}(N − 2) + 4S_{2}(N − 1) − 8S_{1}(N − 2)
= 4 + S_{1}(N) + S_{1}(N − 1) − 2α_{1}(N − 1)
+ (S_{c−1} − S_{b+c+2})(N) + (S_{c−1} − S_{b+c+1})(N − 1)
+ 2S_{b}(N − 2) + 4S_{2}(N − 1) − 8S_{1}(N − 2).

On invoque à nouveau la concavité des S_{L} pour dire que S_{c−1} − S_{b+c+2} ⩾ S_{1} − S_{b+4} et S_{c−1} − S_{b+c+1} ⩾ S_{1} − S_{b+3}, puisque c ⩾ 2, et donc

𝒟 − ℰ ⩾ 4 + S_{1}(N) + S_{1}(N − 1) − 2α_{1}(N − 1)
+ (S_{1} − S_{b+4})(N) + (S_{1} − S_{b+3})(N − 1)
+ 2S_{b}(N − 2) + 4S_{2}(N − 1) − 8S_{1}(N − 2),

et, comme S_{b+4}(N) ⩽ S_{b+3}(N − 1) + 2α_{1}(N − 1),

𝒟 − ℰ ⩾ 4 + 2S_{1}(N) + 2S_{1}(N − 1) − 2α_{1}(N − 1)
− 2S_{b+3}(N − 1) − 2α_{1}(N − 1)
+ 2S_{b}(N − 2) + 4S_{2}(N − 1) − 8S_{1}(N − 2).

Utilisant maintenant S_{b+3}(N − 1) ⩽ S_{b+2}(N − 2) + 2α_{1}(N − 2), on obtient

𝒟 − ℰ ⩾ 4 + 2S_{1}(N) + 2S_{1}(N − 1) − 4α_{1}(N − 1)
+ 2(S_{b} − S_{b+2})(N − 2) − 4α_{1}(N − 2)
+ 4S_{2}(N − 1) − 8S_{1}(N − 2).

Enfin, on utilise S_{b} − S_{b+2} ⩾ S_{1} − S_{3} et 2S_{2}(N − 1) ⩾ S_{1}(N) + S_{1}(N − 1) − 1, ce qui donne

𝒟 − ℰ ⩾ 4 + 2S_{1}(N) + 2S_{1}(N − 1) − 4α_{1}(N − 1)
+ 2S_{1}(N − 2) − 2S_{1}(N − 1) + 2 − 4α_{1}(N − 2)
+ 2S_{1}(N) + 2S_{1}(N − 1) − 2 − 8S_{1}(N − 2)
= 4 + 2α_{1}(N − 2) ⩾ 0,

ce qui prouve l’inégalité 𝒟 ⩾ ℰ dans le cas b ⩾ 2.

Pour b = 1 (et donc L = a + c + 1), la multi-distance à droite de (4.6)

se décompose en

d(u′_{0}, …, s_{a−1}) + d(s_{a−1}, t_{a−1}, u′_{a}, u′_{a^{∗}}) + d(u′_{a^{∗}}, s_{a^{∗}}, t_{a^{∗}}) + d(t_{a^{∗}}, …, u′_{L}), ce qui donne

𝒟 − ℰ ⩾ 2a + 2c + 2(S_{3a−2} + S_{3} + S_{2} + S_{3c−2})(N − 1) − 2S_{L}(N)
− (6S_{1} + α_{3a−2} + α_{3} + α_{3c−2})(N − 2)
= 2a + 2c + S_{3a−2}(N − 1) + S_{3a−2}(N − 2)
+ S_{3}(N − 1) + S_{3}(N − 2) + S_{3c−2}(N − 1) + S_{3c−2}(N − 2)
+ 2S_{2}(N − 1) − 6S_{1}(N − 2) − 2S_{L}(N).

Comme précédemment, minorons S_{3a−2} et S_{3c−2} avec (4.4), et majorons 2S_{L}(N) avec (4.7) : il vient

𝒟 − ℰ ⩾ 4 + S_{a−1}(N) + S_{a−1}(N − 1) + S_{c−1}(N) + S_{c−1}(N − 1)
+ S_{1}(N) + S_{1}(N − 1) − 2 + 2S_{2}(N − 1) − 6S_{1}(N − 2)
− S_{L}(N) − S_{L−1}(N − 1) − 2α_{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)
+ 2S_{2}(N − 1) − 6S_{1}(N − 2) − 2α_{1}(N − 1),

et les inégalités de concavité S_{a−1}−S_{a+c+1} ⩾ S_{1}−S_{c+3} et S_{a−1}−S_{a+c} ⩾ S_{1}−S_{c+2} donnent

𝒟 − ℰ ⩾ 2 + (2S_{1} + S_{c−1} − S_{c+3})(N) + (2S_{1} + S_{c−1} − S_{c+2})(N − 1)
+ 2S_{2}(N − 1) − 2α_{1}(N − 1) − 6S_{1}(N − 2),

puis, les inégalités S_{c−1} − S_{c+3} ⩾ S_{1} − S_{5} et S_{c−1} − S_{c+2} ⩾ S_{1} − S_{4} donnent

𝒟 − ℰ ⩾ 2 + 3S_{1}(N) + 3S_{1}(N − 1) − S_{5}(N) − S_{4}(N − 1)
+ 2S_{2}(N − 1) − 2α_{1}(N − 1) − 6S_{1}(N − 2).

Des majorations S_{5}(N) ⩽ (S_{4} + 2α_{1})(N − 1) et S_{4}(N − 1) ⩽ (S_{3} + 2α_{1})(N − 2), on déduit

𝒟 − ℰ ⩾ 4 + 3S_{1}(N) + S_{1}(N − 1) + 2S_{2}(N − 1)
− 4α_{1}(N − 1) − 4α_{1}(N − 2) − 6S_{1}(N − 2),

et, comme 2S_{2}(N − 1) ⩾ S_{1}(N) + S_{1}(N − 1) − 1, d’après (3.8),

𝒟 − ℰ ⩾ 3 + 4S_{1}(N) + 2S_{1}(N − 1) − 4α_{1}(N − 1) − 4α_{1}(N − 2) − 6S_{1}(N − 2)
= 3 + 2α_{1}(N − 2) ⩾ 0,

ce qui prouve l’inégalité 𝒟 ⩾ ℰ dans le cas b = 1.

Enfin, pour b = 0 (et donc L = a + c), la multi-distance à droite de (4.6)

se décompose en

d(u′_{0}, …, s_{a−1}) + d(s_{a−1}, t_{a−1}, u′_{a}, s_{a}, t_{a}) + d(t_{a}, …, u′_{L}),

ce qui donne

𝒟 − ℰ ⩾ 2a + 2c + 2(S_{3a−2} + S_{4} + S_{3c−2})(N − 1) − 2S_{L}(N)
− (4S_{1} + α_{3a−2} + α_{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)
+ 2S_{4}(N − 1) − 4S_{1}(N − 2) − 2S_{L}(N).

Utilisons à nouveau (4.4) et (4.7) : il vient

𝒟 − ℰ ⩾ 4 + (S_{a−1} + S_{c−1} − S_{L})(N) + (S_{a−1} + S_{c−1} − S_{L−1})(N − 1)
+ 2S_{4}(N − 1) − 4S_{1}(N − 2) − 2α_{1}(N − 1),

et les inégalités S_{a−1} − S_{a+c} ⩾ S_{1} − S_{c+2} et S_{a−1} − S_{a+c−1} ⩾ S_{1} − S_{c+1}, puis S_{c−1} − S_{c+2} ⩾ S_{1} − S_{4} et S_{c−1} − S_{c+1} ⩾ S_{1} − S_{3}, donnent successivement

𝒟 − ℰ ⩾ 4 + (S_{1} + S_{c−1} − S_{c+2})(N) + (S_{1} + S_{c−1} − S_{c+1})(N − 1)
+ 2S_{4}(N − 1) − 4S_{1}(N − 2) − 2α_{1}(N − 1)
⩾ 4 + (2S_{1} − S_{4})(N) + (2S_{1} − S_{3})(N − 1)
+ 2S_{4}(N − 1) − 4S_{1}(N − 2) − 2α_{1}(N − 1),

et, comme S_{4}(N) ⩽ (S_{3} + 2α_{1})(N − 1),

𝒟 − ℰ ⩾ 4 + 2S_{1}(N) + 2S_{1}(N − 1) − 2S_{3}(N − 1) − 2α_{1}(N − 1)
+ 2S_{4}(N − 1) − 4S_{1}(N − 2) − 2α_{1}(N − 1)
= 6 + 2S_{1}(N − 1) + 2S_{4}(N − 1) − 4S_{1}(N − 2) − 4α_{1}(N − 1),

et enfin, en minorant S_{4} par S_{3}, il vient

𝒟 − ℰ ⩾ 4 + 2S_{1}(N − 1) + 2S_{1}(N) − 4S_{1}(N − 2) − 4α_{1}(N − 1)
= 4 + 4α_{1}(N − 2) − 2α_{1}(N − 1) ⩾ 0,

puisque α_{1}(N − 1) ⩽ 2α_{1}(N − 2), d’après (2.2). On a donc également 𝒟 ⩾ ℰ si b = 0. En résumé, l’inégalité 𝒟 ⩾ ℰ est satisfaite dans tous les cas où a, c ⩾ 2.

4.2.2. Sous-cas a = c = 1. Supposons maintenant a = c = 1 (et donc L = b + 2). On distinguera ici encore le cas b ⩾ 2 et les cas b = 0, 1.

Pour b ⩾ 2, la multi-distance à droite de (4.6)

se décompose en

d(u′_{0}, s_{0}, t_{0}, u′_{1}) + d(u′_{1}, …, u′_{L−1}) + d(u′_{L−1}, s_{L−1}, t_{L−1}, u′_{L}),

ce qui donne

𝒟 − ℰ ⩾ 4 + 2(S_{3} + S_{b} + S_{3})(N − 1) − 2S_{L}(N)
− (4S_{1} + 2α_{max{b,3}})(N − 2).

Pour b ⩾ 3, on a

𝒟 − ℰ ⩾ 4 + (4S_{3} + 2S_{b})(N − 1) − 2S_{L}(N) − (4S_{1} + 2α_{b})(N − 2)
= 4 + 4S_{3}(N − 1) + 2S_{b}(N − 2) − 2S_{L}(N) − 4S_{1}(N − 2)
= 4α_{1}(N − 1) + 4α_{1}(N − 2) + 2S_{b}(N − 2) − 2S_{b+2}(N)

= 2[(S_{b} + 2α_{1})(N − 2) − S_{b+1}(N − 1)] + 2[(S_{b+1} + 2α_{1})(N − 1) − S_{b+2}(N)],

et les deux expressions entre crochets sont positives, par le Lemme 3.4, donc 𝒟 ⩾ ℰ si b ⩾ 3.

Pour b = 2 (et donc L = 4), on a

𝒟 − ℰ ⩾ 4 + (4S_{3} + 2S_{2})(N − 1) − 2S_{4}(N) − (4S_{1} + 2α_{3})(N − 2)
= 4 + 2S_{3}(N − 1) + 2S_{3}(N − 2) + 2S_{2}(N − 1) − 2S_{4}(N) − 4S_{1}(N − 2),

et, comme S_{4}(N) ⩽ S_{3}(N − 1) + 2α_{1}(N − 1), il vient

𝒟 − ℰ ⩾ 2 + 2S_{1}(N − 1) − 4S_{1}(N − 2) − 4α_{1}(N − 1) + 2S_{2}(N − 1)  (4.8)

et avec l’inégalité 1 + 2S_{2}(N − 1) ⩾ S_{1}(N − 1) + S_{1}(N), on en déduit

𝒟 − ℰ ⩾ 1 + 4α_{1}(N − 2) − 3α_{1}(N − 1).

Cette expression est positive dans tous les cas où α_{1}(N − 1) ⩽ \frac{4}{3}α_{1}(N − 2), c’est-à-dire pour tout N ⩾ 6 d’après le Lemme 3.7, et pour N = 4. Elle est également positive (nulle, en fait) pour N = 3. Enfin, quand N vaut 2 ou 5, le membre de droite de (4.8) est positif (il vaut 0 et 2 respectivement). On a donc toujours 𝒟 ⩾ ℰ si b = 2.

Pour b = 1 (et donc L = 3), la multi-distance à droite de (4.6)

se décompose en

d(u′_{0}, s_{0}, t_{0}, u′_{1}, u′_{2}) + d(u′_{2}, s_{2}, t_{2}, u′_{3}),

ce qui donne

\begin{aligned}𝒟 − ℰ & ⩾ 4 + 2(S_{4} + S_{3})(N − 1) − 2S_{3}(N) − (2S_{1} + α_{4})(N − 2) \\ & = 4 + S_{4}(N − 1) + S_{4}(N − 2) + 2S_{1}(N) − 2S_{1}(N + 1) − 2S_{1}(N − 2). \end{aligned} (4.9)

La concavité des S_{L} permet d’écrire 3S_{4} ⩾ 2S_{3} + S_{6}, et donc

\begin{aligned}S_{4}(n) & ⩾ \frac{2}{3}S_{3}(n) + \frac{1}{3}S_{6}(n) ⩾ \frac{2}{3}S_{1}(n + 1) + \frac{1}{3}S_{2}(n + 1) − \frac{4}{3} \\ & ⩾ \frac{2}{3}S_{1}(n + 1) + \frac{1}{6}[S_{1}(n + 1) + S_{1}(n + 2) − 1] − \frac{4}{3} \\ & = \frac{5}{6}S_{1}(n + 1) + \frac{1}{6}S_{1}(n + 2) − \frac{3}{2} \end{aligned}  (4.10)

pour tout entier naturel n. Par conséquent,

𝒟 − ℰ ⩾ 4 + \frac{5}{6}S_{1}(N) + \frac{1}{6}S_{1}(N + 1) − \frac{3}{2} + \frac{5}{6}S_{1}(N − 1) + \frac{1}{6}S_{1}(N) − \frac{3}{2}
+ 2S_{1}(N) − 2S_{1}(N + 1) − 2S_{1}(N − 2)
= 1 + \frac{5}{6}S_{1}(N − 1) + 3S_{1}(N) − \frac{11}{6}S_{1}(N + 1) − 2S_{1}(N − 2)
= 1 + 2α_{1}(N − 2) + \frac{7}{6}α_{1}(N − 1) − \frac{11}{6}α_{1}(N).

On déduit du Lemme 3.7 que cette dernière expression est positive pour tout N ⩾ 6. Elle est positive également pour N = 3, 4, 5. Enfin, pour N = 2, le membre de droite de (4.9) est positif (il vaut 0). On a donc toujours 𝒟 ⩾ ℰ si b = 1.

Finalement, observons que le cas b = 0 (et donc L = 2) se ramène au cas E = ∅, déjà traité, en échangeant les rôles des colonnes 2 et 3.

En résumé, l’inégalité 𝒟 ⩾ ℰ est valable dans tous les cas où a = c = 1.

4.2.3. Sous-cas a = 1, c ⩾ 2. Il reste le cas où un exactement des deux nombres a, c est > 1. Pour des raisons de symétrie, il suffira d’étudier le cas a = 1, c ⩾ 2.

Pour b ⩾ 2, la multi-distance à droite de (4.6)

se décompose en

d(u′_{0}, s_{0}, t_{0}, u′_{1}) + d(u′_{1}, u′_{2}, …, u′_{a^{∗}}) + d(u′_{a^{∗}}, s_{a^{∗}}, t_{a^{∗}}) + d(t_{a^{∗}}, …, u′_{L}),

ce qui donne

𝒟 − ℰ ⩾ 2a + 2c + 2(S_{3} + S_{b} + S_{2} + S_{3c−2})(N − 1) − 2S_{L}(N)
− (6S_{1} + α_{max{b,3}} + α_{b} + α_{3c−2})(N − 2)

= 2 + 2c + 2(S_{3} + S_{b} + S_{2})(N − 1) − 2S_{L}(N) − (6S_{1} + α_{max{b,3}} + α_{b})(N − 2)

+ S_{3c−2}(N − 1) + S_{3c−2}(N − 2).

Avec les inégalités (4.4) et (4.7), il vient

𝒟 − ℰ ⩾ 4 + 2(S_{3} + S_{b} + S_{2})(N − 1) − (6S_{1} + α_{max{b,3}} + α_{b})(N − 2)
+ (S_{c−1} − S_{L})(N) + (S_{c−1} − S_{L−1})(N − 1) − 2α_{1}(N − 1),

24 THIERRY BOUSCH

et, comme S_{c−1} − S_{1+b+c} ⩾ S_{1} − S_{b+3} et S_{c−1} − S_{b+c} ⩾ S_{1} − S_{b+2}, on a

\begin{aligned}𝒟 − ℰ & ⩾ 4 + 2(S_{3} + S_{b} + S_{2})(N − 1) − (6S_{1} + α_{max\{b,3\}} + α_{b})(N − 2) \\ & + S_{1}(N) − S_{b+3}(N) + S_{1}(N − 1) − S_{b+2}(N − 1) − 2α_{1}(N − 1). \end{aligned} (4.11)

Pour b ⩾ 3, cela s’écrit

𝒟 − ℰ ⩾ 4 + 2(S_{3} + S_{2})(N − 1) − 6S_{1}(N − 2) + 2S_{b}(N − 2)

+ S_{1}(N) − S_{b+3}(N) + S_{1}(N − 1) − S_{b+2}(N − 1) − 2α_{1}(N − 1),

et, comme S_{b+3}(N) ⩽ (S_{b+2} + 2α_{1})(N − 1),

𝒟 − ℰ ⩾ 4 + 2(S_{3} + S_{2})(N − 1) − 6S_{1}(N − 2) + 2S_{b}(N − 2)
+ S_{1}(N) + S_{1}(N − 1) − 2S_{b+2}(N − 1) − 4α_{1}(N − 1).

Ensuite, S_{b}(N − 2) ⩾ S_{b+1}(N − 1) − 2α_{1}(N − 2) et S_{b+1} − S_{b+2} ⩾ S_{1} − S_{2}, donc

𝒟 − ℰ ⩾ 4 + 2(S_{3} + S_{2})(N − 1) − 6S_{1}(N − 2) + 2S_{b+1}(N − 1) − 4α_{1}(N − 2)
+ S_{1}(N) + S_{1}(N − 1) − 2S_{b+2}(N − 1) − 4α_{1}(N − 1)
= 4 + 2S_{3}(N − 1) − 6S_{1}(N − 2) + 2S_{1}(N − 1) − 4α_{1}(N − 2)
+ S_{1}(N) + S_{1}(N − 1) − 4α_{1}(N − 1)

= 2 + 3S_{1}(N) + 3S_{1}(N − 1) − 6S_{1}(N − 2) − 4α_{1}(N − 1) − 4α_{1}(N − 2)

= 2 + 2α_{1}(N − 2) − α_{1}(N − 1),

et cette expression est positive, par (2.2). Ceci montre que 𝒟 ⩾ ℰ si b ⩾ 3.

Pour b = 2, l’inégalité (4.11) s’écrit

𝒟 − ℰ ⩾ 4 + 2S_{3}(N − 1) + 4S_{2}(N − 1) − 6S_{1}(N − 2) − α_{3}(N − 2) − α_{2}(N − 2)
+ S_{1}(N) + S_{1}(N − 1) − S_{5}(N) − S_{4}(N − 1) − 2α_{1}(N − 1)

= 4 + S_{3}(N − 1) + S_{3}(N − 2) + 3S_{2}(N − 1) + S_{2}(N − 2) − 6S_{1}(N − 2)

+ S_{1}(N) + S_{1}(N − 1) − S_{5}(N) − S_{4}(N − 1) − 2α_{1}(N − 1).

On a S_{5}(N) ⩽ (S_{4} + 2α_{1})(N − 1) et S_{4}(N − 1) ⩽ (S_{3} + 2α_{1})(N − 2), donc

𝒟 − ℰ ⩾ 4 + S_{3}(N − 1) + S_{3}(N − 2) + 3S_{2}(N − 1) + S_{2}(N − 2) − 6S_{1}(N − 2)
+ S_{1}(N) + S_{1}(N − 1) − 2S_{4}(N − 1) − 4α_{1}(N − 1)

⩾ 4 + S_{3}(N − 1) − S_{3}(N − 2) + 3S_{2}(N − 1) + S_{2}(N − 2) − 6S_{1}(N − 2)

+ S_{1}(N) + S_{1}(N − 1) − 4α_{1}(N − 1) − 4α_{1}(N − 2)
= 4 + 3S_{2}(N − 1) + S_{2}(N − 2)
+ 2S_{1}(N) − 6S_{1}(N − 2) − 4α_{1}(N − 1) − 4α_{1}(N − 2)
⩾ 4 + \frac{3}{2}[S_{1}(N − 1) + S_{1}(N) − 1] + \frac{1}{2}[S_{1}(N − 2) + S_{1}(N − 1) − 1]
+ 2S_{1}(N) − 6S_{1}(N − 2) − 4α_{1}(N − 1) − 4α_{1}(N − 2)

= 2 + \frac{7}{2}S_{1}(N) + 2S_{1}(N − 1) − \frac{11}{2}S_{1}(N − 2) − 4α_{1}(N − 1) − 4α_{1}(N − 2)

= 2 + \frac{3}{2}α_{1}(N − 2) − \frac{1}{2}α_{1}(N − 1),

et cette expression est positive, par (2.2). Ceci montre que 𝒟 ⩾ ℰ si b = 2.

Pour b = 1 (et donc a^{∗} = 2 et L = c + 2), la multi-distance à droite de (4.6)

se décompose en

d(u′_{0}, s_{0}, t_{0}, u′_{1}) + d(u′_{1}, u′_{2}, s_{2}, t_{2}) + d(t_{2}, …, u′_{L}),

ce qui donne

𝒟 − ℰ ⩾ 2a + 2c + 2(S_{3} + S_{3} + S_{3c−2})(N − 1) − 2S_{L}(N)
− (4S_{1} + α_{3} + α_{3c−2})(N − 2)

= 2 + 2c + 3S_{3}(N − 1) + S_{3}(N − 2) + S_{3c−2}(N − 1) + S_{3c−2}(N − 2)

− 2S_{L}(N) − 4S_{1}(N − 2).

Avec les inégalités (4.4) et (4.7), puis la concavité des S_{L}, il vient

𝒟 − ℰ ⩾ 3S_{1}(N) + S_{1}(N − 1) + (S_{c−1} − S_{c+2})(N) + (S_{c−1} − S_{c+1})(N − 1)
− 2α_{1}(N − 1) − 4S_{1}(N − 2)
⩾ 3S_{1}(N) + S_{1}(N − 1) + (S_{1} − S_{4})(N) + (S_{1} − S_{3})(N − 1)
− 2α_{1}(N − 1) − 4S_{1}(N − 2)

= 4S_{1}(N) + 2S_{1}(N − 1) − S_{4}(N) − S_{3}(N − 1) − 2α_{1}(N − 1) − 4S_{1}(N − 2)

et S_{4}(N) ⩽ (S_{3} + 2α_{1})(N − 1), donc

𝒟 − ℰ ⩾ 4S_{1}(N) + 2S_{1}(N − 1) − 2S_{3}(N − 1) − 4α_{1}(N − 1) − 4S_{1}(N − 2)
= 2 + 2S_{1}(N) + 2S_{1}(N − 1) − 4α_{1}(N − 1) − 4S_{1}(N − 2)
= 2 + 4α_{1}(N − 2) − 2α_{1}(N − 1),

et cette expression est positive, par (2.2). Ceci montre que 𝒟 ⩾ ℰ si b = 1. Pour b = 0 (et donc L = c + 1), la multi-distance à droite de (4.6)

se décompose en

d(u′_{0}, s_{0}, t_{0}, u′_{1}, s_{1}, t_{1}) + d(t_{1}, …, u′_{L}),

ce qui donne

\begin{aligned}𝒟 − ℰ & ⩾ 2a + 2c + 2(S_{5} + S_{3c−2})(N − 1) − 2S_{L}(N) \\ & − (2S_{1} + α_{max\{5,3c−2\}})(N − 2). \end{aligned}  (4.12)

Pour c ⩾ 3, cela s’écrit

𝒟 − ℰ ⩾ 2 + 2c + 2S_{5}(N − 1) + S_{3c−2}(N − 1) + S_{3c−2}(N − 2)
− 2S_{L}(N) − 2S_{1}(N − 2).

Avec les inégalités (4.4) et (4.7), puis la concavité des S_{L}, il vient

𝒟 − ℰ ⩾ 4 + 2S_{5}(N − 1) + (S_{c−1} − S_{c+1})(N) + (S_{c−1} − S_{c})(N − 1)
− 2α_{1}(N − 1) − 2S_{1}(N − 2)
⩾ 4 + 2S_{5}(N − 1) + (S_{2} − S_{4})(N) + (S_{2} − S_{3})(N − 1)
− 2α_{1}(N − 1) − 2S_{1}(N − 2).

La concavité des S_{L} permet également d’écrire 3S_{5} ⩾ S_{3} + 2S_{6}, et donc

\begin{aligned}S_{5}(n) & ⩾ \frac{1}{3}S_{3}(n) + \frac{2}{3}S_{6}(n) ⩾ \frac{1}{3}S_{1}(n + 1) + \frac{2}{3}S_{2}(n + 1) − \frac{5}{3} \\ & ⩾ \frac{1}{3}S_{1}(n + 1) + \frac{1}{3}[S_{1}(n + 1) + S_{1}(n + 2) − 1] − \frac{5}{3} \\ & = \frac{2}{3}S_{1}(n + 1) + \frac{1}{3}S_{1}(n + 2) − 2 \end{aligned}  (4.13)

pour tout n entier naturel. Avec ceci, et l’inégalité S_{4}(N) ⩽ (S_{3} +2α_{1})(N −1), on obtient

𝒟 − ℰ ⩾ 4 + 2S_{5}(N − 1) + S_{2}(N) + S_{2}(N − 1) − S_{4}(N) − S_{3}(N − 1)
− 2α_{1}(N − 1) − 2S_{1}(N − 2)
⩾ 4 + 2S_{5}(N − 1) + S_{2}(N) + S_{2}(N − 1)
− 2S_{3}(N − 1) − 4α_{1}(N − 1) − 2S_{1}(N − 2)
⩾ 4 + \frac{4}{3}S_{1}(N) + \frac{2}{3}S_{1}(N + 1) − 4
+ \frac{1}{2}S_{1}(N) + \frac{1}{2}S_{1}(N + 1) − \frac{1}{2} + \frac{1}{2}S_{1}(N − 1) + \frac{1}{2}S_{1}(N) − \frac{1}{2}
− 2S_{1}(N) + 2 − 4α_{1}(N − 1) − 2S_{1}(N − 2)
= 1 + \frac{1}{2}S_{1}(N − 1) + \frac{1}{3}S_{1}(N) + \frac{7}{6}S_{1}(N + 1) − 4α_{1}(N − 1) − 2S_{1}(N − 2)
= 1 + 2α_{1}(N − 2) − \frac{5}{2}α_{1}(N − 1) + \frac{7}{6}α_{1}(N)
⩾ 1 + 2α_{1}(N − 2) − \frac{4}{3}α_{1}(N − 1),

et cette expression est positive, comme on le vérifie facilement à l’aide du Lemme 3.7. Ceci montre que 𝒟 ⩾ ℰ si b = 0, c ⩾ 3.

Pour c = 2, l’inégalité (4.12) s’écrit

𝒟 − ℰ ⩾ 6 + 2(S_{5} + S_{4})(N − 1) − 2S_{3}(N) − (2S_{1} + α_{5})(N − 2)
= 6 + S_{5}(N − 1) + S_{5}(N − 2) + 2S_{4}(N − 1) − 2S_{3}(N) − 2S_{1}(N − 2),

et des minorations (4.10) et (4.13) on déduit

𝒟 − ℰ ⩾ 6 + \frac{2}{3}S_{1}(N) + \frac{1}{3}S_{1}(N + 1) − 2 + \frac{2}{3}S_{1}(N − 1) + \frac{1}{3}S_{1}(N) − 2
+ \frac{5}{3}S_{1}(N) + \frac{1}{3}S_{1}(N + 1) − 3 − 2S_{1}(N + 1) + 2 − 2S_{1}(N − 2)
= 1 + \frac{2}{3}S_{1}(N − 1) + \frac{8}{3}S_{1}(N) − \frac{4}{3}S_{1}(N + 1) − 2S_{1}(N − 2)
= 1 + 2α_{1}(N − 2) + \frac{4}{3}α_{1}(N − 1) − \frac{4}{3}α_{1}(N)
⩾ 1 + 2α_{1}(N − 2) − \frac{4}{3}α_{1}(N − 1),

et cette expression, on l’a vu, est positive. Ceci montre que 𝒟 ⩾ ℰ si b = 0, c = 2.

Nous avons ainsi établi l’inégalité 𝒟 ⩾ ℰ dans tous les cas où K = 0. Ceci termine la preuve de la récurrence, et donc du Théorème 2.2.

5. Pourquoi ces pénalités?

La démonstration du Théorème 2.2, on le voit, est fastidieuse à cause de la disjonction de cas, mais pas vraiment difficile. En fait, l’essentiel de la difficulté dans le problème de Stockmeyer consiste à imaginer la “bonne” minoration sur les distances entre empilements. Dans ce chapitre, je tâcherai d’expliquer comment je suis arrivé à cette inégalité.

Une “bonne” minoration des distances doit être (i) vraie, évidemment, (ii) devenir une égalité entre les empilements qui nous intéressent, et, ce qui est sans doute le plus difficile à réaliser, (iii) se prêter à une démonstration par récurrence sur le nombre de disques.

Je me suis évidemment inspiré des méthodes de l’article [Bou] pour la résolution du Reve’s Puzzle, mais la Tour de Stockmeyer présente certaines particularités qui font que ces méthodes ne sont pas toutes utilisables, et qu’il faut en introduire de nouvelles.

Une différence importante est que le Reve’s Puzzle possède la propriété de midpoint [BH, KF], qui dit qu’entre deux empilements parfaits, il existe un chemin géodésique symétrique autour de son arête centrale, qui est l’unique mouvement du plus grand disque. Entre deux empilements quelconques, les choses sont plus compliquées, mais des arguments similaires permettent de décomposer le chemin en une “partie gauche” et une “partie droite” dont les longueurs peuvent être évaluées par une même formule; ceci est utilisé dans [Bou] pour montrer l’équivalence entre les inégalités (5.3) et (5.4). Ces dernières inégalités sont plus commodes, car elles ne dépendent que d’une des extrémités du chemin : grâce à ça, elles peuvent être facilement “monotonisées” (une manipulation qui joue un rôle essentiel dans [Bou]).

Il ne semble pas possible de faire quelque chose de similaire pour la Tour de Stockmeyer : même entre empilements parfaits (sur des tiges extérieures), le plus grand disque effectue deux mouvements, ce qui décompose le chemin en trois parties : une partie gauche et une partie droite, mais aussi une partie centrale qui n’est pas de même nature. On doit donc se contenter d’inégalités telles que (2.8) ou (2.11), qui font dépendre la longueur du chemin de ses deux extrémités. Cette double dépendance complique et affaiblit beaucoup la monotonisation, qui du coup ne paraît plus du tout souhaitable.

D’autres différences sont que le nombre (conjecturalement) minimum de mouvements de disques est plus compliqué pour la Tour de Stockmeyer que pour le Reve’s Puzzle, et que le groupe de symétrie est plus petit. Tout cela suggère que le problème de Stockmeyer n’est peut-être pas si facile …

J’ai expliqué en § 2 comment on est amené à postuler l’inégalité (2.10) pour les multidistances alternantes entre configurations parfaites. Comment modifier cette inégalité conjecturale si les configurations u_{0}, u_{L} ne sont plus supposées parfaites?

On considérera l’exemple suivant : on reprend les notations de § 2, avec L ⩾ 1, u_{0} et u_{L} sont les configurations parfaites à N disques sur les tiges p_{0} et p_{L}, et ũ_{0}, ũ_{L} les empilements obtenus à partir de u_{0}, u_{L} en transférant les M plus petits disques vers la tige 2. Il est clair qu’on peut aller de u_{0} vers ũ_{L} (ou de ũ_{0} vers u_{L}) avec 2S_{1}(M)+L (3^{N−M}−1) mouvements de disques, et de ũ_{0} vers ũ_{L} avec L (3^{N−M} − 1) mouvements de disques — en passant, dans tous les cas, par les mêmes configurations intermédiaires u_{1}, …, u_{L−1}. On a donc

d(u_{0}, u_{1}, …, u_{L−1}, u_{L}) ⩽ 2S_{1}(N),
d(u_{0}, u_{1}, …, u_{L−1}, ũ_{L}) ⩽ 2S_{1}(N) − 2S_{1}(M),
d(ũ_{0}, u_{1}, …, u_{L−1}, u_{L}) ⩽ 2S_{1}(N) − 2S_{1}(M),
d(ũ_{0}, u_{1}, …, u_{L−1}, ũ_{L}) ⩽ 2S_{1}(N) − 4S_{1}(M),

et il est raisonnable de supposer que ces inégalités sont en fait des égalités. Si c’est le cas, on voit que la multi-distance est diminuée de 2S_{1}(M) = ∑_{k<M}2α_{1}(k) si les M plus

petits disques sont hors de la colonne p_{0} au départ, et diminuée d’autant s’ils sont hors de la colonne p_{L} à l’arrivée, ces deux effets pouvant se cumuler. Cet exemple, et d’autres similaires, suggèrent la formule

d(u_{0}, u_{1}, …, u_{L}) ⩾ 2S_{L}(N) − ∑_{\begin{matrix}k∈[N] \\ u_{0}(k)≠p_{0} \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N] \\ u_{L}(k)≠p_{L} \end{matrix}} 2α_{1}(k)  (5.1)

pour les multi-distances alternantes entre deux configurations extrêmes quelconques.

Cette inégalité (conjecturale) semble donc un bon point de départ pour une démonstration. On peut, comme en § 4, essayer de démontrer (5.1) par récurrence entre N − 1 et N disques, par une disjonction de cas sur les mouvements du plus grand disque : cela conduit à un certain nombre d’inégalités à démontrer sur les S_{L}, une pour chaque cas. Beaucoup de ces inégalités sont vraies (au moins numériquement, je n’ai pas cherché à les prouver rigoureusement), mais un petit nombre d’entre elles sont fausses — et donc, cette idée de preuve ne fonctionne pas.

On pourrait envisager de démontrer (5.1) par une récurrence entre N − 2 et N disques, mais cela nécessiterait une disjonction de cas portant sur les mouvements des deux plus grands disques, et serait probablement très fastidieux. Il paraît préférable de s’en tenir à une récurrence entre N − 1 et N disques. La précédente tentative de preuve de (5.1) ayant échoué de peu, on se dit qu’une toute petite amélioration de cette inégalité suffirait pour venir à bout des quelques cas problématiques.

En outre, dans la récurrence apparaît une complication technique : l’augmentation du terme constant 2S_{L}(·) entre N − 1 et N disques, à savoir 2α_{L}(N − 1), ne présente pas de relation simple avec la pénalité du plus grand disque, qui vaut 2α_{1}(N − 1), lorsque L > 1. Cela a pour conséquence que les inégalités sur N −1 et N disques ne se raccordent pas très bien, même dans des cas qui devraient être triviaux. En particulier, si le plus grand disque est dans la colonne 2 au départ et à l’arrivée, il n’a aucun intérêt à bouger, et d(u_{0}, …, u_{L}) = d(u′_{0}, …, u′_{L}). Cependant, la formule (5.1) donnera des minorations différentes pour d(u_{0}, …, u_{L}) et d(u′_{0}, …, u′_{L}), ce qui n’est pas très satisfaisant. Cela suggère que pour L > 1 la pénalité du plus grand disque n’est peut-être pas la bonne, et devrait être α_{L}(N − 1) au lieu de 2α_{1}(N − 1).

Pour L = 1, aucune amélioration (i.e. diminution) des pénalités n’est possible, comme on le voit en prenant pour u_{0}, u_{1} deux configurations parfaites identiques.

En résumé, il semble que pour L > 1 (et N ⩾ 1) la “bonne” minoration des multidistances alternantes serait plutôt

d(u_{0}, u_{1}, …, u_{L}) ⩾ 2S_{L}(N) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠p_{0} \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈\{N−1\} \\ u_{0}(k)≠p_{0} \end{matrix}} α_{L}(k)

− ∑_{\begin{matrix}k∈[N−1] \\ u_{L}(k)≠p_{L} \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈\{N−1\} \\ u_{L}(k)≠p_{L} \end{matrix}} α_{L}(k),

(5.2)

inégalité légèrement plus fine que (5.1) puisque la pénalité du plus grand disque est plus petite, et qui se comporte mieux vis-à-vis de la récurrence.

Mais justement, comme c’est un énoncé plus fort, il a plus de chances d’être faux. Les arguments ci-dessus ne disent rien quant à la véracité de la formule (5.2), seulement que les calculs pourraient se passer mieux qu’avec (5.1). Et puis, la formule (5.2) n’a pas une très bonne tête : elle est manifestement trop compliquée, fait jouer un rôle spécial au plus grand disque, et n’inclut pas le cas L = 1. Pourquoi devrait-on y croire?

La raison est un argument de type midpoint, qui affirme que pour toute valeur paire de L, on peut déduire les inégalités (5.2) des inégalités (5.1) pour la même valeur de L. Pour fixer les idées, examinons le cas L = 4. On veut montrer que toute multi-distance alternante (à quatre termes) satisfait

d(u_{0}, u_{1}, u_{2}, u_{3}, u_{4}) ⩾ 2S_{4}(N) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠1 \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−1] \\ u_{4}(k)≠1 \end{matrix}} 2α_{1}(k) − Kα_{4}(N − 1),

où K ∈ {0, 1, 2} est défini par (4.2). Si K = 0, c’est-à-dire u_{0}(N − 1) = u_{4}(N − 1) = 1, cette inégalité est identique à (5.1), et il n’y a rien à démontrer. Si K = 2, c’est-à-dire u_{0}(N − 1) ≠ 1 et u_{4}(N − 1) ≠ 1, on écrit

d(u_{0}, u_{1}, u_{2}, u_{3}, u_{4}) ⩾ d(u′_{0}, u′_{1}, u′_{2}, u′_{3}, u′_{4})

⩾ 2S_{4}(N − 1) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠1 \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−1] \\ u_{L}(k)≠1 \end{matrix}} 2α_{1}(k)

= 2S_{4}(N) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠1 \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−1] \\ u_{L}(k)≠1 \end{matrix}} 2α_{1}(k) − 2α_{4}(N − 1),

qui est l’inégalité cherchée.

Reste le cas K = 1, c’est-à-dire que u_{0}(N − 1) ≠ 1 ou bien u_{4}(N − 1) ≠ 1. Ces deux cas étant symétriques, je supposerai par exemple u_{0}(N − 1) = 1 ≠ u_{4}(N − 1). C’est ici qu’intervient la parité de L : on écrit

d(u_{0}, u_{1}, u_{2}, u_{3}, u_{4}) = d(u_{0}, u_{1}, u_{2}) + d(u_{2}, u_{3}, u_{4})
⩾ d(u_{0}, u_{1}, u_{2}) + d(u′_{2}, u′_{3}, u′_{4})
⩾ \frac{1}{2}d(u_{0}, u_{1}, u_{2}, u_{1}, u_{0}) + \frac{1}{2}d(u′_{4}, u′_{3}, u′_{2}, u′_{3}, u′_{4}).

Ces deux dernières multi-distances sont alternantes, donc on peut leur appliquer la minoration (5.1), ce qui donne

d(u_{0}, u_{1}, u_{2}, u_{1}, u_{0}) ⩾ 2S_{4}(N) − ∑_{\begin{matrix}k∈[N] \\ u_{0}(k)≠1 \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N] \\ u_{0}(k)≠1 \end{matrix}} 2α_{1}(k) = 2S_{4}(N) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠1 \end{matrix}} 4α_{1}(k),

d(u′_{4}, u′_{3}, u′_{2}, u′_{3}, u′_{4}) ⩾ 2S_{4}(N − 1) − ∑_{\begin{matrix}k∈[N−1] \\ u_{4}(k)≠1 \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−1] \\ u_{4}(k)≠1 \end{matrix}} 2α_{1}(k) = 2S_{4}(N − 1) − ∑_{\begin{matrix}k∈[N−1] \\ u_{4}(k)≠1 \end{matrix}} 4α_{1}(k),

et par conséquent

d(u_{0}, u_{1}, u_{2}, u_{3}, u_{4}) ⩾ 2S_{4}(N) − ∑_{\begin{matrix}k∈[N−1] \\ u_{0}(k)≠1 \end{matrix}} 2α_{1}(k) − ∑_{\begin{matrix}k∈[N−1] \\ u_{4}(k)≠1 \end{matrix}} 2α_{1}(k) − α_{4}(N − 1),

qui est l’inégalité cherchée.

Cet argument s’étend évidemment à toute valeur paire de L (et plus généralement, quand le produit KL est pair). Bien qu’il ne suffise pas à établir (5.2) dans tous les cas, il suggère que ces inégalités ont de bonnes chances d’être vraies, et qu’on peut se lancer avec confiance dans une démonstration.

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

Références

[BH] J.-P. Bode & A. M. Hinz, Results and open problems on the Tower of Hanoi, Congressus Numerantium 139 (1999), 113–122

[Bou] T. Bousch, La quatrième tour de Hanoï, Bulletin of the Belgian Mathematical Society Simon Stevin 21 (2014), 895–912

[CM] J. Chappelon & A. Matsuura, On generalized Frame–Stewart numbers, Discrete Mathematics 312 (2012), 830–836

[CS] X. Chen & J. Shen, On the Frame–Stewart conjecture about the Towers of Hanoi, SIAM Journal on Computing 33 (2004), 584–589

[Dud] H. E. Dudeney, The Canterbury puzzles and other curious problems, E. P. Dutton, New York (1908)

[Dun] O. Dunkel, Editorial Note concerning Advanced Problem 3918, American Mathematical Monthly 48 (1941), page 219

[Gro] C. Grosu, A new lower bound for the Towers of Hanoi problem, Electronic Journal of Combinatorics 23 (2016), Article #P1.22

[HP] A. M. Hinz & C. Petr, Computational solution of an old Tower of Hanoi problem, Electronic Notes in Discrete Mathematics 53 (2016), 445–458

[H+] A. M. Hinz, S. Klavžar, U. Milutinović & C. Petr, The tower of Hanoi, myths and maths, Birkhäuser (2013)

[Fra] J. S. Frame, Solution to Advanced Problem 3918, American Mathematical Monthly 48 (1941), 216–217

[Knu] D. E. Knuth, The art of computer programming, volume 3: sorting and searching, Addison– Wesley (1973)

[KF] R. E. Korf & A. Felner, 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

[Min] D. J. Mintz, 2,3 sequence as binary mixture, Fibonacci Quarterly 19 (1981), 351–360

[Mor] P. Moree, Integers without large prime factors: from Ramanujan to de Bruijn, Integers 14A (2014), Article #A5

[Roc] R. T. Rockafellar, Convex analysis, Princeton Mathematical Series 28, Princeton University Press (1970)

[Slo] N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, http://oeis.org

[St1] B. M. Stewart, Advanced Problem 3918, American Mathematical Monthly 46 (1939), page 363 [St2] B. M. Stewart, Solution to Advanced Problem 3918, American Mathematical Monthly 48

(1941), 217–219

[Sto] P. K. Stockmeyer, Variations on the four-post Tower of Hanoi puzzle, Congressus Numerantium 102 (1994), 3–12

[Sze] M. Szegedy, In how many steps the k-peg version of the Towers of Hanoi game can be solved?, Lecture Notes in Computer Science 1563 (1999), 356–361

Laboratoire de Mathématique (UMR 8628 du CNRS), bât. 425/430, Université de Paris-Sud, 91405 Orsay Cedex, France

  E-mail address: Thierry.Bousch@math.u-psud.fr