[Chercher, Modéliser.
]
D’après bac S, Centres étrangers, 2017
L’arbre de Stern-Brocot a été découvert séparément par
le mathématicien allemand Moritz Abraham Stern (1858)
et par Achille Brocot (1861), horloger français qui l’a
utilisé pour concevoir des systèmes d’engrenages avec
un rapport entre rouages proche d’une valeur souhaitée.
Cet exercice aborde la méthode
avec des matrices carrées.
On considère les deux matrices
G=(1101) et
D=(1011).
On construit à partir d’une matrice initiale un arbre
descendant de la façon suivante : de chaque matrice
carrée
M de l’arbre partent deux nouvelles branches
vers les deux autres matrices
M×G (à gauche) et
M×D
(à droite). Ces deux nouvelles matrices sont appelées
les matrices filles de
M.
Dans la méthode considérée, on prend comme matrice
initiale la matrice
I=(1001).
1. Déterminer les deux matrices manquantes
A et
B dans la troisième ligne de l’arbre de Stern‑Brocot ci‑dessous.
Dans la suite de l’exercice, on admet que, pour toute
matrice
M=(abcd), de l’arbre de Stern‑Brocot, les
nombres
a,
b,
c et
d sont des entiers vérifiant :
b+d=0.
2. On associe à une matrice
M=(abcd) de l’arbre de
Stern‑Brocot la fraction
b+da+c.
Montrer que, dans cette association, le trajet
« gauche - droite - gauche », à partir de la matrice
initiale dans l’arbre, aboutit à une matrice
correspondant à la fraction
53.
3. Soit
M=(abcd) une matrice de l’arbre.
On rappelle que
a,
b,
c et
d sont des entiers.
On note
ΔM=ad−bc, la différence des produits
diagonaux de cette matrice.
a. Montrer que si
ad−bc=1, alors
d(a+c)−c(b+d)=1.
b. En déduire que si
M=(abcd) est une matrice de
l’arbre de Stern-Brocot telle que
ΔM=ad−bc=1, alors
ΔM×G=1, c’est‑à‑dire que la différence des produits diagonaux de la matrice
M×G est aussi égale à
1.
On admet de même que
ΔM×D=1, et que toutes les
autres matrices
N de l’arbre de Stern-Brocot vérifient
l’égalité
ΔN=1.
4. Déduire de la question précédente que toute fraction associée à une matrice de l’arbre de Stern‑Brocot est irréductible.
5. Soit
m et
n deux entiers naturels non nuls premiers entre eux. Ainsi, la fraction
nm est irréductible. On considère l’algorithme suivant.
Tant que (m=n) faire :
Si (m < n) :
Afficher « Gauche »
n←n−m
Sinon :
Afficher « Droite »
m←m−n
Fin Si
Fin Tant que
a. Recopier et compléter le tableau suivant.
Indiquer ce qu’affiche l’algorithme lorsqu’on le fait
fonctionner avec les valeurs
m=4 et
n=7.
b. Conjecturer le rôle de cet algorithme.
Vérifier à l’aide d’un calcul matriciel le résultat obtenu
avec les valeurs
m=4 et
n=7.