Les tours de Hanoï II : le problème avec quatre piquets et plus

Piste rouge 22 septembre 2016  - Ecrit par  Jonathan Chappelon Voir les commentaires

Après avoir présenté le problème classique des tours de Hanoï avec trois piquets le trimestre dernier [1], nous nous intéressons ici à sa généralisation pour quatre piquets et plus.

Le problème des tours de Hanoï avec quatre piquets a été énoncé pour la première fois par Henry Dudeney en 1907 [2] mais sous une autre forme. Il l’appelle alors problème de Reve. On considère quatre tabourets. Il s’agit de déplacer des fromages de différentes tailles d’un tabouret à un autre en respectant les règles :

  • un seul fromage peut être déplacé à la fois,
  • un fromage ne peut être placé sur un fromage de taille plus petite.

En 1939 [3], Bonnie M. Stewart pose le problème des tours de Hanoï de manière plus générale, pour $k$ piquets avec $k\geqslant 4$, dans la revue American Mathematical Monthly qui est une revue américaine de mathématiques destinée à un large public. Quelques années plus tard, en 1941, Stewart [4] et James S. Frame [5] proposent indépendamment une solution algorithmique du problème pour quatre piquets ou plus. Cette solution, que nous allons exposer dans la suite, permet d’obtenir une borne supérieure du nombre optimal de mouvements nécessaires pour résoudre le problème des tours de Hanoï à $k\geqslant 4$ piquets.

L’algorithme de Frame-Stewart

On souhaite transférer $n\geqslant 0$ disques en utilisant $k\geqslant 3$ piquets. Posons $\mathrm{FS}(k,n)$ le nombre de mouvements de disques utilisés dans cet algorithme pour déplacer une pile de $n$ disques d’un piquet initial à un piquet terminal en autorisant l’utilisation de $k$ piquets.

Pour $k=3$ piquets, comme présenté dans l’article du trimestre dernier, on sait déplacer les $n$ disques de manière optimale en $2^{n}-1$ mouvements. Il est alors légitime de poser $\mathrm{FS}(3,n)=2^{n}-1$ pour tout $n\geqslant 0$.

Pour $k\geqslant 4$, on procède de manière récursive. Pour $n=0$, il est évident qu’aucun mouvement n’est nécessaire. On pose donc $\mathrm{FS}(k,0)=0$.

Pour $n\geqslant 1$ disques, on considère un entier $t$ tel que $0\leqslant t\leqslant n-1$. Il est alors possible de déplacer les $n$ disques de la manière suivante :

  • on transfère les $t$ plus petits disques de la pile des $n$ disques du piquet initial à un piquet intermédiaire (non terminal) en utilisant les $k$ piquets,
  • le restant de la pile de départ, les $n-t$ plus grand disques, sont déplacés du piquet initial au piquet terminal en utilisant $k-1$ piquets, en ignorant le piquet intermédiaire occupé par les $t$ plus petits disques,
  • on transfère les $t$ plus petits disques du piquet intermédiaire au piquet terminal en utilisant les $k$ piquets.

Les étapes 1 et 3 sont effectuées en $\mathrm{FS}(k,t)$ mouvements chacune et l’étape 2 en $\mathrm{FS}(k-1,n-t)$ mouvements. Au total, les $n$ disques ont été déplacés en $2\mathrm{FS}(k,t)+\mathrm{FS}(k-1,n-t)$ mouvements. On choisit alors la valeur de $t\in\{0,1,\ldots,n-1\}$ telle que ce nombre de mouvements est le plus petit possible. Ainsi, pour $k$ piquets, les $n$ disques sont déplacés du piquet initial au piquet terminal en
\[ \mathrm{FS}(k,n) = \min_{0\leqslant t\leqslant n-1}\left\{ 2\mathrm{FS}(k,t)+\mathrm{FS}(k-1,n-t)\right\} \]
mouvements.

Notons $\mathrm{T}(k,n)$ le nombre minimal de mouvements nécessaires et suffisants pour déplacer une tour de $n\geqslant 0$ disques d’un piquet initial vers un piquet terminal en utilisant $k\geqslant 3$ piquets. Alors,

Pour tout $k\geqslant 3$ et $n\geqslant 0$, on a
\[ \mathrm{T}(k,n) \leqslant \mathrm{FS}(k,n), \]

