La pile d'assiettes

[nodjim]

Bonjour à tous.
Ce problème a été proposé par Edouard Lucas, connu pour son travail entre autres sur les suites de Fibonacci.

Une pile d'assiettes ne comprend que des assiettes de tailles différentes, elles sont empilées de la plus grande en bas à la plus petite en haut.
On se propose de la déplacer.
Contraintes:
-On ne peut déplacer qu'une seule assiette à la fois.
-On ne peut poser une assiette sur une autre plus petite.

2 questions:
Combien d'emplacements libres faut il pour déplacer une pile de n assiettes ?
Combien de manipulations d'assiettes ?

Je n'ai pas du tout regardé, je ne sais pas si c'est compliqué, mais ça m'a l'air intéressant.:dingue:

[adrd]

Salut, c'est le jeu des "tours de Hanoï", non ?
Il y a combien de piles d'assiettes ?

[nodjim]

Salut, c'est le jeu des "tours de Hanoï", non ?
Il y a combien de piles d'assiettes ?

Oui, ça s'appelle aussi comme ça. Une seule pile de n assiettes, c'est trop simple ?

[adrd]

Il faut avoir au moins 3 piles d'assiettes pour pouvoir déplacer une pile car si on met la première assiette dans une deuxième pile on ne peut rien rajouter dessus car c’est la plus petite. Il y a donc 3 piles et on peut résoudre le problème avec autant d’assiette que l’on veut.

[nodjim]

Oui, je viens de tester. C'est déja pas mal avec 5 assiettes.
Donc restons en à 3 emplacements disponibles, y compris celui de la pile de départ.
Combien de déplacements minimum ?

[nodjim]

Résultat: -1+2^n si je ne m'abuse.
Quelqu'un pour confirmer ?

[Quidam]

Résultat: -1+2^n si je ne m'abuse.
Quelqu'un pour confirmer ?

Je confirme. c'est
C'est exactement le problème des tours de Hanoï !