Bac S 2013 Spé Maths Amérique du Nord Exercice 2

Enoncé

Partie A

On considère l’algorithme suivant :

Bac S 2013 Spé Maths Amérique du Nord Exercice 2 2013-an-exo2s-1

Question 1

Faire fonctionner cet algorithme avec a = 13 et b = 4 en indiquant les valeurs des variables à chaque étape.

C’est parti ! Passons en revue les instructions de l’algorithme une par une afin de déterminer les valeurs que contiennent les variables a, b et c à chaque instant :

Bac S 2013 Spé Maths Amérique du Nord Exercice 2 2013-an-exo2s-2

Les trois première instructions de l’algorithme sont les instructions de déclaration des variables.

Ici, trois variables sont déclarées : a, b et c. Grâce à ces instructions, on sait que ces variables vont contenir des entiers naturels.

Au moment de la déclaration des variables, quelle valeur est stockée dans chacune d’entre elles ?  0 ?

Très bonne question ! Au moment de la déclaration des variables, aucune valeur n’y est stockée.

Commençons notre tableau de valeurs :

Variables a b c

Passons à la phase d’initialisation :

Bac S 2013 Spé Maths Amérique du Nord Exercice 2 2013-an-exo2s-3

C’est grâce à ces trois instructions que les variables a, b et c vont recevoir leur toute première valeur :

  • « Affecter à c la valeur  0 » : la variable c est initialisée avec la valeur  0 ;
  • « Demander la valeur de a » : l’algorithme attend que l’utilisateur saisisse la valeur avec laquelle il souhaite que la variable a soit initialisée. Ici, l’énoncé nous indique que a doit être initialisée avec la valeur 13 ;
  • « Demander la valeur de a » : de même que pour a, l’algorithme attend que l’utilisateur saisisse la valeur avec laquelle il souhaite que la variable b soit initialisée. Cette fois-ci, l’énoncé nous indique que b doit être initialisée avec la valeur 4.

Ainsi, notre tableau de valeurs peut être complété de la façon suivante :

Variables a b c
Initialisation 13 4  0

Passons à la phase de traitement :

Bac S 2013 Spé Maths Amérique du Nord Exercice 2 2013-an-exo2s-4

La phase de traitement consiste ici en une boucle « Tant que ». Cela signifie que les instructions qui sont contenues dans cette boucle doivent être déroulées tant que la condition invoquée (« a \geq b ») est vérifiée :

  • Premier passage dans la boucle : après l’initialisation des variables, a vaut 13 et b vaut 4 donc on a bien a \geq b d’où un premier passage dans la boucle :
    • « Affecter à c la valeur c + 1 » : c a été initialisé avec la valeur  0 . Après cette instruction, il vaut donc 0 + 1, soit 1 ;
    • « Affecter à a la valeur a - b » : a et b ont été initialisées respectivement avec les valeurs 13 et 4 donc, après cette instruction, a vaut 13 - 4 soit 9.

     
    La tableau de valeurs peut donc être complété de la façon suivante :

    Variables a b c
    Initialisation 13 4  0
    Traitement 9 4 1
  • Deuxième passage dans la boucle : après un premier passage dans la boucle « Tant que », a vaut désormais 9 et b vaut toujours 4. Donc la condition a \geq b est toujours vérifiée, d’où un deuxième passage dans la boucle :
    • « Affecter à c la valeur c + 1 » : après le premier passage dans la boucle, c valait 1. Après cette instruction, il vaut 1 + 1, soit 2 ;
    • « Affecter à a la valeur a - b » : après cette instruction, a vaut 9 - 4 soit 5.

     
    On peut donc à nouveau compléter notre tableau de valeurs :

    Variables a b c
    Initialisation 13 4  0
    Traitement 9 4 1
    5 4 2
  • Troisième passage dans la boucle : après un deuxième passage dans la boucle « Tant que », a vaut désormais 5 et b vaut toujours 4. Donc la condition a \geq b est toujours vérifiée, d’où un troisième passage dans la boucle :
    • « Affecter à c la valeur c + 1 » : après le deuxième passage dans la boucle, c valait 2. Après cette instruction, il vaut 2 + 1, soit 3 ;
    • « Affecter à a la valeur a - b » : après cette instruction, a vaut 5 - 4 soit 1.

     
    On peut donc à nouveau compléter notre tableau de valeurs :

    Variables a b c
    Initialisation 13 4  0
    Traitement 9 4 1
    5 4 2
    1 4 3

    Cette fois-ci, on peut voir que a est strictement inférieur à b donc la condition « a \geq b » n’est plus vérifiée. On ne passe donc plus dans la boucle.

