DM de Maths Terminale S - Les tours de hanoi

Roromix · Octobre 2, 2006, 10:06

Je n’arrive pas à résoudre la question 1 de ce dm, quelqu’un peut-il m’aider ?

EXERCICE 1 : Les tours de Hanoï

Peut-on empiler les n disques qui sont initialement sur la tige C, sur la tige A avec la règle suivante:
“On ne déplace qu’un seul disque à la fois et un disque ne doit jamais être posé sur un plus petit que lui” ?

Montrer par récurrence que quel que soit le nombre n de disques, ce problème a une solution.

Montrer par récurrence que le nombre de coups nécessaires pour déplacer une pile de n disques est (2^n)-1

Une légende qui remonte à l’ol’igine des temps:

Dans le fameux temple de Benares (Inde), sous le dôme marquant le centre du monde, trône un socle de bronze sur lequel sont fixées 3 aiguilles de diamant. Sur l’une de ces aiguilles, à la création, Dieu empila 64 disques d’or, du plus grand au plus petit. C’est la tour de Brahma. Jour et nuit, inlassablement, les moines déplacent les disques d’une aiguille à une autre en respectant les lois de Brahma qui obligent les moines à ne déplacer qu’un disque à lafois et à ne jamais le déposer sur un plus petit que lui. Quand les 64 disques auront été déplacé de l’aiguille sur laquelle Dieu les déposa à la création vers l’une des autres aiguilles, la tour, le temple, et les Brahmanes seront réduits en poussière, et le monde disparaîtra dans un grondement de tonnerre.
Question: La fin du monde est-elle pour bientôt? (En comptant une seconde par déplacement, donner une estimation du nombre d’années)

Merci d’avance

enaid · Octobre 2, 2006, 10:40

Démontrer par récurrence, c’est démontrer au rang 0, puis démontrer au rang 1, puis en adaptant vrai au rang n, démontrer que c’est toujours vrai au rang n+1 …

Darth_casimir · Octobre 2, 2006, 10:41

Dans les tours de Hanoï y a des turbos vietnamiennes? :love:

manukult_1_1 · Octobre 2, 2006, 10:45

Pour les tours de Hanoï, j’avais fait un truc en Java durant ma deuxième année de GTR…pfff c’est la misère :pfff:

Naara · Octobre 2, 2006, 10:46

c’est fou ce que ca donne envie d’aller en terminal S :paf: :paf:

Darth_casimir · Octobre 2, 2006, 10:48

Perso y a prescription maintenant 36 15 j’ai pas envie de taffer les mecs envoyez moi vos réponses … c’est chouette internet… Msieu le palm wifi c’est autorisé au bac?

Roromix · Octobre 2, 2006, 11:00

Je sais comment faire pour les autres questions mais je n’arrive pas a faire la question 1

Roromix · Octobre 2, 2006, 11:02

Je pense pas qu’on aurait le temps d’avoir les réponses pendant la durée de l’examen.

d9pouces · Octobre 2, 2006, 11:50

de mémoire, y a la solution dans le manuel complet de la TI-92 (pas la TI92+, hein )

et j’ai la flemme de rédiger la solution, dsl

Kadoura · Octobre 2, 2006, 11:51

Rassure moi, c’pas à rendre pour demain? :paf:

LardonCru_1_1 · Octobre 3, 2006, 1:28

Je crois qu’il a cassé sa tirelire et qu’il est en train de faire des piles de pièces. Vous moquez pas, c’est comme ça que j’ai trouvé “l’algorithme” pour faire les piles et que j’ai résolu ce problème. :paf:

enaid · Octobre 3, 2006, 11:31

non hier [:sabathan666]

Asbel · Octobre 3, 2006, 11:49

Pour la démonstration de la première question :

Initialisation : pour un disque.
Tu peux le déplacer directement sur la tige A. (solution en 1 coup)
Donc la propriété est vraie pour n=1.

Propagation : on suppose la propriété vraie pour n.
Démonstration pour n+1 : la propriété étant vraie pour n, on peut déplacer les n premiers disques de C vers B. Le dernier disque peut être déplacé en un coup de C vers A. Et la propriété étant vraie pour n, on peut à nouveau redéplacer les n premiers disques de B vers A. Ainsi, on a bien déplacé n+1 disques de C vers A. La propriété est donc vraie pour n+1.

Ainsi, par récurrence, la propriété est vraie pour tout n >= 1.

Docte56 · Octobre 3, 2006, 11:50

BIen qu’ayant eu une excellent note au bac de maths en Term S, je suis maintenant absolument incapable de répondre à la question, et j’avoue que c’est devenu du chinois pour moi :paf: :paf:

Asbel · Octobre 3, 2006, 12:01

Les tours de Hanoi, on les mange à toutes les sauces en informatique :paf:
Le plus drôle, c’est quand il faut supprimer la récursivité de l’algo pour le faire en itératif [:faim]

cybermagic · Octobre 3, 2006, 12:02

Vietnamien Hanoï [:sabathan666]

smlamy · Octobre 3, 2006, 2:26

ouep mais bon la prepa math sup a beau etre assez proche dans le passé le resulta lui reste assez loin dans le futur :ane:

Oncle_Tony · Octobre 3, 2006, 5:15

Je l’avais fait en 2de si je me souviens bien, mais le prof avait une maquette en bois pour faire des essais, et une petite légende marrant qui finissait par des moines qui faisaient des piles pendant 10^16 ans en attendant la fin du monde…

C’est loin tout ça

Roromix · Octobre 3, 2006, 10:16

Merci asbel pour tout aide ! Je débute la récurrence en terminale S ! Et la c’est de la recurrence en baratin et non en calcul, j’avais pas encore fait.

C’est à rendre pour lundi prochain. Merci pour toutes vos réponses.

Roromix · Octobre 3, 2006, 10:41

Voila donc pour la question 1 :

Montrons par récurrence que quel que soit le nombre n de disques, on peut empiler les disques de la tige C vers la tige A en respectant les règles.

Initialisation :
Si n=1, soit pour un disque.
On peut le déplacer directement de la tige C à la tige A en un seul coup.
La proposition est donc vraie pour n=1, soit pour un disque.

Hérédité :
On suppose que la proposition est vraie pour le rang n, soit pour n disques.

Montrons que la proposition est vraie pour le rang suivant n+1, soit pour n+1 disques.
La propriété étant vraie pour le rang n, on peut déplacer les n premiers disques de la tige C vers la tige B. Le dernier disque peut être déplacé en un coup de la tige C vers la tige A. Et la propriété étant vraie pour n disques, on peut à nouveau déplacer les n premiers disques de la tige B vers la tige A.
Ainsi, on a bien déplacé n+1 disques de la tige C vers la tige A.
La proposition est donc vraie pour le rang suivant n+1, soit pour n+1 disques.

Donc la proposition est vraie pour n=1 et elle est héréditaire, donc daprès le principe de récurrence, elle est vraie pour tout entier n >= 1.