The Towers of Hanoi





Le problème des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de «départ» à une tour d'«arrivée» en passant par une tour «intermédiaire» et ceci en un minimum de coups, tout en respectant les règles suivantes: on ne peut déplacer plus d'un disque à la fois, et on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.


Résoudre le problème de la Tour de Hanoï à trois disques est une tâche facile pour un adulte. On identifie assez aisément que le premier sous-but consiste à placer le grand disque à droite. Pour cela, l’emplacement de droite doit être libre et les deux autres disques doivent être sur l’emplacement du milieu. Il faut donc commencer par mettre le petit disque à droite, ensuite le disque moyen au centre et enfin le petit disque au centre. Pour parvenir à ce premier sous but, une planification n’est pas nécessaire, il n’est même pas besoin d’un raisonnement explicite, une simple anticipation perceptive suffit, d’autant que le nombre d’action à anticiper ne dépasse pas les capacités de la mémoire de travail.
  • Pour 3 disques, leurs déplacements sont faisables au minimum en 7 coups.
  • Pour 4 disques, leurs déplacements sont faisables au minimum en 15 coups.
  • Pour 5 disques, leurs déplacements sont faisables au minimum en 31 coups.
  • Pour 6 disques, leurs déplacements sont faisables au minimum en 63 coups.
  • Pour 7 disques, leurs déplacements sont faisables au minimum en 127 coups.
  • Pour 8 disques, leurs déplacements sont faisables au minimum en 255 coups.
On voit aisément que la tour de Hanoï peut être résolu en 7 coups, ce que font effectivement la plupart des adultes et leur donne le sentiment que cette situation n’est pas vraiment un problème, tant la procédure est facile à trouver. Il en va tout autrement de la Tour de Hanoï à 5 disques. Pour mettre le disque numéro 4 au milieu, il faut que les disques 3, 2 et 1 soient à droite, ce qui suppose que l’on commence par y mettre le disque 3 et donc que les disques 1 et 2 soient au milieu, ce qui n’est possible que si on a commencé par mettre le disque 1 à droite et le disque 2 au milieu.  

On voit bien que la résolution de ce problème ne peut plus reposer seulement sur une anticipation perceptive et que les capacités de la mémoire de travail vont rapidement se trouver dépassées. Ainsi, pour déplacer le plus grand disque (ce qui constituait le premier sous-but dans la tour à trois disques), il faut construire quatre sous-buts en appliquant à chaque fois la même règle : Pour mettre un disque à un emplacement, il faut que tous les autres disques soient à un emplacement différent de celui où l’on veut mettre le disque. Ce qui constitue la difficulté de la tour de Hanoï à cinq disques, c’est le nombre d’opération de raisonnement nécessaire pour parvenir à identifier les sous buts, autrement dit la complexité de la stratégie à mettre en œuvre.


Raisonnement mathématique par tâtonnements :

Désignons la suite Tn le nombre minimal de déplacement nécessaire pour bouger une tour de Hanoï de taille n d'un axe à un autre.

Si la tour n'est composée d'aucun disque, il nous faudra aucun mouvement pour la déplacer. Donc T0=0.

Si la tour est composée d'un seul disque, il nous faudra un coup au minimum pour la déplacer. Donc T1=1.

On a T0, on a T1. Il est donc temps de généraliser à n'importe quel n ! Passons donc à Tn.
Une stratégie possible pour déplacer une tour de taille n, c'est de d'abord déplacer les n-1 plus petits disques sur le deuxième axe, de déplacer le plus grand des disques sur le troisième axe, puis de déplacer la tour du deuxième axe sur le grand disque, sur l'axe 3.


Dans le cas n=2, par exemple : on déplace le petit disque sur l'axe 2 (1 coup), on déplace le grand disque sur l'axe 3 (2 coups) puis on déplace le petit disque sur l'axe 3 (3 coups). Donc T2≤3 ! (On met le signe ≤ car on n'est pas encore certains qu'il n'y a pas une solution plus rapide)

Dans le cas n=3 : on déplace les deux plus petits disques sur l'axe 2 (3 coups), on déplace le grand disque sur l'axe 3 (4 coups) puis on déplace les deux disques de l'axe 2 sur l'axe 3 (7 coups). Donc T3≤7.

Dans le cas général, avec notre stratégie : on déplace les n-1 plus petits disques sur l'axe 2 (Tn-1 coups), on déplace le grand disque sur l'axe 3 (Tn-1 +1 coups) puis on déplace les n-1 plus petits disques sur l'axe 3 (2.Tn-1+1 coups).
On a alors la formule générale : Tn≤2.Tn-1 +1 (Formule qui permet de majorer le nombre minimal de coup)
Est-il possible de le faire en moins de coups ? Et bien, malheureusement, non ! En effet, il faut à un moment ou à un autre déplacer le plus grand des disques, et on ne peut le déplacer que si tous les disques sont bien rangés en position centrale (sinon, il faudrait mettre le grand disque sur un plus petit). Il faudra donc T_n-1 déplacements pour mettre les n-1 plus petits disques au milieu, 1 déplacement de plus pour déplacer le grand disque, et redéplacer la tour centrale sur le grand disque en T_n-1 déplacements. Moralité : Le nombre minimal de mouvement Tn est plus grand que 2.Tn-1 +1.
On en conclut :
Cette relation permet de calculer Tn seulement si on connaît la valeur de Tn+1. Puisque l'on connaît T_0, on peut calculer n'importe quel Tn. Une formule de ce genre est appelée "relation de récurrence".

Pour connaitre le nombre de mouvements nécessaires aux prêtres pour bouger la Tour de Hanoï, il ne reste plus qu'à calculer T64 !
T0 = 0
T1 = 2×0 + 1 = 1
T2 = 2×1 + 1 = 3
T3 = 2×3 + 1 = 7
T4 = 2×7 + 1 = 15
T5 = 2×15 + 1 = 31
T6 = 2×31 + 1 = 63
T7 = 2×63 + 1 = 127
T8 = 2×127 + 1 = 255 (Il faut 255 coups pour déplacer la tour de Hanoï!)
Article plus récent Article plus ancien Accueil