Les tours de Hanoï

Mathématiques — 1re spécialité · Suites récurrentes
ChercherModéliserCalculerRaisonnerCommuniquer
⌂ Accueil webclasse.fr

1Introduction au problème

Objectif : comprendre et appliquer les notions de suite et de récurrence à travers le problème des tours de Hanoï.

Règles du jeu

  1. On dispose de trois tiges et d’un certain nombre de disques de tailles différentes.
  2. Au départ, les disques sont empilés sur la première tige par ordre décroissant de taille.
  3. Le but est de déplacer tous les disques de la tige 1 vers la tige 3, en utilisant la tige 2 comme intermédiaire.
  4. On ne peut déplacer qu’un seul disque à la fois.
  5. Un disque ne peut être posé que sur un disque plus grand ou sur une tige vide.

▶Le plateau de jeu

Cliquez sur une tige pour saisir le disque du dessus, puis sur la tige d’arrivée pour le poser. Au clavier : 1 2 3.

Coups : 0
Choisissez un nombre de disques et commencez !

2Observations et hypothèse

On note n le nombre total de disques. Au départ, tous les disques sont sur la tige de gauche.

a. Pour n = 1 et n = 2, déterminer le nombre minimal de coups permettant de déplacer les disques de la tige 1 à la tige 3.
Coup de pouce
Testez sur le plateau ci-dessus avec 1 puis 2 disques. Avec 2 disques, il faut d’abord « libérer » le grand disque.
b. Pour n = 3, compléter le nombre de coups nécessaires pour passer d’une étape à l’autre.
Coup de pouce
Pour amener les deux petits disques sur la tige 2, c’est exactement le problème à 2 disques… mais vers une autre tige !
c. Expérimentation : pour n = 4, déterminer le nombre minimal de coups en utilisant le plateau (ou vos propres tours de Hanoï, voir l’annexe A).
Coup de pouce
Même stratégie qu’en b : déplacer les 3 disques du dessus vers la tige 2, puis le grand disque, puis les 3 disques par-dessus.

3Analyse et généralisation

Pour n ≥ 1, on note dn le nombre minimal de déplacements pour déplacer n disques. Compléter la formule de récurrence :

dn+1 = × dn +
Coup de pouce
Pour déplacer n+1 disques, il faut obligatoirement, à un moment, déplacer le plus grand. Que doit-il y avoir sur les autres tiges à ce moment-là ?
Pourquoi ? Pour déplacer n+1 disques de la tige 1 vers la tige 3 :
  1. on déplace les n disques du dessus vers la tige 2 : dn coups ;
  2. on déplace le plus grand disque vers la tige 3 : 1 coup ;
  3. on replace les n disques par-dessus, sur la tige 3 : dn coups.
Au total : dn+1 = dn + 1 + dn = 2dn + 1, avec d1 = 1.

4Application de la formule

Utiliser la formule pour calculer le nombre minimal de déplacements pour 5, 6 et 7 disques.

n1234567
dn1………

Les valeurs de d2, d3, d4 s’affichent quand les questions 2 sont réussies.

Pour aller plus loin : on ajoute 1 à chaque terme de la suite, c’est-à-dire qu’on observe les nombres d1 + 1, d2 + 1, d3 + 1, … (et non dn+1). Quelle formule explicite peut-on conjecturer pour dn ?
Les valeurs 2, 4, 8, 16, 32… de dn + 1 sont les puissances de 2. En effet dn+1 + 1 = 2(dn + 1) : la suite (dn + 1) est géométrique de raison 2 et de premier terme 2, d’où dn = 2n − 1. Avec 64 disques (la légende du temple de Bénarès), à un disque par seconde, il faudrait environ 585 milliards d’années !

5Faire calculer par un script Python

Compléter le script ci-dessous pour qu’il calcule dn quelle que soit la valeur de n (on pourra s’inspirer de l’activité « Modéliser l’évolution d’une épidémie à l’aide d’une suite »).

n = int(input("Nombre de disques : "))
d =             # valeur de d_1
for k in range(1, n):
    d =    # calcul de d_(k+1) à partir de d_k
print("d_n =", d)
Coup de pouce
La variable d contient le terme courant ; la nouvelle valeur s’obtient avec la formule de récurrence de la question 3 (en Python, le produit s’écrit *).

AAnnexe A — Fabriquer ses tours de Hanoï (impression 3D)

Les deux pièces ont été modélisées avec OpenSCAD. Vous pouvez télécharger directement les fichiers .stl à imprimer, ou les scripts .scad pour les modifier (nombre de disques, rayons, hauteur des tiges…).

Le socle et les trois tigesbase

Socle de 102 × 34 × 4 mm (enveloppe convexe de trois cylindres de rayon 17 mm), tiges de rayon 2 mm et de hauteur 30 mm, espacées de 34 mm.


      

      

        
Les six disquesdisques

        
Six disques de 4 mm d’épaisseur, de rayons 15, 13, 11, 9, 7 et 5 mm, percés d’un trou de rayon 2,5 mm (jeu de 0,5 mm autour des tiges).

        

          
          
          
        

        

      

    

  


  
  

    
BAnnexe B — Une solution récursive en Python

    
La fonction hanoi ci-dessous ne compte pas les coups : elle affiche la liste des déplacements à effectuer.
      Elle traduit exactement le raisonnement de la question 3 : pour déplacer n disques de depart vers arrive,

    
    
      
  1. on déplace les n − 1 disques du dessus vers la tige intermediaire (appel récursif) ;
    2. 
      
  2. on déplace le plus grand disque de depart vers arrive (le print) ;
    3. 
      
  3. on déplace les n − 1 disques de intermediaire vers arrive (appel récursif).
    4. 
    

    
Une fonction qui s’appelle elle-même est dite récursive. Le cas n = 0 (rien à faire) arrête les appels.

    
def hanoi(nombre_de_disques,depart="A",intermediaire="B",arrive="C"):
    if (nombre_de_disques > 0):
        hanoi(nombre_de_disques-1,depart,arrive,intermediaire)
        print(depart,"------>",arrive)
        hanoi(nombre_de_disques-1,intermediaire,depart,arrive)

hanoi(5)

    

      
      
    


    
Voir le script en action

    
Les tiges A, B, C correspondent aux tiges 1, 2, 3. Chaque ligne affichée par le script est un déplacement, rejoué sur le plateau.

    

      
      
      
      
    

    

      

        
Coups : 0

      
>>>