200 CITVR – LUNDI AU VENDREDI - Ville de Saint

C ONTRÔLE N°2
28/11/14
TS3 & TS4
Exercice 1 :
En montagne, un randonneur a effectué des réservations dans deux types d’hébergements :
L’hébergement A et l’hébergement B.
Une nuit en hébergement A coûte 24 e et une nuit en hébergement B coûte 45 e.
Il se rappelle que le coût total de sa réservation est de 438 e.
On souhaite retrouver les nombres x et y de nuitées passées respectivement en hébergement A et en hébergement B
1.
(a) Montrer que les nombres x et y sont respectivement inférieurs ou égaux à 18 et 9.
(b) Recopier et compléter les lignes (1), (2) et (3) de l’algorithme suivant afin qu’il affiche les couples (x ; y) possibles.
Entrée :
Traitement :
x et y sont des nombres
Pour x variant de 0 . . .
(1)
Pour y variant de 0 . . . (2)
Si . . .
(3)
Afficher x et y
Fin Si
Fin Pour
Fin Pour
Fin traitement
2. Justifier que le coût total de la réservation est un multiple de 3.
3. Restitution organisée de connaissance.
On rappelle le théorème de B ÉZOUT :
Deux entiers relatifs non nuls a et b sont premiers entre eux si et seulement si il existe deux entiers
relatifs u et v tels que au + bv = 1.
(a) En prenant pour pré-requis l’identité de B ÉZOUT, que vous citerez, démontrez le théorème de B ÉZOUT ci-dessus.
(b) Justifier que l’équation
8x + 15y = 1
(1)
admet pour solution au moins un couple d’entiers relatifs, puis proposer une solution de cette équation.
(c) Déterminer alors toutes les solutions entières de l’équation (1).
4. En déduire les solutions de l’équation :
8x + 15y = 146
où x et y sont des nombres entiers relatifs.
5. Le randonneur se souvient avoir passé au maximum 13 nuits en hébergement A.
Déterminer alors le nombre exact de nuits passées en hébergement A et celui des nuits passées en hébergement B.
F IGURE 1 – Etienne B ÉZOUT (1730 - 1783)
1
(2)
Exercice 2 :
Étienne veut réaliser une feuille de calculs sur un tableur qui permet de déterminer le PGCD de deux nombres a et b ainsi
que les coefficients u et v associés à l’identité de B ÉZOUT.
Pour ce faire, il a préparé le travail suivant :
Dans un premier temps, Étienne ne se soucie pas de voir apparaitre sur sa feuille de calcul des messages d’erreurs du type
"Division par 0" ou bien du texte inutile.
1. Algorithme D ’E UCLIDE :
La feuille de calculs est prévue pour qu’un utilisateur saisisse les valeurs de a et b dans les cellules A5 et B5.
Quelles formules, à recopier vers le bas, Étienne doit-il saisir dans les cellules C5, D5, A6 et B6 ?
2. Coefficients de B ÉZOUT :
Notons respectivement (a n ), (b n ), (q n ) et (r n ) les "suites" des nombres formés dans les colonnes A, B, C et D à partir de
la ligne 5. Ainsi les "suites" (a n ) et (b n ) sont initialisées à a 0 = a et b 0 = b.
On définit alors les suites (u n ) et (v n ) permettant de déterminer les coefficients de B ÉZOUT par :

 u0
u
 1
u n+2
=
=
=
1
0
u n − u n+1 × q n+1
et

 v0
v
 1
v n+2
=
=
=
0
1
v n − v n+1 × q n+1
Ces deux suites sont construites de telle sorte que pour tout entier naturel n,
r n = a u n+2 + b v n+2
Quelles formules, à recopier vers le bas, Étienne doit-il saisir dans les cellules F5 et G5 ?
3. Une fois la feuille de calculs réalisée, Étienne la teste avec les valeurs indiquées sur la copie d’écran :
a 0 = 561
et
b 0 = 180
Sachant que le dernier reste non nul apparait à la ligne 8, indiquer sur quelle ligne apparaissent les coefficients de
l’identité de B ÉZOUT.
4. (Question bonus)
Étienne veut maintenant modifier sa feuille de calculs afin qu’il n’y ait pas de message d’erreur ou de texte inutile.
Quelles formules doit-il saisir ?
2
É LÉMENTS DE C ORRECTION :
C ONTRÔLE N°2
Corrigé de l’exercice 1 :
1. x et y sont des entiers naturels tels que 24x + 45y = 438, par conséquent :
438
= 18,25, donc x 6 18 ;
24
438
≈ 9,73, donc y 6 9.
• 45y 6 438 d’où y 6
45
• 24x 6 438 d’où x 6
2. Voici l’algorithme complété :
Entrée :
Traitement :
x et y sont des nombres
Pour x variant de 0 à 18
(1)
Pour y variant de 0 à 9 (2)
Si 24x + 45y = 438 (3)
Afficher x et y
Fin Si
Fin Pour
Fin Pour
Fin traitement
3. Le coût total de réservation étant de 438 €, et 438 étant égal à 146 × 3, ce montant est multiple de 3 !
4.
(a) Les entiers 8 et 15 étant premiers entre eux, le théorème de Bézout entraîne l’existence d’un couple (x ; y) d’entiers
relatifs tels que 8x + 15y = 1.
(b) On a de façon évidente 8 × 2 + 15 × (−1) = 1, le couple (2 ; −1) est donc une solution particulière.
(c) On a 8 × 2 + 15 × (−1) = 1, donc, en multipliant par 146 :
8 × 292 + 15 × (−146) = 146.
Soit (x ; y) un autre couple solution de (E), alors :
8x + 15y = 8 × 292 + 15 × (−146) ⇐⇒ 8(x − 292) = 15(−y + 146).
(1)
15 et 8 sont premiers entre eux et 15 divise 8(x − 292), donc, d’après un théorème de Gauss, 15 divise x − 292.
Il existe donc un entier relatif k tel que x −292 = 15k. La relation (1) entraîne alors que 8×15k = 15(−y +146), d’où
y = −146 − 8k.
Les couples solutions sont donc de la forme (292 + 15k ; −146 − 8k).
Réciproquement, de tels couples sont bien solutions de (E) car :
8(292 + 15k) + 15(−146 − 8k) = 146.
©
ª
L’ensemble des solutions de (E) est donc (292 + 15k ; −146 − 8k) où k ∈ Z .
5. Soit x et y le nombre de nuitées passées respectivement dans les hébergements A et B, alors 24x + 45y = 438 ⇔ 8x +
15y = 146. Il existe alors un entier relatif k tel que x = 292 + 15k, et par ailleurs x > 0 et x 6 13, d’où :
0 6 292 + 15k 6 13 ⇐⇒ −
292
279
6k 6−
.
15
15
292
279
≈ −19,47 et −
= −18,6, la seule possibilité est que k = −19.
15
15
On en déduit que x = 292 + 15 × (−19) = 7 et que y = −146 − 8 × (−19) = 6.
Ce randonneur a donc passé 7 nuits en hébergement A et 6 nuits en hébergement B.
Comme −
3

Download Report