Exercice 22

1. Montrons par récurrence sur $n \geqslant 1$ l'assertion $P(n)$ : « on peut déplacer une pile de $n$ disques d'un piquet à n'importe quel autre, en respectant les règles ». Il est commode de l'énoncer pour deux piquets quelconques, et de remarquer qu'on peut ignorer des disques plus grands posés sous la pile, puisque tout disque peut être posé sur eux.

Initialisation : Un seul disque se déplace en un coup.

Hérédité : Supposons $P(n)$ et considérons une pile de $n + 1$ disques sur le piquet $i$, à déplacer vers le piquet $j$, le troisième piquet étant $k$. On déplace les $n$ disques supérieurs de $i$ vers $k$, ce qui est possible par $P(n)$, le grand disque restant immobile sous eux ; on déplace le grand disque de $i$ vers $j$ ; puis on déplace les $n$ disques de $k$ vers $j$, à nouveau par $P(n)$, sur le grand disque.

Conclusion : Le jeu peut être résolu pour tout $n \geqslant 1$.

2. Notons $m_{n}$ le nombre minimal de coups pour déplacer $n$ disques d'un piquet à un autre. La stratégie précédente utilise $2m_{n} + 1$ coups pour $n + 1$ disques, donc $m_{n+1} \leqslant 2m_{n} + 1$. Inversement, dans toute solution pour $n + 1$ disques, considérons le premier déplacement du grand disque, de $i$ vers $j$. À ce moment, aucun disque n'est au-dessus de lui sur $i$ ni sur $j$ : les $n$ petits disques sont tous sur le troisième piquet, et il a fallu au moins $m_{n}$ coups pour les y amener. Après le dernier déplacement du grand disque, il faut encore au moins $m_{n}$ coups pour reposer les $n$ petits disques sur lui. D'où $m_{n+1} \geqslant m_{n} + 1 + m_{n}$, et finalement $m_{n+1} = 2m_{n} + 1$, avec $m_{1} = 1$. On vérifie alors par récurrence que $m_{n} = 2^{n} - 1$ : c'est vrai pour $n = 1$, et $2(2^{n} - 1) + 1 = 2^{n+1} - 1$. $$\boxed{\text{Le nombre minimal de coups est } 2^{n} - 1.}$$ Pour $n = 3$, il faut $7$ coups, et pour $n = 64$, la légende qui accompagne le jeu imagine des moines déplaçant un disque par seconde : il leur faudrait $2^{64} - 1 \approx 1{,}8 \times 10^{19}$ secondes, soit plus de $500$ milliards d'années.