où $\mathrm{FS}(k,n)$ sont les nombres de Frame-Stewart définis par

  • $\mathrm{FS}(3,n)=2^n-1$ pour tout $n\geqslant 0$,
  • $\mathrm{FS}(k,0)=0$ pour tout $k\geqslant 3$,
  • $\mathrm{FS}(k,n)= \min_{0\leqslant t\leqslant n-1}\left\{ 2\mathrm{FS}(k,t)+\mathrm{FS}(k-1,n-t)\right\}$ pour tout $k\geqslant 4$ et $n\geqslant 1$.

En 1941, Frame et Stewart conjecturèrent que cette borne supérieure est en fait la valeur minimale du nombre de mouvements pour résoudre le problème des tours de Hanoï à $k$ piquets.

Conjecture de Frame-Stewart.
Pour tout $k\geqslant 3$ et $n\geqslant 0$,
\[ \mathrm{T}(k,n) = \mathrm{FS}(k,n). \]

Comme prouvé dans l’article du trimestre dernier, cette conjecture est vraie pour $k=3$. Pour $k=4$, une preuve que cette conjecture est vraie a été apportée par Thierry Bousch en 2014 [6]. Pour $k\geqslant 5$, cette conjecture est complètement ouverte.

Les nombres de Frame-Stewart pour $k=4$

Dans la suite, nous nous intéresserons essentiellement aux nombres de Frame-Stewart $\mathrm{FS}(4,n)$ pour quatre piquets.

Commençons par déterminer les premières valeurs de $\mathrm{FS}(4,n)$.

$\mathrm{FS}(4,0) = 0$.

$ \begin{array}{l} 2\mathrm{FS}(4,0)+\mathrm{FS}(3,1) = 2\times0 + (2^1-1) = 1 \Longrightarrow \mathrm{FS}(4,1)=1 \end{array} $

$ \left.\begin{array}{l} 2\mathrm{FS}(4,0)+\mathrm{FS}(3,2) = 2\times0 + (2^2-1) = \color{red}{3} \\ 2\mathrm{FS}(4,1)+\mathrm{FS}(3,1) = 2\times1 + (2^1-1) = 2+1 = \color{red}{3} \\ \end{array}\right\}\Longrightarrow \mathrm{FS}(4,2)=3 $

$ \left.\begin{array}{l} 2\mathrm{FS}(4,0)+\mathrm{FS}(3,3) = 2\times0 + (2^3-1) = 7 \\ 2\mathrm{FS}(4,1)+\mathrm{FS}(3,2) = 2\times1 + (2^2-1) = 2+3 = \color{red}{5} \\ 2\mathrm{FS}(4,2)+\mathrm{FS}(3,1) = 2\times3 + (2^1-1) = 6+1 = 7 \\ \end{array}\right\}\Longrightarrow \mathrm{FS}(4,3)=5 $

$ \left.\begin{array}{l} 2\mathrm{FS}(4,0)+\mathrm{FS}(3,4) = 2\times0 + (2^4-1) = 15 \\ 2\mathrm{FS}(4,1)+\mathrm{FS}(3,3) = 2\times1 + (2^3-1) = 2+7 = \color{red}{9} \\ 2\mathrm{FS}(4,2)+\mathrm{FS}(3,2) = 2\times3 + (2^2-1) = 6+3 = \color{red}{9} \\ 2\mathrm{FS}(4,3)+\mathrm{FS}(3,1) = 2\times5 + (2^1-1) = 10+1 = 11 \\ \end{array}\right\}\Longrightarrow \mathrm{FS}(4,4)=9 $

$ \left.\begin{array}{l} 2\mathrm{FS}(4,0)+\mathrm{FS}(3,5) = 2\times0 + (2^5-1) = 31 \\ 2\mathrm{FS}(4,1)+\mathrm{FS}(3,4) = 2\times1 + (2^4-1) = 2+15 = 17 \\ 2\mathrm{FS}(4,2)+\mathrm{FS}(3,3) = 2\times3 + (2^3-1) = 6+7 = \color{red}{13} \\ 2\mathrm{FS}(4,3)+\mathrm{FS}(3,2) = 2\times5 + (2^2-1) = 10+3 = \color{red}{13} \\ 2\mathrm{FS}(4,4)+\mathrm{FS}(3,1) = 2\times9 + (2^1-1) = 18+1 = 19 \\ \end{array}\right\}\Longrightarrow \mathrm{FS}(4,5)=13 $

