Sujet numéro 15 Agrégation Marocaine d'Informatique Page 1 sur 5

Épreuve de modélisation Année 2025

Conseils du Jury :
Il est rappelé que le jury n’exige pas une compréhension exhaustive du texte. Vous êtes laissé(e) libre d’orga­
niser votre discussion comme vous l’entendez. Des suggestions de développement, largement indépendantes
les unes des autres, vous sont proposées en fin de texte. Vous n’êtes pas tenu(e) de les suivre. Il vous est
conseillé de mettre en lumière vos connaissances à partir du fil conducteur constitué par le texte. Le jury
appréciera que la discussion soit accompagnée d’exemples traités sur ordinateur.

Sujet à traiter : Problème de la tour de Hanoï

Quelques notations et rappels : Dans ce sujet,
→ la lettre 𝑛 désigne un entier naturel non nul.
→ Pour 𝑘 un entier naturel, 𝐸𝑘 désigne l'ensemble des entiers compris entre 0 et 𝑘 − 1. En particulier,
on a 𝐸0 = ∅. On utilise aussi la notation 𝐸𝑘∗ pour désigner 𝐸𝑘 ∖ {0}.
→ La notation 𝑢 % 𝑣 désigne le reste de la division euclidienne d'un entier quelconque 𝑢 par un entier
naturel non nul 𝑣.
→ Si 𝐴 et 𝐵 sont deux ensembles quelconques, alors leur différence symétrique est l'ensemble noté
𝐴Δ𝐵 et défini par 𝐴Δ𝐵 = (𝐴 ∪ 𝐵) ∖ (𝐴 ∩ 𝐵), c'est-à-dire que 𝐴Δ𝐵 est l'ensemble des éléments qui
sont dans 𝐴 ∪ 𝐵 et qui ne sont pas dans 𝐴 ∩ 𝐵.
→ Si 𝑓 est une application ou fonction d'un ensemble 𝐴 à valeurs dans un ensemble 𝐵, alors l'image
réciproque d'une partie 𝐾 de 𝐵 par la fonction 𝑓 est la partie de 𝐴 notée 𝑓 −1(𝐾) et définie par
𝑓 −1(𝐾) = {𝑢 ∈ 𝐴 : 𝑓(𝑢) ∈ 𝐾}.
→ On note >> l'opérateur logique permettant de décaler à droite les bits d'un certain nombre de rangs
et & l'opérateur logique AND, bit à bit, sur les entiers. Les langages de programmation Python et
C utilisent les mêmes symboles pour ces opérateurs. Par exemple, l'obtention de 115 >> 3 se fait en
écrivant 115 en binaire 1110011 puis en décalant ces bits de 3 rangs :

115 >> 3 = 1110011 >> 3 = 0001110 = 14.

De même, pour obtenir 115 & 75, on écrit les entiers 115 et 75 en binaire puis ensuite on applique
bit à bit l'opérateur & :

115 & 75 = 1110011 & 1001011 = 1000011 = 67.

Pour les bits, on rappelle que 1 & 1 = 1 et que 1 & 0 = 0 & 1 = 0 & 0 = 0.

Problème de la Tour de Hanoï : On dispose de 𝑛 disques notés 𝐷0, … , 𝐷𝑛−1 et de trois tours
notées 𝑇0, 𝑇1 et 𝑇2. On suppose que les diamètres de ces disques vérifient diam(𝐷0 ) < ⋯ < diam(𝐷𝑛−1 ),
où diam(𝐷𝑖 ) est le diamètre du disque 𝐷𝑖 pour 𝑖 = 0, … , 𝑛 − 1. Ces disques sont supposés tous placés
sur une tour 𝑇𝑎, avec 𝑎 dans 𝐸3, de sorte que 𝐷𝑖 soit placé au dessus de 𝐷𝑖+1 pour 𝑖 dans 𝐸𝑛 lorsque
𝑛 ⩾ 2. Voir le schéma ci-dessous pour le cas de 𝑛 = 4 et 𝑎 = 0. La résolution du problème de la Tour
de Hanoï consiste à effectuer une série de déplacements 𝑑1, … , 𝑑𝑞 permettant de déplacer tous les disque
de la tour initiale 𝑇𝑎 à une tour finale 𝑇𝑏 avec 𝑏 ∈ 𝐸3 et 𝑏 ≠ 𝑎. Chaque déplacement est effectué tout en
respectant les trois règles suivantes :
règle 1 : on ne déplace que le seul disque qui se trouve au sommet d'une tour
règle 2 : on ne déplace qu'un seul disque à la fois
règle 3 : on ne peut placer un disque que sur un autre disque ayant un diamètre plus grand ou sur
un emplacement vide.
Ci-dessous, on présente les situations initiale et finale pour le cas de 𝑛 = 4, 𝑎 = 0 et 𝑏 = 2.
 Sujet numéro 15 Agrégation Marocaine d'Informatique Page 2 sur 5
