Exercice 4

Sujet

Paul est face à un « mur» constitué de briques identiques issues d'un jeu de construction.
Ce mur, d'un seul tenant, est constitué de piles (comme par exemple le mur A ci-dessous).
Il effectue alors la manipulation suivante :
Il prend les briques de la première pile (la plus à gauche) et les distribue sur les piles suivantes en en posant une sur la deuxième pile, deux sur la troisième etc. jusqu'à épuiser les briques, en créant, si besoin est, de nouvelles piles. S'il constate qu'il ne lui reste plus assez de briques pour poursuivre le processus, il dépose malgré tout ces briques restantes sur la pile suivante.

Exemple :

Le mur A ci-dessous, est constitué de 24 briques réparties en quatre piles. Paul prend alors les 12 briques de la première pile puis pose 1 brique sur la deuxième pile, puis 2 briques sur la troisième pile, puis 3 briques sur la quatrième. Avec les six briques restantes, il crée une nouvelle pile constituée de 4 briques. Il lui reste alors 2 briques avec lesquelles il créé une dernière pile.
Après la manipulation il obtient le mur B à 5 piles ci-dessous.
Si Paul recommence l'opération à partir du mur B , en distribuant les cinq briques de la première pile, il obtient le mur C suivant.

Mur A

Mur B

Mur C

Dans la suite il sera pratique de représenter un mur par la liste des nombres entiers naturels correspondant aux nombres de briques de chacune des piles du mur, en les considérant de gauche à droite.

Ainsi le mur A est représenté par ( \(12,4,6,2\) ), le mur B par ( \(5,8,5,4,2\) ) et le mur C par ( \(9,7,6,2\) ).

Partie A :Deux caractéristiques décrivant l'évolution des murs lors de manipulations successives

Paul part du mur \(\mathrm{M}_{1}:(1,1,4)\).
Après plusieurs manipulations successives il obtient les murs
\(\mathrm{M}_{2}:(2,4) ; \mathrm{M}_{3}:(5,1) ; \mathrm{M}_{4}:(2,2,2) ; \mathrm{M}_{5}:(3,3) ; \mathrm{M}_{6}:(4,2) ; \mathrm{M}_{7}:(3,2,1)\) et \(\mathrm{M}_{8}:(3,3)\).
On pourra, pour décrire l'évolution de ce mur, utiliser la notation suivante :
\((1,1,4) \rightarrow(2,4) \rightarrow(5,1) \rightarrow(2,2,2) \rightarrow(3,3) \rightarrow(4,2) \rightarrow(3,2,1) \rightarrow(3,3)\).
Paul remarque alors que les murs \(\mathrm{M}_{5}\) et \(\mathrm{M}_{8}\) sont identiques et que, de ce fait, les manipulations suivantes donneront constamment la même séquence des 3 murs \(\mathrm{M}_{5} \mathrm{M}_{6} \mathrm{M}_{7}\) qui se répètera indéfiniment.
Paul a donc observé 2 phases dans l'évolution :

• une phase tout d'abord «anarchique », avec les 4 murs \(\mathrm{M}_{1}, \mathrm{M}_{2}, \mathrm{M}_{3}, \mathrm{M}_{4}\);
• puis une phase plus «régulière» avec la répétition des 3 murs \(\mathrm{M}_{5}, \mathrm{M}_{6}, \mathrm{M}_{7}\).

Il décide d'appeler latence le nombre de murs de la phase anarchique et période le nombre de murs de la séquence répétitive de la phase régulière. Le mur \((1,1,4)\) est donc de latence 4 et de période 3 .

1. Quelles sont la latence et la période du mur (9) qui n'est constitué que d'une pile de 9 briques?
2. Même question pour les murs \((4,5,2)\) et \((3,3,2)\).

Partie B la recherche des isomurs de longueur 4

Paul observe que dans l'évolution de certains murs le nombre de piles du mur change au cours des manipulations alors pour d'autres le nombre de piles ne change pas. Il décide d'appeler longueur d'un mur le nombre de piles de ce mur et isomur un mur dont la longueur ne change jamais au cours de manipulations successives.

1. 1Y a-t-il des isomurs parmi les murs des questions 1. et 2. de la partie A?

Dans toute la suite de l'exercice on s'intéresse aux murs de longueurs 4.

Soit un mur ( \(a, b, c, d\) ) de longueur 4 où \(a, b, c\) et \(d\) sont quatre entiers naturels non nuls.
2. a) À quelle condition nécessaire et suffisante sur l'entier \(a\) obtient-on, après une manipulation, un mur de longueur 4 ?
b) Écrire à l'aide de \(a, b, c\) et \(d\) le nouveau mur obtenu.
3. Montrer que si ( \(a, b, c, d\) ) est un isomur, alors il est de latence 0 et de période au plus 4 . Préciser les conditions nécessaires et suffisantes sur \(a, b, c, d\) pour pouvoir construire un tel mur.
4. Écrire, à l'aide de l'entier a, la forme d'un isomur de période 1.

Vérifier qu'il y a quatre isomurs de période 1 dont on dressera la liste.
5. Montrer qu'il existe des isomurs de période 2 et les écrire à l'aide des entiers \(a\) et \(b\). Écrire un algorithme permettant d'en dresser la liste. Combien y en a-t-il?
6. Existe-t-il des isomurs de période 3 ?
7. Combien y a-t-il d'isomurs de période 4 ?