Les tours de Hanoi

[Marc-math]

Bonsoir
Un petit exo ou je réfléchis depuis plusieurs jours je suis bloque

On dispose de trois paquets et de n disques de tailles croissante
Au départ les n disques sont empiles sur un piquet, du plus grand au plus petit
Le but du jeu est de placer ces n disques sur un autre piquet en respectant la règle suivante : un disque ne doit jamais être place sur un disque plus petit que lui


Soit n un entier naturel supérieur ou égal a 1.
On appelle Un le nombre minimal de déplacements nécessaire pour transporter une tour de n étages (n ;) 1 ) d'une tige a l autre

1. déterminer u1 u2 u3 et vérifier que u4= 15
2. en remarquant que pour, pour pouvoir déplacer la pièce la plus grosse , il est nécessaire d avoir reconstitue une tour avec les autres pieces sur une sur tige , expliquer pourquoi la suite (Un) verifier la relation de recurrence Un+1= 2Un+1
3. en déduire le nombre minimal de déplacements nécessaire pour une tour de 6 étages
4. en utilisant la suite (Vn ) définie pourtout n par Vn = Un+1 exprimer un en fonction de n
5. en admettant qu'on déplace une pièce par seconde combien de temps faut il pour reconstituer une tout de 10 étages ? 20 étages ?30 étages ?

Merci a vous tous :happy2:

[amine801]

slt

[Marc-math]

Bonjour

ta formule est juste mais je suis bloque sur la 2

[emdro]

Bonjour,

Pour déplacer n+1 disques, il faut
Déplacer les n disques supérieurs: Un déplacements
Déplacer le gros disque: 1
Replacer les n disques supérieurs au dessus du gros: Un

Bilan des opérations: Un + 1 + Un
soit 1+2Un

C'est bon?