Baccalauréat S Centres étrangers 13 juin 2017 - Spécialité
Spécialité 5 points
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 = \begin{pmatrix}1&0\\1&1\end{pmatrix}$ et $D = \begin{pmatrix}1&1\\0&1\end{pmatrix}$.
On construit un arbre descendant à partir d'une matrice initiale, de la façon suivante : de chaque matrice carrée $M$ de l'arbre partent deux nouvelles branches vers les deux autres matrices $M \times G$ (à gauche) et $M \times 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 = \begin{pmatrix}1&0\\0&1\end{pmatrix}$.
- 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 = \begin{pmatrix}a&c\\b&d\end{pmatrix}$ de l'arbre de Stern- Brocot, les nombres $a$, $b$, $c$, $d$ sont des entiers vérifiant : \\ $b + d \ne 0$. - On associe à une matrice $M = \begin{pmatrix}a&c\\b&d\end{pmatrix}$ de l'arbre de Stern-Brocot la fraction $\dfrac{a + c}{b + d}$. Montrer que, dans cette association, le trajet « gauche-droite-gauche » à partir de la matrice initiale dans l'arbre, aboutit à une matrice correspondant à la fraction $\dfrac{3}{5}$.
- Soit $M = \begin{pmatrix}a&c\\b&d\end{pmatrix}$ une matrice de l'arbre. On rappelle que $a$, $b$, $c$, $d$ sont des entiers. On note $\Delta_M = ad - bc$, la différence des produits diagonaux de cette matrice.
- Montrer que si $ad - bc = 1$, alors $d(a + c) - c(b + d) = 1$.
- En déduire que si $M = \begin{pmatrix}a&c\\b&d\end{pmatrix}$ est une matrice de l'arbre de Stern-Brocot telle que $\Delta_M = ad-bc = 1$, alors $\Delta_{M\times G} = 1$, c'est-à-dire que la différence des produits diagonaux de la matrice $M \times G$ est aussi égale à $1$. On admet de même que $\Delta_{M \times D} = 1$, et que toutes les autres matrices $N$ de l'arbre de Stern-Brocot vérifient l'égalité $\Delta_N = 1$.
- Déduire de la question précédente que toute fraction associée à une matrice de l'arbre de Stern-Brocot est irréductible.
- Soit $m$ et $n$ deux entiers naturels non nuls premiers entre eux. Ainsi la fraction $\dfrac{m}{n}$ est irréductible. On considère l'algorithme suivant $$\begin{array}{|l |l |}\hline \text{ VARIABLES : }& m \text{ et } n \text{ sont des entiers naturels non nuls et premiers entre eux }\\ \text{ TRAITEMENT : }& \text{ Tant que }m \neq n \text{ , faire} \\ &\hspace{1cm}\text{ Si } m < n \\ &\hspace{2cm} \text{ Afficher « Gauche » }\\ &\hspace{2cm} n \text{ prend la valeur } n - m \\ &\hspace{1cm} \text{ Sinon } \\ & \hspace{2cm}\text{ Afficher « Droite » }\\ & \hspace{2cm} m \text{ prend la valeur } m - n \\ \hline \end{array} $$
- 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$. $$ \begin{array}{|c|c|c|c|c|c|}\hline \text{Affichage } & &\ldots&\ldots&\ldots&\ldots\\ \hline m &4 &\ldots &\ldots &\ldots&\ldots\\ \hline n &7 &\ldots &\ldots &\ldots&\ldots\\ \hline \end{array}$$
- Conjecturer le rôle de cet algorithme. Vérifier par un calcul matriciel le résultat fourni avec les valeurs $m = 4$ et $n = 7$.
- Vues: 26160