$ \left.\begin{array}{l} 2\mathrm{FS}(4,0)+\mathrm{FS}(3,6) = 2\times0 + (2^6-1) = 63 \\ 2\mathrm{FS}(4,1)+\mathrm{FS}(3,5) = 2\times1 + (2^5-1) = 2+31 = 33 \\ 2\mathrm{FS}(4,2)+\mathrm{FS}(3,4) = 2\times3 + (2^4-1) = 6+15 = 21 \\ 2\mathrm{FS}(4,3)+\mathrm{FS}(3,3) = 2\times5 + (2^3-1) = 10+7 = \color{red}{17} \\ 2\mathrm{FS}(4,4)+\mathrm{FS}(3,2) = 2\times9 + (2^2-1) = 18+3 = 21 \\ 2\mathrm{FS}(4,5)+\mathrm{FS}(3,1) = 2\times13 + (2^1-1) = 26+1 = 27 \\ \end{array}\right\}\Longrightarrow \mathrm{FS}(4,6)=17 $

$ \left.\begin{array}{l} 2\mathrm{FS}(4,0)+\mathrm{FS}(3,7) = 2\times0 + (2^7-1) = 127 \\ 2\mathrm{FS}(4,1)+\mathrm{FS}(3,6) = 2\times1 + (2^6-1) = 2+63 = 65 \\ 2\mathrm{FS}(4,2)+\mathrm{FS}(3,5) = 2\times3 + (2^5-1) = 6+31 = 37 \\ 2\mathrm{FS}(4,3)+\mathrm{FS}(3,4) = 2\times5 + (2^4-1) = 10+15 = \color{red}{25} \\ 2\mathrm{FS}(4,4)+\mathrm{FS}(3,3) = 2\times9 + (2^3-1) = 18+7 = \color{red}{25} \\ 2\mathrm{FS}(4,5)+\mathrm{FS}(3,2) = 2\times13 + (2^2-1) = 26+3 = 29 \\ 2\mathrm{FS}(4,6)+\mathrm{FS}(3,1) = 2\times17 + (2^1-1) = 34+1 = 35 \\ \end{array}\right\}\Longrightarrow \mathrm{FS}(4,7)=25 $

Ainsi les premiers éléments de la suite $\left(\mathrm{FS}(4,n)\right)_{n\geqslant 0}$ sont
\[ \left(\mathrm{FS}(4,n)\right)_{n\geqslant 0} = \left( 0,1,3,5,9,13,17,25,\ldots\right). \]

Nous allons donner dans la suite une formule explicite pour ces nombres. Dans un premier temps, intéressons-nous aux différences $\Delta\mathrm{FS}(4,n)=\mathrm{FS}(4,n)-\mathrm{FS}(4,n-1)$ pour tout $n\geqslant 1$.

Les premiers éléments de la suite $\left(\Delta\mathrm{FS}(4,n)\right)_{n\geqslant 1}$ sont
\[ \left(\Delta\mathrm{FS}(4,n)\right)_{n\geqslant 1} = \left( 1,2,2,4,4,4,8,\ldots\right). \]

Si l’on continue les calculs, on obtient les éléments suivants
\[ (1,\underbrace{2,2}_{2\times},\underbrace{4,4,4}_{3\times},\underbrace{8,8,8,8}_{4\times},\underbrace{16,16,16,16,16}_{5\times},\ldots\ldots). \]

Afin de décrire au mieux cette suite, nous allons introduire les nombres triangulaires $T_m$ qui sont la somme des $m$ premiers entiers naturels pour tout $m\geqslant 1$.

\[ T_m = 1+2+\cdots+(m-1)+m = \frac{m(m+1)}{2}. \]

Preuve

Une preuve simple de ce résultat peut être obtenue en écrivant la somme dans les deux sens. On effectue alors la somme colonne par colonne et on obtient $m$ sous-sommes égales à $m+1$ chacune.
\[ \color{red}{2T_m} = \begin{array}[t]{ccccccccccc} & 1 & + & 2 & + & \cdots & + & m-1 & + & m \\ + & m & + & m-1 & + & \cdots & + & 2 & + & 1 \\ \hline & (m+1) & + & (m+1) & + & \cdots & + & (m+1) & + & (m+1) & = \color{red}{m(m+1)}.\\ \end{array} \]
Traditionnellement, l’origine de cette preuve très simple est attribuée à Gauss.

