Étudier la tour de HanoïProblème

La tour de Hanoï est un problème de mathématique très classique. 

On considère trois tours notés T_1T_2 et T_3

Sur la tour T_1, on place n disques de tailles différentes de telle sorte qu'un disque est toujours positionné sur un disque plus grand. 

L'objectif du jeu est de déplacer la pile de disques sur la tour T_3 en suivant les règles suivantes : 

  • On ne peut déplacer qu'un disque à la fois.
  • On ne peut poser un disque que sur un disque plus grand ou sur la base. 

 

La figure suivante montre comment gagner en faisant de le moins de mouvements possible dans le cas où n=3

On souhaite trouver une formule donnant le nombre de coups minimal nécessaire pour déplacer une tour de n disques. 

On note cette suite (M_n).

-

Dans le cas où n=1, combien faut-il de mouvements pour déplacer la tour ? 

Dans le cas où n=2, combien faut-il de mouvements pour déplacer la tour ? 

Quelle formule peut-on conjecturer pour (M_n) ? 

Soit n \in \mathbb{N}

On suppose que, pour une tour à n disques, le nombre minimum de coups pour réussir est M_n = 2^n−1

Quelle relation existe entre M_{n+1} et M_{n} ?