Devoir à la maison , Terminale S : Planètes des singes , demonstration par récurrence ..

[invitea08413d9]

Bonjour à tous !
Je dois rendre un DM pour Lundi
et je bloque un peu sur le dernier exercice (je n'y arrive pas du touuuuut )
Voici l'énoncé :

Dans le film la planète des singes les origines il est question des tours d'Hanoi
Le but de ce jeu est de déplacer n rondelles de diamètre différents d'une tour de départ à une tour d'arrivée en un minimum de coup

Un coup consiste a deplacer une rondelle située au sommet d'une tour au sommet d'une autre tour en respectan les regles suivantes :
on ne déplace qu'une rondelle à la fois
Une rondelle ne doit jamais se retrouver au dessus d'une rondelle plus petite


On note Un le nombre minimal de déplacements nécessaires pour résoudre un jeu omportant n rondelles sur la tour de départ



1/ déterminer U1 et U2 , puis justifier a l'aide d'un schéma déplacement par déplacer des tour d'Hanoi (7 deplacements et 3 rondelles) que u3=7

2/ En remarquant que pour pouvoir déplacer la piece la plus grosse de la tour d départ a la tour d'arrivée il est nécessaire d'avoir constitué une tour avec les autres pieces sur la tour intermédiaire , montrer que la suite Un vérifie la relation de récurrence :

(un+1) = 2(un) +1

3/ a l'aide d'un tableur (vous en ferez une copie d'écran) calculer les 10 premiers termes de la suite (un)

4/ Soit la suite (vn) définie par vn=(un) +1

a- calculer les 10 premiers termes de la suite vn a l'aide de la feuille de cacul précedente
b- Conjecturer l'expression de (un) en fonction de n
c- Démontrer par récurence cette conjecture



Merci d'avance pour votre aide/explication
-----

[pallas]

La premiere question est evidente mais saches qu'il y a trois tours ( va voir sur wikipedia

[invitebac64493]

Il faut que tu dessines un schema et tous coulera de source. Tu as trois colonnes et tu as une tour et sur une des autres colonnes tu dois former une nouvelle tour. U1 signifiera qu'il y a 1 rondelle donc combien de coups pour reproduire cette tour ??? (la réponse est évidente=)). J'éspère t'avoir aidé!

[invitea08413d9]

Bonjour
Tout d'abord merci pour votre réponse
Je bloque vraiment pour cet exercice et je ne comprends pas comment U1 peut etre égal a 1
U2 = 3
U3=7

Sachant que Un est le nombre minimal de déplacement nécessaire pour resoudre un jeu comportant n rondelles sur la tour de départ
c'est a dire que pour U1 il y aurait qu'une seule rondelle sur le tour de départ ? Ce qui entrainerait un deplacement ?
ce n'est pas clair pour moi ...

Merci encore

[A voir en vidéo sur Futura]

[invitea08413d9]

Bonjour Jeandesjean merci pour votre réponse!
J'ai bien reussi a finir le schéma des tours d'Hanoi et j'arrive effetivement a 7 deplacement et j'ai reussi a bien déplacer toutes les rondelles malheureusement comme je l'ai dis dans mon poste précédent ce n'est pas clair pour moi quand on commence a parler des suites je ne vois pas la logique à U1=1 , U2=3 et U3=7
je n'ai pas du comprendre à quoi correspond UN et l'indice n je pense pourtant j'ai bien relu mon énoncé

Merci encore
Eloooo

[invitebac64493]

Très bien tu as fait le plus dur maintenant je vais t'aider un peu. Regarde tu as U0=0 U1=1 U2=3 U3=7
Tu dois émettre une conjecture. SI tu regardes 2^n
2^0=1 2^1=2 2^2=4 2^3=8
U0 = 0 U1=1 U2=3 U3=7
J'éspère que ma mise en page t'as aidé a trouver la conjecture^^
Cordialement Jean

[invitea08413d9]

Merci de votre aide ,

Alors pour moi la conjecture serait la question de l'exercice 2 à savoir U(n+1) = 2Un + 1 non ?
Je dois montrer que Un vérifie la relation de recurrence ( soit la conjecture que je viens de mettre )
Je dois faire une démonstration par récurrence ? (avec inialisation , héridité ect.. ? )

Merci JeanDesJean
Eloooo

[invitea08413d9]

Ah je crois avoir compris
J'ai u0 = 0
U1 = 1
u2=3
u3 = 7

Grace a la formule u(n+1) =2Un +1 je peux vérifier les résultats que j'ai trouvé précédemment

Pour u1 = 2*U0+1
u1 = 1
Ect...

En revanche je ne sais pas comment je dois expliquer ça sur ma copie ..
Je dois faire une démonstration ? Ou donner des exemples comme je viens de le faire

MERCI !

[invitea08413d9]

Pour la question 4)b/
J'hésite entre plusieur conjecture :
Vn=2^n +1
Ou Un = 2^n ...
Merci

[invitebac64493]

Non juste que Un=2^n-1 mais t'y etais un peu pres^^

[invitea08413d9]

merci bcp pour votre aide !!!!
donc la conjecture est Un=2^n - 1
et a partir de ca je fais une demonstration par récurrence?
Merci encore bonne soiréée

[invitebac64493]

oui la tu sais que Un=2^n-1 et Un+1 = 2^n+1 donc il te reste plus qu'a tous démontrer bonne chance!