Les premiers éléments de la suite $\left(T_m\right)_{m\geqslant 0}$ sont
\[ \left(T_m\right)_{m\geqslant 0} = \left( 0,1,3,6,10,15,21,28,\ldots\right). \]

Ainsi, par définition, il est très facile de passer de $T_{m-1}$ à $T_{m}$,
\[ T_{m} = 1+2+\cdots+(m-1)+m = T_{m-1} + m. \]
et donc $\Delta T_m=T_m-T_{m-1}=m$ pour tout $m\geqslant 1$.

Ainsi les premiers éléments de la suite $\left(\Delta T_m\right)_{m\geqslant 1}$ est la suite des entiers naturels
\[ \left(\Delta T_m\right)_{m\geqslant 1} = \left( 1,2,3,4,5,6,7,\ldots\right). \]

Enfin, remarquons que la suite $\left(T_m\right)_{m\geqslant 0}$ est strictement croissante.

A l’aide des nombres triangulaires, non seulement nous allons déterminer la valeur exacte de $\mathrm{FS}(4,n)$ mais nous allons aussi déterminer pour quelle valeur de $t\in\{0,1,\ldots,n-1\}$ le minimum de
\[ \mathrm{FS}(4,n)= \min_{0\leqslant t\leqslant n-1}\left\{ 2\mathrm{FS}(4,t)+\mathrm{FS}(3,n-t)\right\} \]
est atteint. De plus, cela permettra de mieux comprendre l’algorithme de résolution proposé par Frame et Stewart.

Afin de simplifier l’écriture, on considère les nombres $\mathrm{FS}(4,n,t)$ définis par
\[ \mathrm{FS}(4,n,t) = 2\mathrm{FS}(4,t)+\mathrm{FS}(3,n-t) \]
pour tout $t\in\{0,1,\ldots,n-1\}$ et $n\geqslant 1$. Ainsi, les nombres $\mathrm{FS}(4,n)$ sont définis par
\[ \mathrm{FS}(4,n) = \min_{0\leqslant t\leqslant n-1}\mathrm{FS}(4,n,t) \]
pour tout $n\geqslant 1$.

Le résultat suivant peut alors être obtenu.

Soit $n$ un entier strictement positif et soit $m$ l’entier tel que
\[ T_m+1 \leqslant n \leqslant T_{m+1}. \]
Alors
\[ \Delta\mathrm{FS}(4,n) = 2^m, \]
et
\[ \mathrm{FS}(4,n) = \mathrm{FS}(4,n,n-m-1). \]

La preuve donnée ci-dessous est très technique. Néanmoins il n’est pas nécessaire de la comprendre entièrement pour poursuivre la lecture.

Preuve

Pour $n=1$, on a $m=0$ car $1=T_0+1\leqslant n\leqslant T_1=1$. Le résultat est alors vérifié car $\Delta\mathrm{FS}(4,1)=1=2^0$ et $\mathrm{FS}(4,1)=\mathrm{FS}(4,1,0)$.

Supposons que le résultat soit vrai pour toute valeur comprise entre $1$ et $n-1$ et montrons le pour $n$.