Épreuve de modélisation Année 2025

𝑇0 𝑇1 𝑇2 𝑇0 𝑇1 𝑇2

𝐷0 𝐷0
𝐷1 𝐷1
𝐷2 𝐷2
𝐷3 𝐷3

Situation initiale Situation finale

Dans la littérature, on trouve des algorithmes destinés à résoudre ce problème. La plus part de ces
algorithme sont récursifs. Pour un algorithme itératif destiné à résoudre le problème de la Tour de
Hanoï, on peut assimiler le déplacement 𝑑𝑘 à l'instruction suivante :

𝑑𝑘 : Déplacer le disque du sommet de la tour 𝛼(𝑘) au sommet de la tour 𝛽(𝑘) (1)

où 𝛼 et 𝛽 sont des fonctions de ℕ∗ à valeurs dans 𝐸3 qui vérifient les conditions suivantes :
𝐜1 : Sur la tour numéro 𝛼(𝑘), est placé au moins un disque.
𝐜2 : La tour numéro 𝛽(𝑘) est vide ou le disque placé sur son sommet a un diamètre plus grand que
celui placé au sommet de la tour numéro 𝛼(𝑘).
L'instruction (ou déplacement) 𝑑𝑘 définie dans (1) dépend des fonctions 𝛼 et 𝛽. Il sera convenable dans
la suite de la noter 𝑑𝑘(𝛼, 𝛽). En se basant sur ces instructions, on obtient l'algorithme qu'on note
hanoi(𝛼, 𝛽, 𝑞) et qu'on décrit ci-dessous :

Algorithme hanoi(𝛼, 𝛽, 𝑞) :
• pour 𝑘 allant de 1 à 𝑞 faire
•• exécuter l'instruction 𝑑𝑘(𝛼, 𝛽)
Lorsque 𝑞 = 0, aucune instruction n'est exécutée et la situation initiale est conservée. L'exécution de
hanoi(𝛼, 𝛽, 𝑞) exige seulement la connaissance de 𝛼(𝑘) et 𝛽(𝑘) pour 𝑘 dans {1, … , 𝑞}. On note alors
𝑆𝑘(𝛼, 𝛽) la situation obtenue après exécution de l'algorithme hanoi(𝛼, 𝛽, 𝑘) pour tout 𝑘 dans ℕ. De
manière générale, une situation 𝐴 est juste un triplet de la forme (𝐴0, 𝐴1, 𝐴2 ), où 𝐴0, 𝐴1 et 𝐴2 sont des
parties de 𝐸𝑛. On note alors

𝑆𝑘(𝛼, 𝛽) = (𝑆𝑘0(𝛼, 𝛽), 𝑆𝑘1(𝛼, 𝛽), 𝑆𝑘2(𝛼, 𝛽)) . (2)

Par exemple, pour 𝑛 = 4 et 𝑎 = 0,

- la situation initiale est 𝑆0(𝛼, 𝛽) = (𝐸4, ∅, ∅) qui se traduit par le fait que tous les disques sont sur
la tour 𝑇0.
- si on pose (𝛼(1), 𝛽(1)) = (0, 2), (𝛼(2), 𝛽(2)) = (0, 1), (𝛼(3), 𝛽(3)) = (2, 1) et (𝛼(4), 𝛽(4)) = (0, 2),
alors 𝑆4(𝛼, 𝛽) = ({3}, {0, 1}, {2}) et cela se traduit par le fait que le disque 𝐷3 est sur la tour 𝑇0,
les disques 𝐷0 et 𝐷1 sont sur la tour 𝑇1 et le disque 𝐷2 est sur la tour 𝑇2.
Pour deux situations 𝐴 = (𝐴0, 𝐴1, 𝐴2 ) et 𝐵 = (𝐵0, 𝐵1, 𝐵2 ), on définit la situation 𝐴Δ𝐵 par :

