Les tours de Hanoï

De 1 à 8 disques à transporter d'une tour à une autre, avec 3, 4 ou 5 tours. Avec trois tours, le minimum est $2^n - 1$ coups ; une tour de plus, et la question devient un problème de recherche.

On transporte une pile de $n$ disques, de $1$ à $8$, de la première tour à la dernière, un disque à la fois et sans jamais poser un disque sur un plus petit ; le jeu se joue avec $3$, $4$ ou $5$ tours. La page compte les coups, indique le minimum depuis le départ et depuis la position courante, et peut jouer un coup ou montrer une solution.

Ce que cela signifie : avec trois tours, le nombre minimal $T(n)$ de coups vérifie $T(n) = 2T(n-1) + 1$ et $T(1) = 1$, donc $T(n) = 2^n - 1$, soit $255$ coups pour huit disques. La majoration vient d'une stratégie (déplacer $n-1$ disques, puis le grand, puis les $n-1$ disques) ; la minoration vient de ce que, au premier et au dernier déplacement du grand disque, les $n-1$ autres sont empilés sur une seule tour. Avec quatre tours, les minimums sont $1, 3, 5, 9, 13, 17, 25, 33$ pour un à huit disques ; l'optimalité de la stratégie de Frame et Stewart n'a été démontrée qu'en 2014 par Thierry Bousch, et la question reste ouverte pour cinq tours et plus. Les nombres affichés viennent d'un parcours de toutes les positions, au plus $5^8 = 390\,625$.

Le piège le plus courant est de confondre « j'ai une solution en $2^n - 1$ coups » avec « $2^n - 1$ est le minimum » : une stratégie ne donne qu'une majoration, et il faut un second raisonnement pour la minoration.