Baccalauréat S Centres étrangers 13 juin 2017 - Correction Spécialité
Correction de l'exercice de 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.
- 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}$. La matrice gauche associée à la matrice $\begin{pmatrix}1&1\\1&2\end{pmatrix}$ est :
- 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$. $\begin{align*} d(a+c)-c(b+d)&=ad+dc-cb-cd \\
- 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$. On a $M\times G=\begin{pmatrix} a+c&c\\b+d&d\end{pmatrix}$
&=ad-bc \\
&=1
\end{align*}$
$\quad$
Ainsi :
$\Delta_{M\times G}=d(a+c)-c(b+d)$
D’après la question précédente, puisque $\Delta_M=1$ alors $\Delta_{M\times G}=1$.
$\quad$ - Déduire de la question précédente que toute fraction associée à une matrice de l'arbre de Stern-Brocot est irréductible. Pour toutes les matrices $N$ de l’arbre de Stern-Brocot on a $d(a+c)-c(b+d)=1$
- 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}$$ $\begin{array}{|c|c|c|c|c|c|}
- 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$. On peut émettre la conjecture suivante : « l’algorithme fournit le chemin à suivre à partir de la matrice unité pour obtenir une fraction $\dfrac{m}{n}$ donnée.»
\hline
\text{Affichage}&\phantom{\text{Gauche}}&\text{Gauche}&\text{Droite}&\text{Gauche}&\text{Gauche}\\
\hline
m&4&4&1&1&1\\
\hline
n&7&3&3&2&1\\
\hline
\end{array}$
$\quad$
En suivant ce chemin $GDGG$ on obtient les matrices suivantes :
$\begin{pmatrix} 1&0\\0&1\end{pmatrix}$ $\to \begin{pmatrix}1&0\\1&1\end{pmatrix}$ $\to \begin{pmatrix} 1&1\\1&2\end{pmatrix}$ $\to \begin{pmatrix}2&1\\3&2\end{pmatrix}$ $\to \begin{pmatrix}3&1\\5&2\end{pmatrix}$
La fraction associée à cette dernière matrice est $f=\dfrac{3+1}{5+2}=\dfrac{4}{7}$.
$B=\begin{pmatrix}1&1\\0&1\end{pmatrix}\times \begin{pmatrix}1&0\\1&1\end{pmatrix}=\begin{pmatrix}2&1\\1&1\end{pmatrix}$
$\quad$
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$.
$C=A\times G=\begin{pmatrix}2&1\\3&2\end{pmatrix}$
La fraction est donc $\dfrac{2+1}{3+2}=\dfrac{3}{5}$.
$\quad$
D’après le théorème de Bezout, cela signifie que $a+c$ et $b+d$ sont premiers entre-eux et donc que la fraction $\dfrac{a+c}{b+d}$ est irréductible.
$\quad$
- Vues: 24489