$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th
Dictionnaire de mathématiques > Applications > Récréations mathématiques >

Tours de Hanoï

Les tours de Hanoï sont un petit divertissement mathématique mis au point par Edouard Lucas en 1883. Il consiste en 3 piquets, le premier porte $n$ disque de tailles toutes différentes, empilés du plus grand (en bas) au plus petit (en haut). Le problème des tours de Hanoï consiste à faire passer tous ces disques au piquet 2, en s'aidant du troisième piquet, sachant qu'on ne déplace qu'un disque à la fois, et en respectant la règle suivante : aucun disque ne doit être empilé sur un disque de diamètre inférieur.

Il existe un algorithme récursif très classique pour résoudre ce problème. Supposons qu'on sache déplacer $n-1$ disques. Pour en déplacer $n,$ il suffit de déplacer $(n-1)$ disques du piquet 1 au piquet 3, puis de déplacer le grand disque du piquet 1 au piquet 2. On termine en déplaçant les $(n-1)$ autres disques du piquet 3 vers le piquet 2.

Si $h_n$ est le nombre de déplacement de disques nécessaires pour déplacer les $n$ disques, on a la formule de récurrence suivante : $h_n=2h_{n-1}+1$ avec la condition $h_1=1.$ Par un calcul par récurrence facile, on trouve : $h_n=2^n-1.$

Certaines sources signalent l'arithméticien Edouard Lucas comme étant à l'origine de ce divertissement. D'autres en donnent une explication plus mythologique :
  Dans le grand temple de Bénarès, sous le dôme qui marque le centre du monde, se trouve une plaque de bronze où sont fixées trois aiguilles de diamant, hautes chacune d'une coudée et fines comme la taille d'une guêpe. Sur une de ces aiguilles, lors de la création du monde, Dieu a placé 64 disques d'or pur, le plus large reposant sur la plaque de bronze, et les autres allant en décroissant jusqu'au plus petit. C'est la Tour de Bramah. Jour et nuit, sans arrêt, les prêtres transfèrent les disques d'une aiguille de diamant à une autre, en suivant les lois immuables de Bramah qui veulent que le prêtre de service ne prenne qu'un disque à la fois, et qu'il le place sur une aiguille de telle manière qu'il ne se trouve jamais sous lui de disque plus petit. Lorsque les soixante-quatre disques auront été transférés de l'aiguille sur laquelle Dieu les a mis lors de la création du monde, à une des autres aiguilles, la Tour, le Temple et les Brahmanes s'écrouleront en poussière, et dans un coup de tonnerre, le Monde s'évanouira.
Recherche alphabétique
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Recherche thématique
  • Algèbre
  • Analyse
  • Applications
  • Arithmétique
  • Probabilité et statistiques
  • Géométrie
  • Fondements
  • Histoire
  • Mathématiques discrètes
  • Mathématiques interactives