Inscription / Connexion Nouveau Sujet
Problème : La Tour de Hanoï
Soit
On appelle
1°) Déterminer
Vérifier que
2°) En remarquant que, pour pouvoir déplacer la pièce la plus grosse, il est nécessaire d'avoir reconstitué une tour avec les autres pièces sur une des tiges, expliquer pourquoi la suite
3°) En déduire le nombre minimal de déplacements nécessaires pour une tour de huit étages.
4°) En observant les termes de la suite
5°) En admettant qu'on déplace une pièce par seconde, combien de temps faut-il pour reconstituer une tour de 64 étages ?
Bonjour,
j'ai quelques ennuis avec ce problème... je ne sais déjà pas, à quoi correspondent
Bonjour,
c'est dit dans l'énoncé.
On appelle un le nombre minimal de déplacements nécessaires pour transporter une tour de n étages d'une tige à l'autre.
U1 c'est le nombre minimum pour déplacer une tour de 1 étage
U2 c'est le nombre minimum pour déplacer une tour de 2 étages
U3 c'est le nombre minimum pour déplacer une tour de 3 étages
etc
Fais un dessin pour mieux comprendre, avec différentes valeurs de n
Un, c'est le nombre de déplacement(s) que l'on doit faire pour changer une tour de n éléments sur un autre tige.
A noter qu'une tour, c'est toujours une pièce petite sur une pièce plus grosse sur une pièce plus grosse etc.
Ainsi, U1 est le nombre de déplacement(s) pour déplacer une tour de 1 élément sur une autre tige.
U2 est le nombre de déplacements pour déplacer une tour de 2 éléments sur une autre tige.
etc.
Pour trouver U1, c'est facile, il n'y a qu'une seule pièce à la tour, donc il faudra 1 déplacement pour changer la tour de tige.
U1 = 1
Pour trouver U2, tu peux essayer avec des pièces de monnaies par exemple 
Voici ce que je trouve :
1°)
On remarque que :
2°) La relation de récurrence est vérifiée (cf. 1°)).
3°)
____
Il faut donc au minimum 255 déplacements pour une tour de huit étages.
4°) Si j'ai bien compris il faut trouver une suite explicite ...
bon je vais essayer ça
Pour la question 2, on te demande "d'expliquer"
Je saurai pas l'expliquer clairement personnellement. Je pense qu'il faut expliquer pourquoi, lorsque qu'on travaille sur un étage de plus, il faut jouer 2 fois plus de coups, +1, qu'à l'étage inférieur.
J'essaie d'expliquer alors :
Pour déplacer une tour de étages :
on doit d'abord faire une tour de étages, on déplace la pièce en plus
, et on refait la tour de
étage sur la pièce déplacée.
4°) Je vois pas ce que c'est les termes ""
Mais à partir de cela :
En voyant 255, j'ai pensé à 256; pareil quand j'ai vu 127, j'ai pensé à 128, qui sont des puissances de 2 (cf. RAM sur les pc : 128mo, 256mo, 512mo, 1024mo et cetera).
Donc j'ai pu conjecturer que :
Le problème cest que je semble pas être parti de l'énoncé, et je ne vois pas comment démontrer cela ...
Pour démontrer cela, utilise la récurrence, ce n'est pas très dur
Le problème c'est que je semble pas être parti de l'énoncé
Ce n'est pas un problème, c'est justement ça une conjecture. Tu émets une hypothèse sur la suite. Hypothèse que tu vas prouver par récurrence
Voilà :
On avait :
Considérons les termes de la suite ( :
On remarque que :
On a donc :
D'où l'on déduit :
5°) D'après la suite : :
(énorme
)
un déplacement par seconde, donc il y a autant de secondes que de déplacements :
soit :
Non, tu as juste émis une conjecture, c'est-à-dire quelque chose qui semble juste, tu ne l'as pas prouvé.
Ta conjecture est bonne, mais il faut la démontrer par récurrence :
1) Initialisation
pour n=1
...
2) On suppose Un = 2n - 1. On veut montrer Un+1 = 2n+1 - 1
...
3) La propriété P(n) : "Un = 2n - 1" est vraie pour tout n 
1
à toi de compléter ce qu'il faut
Ah ok (lol j'ai rien fait finalement xD )
1) Initialisation :
2) On suppose que et donc on suppose que
Si on suppose que alors
On veut donc démontrer que :
On a :
or, on suppose que :
... euh je ne vois pas du tout quoi faire 
Attends attends attends ! 
Je remets la question :
4°) En observant les termes de la suite , conjecturer l'expression de
en fonction de n et démontrer cette conjecture.
On te demande d'abord d'observer, donc tu notes les premiers termes (+1) comme tu l'avais fait un peu plus haut :
Maintenant, émettons la conjecture :
Un = 2n - 1
Ensuite, il faut la démontrer (par récurrence par exemple) :
1) Initialisation
pour n=1
...
2) On suppose Un = 2n - 1. On veut montrer Un+1 = 2n+1 - 1
...
3) La propriété P(n) : "Un = 2n - 1" est vraie pour tout n 1
Tu t'étais un petit peu emmêlé les pinceaux, j'ai préféré tout reprendre
Pour l'initialisation, il ne faut tester qu'un seul rang (ici le rang 1).
Donc tu regardes U1, puis 21-1.
Tu montres qu'ils sont identiques.
On passe alors à l'étape 2 et on suppose Un = 2n - 1. On veut alors montrer Un+1 = 2n+1 - 1
Tu avais bien commencé et tu es resté bloqué ici :
Arrivé ici, il faut se servir de
xa.x = xa+1 d'où Un+1 = 2n+1-1
Etape 3 : Tu conclus
Salut ^^ (désolé j'étais parti une semaine)
Je pense avoir compris grâce à ta jolie réponse (dont je te remercie).
Avec les premiers termes obtenus, j'émets une conjecture :
1. Initialisation :
pour
or .
2. Démonstration :
On a conjecturé que
alors (1)
On veut démontrer l'expression (1).
On a
On remplace le par celui conjecturé plus haut :
On retrouve l'expression (1).
Donc, l'expression est vraie
.
Voilà
P.S. une petite question : à quoi sert l'initialisation ?
P.S. une petite question : à quoi sert l'initialisation ?
à initialiser
Plus sérieusement, c'est ce que l'on pourrait appeler le "cas de base", une sorte d'exemple sur lequel on peut s'appuyer pour continuer.
Avec l'exemple "validé", on va supposer que c'est vrai pour tout n, ensuite, on va montrer la propriété au rang suivant, n+1.
C'est assez clair ?
Pour revenir sur ton post précédent, tu as écrit 2-3 trucs maladroits :
Il faut écrire 2^1-1 = 1
Or U1 = 1 donc Un=2^n-1 est vraie au rang 1
Tu saisis le truc ?
Il ne faut pas commencer par écrire U1 = ...
On a conjecturé que
"On suppose
Si tu as encore des questions, n'hésite pas
Parfait merci beaucoup !
J'ai compris l'initialisation et la mise en forme (j'avoue que je m'embrouillais pas mal avec ça).
Bah, pour ce qui est des questions, je m'attaquerai demain aux suite arithmétiques, alors j'aurai sûrement encore besoin d'aide ^^
sur ce, encore merci et a +
Pas de quoi
Entraîne-toi à bien comprendre ce schéma de la récurrence, c'est important et ça rapporte des points
Bah, les profs appellent ça comme ça :
ce sont des contrôles qui portent sur toute l'année et qui ont la même durée que ceux du BAC.
La différence est juste que cela ne prends pas en compte le programme de terminale.
Ils ont aussi pour nom "DS de synthèse".
Bonjour, j'ai un exercice sur la Tour de Hanoi à faire mais je bloque sur une question qui est la suivante: " On considère le déplacement d'une pile de n+1 disques, du premier au dernier piquet. Quel est le nombre minimum de coups à effectuer avant de pouvoir déplacer le plus grand disque? "
Merci d'avance pour votre aide.
Bonsoir,
J'ai vu que plusieurs exercices sur la Tour de Hanoi ont déja été résolus sur ce forum mais je n'ai pas trouvé de réponse à ma question qui est la suivante: " On considère le déplacement d'une pile de n+1 disques, du premier au dernier piquet. Quel est le nombre minimum de coups à effectuer avant de pouvoir déplacer le plus grand disque? "
Je dirais qu'il faut d'abord déplacer tous les disques du dessus et reformer une pile mais je ne sais pas comment expliquer cela avec une "formule".
Merci d'avance pour votre aide.
*** message déplacé ***
Bonsoir,
Le sujet est beaucoup traité en ligne, par exemple ici : 
Dans le texte tu verras, avec la démonstration :
De façon générale, le nombre de déplacements pour n anneaux est 2n - 1.
*** message déplacé ***
Bonjour JannC,
J'avais eu ce problème à faire 11 ans auparavant, lorsque j'étais en première...
Apparemment tu n'as pas posté l'intégralité de ton énoncé. As-tu bien regardé celui que j'avais eu dans le premier message ? Il doit y avoir des similitudes entre les deux énoncés qui t'aideront à résoudre ton problème.
la FAQ du forum
Annuler
connectez vous