Exercice corrigé Ancien programme

Les tours de hanoï

On dispose de trois piquets sur un socle et de n disques de tailles deux à deux différentes, troués en leur centre.

Les n disques sont empilés sur le piquet A. Le but du jeu est de les faire passer sur le piquet C en respectant les règles suivantes :

  •  on ne déplace qu'un disque à la fois 
  •  un disque ne peut être mis que sur l'un des trois piquets 
  •  un disque ne peut jamais être mis par-dessus un disque de taille plus petit.

Exemple : Avec cinq disques

On note le nombre de déplacements pour réussir.

Le mouvement d'un disque situé en haut de la pile A déplacé en haut de la pile du piquet B sera noté .

Partie A

1. Préciser les valeurs de , , , en détaillant les déplacements effectués.

2. Montrer que pour déplacer les n disques, il faut nécessairement que tous les disques soient empilés sur le piquet B sauf le plus grand qu'on va pouvoir passer du piquet A au piquet C.

3. En déduire que .

4. En déduire puis .

Partie B

1. Soit la suite définie pour tout n entier par .

Montrer que est une suite géométrique, en préciser la raison et le premier terme.

2. en fonction de n.

b. En déduire en fonction de n.

3. Combien de disques doivent être utilisés pour que le nombre de déplacements dépasse 1 milliard ?

  •  La relation de la question A. 3. montre que est une suite arithmético-géométrique. La partie B fait étudier cette suite. Voir le savoir-faire 7 si nécessaire.
  •  Dans la dernière question de la partie B, il s'agit de résoudre l'inéquation .

Les tours de Hanoï

1. Avec un seul disque, il n'y a qu'un seul déplacement : .

Avec deux disques, on effectue les mouvements : , et .

On a donc .

Avec trois disques, on effectue les mouvements : , , , , et . On a donc .

2. Le plus grand disque doit être déplacé sur le piquet C alors que celui-ci est vide. Avant cela, il faut qu'il soit seul sur le piquet A, les autres ayant été déplacés ailleurs. Le seul piquet où mettre ces autres disques est le piquet B.

3. Pour déplacer disques, il faut d'abord déplacer n disques du piquet A au piquet B : le nombre de mouvements pour effectuer cette opération est un. Ensuite, on déplace le grand disque du piquet A au piquet C, ce qui ajoute un mouvement supplémentaire au décompte total. Enfin, on déplace les n disques du piquet B au piquet C, ce qui ajoute encore déplacements.

Au total, on a : .

4. À l'aide de cette relation de récurrence, on obtient : .

Puis : .

1. .

est une suite géométrique de raison 2, de premier terme .

2. a. Pour tout n entier positif non nul, .

b. .

3. .

À l'aide de la calculatrice, on obtient : , mais .

Avec 30 disques, le nombre de déplacements dépasse un milliard.

Accéder à tous les contenus
dès 6,79€/mois

  • Les dernières annales corrigées et expliquées
  • Des fiches de cours et cours vidéo/audio
  • Des conseils et méthodes pour réussir ses examens
  • Pas de publicités
S'abonner