Petite énigme sans prétention, pour la détente
Pour ceux qui ne connaissent pas les tours de Hanoï:
On a trois piquets et N disques qui peuvent se ficher sur les piquets et s'empiler dessus. Les N disques ont tous des tailles différentes et sont empilés (de bas en haut) sur le premier piquet du plus grand au plus petit, pour former une sorte de pyramide.
Le but est de déplacer tous les disques sur le dernier piquet, sachant que:
- on ne peut déplacer qu'un disque à la fois, d'un piquet vers un autre
- le disque déplacé est toujours au sommet de sa pile
- on ne peut pas empiler un disque sur un autre plus petit
Voici une variante : à l'image du voyageur de commerce, les disques doivent à l'arrivée être tous passés au moins une fois sur chacun des piquets, et les états initiaux / finaux sont les mêmes que dans le problème original.
En combien de déplacements peut-on réaliser ces mouvements, en fonction de N ?
La case réponse valide le cas N=50