Passons à la phase « Sortie ».

Dans la phase « Sortie », on ne fait qu’afficher les valeurs contenues dans les variables a et c à la sortie de la phase « Traitement ». Aucune modification n’est apportée aux valeurs contenues dans les variables.
 
On peut donc à nouveau compléter notre tableau de valeurs avec une dernière ligne :

Variables a b c
Initialisation 13 4  0
Traitement 9 4 1
5 4 2
1 4 3
Sortie 1 4 3

Au final, notre tableau est donc le suivant :

Variables a b c
Initialisation 13 4  0
Traitement 9 4 1
5 4 2
1 4 3
Sortie 1 4 3

Question 2

Que permet de calculer cet algorithme ?

Si on résume ce que fait cet algorithme, en particulier la phase « Traitement », il s’agit de soustraire b à a autant de fois que possible et de compter, à travers la variable c, le nombre de fois où cela a été possible.

Autrement dit, l’algorithme proposé répond à la question « Dans la variable a initiale, combien de fois y a-t-il b ? ». Cela ne vous rappelle-t-il rien ?

Si ! Ca me rappelle l’école primaire quand on m’expliquait comment faire une division !

Exactement :

Cet algorithme soustrait b à a autant de fois que possible et de compter, à travers la variable c, le nombre de fois où cela a été possible.

Autrement dit, il permet de calculer la division euclidienne de a par b. A la sortie de l’algorithme, c contient le quotient de la division de la valeur initiale de a par b et la valeur finale de a contient le reste de cette division.


Partie B

A chaque lettre de l’alphabet, on associe, grâce au tableau ci-dessous, un nombre entier compris entre 0 et 25.

Bac S 2013 Spé Maths Amérique du Nord Exercice 2 2013-an-exo2s-5

On définit un procédé de codage de la façon suivante :

  • Etape 1 : A la lettre que l’on veut coder, on associe le nombre m correspondant dans le tableau ;
  • Etape 2 : On calcule le reste de la division euclidienne de 9m + 5 par 26 et on le note p ;
  • Etape 3 : Au nombre p, on associe la lettre correspondante dans le tableau.

Question 1

Coder la lettre U.

Suivons consciencieusement le procédé de codage proposé par l’énoncé :

  • Etape 1 : La lettre U correspond à m = 20.
  • Etape 2 : 9m + 5 = 9 \times 20 + 5 = 185 et 185 = 7 \times 26 + 3 donc le reste de la division euclidienne de 185 par 26 vaut 3. Donc p = 3.
  • Etape 3 : Au nombre p, on associe la lettre D.
Donc, la lettre U se code en D.

Question 2

Modifier l’algorithme de la partie A pour qu’à une valeur de m entrée par l’utilisateur, il affiche la valeur de p, calculée à l’aide du procédé de codage précédent.

Le procédé de codage repose sur le reste p de la division euclidienne de 9m + 5 par 26.

Or, l’algorithme proposé au départ permettait notamment de déterminer le reste de la division euclidienne d’un nombre a par un nombre b et de stocker ce reste dans à la variable a à la sortie de la phase « Traitement ».

Ici, il s’agit donc de stocker dans p le reste de la division euclidienne de 9m + 5 par 26. Autrement dit :

  • p joue le rôle de a à ceci près que la valeur initiale de p n’est, non pas une valeur saisie par l’utilisateur, mais 9m + 5 ;
  • 26 joue le rôle de b ;
  • il faut introduire la variable m qui, elle, n’existait pas avant, et dans laquelle on va pouvoir stocker la valeur initiale saisie par l’utilisateur.
