La tour de Hanoï
Le mathématicien français Édouard Lucas (1842-1891)
a inventé un jeu de réflexion mathématique appelé
la tour de Hanoï. Ce jeu utilise trois tiges T₁, T₂ et T3
ainsi que des disques percés de diamètres distincts
deux à deux.
Au début du jeu, les disques sont tous empilés sur T,
dans l'ordre décroissant de leur diamètre, le plus grand
disque reposant à la base.
T₁
T₂
T3
Le but du jeu est de déplacer la « tour » de disques de
T₁ à T3, en respectant les deux règles suivantes :
- on ne déplace qu'un seul disque à la fois, d'une tige
à une autre;
- un disque ne doit jamais être placé au-dessus d'un
disque de diamètre inférieur au sien.
Pour tout entier /> 1, on note L, le nombre minimal
de déplacements nécessaires pour transporter une
tour de n disques d'une tige à une autre.
1. Déterminer L, et L₂.
2. En remarquant que pour pouvoir déplacer le plus
grand disque de T, à T3, il faut d'abord avoir déplacé
la tour des autres disques de T₁ à T₂, montrer que pour
tout entier /> 1, L + 1 = L₂ + 1 + Lµ•
3. Déterminer le nombre de disques nécessaires pour
que ce jeu dure au moins une heure à raison d'un dépla-
cement de disque par seconde.
4. a. Peut-on transporter une tour de trois disques de
T₁ à T3 en moins de sept déplacements? Expliquer.
b. Compléter la liste de sept déplacements ci-dessous
permettant de transporter une tour de trois disques
de T₁ à T3.
• 1er déplacement: petit disque de T, en T3.
• 2e déplacement: moyen disque de T, en T₂.
• 3e déplacement : petit disque de T3 en T₂.
• 4e déplacement: grand disque de ... en ...
• 5e déplacement: ...
• 6e déplacement:...
.
• 7e déplacement: ...