Corrigé de l’exercice « spé » du bac S Centres Étrangers 2017

dimanche 18 juin 2017
par  Alain BUSSER

Le sujet est lisible ici. Il se situe dans le prolongement de cet article. Dans le présent article, on va montrer comment refaire les manips avec Sofus, et notamment ses nouvelles fonctionnalités de calcul matriciel.

C’est Sofus en ligne qui a été utilisé pour les scripts de l’article. En particulier, la tortue de Sofus a été utilisée (hors sujet) pour tracer l’arbre de Stern-Brocot puis le parcourir.


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 et D (ci-dessous).
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 ×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.

Corrigé Sofus

Voici un « script » permettant d’enregistrer dans la mémoire de Sofus, les trois matrices G, D et I :

Note : Ces trois matrices n’auront pas le même statut dans la suite : G et D seront considérées comme des matrices constantes comme dans l’expression « multiplier par G », alors que la matrice I est variable : C’est elle qui sera multipliée par G ou D à chaque étape. La matrice I ne restera donc pas la matrice identité tout au long du script (elle ne restera même pas une matrice carrée tout au long de certains scripts).


1. Déterminer les deux matrices manquantes A et B (en rouge), dans la troisième ligne de l’arbre de Stern-Brocot ci-dessous.

image/svg+xml [1, 0] [0, 1] [1, 0] [1, 1] [1, 0] [2, 1] [1, 1] [1, 2] [1, 1] [0, 1] [2, 1] [1, 1] [1, 2] [0, 1]

On remarque que la matrice A s’obtient en multipliant la matrice I par G puis par D (parcours de l’arbre),

Corrigé

Voici un script permettant de la calculer (ce qui a été fait en rouge ci-dessus) :

Et la matrice B s’obtient en multipliant I d’abord par D et ensuite par G.


Dans la suite de l’exercice, on admet que pour toute matrice M de l’arbre de Stern-Brocot, la somme des coefficients de la seconde ligne est non nulle.
2. On associe à une matrice une fraction...

Passage par un vecteur

Comme le numérateur de la fraction est la somme des éléments de la première ligne de M et le dénominateur est la somme des éléments de la seconde ligne de M, ce sont les éléments du produit de M par le vecteur (1 ;1). Si on dessine l’arbre de Stern-Brocot avec les fractions :

puis on ajoute la multiplication par le vecteur :

et enfin la division de l’abscisse de ce vecteur par son ordonnée :

on obtient l’arbre de Stern-Brocot en version fractions. Ce n’est pas le choix de l’énoncé mais il lui est équivalent.


Montrer que, dans cette association, le trajet « gauche-droite-gauche » à partir de la matrice initiale dans l’arbre, aboutit à une matrice correspondant à la fraction 3/5.

Corrigé

Le trajet « gauche-droite-gauche » revient à multiplier I successivement par G, par D puis par G, et ensuite on le multiplie par le vecteur (1 ;1) pour avoir le numérateur et le dénominateur de la fraction obtenue :

Celle-ci est donc bien égale à 3/5.


3. Soit M une matrice de l’arbre ... On note ∆M = ad −bc, la différence des produits diagonaux de cette matrice.

Déterminant

La différence est notée Δ parce que c’est un déterminant (mathématiques). Sofus permet de vérifier expérimentalement que ce déterminant est toujours égal à 1 :


a. Montrer que si ad −bc = 1, alors d(a +c)−c(b +d) = 1.

Corrigé

En développant d(a +c)−c(b +d) on constate qu’il est égal à ad-bc :

Par conséquent si le premier est égal à 1, le second aussi, puisqu’ils sont égaux entre eux. Comme le déterminant de la matrice identité est égal à 1, on peut montrer par récurrence sur le parcours de l’arbre, qu’il en est de même pour toutes les matrices de l’arbre.


b.En déduire que si M est une matrice de l’arbre de Stern-Brocot telle que ∆M = 1, alors ∆M×G = 1, c’est-à-dire que la différence des produits diagonaux de la matrice M ×G est aussi égale à 1.

Corrigé

L’expression développée au (a) est justement le déterminant de M×G.

Ce résultat se généralise à un résultat hors programme : Le déterminant du produit de deux matrices, est égal au produit des deux déterminants. Or ici on multiplie M par G dont le déterminant est 1×1-0×1=1 et cette multiplication par G ne change donc pas le déterminant. Idem pour la multiplication par D, dont le déterminant est aussi égal à 1. Ce sont les résultats admis dans la suite de l’exercice.


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.

Corrigé

Du fait que ad-bc=1, il résulte d’après le théorème de Bachet-Bézout que a et c sont premiers entre eux. Or a et c sont les numérateur et dénominateur d’une fraction de l’arbre de Stern-Brocot. Cette fraction est donc irréductible.


5. Soit m et n deux entiers naturels non nuls premiers entre eux. Ainsi la fraction m/n est irréductible. On considère l’algorithme suivant.


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.

Corrigé

En modifiant le script précédent pour qu’au lieu d’afficher « gauche », on aille à gauche, on obtient l’affichage suivant :

Gauche
4/3
Droite
1/3
Gauche
1/2
Gauche
1

Ce qui correspond au tableau suivant :

Affichage Gauche Droite Gauche Gauche
m 4 4 1 1 1
n 7 3 3 2 1


b. 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.

Cet algorithme calcule le parcours de l’arbre de Stern-Brocot menant à une fraction donnée. On peut vérifier le résultat pour 4/7 avec le programme du début :

Mais aussi, avec la tortue :

De l’arbre aux cercles

