![Les Tours de Hanoi [Evanherk]](https://img.rts.ch/articles/2016/image/21ochh-27802026.image?w=1280&h=720 "Les Tours de Hanoi [Evanherk]")
De nouvelles règles pour les Tours de Hanoï
Tous les mois, retrouvez ici le problème de maths du mois concocté pour vous par le Mathscope de l'Université de Genève, avec, quelque temps plus tard, sa solution. En ce mois de juillet, on vous propose de changer les règles du jeu des Tours de Hanoï.
L'énigme
Vous connaissez le jeu de Tours de Hanoï? Petit rappel pour vous rafraîchir la mémoire:
Le jeu des Tours de Hanoï est constitué de trois piquets A, B et C, placés verticalement, et de n disques de taille décroissante. Chacun des disques est percé en son centre pour être mis autour de l'un ou l'autre des trois piquets. Les n disques sont initialement placés par taille décroissante autour du piquet A (celui de gauche), formant ainsi une tour. Le but du jeu consiste à déplacer les disques jusqu'à parvenir à la situation finale dans laquelle tous les disques se retrouvent autour du piquet C par ordre de taille décroissante. Les disques peuvent aller et venir librement sur les piquets, en suivant deux règles:
- on ne déplace qu'un seul disque à la fois;
- un disque ne peut jamais être posé sur un disque plus petit.
On peut montrer que pour n disques, le nombre minimal d'étapes pour faire passer la tour d'un piquet à l'autre est 2n-1. Vous pouvez essayer par exemple sur le site Prise 2 Tête.
Ajoutons maintenant une contrainte supplémentaire:
On interdit aux disques d'aller directement de A à C ou de C à A.
Quel est le nombre minimal d’étapes pour faire passer une tour composée de trois disques du piquet A au piquet C avec cette nouvelle contrainte?
Vous avez trouvé? Non? Voici La solution!
Mathscope, Université de Genève, RTS Découverte
Publié