La solution!

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 2ⁿ-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?

La solution

Il faut 26 étapes, soit 3³-1. On peut montrer que pour n pièces, il faudra au minimum 3ⁿ-1 étapes.

Si vous voulez en savoir plus, n’hésitez pas à lire l'article de Benoît Rittaud: Les tours de Hanoï et la base trois. Accromath [En ligne]. Vol 11.1 - hiver - printemps 2016: pp. 18-23. Disponible ici: http://accromath.uqam.ca/2016/02/les-tours-de-hanoi-et-la-base-trois/.

Mathscope, Université de Genève, RTS Découverte