problème des tours de Hanoï
tour de Brahma
tour de Hanoï
problème de la pyramide de Lucas
tour de Lucas
COMBINATOIRE
INFORMATIQUE
Le problème de la tour de Hanoï est un jeu de réflexion inventé par Edouard Lucas dans les années 1880, qu’il présente comme « Jeu tombé de Saturne, rapporté du Tonkin par N Claus de Siam », ce qui est en fait son pseudonyme.
Une tour de forme conique est constituée de disques superposés, le plus large en bas, enfilés sur une tige centrale. Deux autres tiges voisinent la tour. Le jeu consiste à tranférer la tour d’une tige sur une autre, en utilisant la troisième comme auxiliaire, et en respectant certaines règles :
I – On ne peut déplacer à chaque coup que l’étage
supérieur d’une pile.
II – On peut enlever l’étage supérieur d’une pile pour
l’enfiler sur une tige relevée n’ayant encore aucun étage.
III – On peut enlever l’étage supérieur d’une pile et le
placer sur une autre pile; à la condition expresse que
l’étage supérieur de celle-ci soit plus grand.
On démontre que pour une tour de n étages, il faut au minimum 2n – 1 étapes.
A la fois problème de réflexion (pour trouver la meilleure stratégie) et de dénombrement, le problème des tours de Hanoï peut aussi être traité en algorithmique.
En ce qui concerne la prétendue tour sacrée du temple de la légende indienne dont N Claus de Siam se serait inspiré, elle comporte 64 étages. Le nombre d’étapes est 264 – 1.
On peut trouver le texte de E. Lucas, numérisé, sur http://edouardlucas.free.fr/fr/liste_des_oeuvres.htm