On peut gonfler les branches de l’arbre comme celles d’un baobab, jusqu’à ce que les branches aient la forme de cercles. On obtient alors les cercles de Ford, qui sont tangents entre eux mais aussi à l’axe des abscisses :

Voici le script en CoffeeScript ayant fait ce dessin :

fs = nouvel Ensemble []
pour p dans [0..840]
    f = nouvelle Fraction p, 840
    fs.ajoute f
pour x dans fs.support
    dessineCercle 10+x.n/x.d*400,400-200/x.d/x.d,200/x.d/x.d,'red'

Il est à utiliser avec alcoffeethmique.

On voit, pour l’exemple de 4/7, que le trajet

  • commence par le disque 1 en haut à droite (départ commun à toutes les fractions, puisque c’est la racine de l’arbre) ;
  • part vers la gauche pour le disque 1/2 en bleu (c’est le seul « grand » disque tangent à 1 que l’on voit sur cette partie de la figure) ;
  • part ensuite vers la droite pour la fraction 2/3 (en bleu) ;
  • puis vers la gauche à nouveau pour la fraction 3/5 (en vert) ;
  • et enfin à nouveau vers la gauche pour aboutir à la fraction 4/7 (également en vert).

On peut donc dessiner les parcours de l’arbre par des ensembles de cercles tangents entre eux :

Les cercles de Ford pourraient s’inscrire dans les nouveaux programmes de Seconde, où il est question de programmation mais aussi de tangente à un cercle : Ces cercles sont en effet non seulement tangents entre eux, mais aussi tous tangents à l’axe des abscisses, comme le montre cet autre graphique où on en a représenté plus, qui suggèrent l’axe des abscisses :

Du point de vue de la géométrie hyperbolique dans le demi-plan de Poincaré, ce sont donc des horicycles tangents entre eux. Voir Jos Leys fait de l’art avec les cercles de Ford. Mais voici une variante où les cercles de Ford, vus ci-dessus, sont transformés en sphères de Ford :

Script pour les sphères de Ford

Voici le script ayant construit l’image ci-dessus, écrit en Povray :

#version 3.7;
#include "colors.inc"
camera {
 location  <0.0, 2.0, -1.0>
 direction 1.5*z
 right     x*image_width/image_height
 look_at   <0.5, 0.0,  0.0>
}
light_source {
 <0, 0, 0>
 color rgb <1, 1, 1>
 translate <-30, 10, -30>
}
sky_sphere {
 pigment {
 color <1,1,1>  }
}
#declare N = 66*2520;
#declare n = 0;
#while(n<=N)
#declare a = n;
#declare b = N;
#while(b>0)
        #declare c = b;
        #declare b = mod(a,b);
        #declare a = c;
#end
sphere {
 <2*n/N,0,a/N*a/N>, a/N*a/N
 texture {
   pigment {
     color Blue
   }
     finish {
        ambient .002
        diffuse .6
        specular .75
        roughness .001
        reflection .02
     }
 }
}
#declare n=n+1;
#end

Mais on peut aller encore plus loin : En rapetissant les cercles de telle manière qu’ils restent tangents à l’axe des abscisses mais ne soient plus tangents entre eux, on obtient ce genre de dessin :

Dans cet article on montre comment, en enroulant le segment tangent à tous les cercles, autour d’une cardioïde, on obtient le squelette de l’ensemble de Mandelbrot...


Bonus : L’exercice 4 du sujet Métropole-Réunion 2017

Il s’agissait de trouver des « triangles rectangles presque isocèles » c’est-à-dire des triplets pythagoriciens dont les deux premiers éléments sont des entiers consécutifs. Si (x,x+1,y) est un tel triplet, on a y²=2x²+2x+1 : Géométriquement, le problème consiste à trouver les points de coordonnées entières sur une hyperbole. Et, plus précisément, à les énumérer par un algorithme diophantien.

Voici comment on peut définir les matrices A et B de l’énoncé :

Ensuite, comme on a déterminé au début de l’exercice que les plus petites valeurs de (x,y) possibles sont (3,5), on itère l’affinité à partir de U=(3,5) :

Ce qui donne quelques exemples de triangles rectangles presque isocèles :

[20, 29]
[119, 169]
[696, 985]
[4059, 5741]
[23660, 33461]
[137903, 195025]
[803760, 1136689]
[4684659, 6625109]
[27304196, 38613965]
[159140519, 225058681]

Celui demandé dans l’exercice était (4059 ; 4060 ; 5741) : 4059²+4060²=32959081 et 5741²=32959081 aussi.

On constate que si on divise l’ordonnée de U par son abscisse, les quotients successifs tendent rapidement vers √2 :

1.45
1.4201680672268908
1.4152298850574712
1.4143877802414389
1.4142434488588336
1.4142186899487321
1.4142144421220264
1.414213713314032
1.414213588270462
1.4142135668163807

La raison de ceci est évoquée ici : On reparamètre l’équation de façon que les côtés de l’angle droit soient (x-1)/2 et (x+1)/2, et on tombe sur l’équation de Pell-Fermat x²-2y²=-1 qu’on peut résoudre avec l’identité de Brahmagupta.

Voir aussi cet article sur une autre équation diophantienne : On y retrouve l’idée de parcourir les points à coordonnées entières sur une hyperbole, sur lesquels l’identité de Brahmagupta définit une structure de groupe. Une autre structure de groupe, avec du degré 3 cette fois-ci, est décrite ici.


Post-scriptum : Les scripts de l’article :

Zip - 12 ko

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

lundi 24 juillet 2017

Publication

759 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

270 aujourd'hui
427 hier
2064650 depuis le début
15 visiteurs actuellement connectés