Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Tours de Hanoï
Résumé
Les tours de Hanoï (originellement, la tour d'Hanoï) sont un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de « départ » à une tour d'« arrivée » en passant par une tour « intermédiaire », et ceci en un minimum de coups, tout en respectant les règles suivantes :
on ne peut déplacer plus d'un disque à la fois ;
on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.
On suppose que cette dernière règle est également respectée dans la configuration de départ.
Le problème mathématique des tours de Hanoï a été inventé par Édouard Lucas. Paru d'abord en fascicule en 1889 , il est publié ensuite dans le tome 3 de ses Récréations mathématiques, parues à titre posthume en 1892. Il annonce que ce problème est dû à un de ses amis, N. Claus de Siam (anagramme de Lucas d'Amiens, Amiens étant sa ville de naissance), prétendument professeur au collège de Li-Sou-Stian (anagramme de Saint Louis, le lycée où Lucas enseignait).
Sous le titre « Les brahmes tombent », Lucas relate que .
Comme indiqué ci-dessous, un jeu à 64 disques requiert un minimum de 2-1 déplacements (soit ). En admettant qu'il faille une seconde pour déplacer un disque, ce qui fait déplacements par jour, la fin du jeu aurait lieu au bout d'environ milliards de jours, ce qui équivaut à peu près à 584,5 milliards d'années, soit 43 fois l'âge estimé de l'univers (13,7 milliards d'années selon certaines sources).
Il est facile de démontrer par récurrence que si n est le nombre de disques, il faut 2n - 1 coups au minimum pour parvenir à ses fins, quantité qui augmente très rapidement avec n. En effet, soient A, B et C les trois emplacements des tours ; notons xn le nombre de déplacements de disques nécessaires au déplacement d'une tour complète. Pour déplacer une tour de n disques de A vers C, on effectue ces trois étapes :
déplacer la tour des n-1 premiers disques de A vers B (étape qui nécessite xn-1 déplacements, d’où la récurrence) ;
déplacer le plus grand disque de A vers C (un déplacement supplémentaire) ;
déplacer la tour des n-1 premiers disques de B vers C (à nouveau xn-1 déplacements).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.