178
4 Approche combinatoire
2. Montrer que la solution de la récurrence peut s’écrire comme
x n =
L
j =1
ν j t 2 j −1 +
L−1
j =0
t n j ;
où ν j est donné dans la proposition 4.11, et où les n j sont définis à partir de la représentation
binaire de n : si (n) 2 = 1b L−1 b L−2 . . . b 0 , alors n j = 1b j 1 . . . b 0 .
3. Montrer que t n peut aussi s’écrire
log 2 n +
1
n
(2 + +log 2 n − 2
log 2 n ),
et se servir de cette expression pour donner une expression de x n .
4. Étudier chacune des deux sommes composant l’expression de x n obtenue à la question
précédente, et conclure.
(Comme précédemment, on pourra se reporter à l’article de Hwang et Steyaert[138].)
Problème 4.19. (Codage des tours de Hanoï par des arbres 2–3) Le problème des tours de
Hanoï consiste à déplacer une pile de h disques d’une position (nous l’appellerons gauche) à une
autre position (droite) (cf. la figure 4.16) respectant les règles suivantes :
(a) un seul disque est déplacé à chaque mouvement ;
(b) au départ, les disques sont numérotés de 1 à h, en ordre croissant de haut en bas (le disque
numéroté 1 est en haut, celui numéroté h est en bas) ;
(c) à aucun moment, un disque ne doit se trouver sur un disque de plus petit numéro.
On appelle suite de résolution une suite de mouvements permettant de déplacer une pile de h
disques de la position gauche à la position droite, en respectant les contraintes ci-dessus.
1. Le déplacement d’un seul disque de la position de gauche vers celle de droite est codé par une
feuille, où le nombre de clés (1 ou 2) indique combien de mouvements ont été utilisés pour
déplacer le disque. Étendre ceci récursivement pour obtenir, en partant d’un arbre 2–3 τ donné
dans la figure 4.17 de hauteur h = 2, une suite σ (τ ) encodant une suite de mouvements pour
résoudre le problème de Hanoï avec 3 disques.
2. Généraliser l’approche de la question précédente pour obtenir un codage par un arbre 2–3 de
hauteur h d’une suite de mouvements de disques déplaçant une tour de hauteur h + 1, sans
repasser par la même configuration des disques.
3. Montrer que le parcours préfixe d’un arbre 2–3 τ fournit une suite σ (τ ) de résolution sans
répétitions ; puis expliciter la bijection réciproque, faisant passer d’une suite de résolutions
sans répétitions à un arbre 2–3.
4. En tirant partie du lien entre le nombre de clés dans un arbre τ et la longueur de la suite σ (τ ),
donner la suite de mouvements qui permet de résoudre le problème des tours de Hanoï en un
Fig. 4.16 Les états de départ et d’arrivée des tours de Hanoï, pour 4 disques
4 Approche combinatoire
2. Montrer que la solution de la récurrence peut s’écrire comme
x n =
L
j =1
ν j t 2 j −1 +
L−1
j =0
t n j ;
où ν j est donné dans la proposition 4.11, et où les n j sont définis à partir de la représentation
binaire de n : si (n) 2 = 1b L−1 b L−2 . . . b 0 , alors n j = 1b j 1 . . . b 0 .
3. Montrer que t n peut aussi s’écrire
log 2 n +
1
n
(2 + +log 2 n − 2
log 2 n ),
et se servir de cette expression pour donner une expression de x n .
4. Étudier chacune des deux sommes composant l’expression de x n obtenue à la question
précédente, et conclure.
(Comme précédemment, on pourra se reporter à l’article de Hwang et Steyaert[138].)
Problème 4.19. (Codage des tours de Hanoï par des arbres 2–3) Le problème des tours de
Hanoï consiste à déplacer une pile de h disques d’une position (nous l’appellerons gauche) à une
autre position (droite) (cf. la figure 4.16) respectant les règles suivantes :
(a) un seul disque est déplacé à chaque mouvement ;
(b) au départ, les disques sont numérotés de 1 à h, en ordre croissant de haut en bas (le disque
numéroté 1 est en haut, celui numéroté h est en bas) ;
(c) à aucun moment, un disque ne doit se trouver sur un disque de plus petit numéro.
On appelle suite de résolution une suite de mouvements permettant de déplacer une pile de h
disques de la position gauche à la position droite, en respectant les contraintes ci-dessus.
1. Le déplacement d’un seul disque de la position de gauche vers celle de droite est codé par une
feuille, où le nombre de clés (1 ou 2) indique combien de mouvements ont été utilisés pour
déplacer le disque. Étendre ceci récursivement pour obtenir, en partant d’un arbre 2–3 τ donné
dans la figure 4.17 de hauteur h = 2, une suite σ (τ ) encodant une suite de mouvements pour
résoudre le problème de Hanoï avec 3 disques.
2. Généraliser l’approche de la question précédente pour obtenir un codage par un arbre 2–3 de
hauteur h d’une suite de mouvements de disques déplaçant une tour de hauteur h + 1, sans
repasser par la même configuration des disques.
3. Montrer que le parcours préfixe d’un arbre 2–3 τ fournit une suite σ (τ ) de résolution sans
répétitions ; puis expliciter la bijection réciproque, faisant passer d’une suite de résolutions
sans répétitions à un arbre 2–3.
4. En tirant partie du lien entre le nombre de clés dans un arbre τ et la longueur de la suite σ (τ ),
donner la suite de mouvements qui permet de résoudre le problème des tours de Hanoï en un
Fig. 4.16 Les états de départ et d’arrivée des tours de Hanoï, pour 4 disques