LA LOGIQUE DES TOURS DE HANOÏ

[CDavid.TS 0]

Connaissez-vous les tours de Hanoï ? Ce jeu se présente sous la forme de trois tours, A, B, et C, avec des palets de différentes tailles initialement sur la tour A dont le but est d'amener successivement tous ces palets sur la tour C avec des règles bien précise.

Un déplacement ne peut se faire que :

- palet par palet (un par un)

- ou si le palet en cours de déplacement va à destination d'un emplacement vide ou sur un palet plus grand.

Il existe une logique bien précise et un système de résolution mathématique pour l'étude des différents déplacements optimaux afin de parvenir à la solution. La question de cette énigme n'est pas de trouver la solution dont l'étude sur différents sites du net ne manque pas, que l'on peut trouver facilement. La question repose sur une autre logique qui amène aussi à la solution sans pour autant faire de calcul, d'étude de graphes ou de groupes mathématiques. Le nombre de palets n'est pas non plus important. L'aspect de la question se présente au niveau des manipulations à effectuer au premier coup d’œil d'une tour de Hanoï, quel que soit le nombre de palets se trouvant sur la tour A.

La question est : au premier coup d’œil d'une tour de Hanoï, se présentant initialement avec tous les palets sur la tour A, comment pouvez-vous être sûr(e) à 100 % des manipulations à effectuer, donc sans vous tromper une seule fois, pour parvenir à la solution en un minimum de coup ? Et ce, quel que soit le nombre de palets présent, même s'il faut plusieurs centaines de manipulations. Aucun calcul n'est demandé. Juste une question de logique.

Modifié 19 mai 2013 par CDavid.TS

[ribi 813]

Soit la procédure : T(n,X,Y) : liste minimale des instructions à réaliser pour déplacer une tour de n palets de la tour X à la tour Y.

T(1,X,Y) est évident : on déplace le palet de la tour X à la tour Y.

T(n,X,Y) nécessite que le plus grand palet de la tour X arrive sur la tour Y dégagée. Si on appelle Z la tour qui n'est ni X ni Y, la suite d'instruction T(n,X,Y) est la suivante:

T(n-1,X,Z) (dégager les n-1 palets supérieurs de la tour X à la tour Z), puis T(1,X,Y) (on déplace le grand palet de la tour X à la tour Y), puis T(n-1,Z,Y) (dégager les n-1 palets de la tour Z pour les mettre au dessus du grand palet)

Pour résoudre le problème au plus vite, il suffit de faire

T(n,A,C) = T(n-1,A, puis T(1,A,C) puis T(n-1,B,C)

=T(n-2,A,C) puis T(1,A, puis T(n-2,C, puis T(1,A,C) puis T(n-2,B,A) puis T(1,B,C) puis T(n-2,A,C)

...

En particulier ,le premier mouvement sera donc de mettre le palet supérieur de A vers C si le nombre de palets est impair, et de A vers B si le nombre de palets est pair.

Si je m'en tiens aux règles données, je résous le problème, il me semble.

Par exemple, si le nombre de palets est impair, mes objectifs successifs seront de mettre le petit palet sur C, puis empiler les deux petits palets sur B, puis empiler les trois petits palets sur C, puis empiler les 4 petits palets sur B...

Je ne sais pas si j'ai bien compris la question.

[CDavid.TS 0]

C'est exactement ça ribi. Cependant, la première partie de la réponse est superflue. Juste le cheminement logique est la bonne réponse. Bien que cela soit possible, une partie avec 70 palets peut être terminée en un minimum de coup sans erreurs. Bonne chance à celui qui veut essayer. Un petit soft Androïd le propose. Mais je n'est pas plusieurs centaines, voire plusieurs milliers d'années à perdre... Je ne suis pas encore immortel

[Cybero 4 299]

Quelqu'un d'autre cherche ou peut-on considérer cette énigme comme résolue ?

[Cybero 4 299]

Sans réponse de l'auteur d'ici une semaine, cette énigme sera considérée comme résolue par ribi

[Cybero 4 299]

Ce sujet est maintenant suspendu.

Pour demander sa réouverture, merci de contacter un modérateur ou moi même