Et qui va jouer le rôle de c alors ?

Personne : c servait à stocker le quotient de la division de a par b. Or, le quotient est une grandeur inutile dans le procédé de codage donc, pas besoin de lui trouver de variable de remplacement !

Ainsi, l’algorithme doit être modifié de la façon suivante. Pour vous permettre de bien comprendre, j’ai placé les instructions « analogues » en parallèle :

Bac S 2013 Spé Maths Amérique du Nord Exercice 2 2013-an-exo2s-6

Partie C

Question 1

Trouver un nombre entier x tel que 9x \equiv 1 \quad [26].

Commençons par un rappel de cours :

a \equiv b \quad [n] \Leftrightarrow a - b \equiv 0 \quad [n]

Ici, cela donne donc :

9x \equiv 1 \quad [26] \Leftrightarrow 9x - 1 \equiv 0 \quad [26]

Or :

a \equiv 0 \quad [n] signifie que a est un multiple de n.

Ainsi, il faut trouver un entier x tel que 9x - 1 soit un multiple de 26. Or, le premier multiple de 26 auquel je pense, c’est 26 lui-même !

Or, 9x - 1 = 26 \Leftrightarrow 9x = 27 \Leftrightarrow x = 3. Donc x = 3 convient :

Or, 9 \times 3 - 1 = 26 et 26 est clairement un multiple de 26 donc x = 3 convient.

Question 2

Démontrer alors l’équivalence :

9m + 5 \equiv  p\quad [26] \Leftrightarrow m \equiv  3p -  15\quad  [26]

Allons-y lentement… mais sûrement ! On nous demande ici de démontrer une équivalence. Nous allons donc prouver un sens de l’équivalence, puis l’autre.

  • Preuve du sens direct : 9m + 5 \equiv  p\quad [26] \Rightarrow m \equiv  3p -  15\quad  [26]

On part de 9m + 5 \equiv  p\quad [26]. Or, je cherche à obtenir m \equiv  3p -  15\quad  [26] donc, ce que je me dis, c’est que je vais « passer le 5 de l’autre côté », comme ça, j’obtiendrai p-5 à droite, ce qui me permettra d’avoir 3p - 15 en multipliant par 3 :

9m + 5 \equiv  p\quad [26] \Rightarrow 9m \equiv p - 5\quad [26]

\Rightarrow 27m \equiv 3p - 15\quad [26]
OK et comment se débarrasse-t-on du 27 qui se trouve devant m alors ?

Pour ça, on va prouver que 27m \equiv m\quad [26]. Ainsi, on aura 27m \equiv 3p - 15\quad [26] et 27m \equiv m\quad [26]. Or :

Si a \equiv b\quad [n] et a \equiv c\quad [n], alors b \equiv c\quad [n].

Cela nous permettra d’en déduire que m \equiv 3p - 15\quad [26].

Prouvons donc que 27m \equiv m\quad [26]. Pour cela, retenez que :

Pour montrer que a \equiv b\quad [n], il suffit de montrer que a - b est un multiple de n, ce qui permet alors d’écrire que a - b \equiv 0\quad [n].

Ici, cela donne :

27m - m = 26m. Or, 26m est clairement un multiple de 26 donc 26m \equiv 0 \quad [26]. D’où 27m - m \equiv 0\quad [26] d’où 27m \equiv m\quad [26].

On peut alors conclure sur le sens direct :

Donc m \equiv  3p -  15\quad  [26].

  • Preuve du sens réciproque : m \equiv  3p -  15\quad  [26] \Rightarrow 9m + 5 \equiv  p\quad [26]

Cette fois-ci, à gauche, je pars de m et je veux obtenir 9m + 5 donc je vais multiplier par 9 puis ajouter 5 :

m \equiv  3p - 15\quad [26] \Rightarrow 9m \equiv 27p - 135\quad [26]

\Rightarrow 9m + 5 \equiv 27p - 130\quad [26]