𝐴Δ𝐵 = (𝐴0 Δ𝐵0, 𝐴1 Δ𝐵1, 𝐴2 Δ𝐵2 ) .

0 1 2
Enfin, pour 𝑢 dans 𝐸3 et 𝑘 dans ℕ, on note 𝑊𝑢, 𝑘 la situation définie par 𝑊𝑢, 𝑘 = (𝑊𝑢, 𝑘, 𝑊𝑢, 𝑘, 𝑊𝑢, 𝑘 ), où

𝑣
∅ si 𝑣 = 𝑢
𝑊𝑢, 𝑘={ (3)
{𝑘} sinon

pour tout 𝑣 dans 𝐸3.

 Sujet numéro 15 Agrégation Marocaine d'Informatique Page 3 sur 5
Épreuve de modélisation Année 2025

Remarque 1. Soit 𝑘 dans ℕ∗. D'après la condition 𝐜1, la tour 𝛼(𝑘) est non vide, c'est-à-dire que
𝛼(𝑘)
𝑆𝑘−1 (𝛼, 𝛽) ≠ ∅. Le passage de la situation 𝑆𝑘−1(𝛼, 𝛽) à 𝑆𝑘(𝛼, 𝛽) se fait en exécutant l'instruction
𝑑𝑘(𝛼, 𝛽) définie dans (1). Cela se traduit par :

𝑆𝑘(𝛼, 𝛽) = 𝑆𝑘−1(𝛼, 𝛽) Δ𝑊𝛾(𝑘), 𝑚(𝑘), (4)

𝛼(𝑘)
où 𝑚(𝑘) = min(𝑆𝑘−1 (𝛼, 𝛽)) et 𝛾(𝑘) est la valeur de 𝐸3 telle que 𝐸3 = {𝛼(𝑘), 𝛽(𝑘), 𝛾(𝑘)}. En d'autres
termes, on a

𝑆𝑘(𝛼, 𝛽) = 𝑆0(𝛼, 𝛽) Δ𝑊𝛾(1), 𝑚(1) Δ ⋯ ⋯ Δ𝑊𝛾(𝑘), 𝑚(𝑘) . (5)

Donc pour déterminer la situation 𝑆𝑘(𝛼, 𝛽), il suffit de connaître la situation initiale et les valeurs de
𝛾(𝑖) et de 𝑚(𝑖) pour 𝑖 = 1, … , 𝑘.

Le but de ce sujet est de déterminer des fonctions 𝑥 et 𝑦 convenables et faciles à calculer et un entier 𝑞 de
sorte que 𝑆𝑞(𝑥, 𝑦) soit la situation où tous les disques sont placés sur la tour 𝑇𝑏. Pour cela, on introduit
quelques fonctions intermédiaires. La première de ces fonctions est notée 𝑔 et elle est définie par :

𝑔(𝑘) = max({𝑖 ∈ ℕ : 2𝑖 divise 𝑘}) . (6)

Une manière simple de déterminer 𝑔(𝑘) est donnée par le résultat suivant :

Proposition 1. Pour 𝑘 dans ℕ∗, 𝑔(𝑘) est le résultat renvoyé par les instructions
i=0
while (k >> i)&1==0 : i=i+1
return i
Les instructions dans la Proposition 1 précédente sont écrites en langage de programmation Python.

La deuxième fonction notée ℎ𝑘, 𝑎, 𝑠 dépend de 𝑘 dans ℕ, 𝑠 dans 𝐸2 et de 𝑎 et elle est définie par :

ℎ𝑘, 𝑎, 𝑠(𝑖) = (𝑎 + (−1)𝑖+𝑠+1 (𝑘 >> 𝑖) + (−1)𝑖+𝑠 (𝑘 >> (𝑖 + 1))) % 3 (7)

pour tout 𝑖 dans ℕ. L'intérêt du paramètre 𝑠 sera vu à la fin de ce sujet. Le lien entre ℎ𝑘, 𝑎, 𝑠 et 𝑔 est
donné par la formule :

ℎ𝑘, 𝑎, 𝑠(𝑖) = (ℎ𝑘−1, 𝑎, 𝑠(𝑖) + (−1)𝑖+𝑠+1 𝛿𝑖, 𝑔(𝑘) ) % 3 (8)

pour 𝑘 dans ℕ∗ et 𝑠 dans 𝐸2, où 𝛿𝑖, 𝑗 est le symbole de Kronecker. Connaissant l'écriture en binaire de 𝑘 :
𝑚−1
𝑘 = 𝑏𝑘(𝑚 − 1) ⋯ 𝑏𝑘(0) = ∑ 𝑏𝑘(𝑢) 2𝑢,
𝑢=0

où 𝑏𝑘(0), … , 𝑏𝑘(𝑚 − 1) sont des bits dans 𝐸2 et 𝑚 un entier naturel tel que 𝑘 < 2𝑚, le résultat suivant
nous donne une forme simple de ℎ𝑘, 𝑎, 𝑠(𝑖) :

Proposition 2. Pour 𝑘 = 𝑏𝑘(𝑚 − 1) ⋯ 𝑏𝑘(0), 𝑠 dans 𝐸2 et 𝑖 dans ℕ, on a

𝑚−1
ℎ𝑘, 𝑎, 𝑠(𝑖) = (𝑎 + (−1)𝑖+𝑠 𝑏𝑘(𝑖) + ∑ (−1)𝑢+𝑠 𝑏𝑘(𝑢)) % 3. (9)
𝑢=𝑖

Maintenant, on utilise les fonctions 𝑔 et ℎ𝑘, 𝑎, 𝑠 pour définir les fonctions 𝑥𝑎, 𝑠 et 𝑦𝑎, 𝑠 :

𝑥𝑎, 𝑠(𝑘) = (ℎ𝑘−1, 𝑎, 𝑠(𝑔(𝑘))) % 3 (10.a)

𝑦𝑎, 𝑠(𝑘) = (ℎ𝑘, 𝑎, 𝑠(𝑔(𝑘))) % 3 (10.b)
 Sujet numéro 15 Agrégation Marocaine d'Informatique Page 4 sur 5
Épreuve de modélisation Année 2025

pour 𝑘 dans ℕ∗ et 𝑠 dans 𝐸2. Une manière simple d'obtenir les valeurs 𝑥𝑎, 𝑠(𝑘) et 𝑦𝑎, 𝑠(𝑘) directement à
l'aide de 𝑔 est donnée par le résultat suivant :

Proposition 3. Pour tout 𝑘 dans ℕ∗, on a

𝑥𝑎, 𝑠(𝑘) = (𝑎 + (−1)𝑠 𝑘 − (−1)𝑔(𝑘)+𝑠 ) % 3, (11.x)

𝑦𝑎, 𝑠(𝑘) = (𝑎 + (−1)𝑠 𝑘 + (−1)𝑔(𝑘)+𝑠 ) % 3 (11.y)

D'après ce denier résultat, on a 𝐸3 = {𝑥𝑎, 𝑠(𝑘), 𝑦𝑎, 𝑠(𝑘), 𝑧𝑎, 𝑠(𝑘)}, où

𝑧𝑎, 𝑠(𝑘) = (𝑎 + (−1)𝑠 𝑘) % 3 (12)

pour 𝑘 dans ℕ∗. En utilisant (9), nous obtenons

Proposition 4. Pour 𝑚 dans ℕ et 𝑠 dans 𝐸2, on a

ℕΔ𝐸𝑚 si 𝑢 = 𝑥𝑎, 𝑠(2𝑚 )

ℎ−1
2𝑚 −1, 𝑎, 𝑠({𝑢}) = ∅ si 𝑢 = 𝑦𝑎, 𝑠(2𝑚 ) (13)
{𝐸 𝑚 si 𝑢 = 𝑧𝑎, 𝑠(2𝑚 ) .

Le résultat suivant justifie la possibilité de déplacer un disque de la tour numéro 𝑥𝑎, 𝑠(𝑘) lorsque celle-ci
est non vide à la tour numéro 𝑦𝑎, 𝑠(𝑘).

Proposition 5. Pour 𝑘 dans ℕ∗ et 𝑠 dans 𝐸2, on a 𝐸𝑔(𝑘) ⊂ ℎ−1 −1

𝑘−1, 𝑎, 𝑠({𝑧𝑎, 𝑠(𝑘)}), ℎ𝑘−1, 𝑎, 𝑠({𝑥𝑎, 𝑠(𝑘)}) ≠ ∅
et 𝑔(𝑘) = min(ℎ−1 𝑘−1, 𝑎, 𝑠({𝑥𝑎, 𝑠(𝑘)})) En plus, l'une des conditions suivantes est vérifiée :
−1
→ ℎ𝑘−1, 𝑎, 𝑠({𝑦𝑎, 𝑠(𝑘)}) = ∅
→ ℎ−1 −1
𝑘−1, 𝑎, 𝑠({𝑦𝑎, 𝑠(𝑘)}) ≠ ∅ et 𝑔(𝑘) < min(ℎ𝑘−1, 𝑎, 𝑠({𝑦𝑎, 𝑠(𝑘)})).

Proposition 6. On a

ℎ−1
𝑘−1, 𝑎, 𝑠({𝑢}) si 𝑢 = 𝑧𝑎, 𝑠(𝑘)
ℎ−1
𝑘, 𝑎, 𝑠({𝑢}) ={ (14)
ℎ−1
𝑘−1, 𝑎, 𝑠({𝑢}) Δ{𝑔(𝑘)} sinon

pour 𝑘 dans ℕ∗, 𝑠 dans 𝐸2 et 𝑢 dans 𝐸3.

Le résultat suivant donne une description de la situation 𝑆𝑘(𝑥𝑎, 𝑠, 𝑦𝑎, 𝑠 ) :

Proposition 7. Pour tout 𝑘 dans 𝐸2𝑛 et tout 𝑠 dans 𝐸2, on a

𝑆𝑘𝑢(𝑥𝑎, 𝑠, 𝑦𝑎, 𝑠 ) = ℎ−1

𝑘, 𝑎, 𝑠({𝑢}) ∩ 𝐸𝑛 (15)

pour tout 𝑢 dans 𝐸3.

Il suffit alors faire les bons choix du paramètre 𝑠 dans 𝐸2 et de l'entier 𝑞 pour voir que les formules (13)
et (15) justifient le fait les disques 𝐷0, … , 𝐷𝑛−1 se sont déplacés de la tour numéro 𝑎 vers la tour numéro 𝑏
et cela après avoir exécuté l'algorithme hanoi(𝑥𝑎, 𝑠, 𝑦𝑎, 𝑠, 𝑞).
Sujet numéro 15 Agrégation Marocaine d'Informatique Page 5 sur 5
Épreuve de modélisation Année 2025

Suggestions pour le développement.

Soulignons qu'il s'agit d’un menu à la carte et que vous pouvez choisir d'étudier certains points, pas tous,
pas nécessairement dans l'ordre, et de façon plus ou moins fouillée. Vous pouvez aussi vous poser d'autres
questions que celles indiquées plus bas. Il est très vivement souhaité que vos investigations comportent
une partie traitée sur ordinateur et, si possible, des représentations graphiques de vos résultats.

Suggestion — 01 —
On pourra expliquer l'obtention des formules (4) et (5) puis les programmer pour l'obtention d'une
situation 𝑆𝑘(𝑥𝑎, 𝑠, 𝑦𝑎, 𝑠 ) pour 𝑘 dans 𝐸2𝑛.

Suggestion — 02 —
On pourra prouver la Proposition 1 puis tester la validité de cette proposition par un petit programme
qu'on applique à des à différentes valeurs de l'entier 𝑘.

Suggestion — 03 —
On pourra justifier la formule (9) puis tester sa validité par un petit programme qu'on applique à
des à différentes valeurs de l'entier 𝑘.

Suggestion — 04 —
On pourra prouver l'une des autres propositions et tester sa validité à l'aide d'un programme conve­
nable.

Suggestion — 05 —
On pourra déterminer la sortie de l'algorithme hanoi(𝑥𝑎, 𝑠, 𝑦𝑎, 𝑠, 2𝑚 − 1) pour différentes valeurs de 𝑚
dans 𝐸𝑛∗ et de 𝑠 dans 𝐸2 puis, à partir de ces tests, déterminer la valeur de 𝑠 pour laquelle les disques
𝐷0, … , 𝐷𝑚−1 se sont déplacés de la tour numéro 𝑎 à la tour numéro 𝑏.