Commençons par simplifier la différence $\mathrm{FS}(4,n,t+1)-\mathrm{FS}(4,n,t)$ pour tout $t\in\{0,\ldots,n-2\}$ :
\[ \mathrm{FS}(4,n,t+1)-\mathrm{FS}(4,n,t) \begin{array}[t]{l} = (2\mathrm{FS}(4,t+1)+\mathrm{FS}(3,n-t-1))-(2\mathrm{FS}(4,t)+\mathrm{FS}(3,n-t)) \\ = 2(\mathrm{FS}(4,t+1)-\mathrm{FS}(4,t)) - (\mathrm{FS}(3,n-t)-\mathrm{FS}(3,n-t-1)) \\ = 2\Delta\mathrm{FS}(4,t+1) - \Delta\mathrm{FS}(3,n-t).\\ \end{array} \]
On peut remplacer $\Delta\mathrm{FS}(3,n-t)$ par sa valeur exacte
\[ \Delta\mathrm{FS}(3,n-t) = (2^{n-t}-1)-(2^{n-t-1}-1) = 2\times2^{n-t-1}-2^{n-t-1} = 2^{n-t-1}. \]
Donc
\[ \mathrm{FS}(4,n,t+1)-\mathrm{FS}(4,n,t) = 2\Delta\mathrm{FS}(4,t+1) - 2^{n-t-1}. \]
Nous allons maintenant utiliser l’hypothèse de récurrence pour la valeur de $\Delta\mathrm{FS}(4,t+1)$ et notamment la croissance des éléments
\[ \Delta\mathrm{FS}(4,1) \leqslant \Delta\mathrm{FS}(4,2) \leqslant \Delta\mathrm{FS}(4,3) \leqslant \cdots \leqslant \Delta\mathrm{FS}(4,n-2) \leqslant \Delta\mathrm{FS}(4,n-1) .\quad\quad (*) \]
Distinguons alors différents cas suivant la valeur de $t$.

  • Pour $0\leqslant t\leqslant n-m-2$,
    \[ t+1\leqslant n-(m+1) \leqslant T_{m+1}-(m+1) = T_m \leqslant n-1 \]
    implique que $\Delta\mathrm{FS}(4,t+1)\leqslant\Delta\mathrm{FS}(4,T_m)$ par l’hypothèse de croissance des éléments de $(*)$. Par hypothèse, on sait que $\Delta\mathrm{FS}(4,T_m)=2^{m-1}$. On en déduit que
    \[ \Delta\mathrm{FS}(4,t+1)\leqslant 2^{m-1}. \]
    De plus, $n-t-1\geqslant m+1$ implique que $2^{n-t-1}\geqslant 2^{m+1}$. On en déduit que
    \[ \mathrm{FS}(4,n,t+1)-\mathrm{FS}(4,n,t) \leqslant 2^m-2^{m+1} <0 \]
    pour tout $0\leqslant t\leqslant n-m-2$. Cela conduit à
    \[ \mathrm{FS}(4,n,n-m-1) < \mathrm{FS}(4,n,n-m-2) < \cdots\cdots < \mathrm{FS}(4,n,1) < \mathrm{FS}(4,n,0). \]
  • Pour $n-m-1\leqslant t\leqslant n-2$,
    \[ n-1\geqslant t+1 \geqslant n-m \geqslant T_m+1-m = T_{m-1}+1 \]
    implique que $\Delta\mathrm{FS}(4,t+1)\geqslant\Delta\mathrm{FS}(4,T_{m-1}+1)$ par l’hypothèse de croissance des éléments de $(*)$. Par hypothèse, on sait que $\Delta\mathrm{FS}(4,T_{m-1}+1)=2^{m-1}$. On en déduit que
    \[ \Delta\mathrm{FS}(4,t+1)\geqslant 2^{m-1}. \]
    De plus, $n-t-1\leqslant m$ implique que $2^{n-t-1}\leqslant 2^{m}$. On en déduit que
    \[ \mathrm{FS}(4,n,t+1)-\mathrm{FS}(4,n,t) \geqslant 2^m-2^{m} = 0 \]
    pour tout $n-m-1\leqslant t\leqslant n-2$. Cela conduit à
    \[ \mathrm{FS}(4,n,n-m-1) < \mathrm{FS}(4,n,n-m) < \cdots\cdots < \mathrm{FS}(4,n,n-2) < \mathrm{FS}(4,n,n-1). \]

Il est ainsi prouvé que
\[ \mathrm{FS}(4,n) = \min_{0\leqslant t\leqslant n-1}\mathrm{FS}(4,n,t) = \mathrm{FS}(4,n,n-m-1). \]

Il reste alors à montrer que $\Delta\mathrm{FS}(4,n)=2^m$.

Pour $T_m+2\leqslant n\leqslant T_{m+1}$, alors $T_m+1\leqslant n-1\leqslant T_{m+1}-1$. On en déduit que
\[ \mathrm{FS}(4,n)=\mathrm{FS}(4,n,n-m-1)\quad\text{ et }\quad\mathrm{FS}(4,n-1)=\mathrm{FS}(4,n-1,n-m-2). \]
Donc
\[ \Delta\mathrm{FS}(4,n) \begin{array}[t]{l} = \mathrm{FS}(4,n)-\mathrm{FS}(4,n-1) \\ = \mathrm{FS}(4,n,n-m-1)-\mathrm{FS}(4,n-1,n-m-2) \\ = (2\mathrm{FS}(4,n-m-1)+\mathrm{FS}(3,m+1))-(2\mathrm{FS}(4,n-m-2)+\mathrm{FS}(3,m+1)) \\ = 2(\mathrm{FS}(4,n-m-1)-\mathrm{FS}(4,n-m-2)) \\ = 2\Delta\mathrm{FS}(4,n-m-1). \\ \end{array} \]
Comme $T_{m}+2\leqslant n\leqslant T_{m+1}$, on en déduit que
\[ T_{m-1}+1 = T_m-m+1 \leqslant n-m-1\leqslant T_{m+1}-(m+1) = T_m \]
et donc $\Delta\mathrm{FS}(4,n-m-1)=2^{m-1}$ par hypothèse de récurrence. Il suit que
\[ \Delta\mathrm{FS}(4,n) = 2\Delta\mathrm{FS}(4,n-m-1) = 2^m \]
dans ce cas.

