Exercice 1 — L'arbre de Stern-Brocot

Sujet

I) Arbre de Stern-Brocot.

Définition : On appelle fraction médiante de deux fractions, la fraction qui est le quotient des numérateurs additionnés et des dénominateurs additionnés des deux fractions de départ. Pour des entiers \(\mathrm{a}, \mathrm{a}^{\prime}, \mathrm{b}, \mathrm{b}^{\prime}\) on note \(\frac{a}{b} \bigoplus \frac{a^{\prime}}{b^{\prime}}\) la médiante de \(\frac{a}{b}\) et \(\frac{a \prime}{b \prime}\). On a donc : \(\frac{a}{b} \bigoplus \frac{a^{\prime}}{b^{\prime}}=\frac{a+a \prime}{b+b \prime}\)

1. Calculer \(\frac{13}{3} \oplus \frac{7}{12}\) et \(\frac{37}{11} \oplus \frac{11}{37}\).
2. On part des deux fractions \(\frac{0}{1}\) et \(\frac{1}{0}\) (bien que 10 ne corresponde pas réellement à un nombre) et ensuite l'algorithme consiste à répéter pour chaque ligne l'instruction :
   Recopier la ligne précédente en insérant entre deux fractions consécutives leur fraction médiante.
   a) Complétez le tableau en annexe avec les premières étapes de cet algorithme.
   b) On peut visualiser cette construction par un arbre binaire que l'on appelle arbre de Stern-Brocot où on ne représente à chaque génération que les nouvelles fractions.
3. On observe sur ces exemples qu'une fraction médiante se trouve entre les deux fractions qui lui ont donné naissance. Prouvons-le :
   a) Justifier que : \(a^{\prime} b-a b^{\prime}>0\).
   b) En déduire que : \(\frac{a}{b}<\frac{a}{b} \bigoplus \frac{a^{\prime}}{b^{\prime}}<\frac{a^{\prime}}{b^{\prime}}\)

II) Une base pour écrire les fractions

On admet que toutes les fractions irréductibles positives apparaissent quelque part dans cet arbre.
Codage droite-gauche. On peut coder chaque fraction par un mot comportant uniquement les lettres D et G qui décrit le chemin qu'il faut suivre dans l'arbre en partant de \(1 / 1\) pour atteindre cette fraction en allant soit à gauche (G) soit à droite (D).

Exemples : 2/3 se code en GD, 3/2 en DG, 5/3 en DGD et DD correspond à 3/1.

1. À quelle fraction correspond le mot GGD?
2. Quel est le code qui correspond à la fraction \(7 / 3\) ? À la fraction \(1 / 7\) ?
3. Justifier que le code pour \(13 / 6\) commence par DDG. Déterminer son code complet.
4. Pour \(n\) entier naturel non nul on note \(A n\) le mot qui comporte \(n\) lettres avec des alternances droite-gauche, en commençant par la lettre D :
   \(A_{1}=\mathrm{D}, A_{2}=\mathrm{DG}, A_{3}=\mathrm{DGD}, A_{4}=\mathrm{DGDG}, A_{5}=\mathrm{DGDGD}, \ldots\)
   Donner les fractions qui correspondent aux mots \(A_{n}\) pour \(n\) allant de 1 à 8 .

III) Opérations sur le code et les fractions.

À un code on associe la fraction correspondante. Par exemple : DGD \(\mapsto 5 / 3\). On notera alors \(\mathcal{F}(\) DGD \()=5 / 3\). On considère alors deux opérations sur les mots M de code :
(1) On met un D au début du mot: \(\mathrm{M} \mapsto \mathrm{DM}\). (2) On échange les lettres D et G du mot: \(\mathrm{M} \mapsto \bar{M}\).

1. Compléter le tableau en annexe qui donne des exemples.
2. Pour un mot M , conjecturer les expressions de \(\mathcal{F}(\mathrm{DM})\) et \(\mathcal{F}(M)\) en fonction de \(\mathcal{F}(\mathrm{M})\).
3. En admettant ces conjectures, déterminer la relation de récurrence vérifiée par la suite ( \(x_{n}\) ) définie pour tout \(n \in \mathbb{N}\) * par \(x_{n}=\mathcal{F}\left(A_{n}\right)\) où \(A_{n}\) est défini à la question II. 4)