La quatrième Tour de Hanoï : Thierry Boush

Les Tours de Hanoï est un jeu de réflexion inventé par le mathématicien amiénois spécialiste des jeux Edouard Lucas. Ce jeu consiste dans sa version originale à déplacer des disques circulaires de tailles décroissantes d’un aiguille à une autre sur un plateau constitué de trois aiguilles.

Voici une illustration de ce jeu :

OLYMPUS DIGITAL CAMERA

Et une version animé :

Tower_of_Hanoi_4

Pour ceux qui souhaite tester en ligne ce jeu, voici une version pour navigateur.

Edouard Lucas avait inventé une histoire assez amusante pour décrire l’origine pseudo asiatique de ce jeu. On retrouve parfois cette légende dans des films de série Z où on nous explique que la fin du monde aura lieu quand la dernière Tour de Hanoï aura été déplacée… Voici un extrait du texte de Lucas (source Wikipédia ) :

Sous le titre « Les brahmes tombent », Lucas relate que « N. Claus de Siam a vu, dans ses voyages pour la publication des écrits de l’illustre Fer-Fer-Tam-Tam, dans le grand temple de Bénarès, au-dessous du dôme qui marque le centre du monde, trois aiguilles de diamant, plantées dans une dalle d’airain, hautes d’une coudée et grosses comme le corps d’une abeille. Sur une de ces aiguilles, Dieu enfila au commencement des siècles, 64 disques d’or pur, le plus large reposant sur l’airain, et les autres, de plus en plus étroits, superposés jusqu’au sommet. C’est la tour sacrée du Brahmâ. Nuit et jour, les prêtres se succèdent sur les marches de l’autel, occupés à transporter la tour de la première aiguille sur la troisième, sans s’écarter des règles fixes que nous venons d’indiquer, et qui ont été imposées par Brahma. Quand tout sera fini, la tour et les brahmes tomberont, et ce sera la fin des mondes ! ».

On démontre facilement par recurrence, dans le cas du jeu classique à trois aiguilles, qu’il y a au minimum besoin de $2^n-1$ déplacements pour réussir ce casse-tête ( n désignant le nombre de disques ). Dans le cas où n=64 on obtient 18 446 744 073 709 551 615 déplacements, ce qui à raison d’un déplacement par seconde laisse 585 milliards d’années avant la fin du monde !

En 1908 Henry Dudeney a proposé une variante des Tours de Hanoï à 4 aiguilles. Dudeney propose même une conjecture quant au nombre minimal de déplacements pour y arriver en fonction du nombre n de disque.

Thierry Boush vient de démontrer cette conjecture en juin 2014 et voici un lien vers cet article passionnant.

Voici ce résultat : le nombre minimal de déplacement pour n disques est donné par la formule suivante :

$2^{\nabla(0)}+2^{\nabla(1)}+2^{\nabla(2)}+...+2^{\nabla(n-1)}$

où $\nabla(p)$ désigne la racine triangulaire de p c’est à dire le plus petit nombre p tel que $p(p+1)/2 \leqslant n$

Comme on sait que $1+2+3+...+p=p(p+1)/2$ on comprend que $\nabla(n)$ correspond au plus petit entier p tel que la somme des p premiers entiers soit inférieure à n.

Par exemple dans le cas de 8 disques le nombre de déplacements est :

$2^0+2^1+2^1+2^2+2^2+2^2+2^3+2^3=33$

A comparer avec le cas classique à trois aiguilles : $2^8-1=255$

1 commentaire

Ciril Petr · mardi 3 mars 2015 à 08:49

Pour savoir plus sur la Tour d’Hanoï, voir The Tower of Hanoi – Myths and Maths by Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, Ciril Petr. Birkhäuser, January 2013, http://tohbook.info/