Pour $n=T_m+1$, on a
\[ \mathrm{FS}(4,n) = \mathrm{FS}(4,T_m+1) = \mathrm{FS}(4,T_m+1,T_m-m) \]
et
\[ \mathrm{FS}(4,n-1) = \mathrm{FS}(4,T_m) = \mathrm{FS}(4,T_m,T_m-m). \]
Donc
\[ \Delta\mathrm{FS}(4,T_m+1) \begin{array}[t]{l} = \mathrm{FS}(4,T_m+1,T_m-m)-\mathrm{FS}(4,T_m,T_m-m) \\ = (2\mathrm{FS}(4,T_m-m)+\mathrm{FS}(3,m+1))-(2\mathrm{FS}(4,T_m-m)+\mathrm{FS}(3,m)) \\ = \mathrm{FS}(3,m+1)-\mathrm{FS}(3,m) \\ = (2^{m+1}-1)-(2^m-1) = 2^{m+1}-2^m = 2^m. \\ \end{array} \]
Cela conclut la preuve.

On obtient alors la valeur exacte de $\mathrm{FS}(4,n)$.

Soit $n\geqslant 2$ un entier et soit $m$ l’entier tel que
\[ T_m+1 \leqslant n \leqslant T_{m+1}. \]
Alors
\[ \mathrm{FS}(4,n) = (n-1-T_{m-1})2^m+1. \]

Preuve

Pour $n=2$ ou $3$, on a $m=1$ puisque $T_1+1=2$ et $T_2=1+2=3$. La formule est alors vérifiée puisque $\mathrm{FS}(4,2)=3=(2-1-T_0)2^1+1$ et $\mathrm{FS}(4,3)=5=(3-1-T_0)2^1+1$.

Supposons maintenant que la formule soit vraie pour tout entier compris entre $2$ et $n-1$ et montrons la pour $n$. Tout d’abord, on sait que
\[ \mathrm{FS}(4,n) = \mathrm{FS}(4,n,n-(m+1)) = 2\mathrm{FS}(4,n-(m+1)) + \mathrm{FS}(3,m+1). \]

Distinguons deux cas suivant la valeur de $n$.

  • Pour $T_m+2\leqslant n\leqslant T_{m+1}$, alors
    \[ T_{m-1}+1 = T_m-m+1 \leqslant n-(m+1) \leqslant T_{m+1}-(m+1) = T_m. \]
    Par hypothèse de récurrence, on a donc
    \[ \mathrm{FS}(4,n-(m+1)) \begin{array}[t]{l} = (n-(m+1)-1-T_{m-2})2^{m-1}+1 \\ = (n-(T_{m-2}+(m-1))-3)2^{m-1}+1 \\ = (n-T_{m-1}-3)2^{m-1}+1. \\ \end{array} \]
    De plus, comme $\mathrm{FS}(3,m+1)=2^{m+1}-1$, on obtient
    \[ \mathrm{FS}(4,n) = (n-T_{m-1}-3)2^{m}+2+2^{m+1}-1 = (n-T_{m-1}-1)2^{m}+1. \]
  • Pour $n=T_m+1$, alors
    \[ n-(m+1) = T_m-m = T_{m-1}. \]
    Par hypothèse de récurrence, on a donc
    \[ \mathrm{FS}(4,n-(m+1)) \begin{array}[t]{l} = \mathrm{FS}(4,T_{m-1}) \\ = (T_{m-1}-1-T_{m-3})2^{m-2}+1 \\ = (2m-4)2^{m-2}+1 \\ = (m-2)2^{m-1}+1. \\ \end{array} \]
    On obtient
    \[ \mathrm{FS}(4,T_m+1) = (m-2)2^{m}+2+2^{m+1}-1 = m2^{m}+1 = ((T_m+1)-1-T_{m-1})2^m+1. \]
    Ce qui conclut la preuve.

