Accueil du site > Actualité de la recherche > Actualités scientifiques




Recherchez sur ce site


A l’occasion d’un article dans "La Recherche" sur un résultat de Thierry Bousch

6 mars 2015

Dans la version "à quatre aiguilles" de la "Tour d’Hanoï", quelle est la meilleure manière de transférer une pile de disques d’une aiguille vers une autre, c’est-à-dire celle qui demande le minimum de mouvements ?

Cette question est abordée dans un court article publié dans le numéro de février 2015 de "La Recherche". A noter, on trouvera dans le même numéro un article de notre collègue Nicolas Bergeron "Comprendre les espaces de dimension 3". Mais revenons plus en détail sur le travail de Thierry Bousch à propos de la quatrième tour d’Hanoï…

- La "Tour d’Hanoï" est un casse-tête classique, inventé en 1883 par le mathématicien français Edouard Lucas (1842-1891) : on dispose d’un plateau muni de trois aiguilles, et de N disques percés en leur centre, de diamètres tous différents, enfilés initialement sur une des aiguilles par taille décroissante. L’objectif est de transférer tous les disques sur une autre aiguille, en respectant deux règles :

(1) ne déplacer qu’un disque à la fois, d’une aiguille vers une autre,

(2) ne jamais poser un disque sur un disque plus petit.

On voit facilement, en raisonnant par récurrence sur le nombre de disques, que le problème admet toujours une solution, avec 2^N-1 mouvements de disques, et que ce nombre est optimal : il est impossible de faire moins. En outre, la solution optimale est unique (si on fixe les colonnes de départ et d’arrivée). Tous ces résultats sont faciles, et étaient connus de Lucas dès la création du jeu.

- Au début du vingtième siècle, le puzzliste anglais Henry Ernest Dudeney (1857-1930) propose de résoudre le problème analogue avec quatre aiguilles au lieu de trois : quel est alors le nombre minimum de mouvements pour transférer N disques d’une colonne vers une autre ? C’est le "Problème du Bailli" ("The Reve’s Puzzle").

Comme solution, Dudeney propose la procédure suivante (récursive sur N) :

(0) Choisir un entier naturel M<N (on verra comment).

(1) Transférer les M plus petits disques vers une aiguille intermédiaire (autre que celles de départ et d’arrivée).

(2) Transférer les N-M disques restants vers l’aiguille d’arrivée, sans utiliser l’aiguille intermédiaire.

(3) Transférer les M plus petits disques de l’aiguille intermédiaire vers l’aiguille d’arrivée.

Cette procédure permet de transférer N disques en \Phi(N) mouvements, où la fonction \Phi est définie par l’équation récursive \Phi(N) = \min_{M<N} 2\Phi(M)+2^{N-M}-1 pour N>0 (et \Phi(0)=0). L’entier M doit bien sûr être choisi de manière à réaliser le minimum dans l’expression précédente. Cette formule permet de calculer \Phi numériquement, et Dudeney observe expérimentalement le rôle particulier que jouent les nombres triangulaires, c.à.d. de la forme p(p+1)/2, dans le problème du bailli : si N est un nombre triangulaire, M doit être le nombre triangulaire immédiatement inférieur.

- En 1941, J.S.Frame et B.M.Stewart donnent une formule close pour \Phi, tout en étendant le problème de Dudeney, et sa solution récursive, à un nombre quelconque d’aiguilles. Pour quatre aiguilles, leur formule s’écrit \Phi(N)=2^{\nabla 0}+2^{\nabla 1}+\cdots+2^{\nabla(N-1)}, où \nabla n désigne la "racine triangulaire" de n, c’est-à-dire le plus grand entier p tel que p(p+1)/2\le n. Pour cinq aiguilles et plus, on a une formule similaire, avec les nombres triangulaires remplacés par les nombres tétraédriques p(p+1) (p+2)/3!, et ainsi de suite.

Cependant, leur étude ne concerne qu’une classe particulière de solutions au problème de Dudeney (généralisé à un nombre quelconque d’aiguilles), qui ont une belle structure récursive. Or, rien ne permet d’affirmer que les solutions optimales font partie de cette classe. Cette difficulté a été soulignée dès la publication de leurs articles, en 1941. Par conséquent, on ne sait pas - et on ne sait toujours pas, aujourd’hui en 2015 - s’il est possible de transférer une pile de disques d’une aiguille vers une autre avec un nombre de mouvements strictement inférieur à ce que donne la formule de Frame-Stewart.

- La contribution de Thierry Bousch au sujet a été de résoudre le problème avec quatre aiguilles, c.à.d. le problème original de Dudeney, le "problème du bailli" : il a montré qu’il est impossible de transférer N disques d’une aiguille vers une autre en strictement moins que \Phi(N) mouvements.

- Son approche a été d’étudier l’optimalité "locale" de la procédure récursive de Dudeney, i.e. son optimalité vis-à-vis de "petites" perturbations : au lieu de transférer tous les M plus petits disques vers une colonne intermédiaire, pourrait-on n’en transférer qu’une partie ? Ce serait peut-être plus économique, en nombre de mouvements. C’est vrai, mais uniquement pour ce qui concerne la construction de la mini-tour intermédiaire (ou son démantèlement, à la fin) ; car l’objectif de grouper tous les petits disques dans une mini-tour est de libérer les trois autres colonnes pour le mouvement des grands disques. Si on laisse des petits disques de côté, même en petit nombre, ils gêneront le mouvement des grands disques ; ou plus précisément, ils devront accompagner leur mouvement, ce qui est très coûteux.

Pour savoir lequel de ces deux effets l’emporte sur l’autre, on a besoin de résoudre un problème plus précis que le problème du bailli : on doit être capable de minorer le nombre de mouvements nécessaires pour transférer une pile de disques d’une aiguille vers une autre, avec éventuellement quelques disques mal positionnés au départ ou à l’arrivée. Divers arguments heuristiques donnent une formule conjecturale pour cette minoration. Et c’est cette formule que Thierry Bousch démontre, par récurrence sur le nombre de disques.

- Le problème du bailli pourra paraître anecdotique, mais c’est un cas particulier d’un problème très général et important : calculer une distance dans un graphe (ici, le graphe des configurations du jeu). C’est une question difficile, et on a peu de méthodes systématiques, surtout pour minorer les distances. Comme le montre le problème du bailli, c’est difficile même pour des graphes hautement structurés. On le voit également avec les "distances de réarrangement" en génomique, qui sont définies comme des distances dans certains graphes, et ces graphes sont, dans certains cas, extrêmement réguliers : des graphes de Cayley dans certains groupes finis. Pourtant, même dans ces cas, le calcul des distances peut être très difficile (voire impossible), et beaucoup de questions sont ouvertes dans ce sujet.

Références : T. Bousch, Bull. Belg. Math. Soc. Simon Stevin, 21 (2014), p. 895-912.

Contact : Thierry Bousch | UMR 8628 | Thierry.Bousch math.u-psud.fr