Comment résoudre la légende des Tours de Hanoï à l'aide des suites ? - Grand oral

Thèmes abordés

Légende des Tours de Hanoï, mathématiques, suite, grand oral, méthode récursive, raisonnement par récurrence, algorithme, double disque, algorithmes exponentiels

Résumé du document

Le problème des Tours de Hanoï consiste à déplacer une tour de disques d'une tige à une autre, en utilisant une tige supplémentaire comme intermédiaire, tout en respectant deux règles simples : on ne peut déplacer qu'un seul disque à la fois, et on ne peut jamais placer un disque plus grand sur un disque plus petit. Ce problème revêt une grande importance dans le domaine des mathématiques ainsi que dans l'informatique, où il est utilisé pour illustrer des concepts tels que la récursivité, la complexité algorithmique et l'optimisation.
Ce problème se décline en plusieurs variantes de jeu, notamment avec le moins de déplacements possible, avec le plus de déplacements, ou en imposant des déplacements uniquement entre voisins proches donc en passant par toutes les positions possibles. Aussi, cette énigme peut varier en fonction du nombre de tiges mais nous on va se concentrer sur 3 tiges car sinon ça deviendrait beaucoup plus compliqué et ça demande plus de temps ou de ressources si on utilise un programme informatique.

Extraits

[...] Approche manuelle Pour résoudre les Tours de Hanoï manuellement, une stratégie optimale pour un grand nombre de disques peut demander beaucoup de mouvements. Par exemple, pour 8 disques, il faut en faire 255 ! La méthode récursive, bien que puissante, peut devenir confuse pour suivre manuellement avec beaucoup de disques. C'est pourquoi plusieurs méthodes plus simples ont été développées. On peut notamment en utiliser une, malgré qu'il y en ait beaucoup d'autres, qui est très simple d'utilisation car le principe se répète jusqu'à l'avoir résolu totalement. [...]

[...] On peut donc se demander : comment résoudre la légende des Tours de Hanoï ? Pour répondre à cette problématique, nous aurons tout d'abord une approche manuelle, en examinant les méthodes traditionnelles de résolution utilisées par les joueurs humains, suivie d'une analyse des suites mathématiques pour déterminer le nombre de déplacements nécessaires. Ensuite, nous nous intéresseront à l'utilisation de l'informatique pour résoudre efficacement le problème. Enfin, nous conclurons en examinant la relation entre la légende des Tours de Hanoï et la réalité mathématique du problème. [...]

[...] Approche informatique Pour résoudre les Tours de Hanoï de manière efficace et plus rapide, on peut utiliser un programme informatique. Par exemple, en Python, qu'on peut utiliser en NSI comme en Maths, on peut écrire un programme qui utilise la récursivité pour déplacer les disques entre les tiges. L'idée principale est de diviser le problème en sous-problèmes plus petits et en effectuant les mêmes étapes que si on le faisait à la main. D'ailleurs pour créer ce programme, on utilise les piles en Python qui nous permettent de résoudre l'énigme et ça nous donne les mêmes contraintes qu'à la main : on peut bouger et accéder seulement au disque en haut de la pile et pour déplacer le disque à la base de la pile, il faut déplacer tous ceux qui sont sur ce disque. [...]

[...] On peut calculer les premiers termes de la suite : u1 = 1 ; u2 = 3 ; u3 = 7 ; u4 = 15 ; u5 = 31 ; u6 = 63 ... En calculant ces premiers termes, on peut remarquer un certain motif : pour avoir le nombre de déplacement avec un certain nombre de disques, on fait 2[nombre de disque] et on enlève 1. Exemple pour 4 disques : = 2x2x2x2 = 16 - 1 = 15 = u4 On peut donc conjecturer que la suite semble être une suite géométrique définie par u? = - 1. [...]

[...] Comment résoudre la légende des Tours de Hanoï à l'aide des suites ? - Grand oral Introduction Avez-vous déjà entendu parler d'un casse-tête si complexe qu'il est dit qu'il pourrait décider du sort du monde ? C'est exactement ce que nous allons voir aujourd'hui avec les Tours de Hanoï. Selon une légende vietnamienne, un moine bouddhiste doit déplacer 64 disques d'une tige à une autre en respectant des règles très strictes. La légende raconte que lorsque cette tâche sera accomplie ça sera la fin du monde. [...]