La tour de Hanoï est un problème de mathématique très classique.
On considère trois tours notés T_1, T_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 ou n=1, il faut un seul mouvement pour déplacer la tour.
En effet, il n'y a qu'un disque à déplacer.
Dans le cas où n=1, il faut un seul mouvement pour déplacer la tour.
Dans le cas où n=2, combien faut-il de mouvements pour déplacer la tour ?
Dans le cas où n=2, il faut 3 mouvements pour déplacer la tour comme l'atteste la figure suivante :
Dans le cas où n=2, il faut 3 mouvements pour déplacer la tour.
Quelle formule peut-on conjecturer pour (M_n) ?
D'après l'énoncé et les questions précédentes, on a :
| n | 1 | 2 | 3 |
| M_n | 1 | 3 | 7 |
On observe les différences :
M_2-M_1 = 2 = 2^1
M_3-M_2 = 4= 2^2
On reconnaît les deux premières puissances de 2.
On peut supposer que M_n est proche de la suite des 2^n.
On a :
2^1 = 2
2^2 = 4
2^3 = 8
Cette suite ressemble à M_n+1.
La suite 2^n-1 semble donc convenir.
En effet :
2^1-1 = 1
2^2 -1= 3
2^3 -1= 7
On retrouve bien les termes connus de (M_n).
D'après les données, on peut donc conjecturer que :
\forall n \in \mathbb{N}, M_n = 2^n -1
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} ?
On considère une pile de n+1 disques.
Afin de déplacer les n premiers disques de la tour T_1 à la tour T_2, d'après l'hypothèse qu'on a émise, il faut M_n= 2^n-1 mouvements.
Il faut ensuite déplacer le dernier disque sur la tour T_3, cela fait un mouvement supplémentaire.
Finalement, il faut déplacer la pile de n disques de la tour T_2 à la tour T_3, ce qui fait encore 2^n-1 mouvements.
Au total, on a :
M_{n+1} = 2^n-1+1+2^n-1
M_{n+1} = 2^n+2^n-1
M_{n+1} = 2^n+2^n-1
M_{n+1} = 2(2^n-1)+1
On identifie M_n et on obtient :
M_{n+1} = 2M_n +1
Si M_n = 2^n-1 pour n \in \mathbb{N}, alors M_{n+1} = 2M_n+1.
Grâce à cette relation, on en déduit que :
Si M_n = 2^n-1 pour n \in \mathbb{N} alors M_{n+1} =2^{n+1}-1.
Autrement dit, on vient de montrer l'hérédité de notre hypothèse :
\forall n \in \mathbb{N}, M_n = 2^n -1
Or, on a montré que cette hypothèse est vraie au rang 1.
Donc l'hypothèse qu'on a émise est vraie.
On a ainsi montré par récurrence que :
\forall n \in \mathbb{N}, M_n = 2^n -1