Exercice 2 — Tours de Hanoï — Olympiades 2013 Réunion et Mayotte

Sujet

Règle du jeu :

Ce jeu est composé de 3 tours \(\mathrm{A}, \mathrm{B}\) et C et d'anneaux tous de taille différente enfilés sur ces tours.
Ces anneaux doivent obligatoirement être posés les uns sur les autres par taille décroissante.
Au départ, tous les anneaux sont enfilés sur la tour A , par taille décroissante. Le jeu consiste à déplacer tous les anneaux placés sur la tour A vers la tour C par exemple, en un minimum de déplacements.
On ne déplace qu'un anneau à la fois et on ne peut placer un anneau que sur un plus grand que lui ou sur une tour vide.

Exemples :

Avec 1 anneau :

Situation de départ

Le problème se résout alors en un coup (au minimum).

Avec deux anneaux

Situation de départ

Situation d'arrivée

Le problème se résout alors en 3 coups (au minimum).

Donner le nombre de coups minimum nécessaires pour déplacer un empilement de 3 anneaux de la tour A vers la tour C , en représentant toutes les étapes intermédiaires.
Montrer que 15 coups suffisent pour déplacer un empilement de 4 anneaux de la tour A vers la tour C.
Alexandre affirme qu'il arrive en 31 coups à déplacer 5 anneaux de la tour A vers la tour C . A-t-il raison?
Quel est le nombre maximum d'anneaux que l'on peut déplacer en moins de 2013 coups ?
Alexandre affirme qu'il arrive à déplacer 30 anneaux en 1073741824 coups. Est-ce possible?

L'exercice s'appuie sur la remarque suivante qui doit faire son chemin dans la tête du candidat au fur et à mesure des questions :
Si on sait déplacer n anneaux d'une tour vers une autre, alors pour déplacer \(\mathrm{n}+1\) anneaux de A vers C , il suffit de :

Déplacer les n anneaux les plus petits de A vers B (ceci est possible car sur la tour A reste le plus grand anneau et que tous les autres anneaux étant plus petits que cet anneau, on peut « négliger » le grand anneau et donc se retrouver dans la situation avec seulement \(n\) anneaux)
Déplacer l'anneau le plus grand de A vers C
Déplacer les \(n\) anneaux qui sont sur la tour B vers la tour C (toujours possible car on est dans une situation similaire à la première étape)
Par ailleurs, si on scinde \(n+1\) en \(p+q\) (avec \(p \neq 1\) et \(q \neq 1\), on pourra dans un premier temps déplacer sans problème les \(p\) anneaux les plus petits de A vers B , mais on sera incapable de déplacer les \(q\) autres anneaux les plus grands de A vers C car la tour B ne pourra pas être utilisée : aucun des \(q\) anneaux ne pourra être placé sur la tour B , pour des considérations de grandeur d'anneau.
Le nombre minimum de coups s'obtient donc avec la démarche énoncée auparavant.

Comme pour déplacer 2 anneaux de A vers C , il fallait au minimum 3 coups, alors pour déplacer 3 anneaux de A vers C , on pourra le faire en \(3+1+3=7\) coups (mais ici, on attend, une réponse basée sur des manipulations).
De même, comme on sait déplacer 3 anneaux de A vers C en 7 coups, alors pour déplacer 4 anneaux de A vers C , on peut le faire en \(7+1+7=15\) coups.
Et, pour déplacer 5 anneaux, on peut le faire en \(15+1+15=31\) coups.

Nombre d'anneaux	1	2	3	4	5	6	7	8	9	10	11
Nombre de coups minimum	1	3	7	4	15	31	63	127	255	511	1023

Remarque : Le \(n^{\text {ème }}\) terme de la seconde ligne est égal à \(2^{n-1}-1\).
Au maximum, on peut donc avoir une tour de 10 anneaux.
5. Le nombre minimum de coups pour déplacer 30 anneaux est nécessairement impair (de proche en proche) ; par ailleurs chaque coup supplémentaire inutile devra être compensé par un coup contraire, ce qui rajoute systématiquement un nombre pair de coups. Donc au total, on ne peut réussir à déplacer 30 anneaux que par un nombre pair de coups. Alexandre a donc tort.