L’algorithme de Frame-Stewart simplifié pour quatre piquets

On obtient ainsi un raffinement sur l’algorithme de Frame-Stewart pour $k=4$.

Soit $n$ un entier strictement positif et soit $m$ l’entier tel que
\[ T_m+1 \leqslant n \leqslant T_{m+1}. \]
Pour déplacer les $n$ disques du piquet $A$ vers le piquet $D$ en utilisant $\mathrm{FS}(4,n)$ mouvements, on procède de la manière suivante :

  • les $n-(m+1)$ plus petits disques sont transférés du piquet $A$ vers le piquet $B$ en utilisant les quatre piquets en $\mathrm{FS}(4,n-(m+1))$ mouvements,
  • les $(m+1)$ plus grands disques sont déplacés du piquet $A$ au piquet $D$ en n’utilisant que les piquets $A$, $C$ et $D$ en $\mathrm{FS}(3,m+1)=2^{m+1}-1$ mouvements,
  • les $n-(m+1)$ plus petits disques sont transférés du piquet $B$ vers le piquet $D$ en utilisant les quatre piquets en $\mathrm{FS}(4,n-(m+1))$ mouvements.

Par exemple, pour $n=8$ (le cas représenté dans le dessin du livre de Dudeney), on obtient $m=3$ car
\[ T_3+1=7\leqslant 8\leqslant 10=T_4. \]
On en déduit que l’on peut transférer $8$ disques d’un piquet $A$ à un piquet $D$ en effectuant les $\mathrm{FS}(4,8)=(8-1-T_2)2^{3}+1=4\times 8+1=33$ mouvements suivants :

  • on déplace les $n-(m+1)=4$ plus petits disques du piquet $A$ au piquet $C$ en utilisant les quatre piquets en $\mathrm{FS}(4,4)=9$ mouvements,
  • on déplace les $m+1=4$ plus grands disques du piquet $A$ au piquet $D$ sans utiliser le piquet $C$ en $\mathrm{FS}(3,4)=2^4-1=15$ mouvements,
  • on déplace les $4$ plus petits disques du piquet $C$ au piquet $D$ en utilisant les quatre piquets en $\mathrm{FS}(4,4)=9$ mouvements.

Comme $T_2+1=4\leqslant T_3=6$, on déplace les $4$ disques d’un piquet à un autre en utilisant les quatre piquets en déplaçant $4-3=1$ disque d’un piquet à un autre, puis les $3$ autres disques en utilisant les trois piquets restants en $2^3-1=7$ mouvements et enfin en déplaçant à nouveau le plus petit disque du début.

Ainsi, en utilisant les quatre piquets, on déplace les $8$ disques en $33$ mouvements comme illustré ci-dessous, où le disque qui vient d’être déplacé est en rouge et les disques d’un piquet qui sont immobilisés sont en bleu.

Pour celles et ceux qui veulent s’aventurer hors des pistes ...

Cela conclut cette présentation des tours de Hanoï et de la conjecture de Frame et Stewart. Pour les lecteurs désireux d’en savoir plus et qui n’ont pas peur de s’aventurer sur des pistes noires ou du hors-piste, je ne peux que vous conseiller le très bon livre de Hinz, Klavžar, Milutinović et Petr sur le sujet [7].

Post-scriptum :

L’auteur et la rédaction d’Images des Mathématiques remercient le relecteur Daniel Massart pour sa relecture attentive et ses commentaires avisés.

Article édité par Shalom Eliahou

Notes

[2Henry E. Dudeney, The Reve’s Puzzle, The Canterbury Puzzles (and Other Curious Problems), Thomas Nelson and Sons, Ltd., London, 1907.

[3Bonnie M. Stewart, Advanced problem 3918, Amer. Math. Monthly 39 (1939), p. 363.

[4Bonnie M. Stewart, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941), p. 217–219.

[5James S. Frame, Solution to advanced problem 3918, Amer. Math. Monthly 48 (1941), p. 216–217.

[6Thierry Bousch, La quatrième tour de Hanoï, Bull. Belg. Math. Soc. Simon Stevin 21 (2014), p. 895-912.

Partager cet article

Pour citer cet article :

Jonathan Chappelon — «Les tours de Hanoï II : le problème avec quatre piquets et plus» — Images des Mathématiques, CNRS, 2016

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM