Olympiades Maths Orient 2023 Corrigé Exercices nationaux

Proposition de corrigé des
Olympiades nationales de mathématiques 2023 Orient
EXERCICES NATIONAUX
Exercice 1 : PLUS FORT!
1. Quelques exemples.
a. [5,6,7,8,4,3,2,1], score=3
b. [1,2,3] score=2
[1,3,2] score=1
[2,1,3] score=1
[2,3,1] score=1
[3,1,2] score=1
[3,2,1] score=0

2. def score(L,n):
s=0
for i in range(0,n-1):
if L[i+1]>L[i]:
s=s+1
return s

3. Le score minimal est 0 si tous les nombres sont rangés dans l’ordre décroissant (exemple :
[3,2,1])
Le score maximal est n-1 si tous les nombres sont rangés dans l’ordre croissant (exemple :
[1,2,3])
Alors tout score est un entier appartenant à [0;n-1].
yucefnohra@gmail.com

1

4. a. Soit a0, a1, a2, ..., an des nombres rangés dans l’ordre croissant.
[a0, an, an-1, an-2, ..., a1] score=1
[a0, a1, an, an-1, an-2, ..., a2] score=2
[a0, a1, a2, an, an-1, an-2, ..., a3] score=3

[a0, a1, a2, a3, ...,an-4, an-3, an, an-1, an-2] score=n-2
Donc quelque soit l’entier k appartenant à [1;n-2], il existe une liste de longueur n et de score
k.
b. oui, par exemple : [a0, an, an-1, an-2, ..., a1] score=1 et [an, an-1, an-2, ..., a2, a0, a1] score=1.

5. Ln(0)=1, c’est lorsque tous les nombres sont rangés dans l’ordre décroissant.
Ln(n-1)=1, c’est lorsque tous les nombres sont rangés dans l’ordre croissant.

6. Une relation de récurrence
a. L3(0)=1, L3(1)=4, L3(2)=1 (question 1.b)
[4, 3, 1, 2] score=1 ou bien [3, 1, 4, 2] score=1.
b. [4, 3, 2, 1] score=0
c. Cherchons L4(1) :
Parmi les listes de longueur 3 et de score 1, on ajoute le nombre 4 comme ci-dessous:
Soit au début de la liste, soit entre les nombres rouges .
[4, 1, 3, 2], [1, 4, 3, 2], [4, 2, 1, 3], [2, 1, 4, 3], [4, 2, 3, 1], [2, 4, 3, 1], [4, 3, 1, 2], [3, 1, 4, 2],
Parmi les listes de longueur 3 et de score 0, on ajoute le nombre 4 comme ci-dessous:
4 occupe les positions 2, 3 et 4.
[3, 4, 2, 1], [3, 2, 4, 1], [3, 2, 1, 4].
yucefnohra@gmail.com

2

Alors L4(1) = 11.
Or, 2L3(1) + 3L3(0) = 2×4 + 3×1 = 11
D’où, L4(1) = 2L3(1) + 3L3(0).
d. Comme expliqué dans la question précédente, il suffit d’ajouter aux listes de longueur n et
de score 1, le nombre n+1, soit au début de la liste soit entre les 2 nombres (rouges) qui
ont généré le score 1. Alors le nombre de ces listes sera multiplié par 2.
Et on ajoute à la liste de longueur n et de score 0, le nombre n+1 aux positions de 2 à n+1,
donc le nombre de ces listes sera n+1-2+1=n.
D’où : Ln+1(1)=2Ln(1) + nLn(0)
e. Prenons un exemple de L8(3) et un autre de L8(2) :
[5, 6, 7, 8, 4, 3, 2, 1] de score 3
Si on ajoute 9, et pour garder le score 3, on doit l’insérer soit avant les nombres qui ont
générer +1 (donc avant 6 ou 7 ou 8 c’est-à-dire 3 possibilités) soit au début (1 possibilité).
Au total il y a 4 possibilités. En généralisant, pour que le score d’une liste Ln reste k, il y a
k+1 possibilités d’insérer le nombre n+1.
[8, 5, 6, 7, 4, 3, 2, 1] de score 2
Pour passer à un score de 3 en ajoutant 9, il ne faut pas le mettre au début (sinon, le score
reste 2) ni avant 6 ou 7 qui ont généré le score 2 (sinon, le score reste 2). Alors on peut
insérer le 9 avant 5, 4, 3, 2, 1 ou à la fin. Au total il y a 9 – 3 = 6 possibilités. En généralisant,
pour que le score d’une liste Ln passe de k-1 à k, il y a (n+1)-k possibilités.
D’où, Ln+1(k) = (k+1)Ln(k) + (n+1-k)Ln(k-1)

f.
yucefnohra@gmail.com

3

Exercice 2: UNE DESCENTE INFINIE
Partie 1.
1. P(‫ݔ( = )ݔ‬-r1)(‫ݔ‬-r2) = ‫ ݔ‬2 + (-r1-r2)‫ ݔ‬+ r1r2.
Par identification : b = -r1-r2 et c = r1r2.
2. c ≥ 0 donc r1 et r2 sont de même signe. Or b ≤ 0, alors r1 ≥0 et r2 ≥0.

Partie 2.
1. a. (‫ ݔ‬1, ‫ ݔ‬2, ‫ ݔ‬3) est solution de (E) donc ‫ ݔ‬12 + ‫ ݔ‬22 + ‫ ݔ‬32 = α‫ ݔ‬1 ‫ ݔ‬2 ‫ ݔ‬3, ce qui implique que
‫ ݔ‬1 ‫ ݔ‬2 ‫ ݔ‬3 ≥ 0, par suite ‫ ݔ‬1 ‫ ݔ‬2 ‫ ݔ‬3 = |‫ ݔ‬1| × |‫ ݔ‬2| × |‫ ݔ‬3|.
Or, ‫ ݔ‬12 + ‫ ݔ‬22 + ‫ ݔ‬32 = |‫ ݔ‬1|2 × |‫ ݔ‬2|2 × |‫ ݔ‬3|2
D’où, (|‫ ݔ‬1|,|‫ ݔ‬2|,|‫ ݔ‬3|) est solution de (E).
b. |‫ ݔ‬1|,|‫ ݔ‬2| et |‫ ݔ‬3| sont des entiers naturels. Donc si (‫ ݔ‬1 , ‫ ݔ‬2 , ‫ ݔ‬3) est solution de (E)
alors il existe un triplet d’entiers naturels aussi solution de (E).
2. Si (‫ ݔ‬1 , ‫ݔ‬2 , ‫ ݔ‬3) est solution de (E) alors (‫ ݔ‬2 , ‫ ݔ‬1 , ‫ ݔ‬3) est aussi solution de (E)
(commutativité de l’addition et de la multiplication).
3. D’après les questions 1. et 2. de cette partie, il existe un triplet d’entiers naturels
(‫ ݔ‬2 , ‫ ݔ‬1 , ‫ ݔ‬3) solution de (E) où l’on peut permuter l’ordre des composantes dans l’ordre
croissant.

Partie 3.
1. ‫ ݔ‬1 ∈ IN, donc ‫ ݔ‬1 ≥ 0. Or ‫ ݔ‬1 ne peut pas être égal à 0 car si oui, on aura
‫ ݔ‬12 + ‫ ݔ‬22 + ‫ ݔ‬32 = α‫ ݔ‬1 ‫ ݔ‬2 ‫ ݔ‬3 = 0. Ce qui entraîne ‫ ݔ‬22 + ‫ ݔ‬32 = 0 c’est-à-dire ‫ ݔ‬22 = ‫ ݔ‬32 = 0 . Ce
qui est impossible car (‫ ݔ‬2 , ‫ ݔ‬1 , ‫ ݔ‬3) ≠ (0,0,0).
2. a. (‫ ݔ‬1,‫ ݔ‬2,‫ )ݕ‬solution de (E) ⇔ ‫ ݔ‬12 + ‫ ݔ‬22 + ‫ݕ‬2 = α‫ ݔ‬1 ‫ ݔ‬2 ‫ݕ‬
⇔ ‫ݕ‬2 - α‫ ݔ‬1 ‫ ݔ‬2 ‫ ݕ‬+ ‫ ݔ‬12 + ‫ ݔ‬22 = 0 ⇔ ‫ ݕ‬est racine de Q.
b. ‫ ݔ‬2 - α‫ ݔ‬1 ‫ ݔ‬2 ‫ ݔ‬+ ‫ ݔ‬12 + ‫ ݔ‬22 = 0, donc ‫ ݔ‬2+ ‫ݔ‬12 +‫ ݔ‬22 = α‫ ݔ‬1 ‫ ݔ‬2 ‫ݔ‬. Alors ‫ ݔ=ݔ‬3 est racine de Q.
c. (3 - α‫ ݔ‬1)‫ ݔ‬22 + (‫ ݔ‬12 – ‫ ݔ‬22) = 3 ‫ ݔ‬22 - α‫ ݔ‬1 ‫ ݔ‬22 + ‫ ݔ‬12 – ‫ ݔ‬22 = 2 ‫ ݔ‬22 - α‫ ݔ‬1 ‫ ݔ‬22 + ‫ ݔ‬12.
Or, Q(‫ ݔ‬2) = ‫ ݔ‬22 - α‫ ݔ‬1 ‫ ݔ‬22 + ‫ ݔ‬12 + ‫ ݔ‬22 = 2 ‫ ݔ‬22 - α‫ ݔ‬1 ‫ ݔ‬22 + ‫ ݔ‬12.
D’où, Q(‫ ݔ‬2) = (3 - α‫ ݔ‬1)‫ ݔ‬22 + (‫ ݔ‬12 – ‫ ݔ‬22) .
De plus, 0 < ‫ ݔ‬1 ≤ ‫ ݔ‬2 implique que ‫ ݔ‬12 – ‫ ݔ‬22 ≤ 0. Et ‫ ݔ‬1 ≥ 1 avec α ≥ 4  3 - α‫ ݔ‬1 < 0.
Par suite, Q(‫ ݔ‬2) < 0.
d. Q(0) = ‫ ݔ‬12 + ‫ ݔ‬22 > 0.
yucefnohra@gmail.com

4

e. Q(‫ ݔ = )ݔ‬2 - α‫ ݔ‬1 ‫ ݔ‬2 ‫ ݔ‬+ ‫ ݔ‬12 + ‫ ݔ‬22 est du second degré et n’est pas une identité
remarquable. En plus, Q(‫ )ݔ‬admet une racine ‫ ݔ‬3 alors il admet une autre racine distincte
‫ݕ‬.

donc 0<‫ ݔ<ݕ‬2<‫ ݔ‬3.
f. ‫ݔݕ‬3 =
2

௖
௔
2

= ‫ ݔ‬12 + ‫ ݔ‬22  ‫= ݕ‬

‫ݔ‬1 + ‫ݔ‬2 +

௫భమ ା௫మమ

௫య
మ
(௫భ ା௫మమ )మ
2
2
2
‫ݔ = ݕ‬1 + ‫ݔ‬2 +
௫యమ
௫భమ ା௫మమ
ఈ௫భ ௫మ ௫య

=

௫య

×

௫య

=

(௫భమ ା௫మమ )(௫యమ ା௫భమ ା௫మమ )
௫యమ

=

(௫భమ ା௫మమ )ఈ௫భ ௫మ ௫య
௫యమ

= ‫ × ݕ‬α‫ ݔ‬1 ‫ ݔ‬2 = α‫ ݔ‬1 ‫ ݔ‬2 ‫ݕ‬

D’où, (‫ ݔ‬1 , ‫ ݔ‬2 , ‫ )ݕ‬est solution de (E).
De plus ‫ ݕ‬+ ‫ ݔ‬3 = -

௕
௔

= α‫ ݔ‬1 ‫ ݔ‬2 où α, ‫ ݔ‬1, ‫ ݔ‬2 et ‫ ݔ‬3 sont des entiers naturels donc ‫ ݕ‬l’est

aussi.
3. (‫ ݔ‬1 , ‫ ݔ‬2 , ‫ )ݕ‬est solution de (E). Et puisqu’on peut permuter les composantes pour avoir
toujours une solution de (E), alors (‫ ݔ‬1 , ‫ ݕ‬, ‫ݔ‬2) est solution de (E). Donc d’après le
raisonnement de la question 2. On obtient Q(‫ < )ݕ‬0.
4. Q(‫ = )ݕ‬0 et Q(‫ < )ݕ‬0, ce qui est impossible. Par suite, le seul triplet appartenant à Z
Z3
solution de (E) est (0,0,0).
5. Soit Pn la proposition suivante : ‫ ݔ‬12 + ‫ ݔ‬22 + ... + ‫ ݔ‬n2 = α‫ ݔ‬1 ‫ ݔ‬2.....‫ ݔ‬n n’admet que (0,0,...,0)
comme n-uplet d’entiers relatifs. On a démontré que P3 est vraie.
Supposons que ça reste vrai jusqu’à l’ordre n et démontrons que Pn+1 est vraie c’est-à
dire que :
yucefnohra@gmail.com

5

‫ ݔ‬12 + ‫ ݔ‬22 + ... + ‫ ݔ‬n2 + ‫ ݔ‬n+12 = α‫ ݔ‬1 ‫ ݔ‬2.....‫ ݔ‬n ‫ ݔ‬n+1 n’admet que (0,0,...,0) comme (n+1)-uplet
d’entiers relatifs.
Puisque (‫ ݔ‬1, ‫ ݔ‬2,....,‫ ݔ‬n)=(0,0,...,0)  ‫ ݔ‬n+1=0  Pn+1 est vraie.

Exercice 3 : CODES DÉTECTEURS ET CORRECTEURS.
Question préliminaire.
1. On procède par disjonction des cas (k et k’ appartiennent à ZZ):
a est pair et b est pair : donc, a=2k et b=2k’  a+b=2(k+k’) qui est pair.
a est impair et b est impair : donc, a=2k+1 et b=2k’+1  a+b=2(k+k’) qui est pair.
a est pair et b est impair (ou vice versa): donc, a=2k et b=2k’+1  a+b=2(k+k’)+1 qui est
impair.
Par suite, a+b est pair ssi a et b sont de même parité.
Codage d’un message.
2. a. M=1+0×2+0×4+1×8=9
b. (0,1,0,1) M=0+1×2+0×4+1×8=10
(1,1,1,1) M=1+1×2+1×4+1×8=15
c. Non, le maximum est 15
d. De 0 à 15.
Codage d’un message avec protection contre les erreurs.
3. Principe du bit de parité.
a. 1+0+0+1=2 pair  ‫=ݕ‬0
b. 1+1+0+1=3 impair  ‫ ݕ‬doit être 1 et non 0  information corrompue
c. Si un seul bit est faux, on détecte une altération mais on ne peut pas la localiser.
Si deux bits sont faux, dans ce cas la somme ne va pas changer de parité et donc on ne
peut pas détecter une altération.
4. Principe des bits de contrôle.
a. 1+0+0=1 impair  ‫ݕ‬1=1
0+0+1=1 impair  ‫ݕ‬2=1
1+0+1=2 pair  ‫ݕ‬3=0
b. 1+1+0=2 pair  ‫ݕ‬1=0
1+0+1=2 pair  ‫ݕ‬2=0
1+0+1=2 pair  ‫ݕ‬3=0, ce qui n’est pas le cas. Donc il y a altération.
yucefnohra@gmail.com

6

c. Notons S1=‫ ݔ‬1+‫ ݔ‬2+‫ ݔ‬3, S2=‫ ݔ‬2+‫ ݔ‬3+‫ ݔ‬4, S3=‫ ݔ‬1+‫ ݔ‬3+‫ ݔ‬4
Si un seul bit est erroné:

si les parités de S1 et S3 ne correspondent plus à celles de ‫ݕ‬1 et ‫ݕ‬3 , alors ‫ ݔ‬1 est faux

si les parités de S2 et S3 ne correspondent plus à celles de ‫ݕ‬2 et ‫ݕ‬3 , alors ‫ ݔ‬4 est faux

si les parités de S1 et S2 ne correspondent plus à celles de ‫ݕ‬1 et ‫ݕ‬2 , alors ‫ ݔ‬2 est faux

si les parités de S1, S2 et S3 ne correspondent plus à celles de ‫ݕ‬1, ‫ݕ‬2 et ‫ݕ‬3 , alors ‫ ݔ‬3
est faux
Si deux bits sont erronés:

conclusion:

si la parité de S1 ne correspond plus à celle de ‫ݕ‬1 , alors ‫ ݔ‬3 et ‫ ݔ‬4 sont faux

si les parités de S1 et S3 ne correspondent plus à celles de ‫ݕ‬1 et ‫ݕ‬3 , alors ‫ ݔ‬2 et ‫ ݔ‬4 sont
faux

si la parité de S3 ne correspond plus à celle de ‫ݕ‬3 , alors ‫ ݔ‬2 et ‫ ݔ‬3 sont faux

si les parités de S1 et S2 ne correspondent plus à celles de ‫ݕ‬1 et ‫ݕ‬2 , alors ‫ ݔ‬1 et ‫ ݔ‬4 sont
faux

si la parité de S2 ne correspond plus à celle de ‫ݕ‬2 , alors ‫ ݔ‬1 et ‫ ݔ‬3 sont faux

si les parités de S2 et S3 ne correspondent plus à celles de ‫ݕ‬2 et ‫ݕ‬3 , alors ‫ ݔ‬1 et ‫ ݔ‬2 sont
faux

yucefnohra@gmail.com

7