Et cette fois-ci, on va prouver que 27p - 130 \equiv p\quad [26], ce qui entraînera que 9m + 5 \equiv p\quad [26] car :

Si a \equiv b\quad [n] et b \equiv c\quad [n], alors a \equiv c\quad[n].
Pour montrer que 27p - 130 \equiv p\quad [26], il suffit d’appliquer l’astuce que tu as mentionné plus haut, et donc de montrer que (27p - 130) - p est un multiple de 26 non ?

Exactement ! Je vois que ça commence à rentrer :

(27p - 130) - p = 26p - 130 = 26(p - 5) donc (27p - 130) - p est un multiple de 26 d’où (27p - 130) - p \equiv 0\quad [26]. On en déduit (27p - 130) \equiv p\quad [26].

Cela nous permet de conclure sur le sens réciproque :

Donc m \equiv  3p -  15\quad  [26] \Rightarrow 9m + 5 \equiv  p\quad [26].

Enfin, n’oubliez pas de conclure sur l’équivalence :

Finalement, 9m + 5 \equiv  p\quad [26] \Leftrightarrow m \equiv  3p -  15\quad  [26].

Question 3

Décoder alors la lettre B.

Décoder la lettre B, c’est trouver la lettre qui, après passage par les 3 étapes du procédé de codage, donne B.

Examinons donc chacune des 3 étapes de ce procédé « en partant de la fin » :

Etape 3 : Au nombre p, on associe la lettre correspondante dans le tableau.
En associant la lettre correspondante à p, on a obtenu B. Donc p vaut 1.
Etape 2 : On calcule le reste de la division euclidienne de 9m + 5 par 26 et on le note p ;
Ainsi, le reste de la division euclidienne de 9m + 5 par 26 vaut 1. Autrement dit, 9m + 5 \equiv 1\quad [26].
Etape 1 : A la lettre que l’on veut coder, on associe le nombre m correspondant dans le tableau ;

Reste donc à trouver m

Ah mais attends, on vient de nous faire montrer à la question précédente que 9m + 5 \equiv  p\quad [26] \Leftrightarrow m \equiv  3p -  15\quad  [26]. Est-ce qu’on ne pourrait pas s’en servir ?

Bien sûr que si ! C’est quelque chose qui doit vous venir immédiatement à l’esprit. Les exercices sont toujours construits à partir d’une certaine logique. Il vous incombe de comprendre cette logique. Ici, la question précédente n’a qu’un seul but : vous donner les moyens de déterminer m à partir d’un p donné. C’est exactement ce que l’on cherche à faire ici.

Or, d’après la question précédente, 9m + 5 \equiv  p\quad [26] \Leftrightarrow m \equiv  3p - 15\quad  [26], donc m \equiv  3 \times 1 - 15\quad  [26] \equiv  -12\quad  [26].

On en déduit :

Donc m + 12 \equiv 0\quad [26].
…donc m + 12 est un multiple de 26 !

Exact :

On en déduit que m + 12 est un multiple de 26, c’est-à-dire qu’il existe un entier k tel que m + 12 = k \times 26.

Essayons avec k = 1 :

En prenant k = 1, on obtient m + 12 = 26 soit m = 14.
Pourquoi ne pas prendre k = 2 ou k = -1 pour « changer un peu » ?

Bonne question ! Si on prend k = 2, on obtient m + 12 = 2 \times 26 = 52 soit m = 40. Or, m doit être compris dans les valeurs proposées par le tableau donc, il est forcément compris entre  0 et 25. Donc k = 2 ne convient pas. Je vous laisse essayer avec k = -1. Vous verrez qu’on obtient une valeur pour m qui n’est pas non plus comprise entre  0 et 25.

Bref, on peut conclure sur m :

14 \in [0 ; 25] donc la valeur 14 convient.

Reste à donner la lettre associée en se référant au tableau :

Donc, en décodant B, on obtient O.

Fin de l’épreuve du Bac S 2013 Spé Maths Amérique du Nord Exercice 2.

Exprimez vous!