BCE Maths approfondies HEC ECS 2004Sujet et corrigé

Epreuve de maths approfondies - ECS 2004

Pas encore noté

Explorer les annales

BanqueBCE Année2004 FilièreECS MatièreMathématiques

Annales BCE ECS Mathématiques BCE ECS 2004 ECS Mathématiques Mathématiques 2004

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Source du document : annales-prepa.fr

Description

Annale de maths approfondies BCE HEC pour la filiere ECS, session 2004.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

BANQUE COMMUNE D'EPREUVES ECRITES POUR LE HAUT ENSEIGNEMENT COMMERCIAL

Concepteur : ECOLE DES HAUTES ETUDES COMMERCIALES

OPTION SCIENTIFIQUE

MATHEMATIQUES I

Vendredi 14 Mai 2004, de 8 h. à 12 h.

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.
Ils ne doivent faire usage d'aucun document : l'utilisation de toute calculatrice et de tout matériel électronique est interdite.
Seule l'utilisation d'une règle graduée est autorisée.

SUR LA TRANSMISSION DE MESSAGES

Le but de ce problème est de construire un système permettant de détecter et de corriger automatiquement des erreurs apparues lors de la transmission de messages binaires.
Dans tout le problème,

m, n, p

désignent des entiers naturels non nuls.

Partie I. L'opération $Δ$ sur les parties d'un ensemble

Dans cette partie on considère un ensemble

E = {e_1, …, e_n}

ayant

n

éléments.
La différence symétrique de deux parties quelconques

A

B

E

, notée

AΔB

, est l'ensemble des éléments de

E

qui appartiennent à l'une et pas à l'autre. On admet que l'opération

Δ

est commutative et associative.
On sait que pour toute partie

A

E

AΔ\emptyset = A, AΔA = \emptyset

Pour toutes parties

A

B

E

, on pose

d(A, B) = Card(AΔB)

a) Pour une partie $A$ de $E$ , déterminer $d(A, \emptyset)$ et $d(A, E)$ .
b) Montrer que pour toutes parties $A$ et $B$ de $E : d(A, B) = d(AΔB, \emptyset)$ .
On sait qu'on peut représenter une partie $A$ de $E$ par le $n$ -uplet $(x_1, \dots, x_n)$ en posant:

à∀i ∈ {1, …, n}, x_i = 1 si e_i appartient à A et 0 sinon

a) Les parties

A, B, AΔB

étant représentées respectivement par (

x_1, \dots, x_n

), (

y_1, \dots, y_n

) et (

z_1, \dots, z_n

), construire pour un entier

i

fixé appartenant à

{1, \dots, n}

, une table à deux lignes et deux colonnes donnant les valeurs de

z_i

en fonction des valeurs de

x_i

y_i

.
Comparer

z_i

|x_i - y_i|

.
b) Montrer que pour toutes parties

A

B

C

E

d(A, C) ⩽ d(A, B) + d(B, C)

Partie II. Une autre algèbre linéaire

On considère l'ensemble

𝕂 = {0, 1}

𝕄_(p, n)(𝕂)

désigne l'ensemble des matrices à

p

lignes et

n

colonnes dont les coefficients appartiennent à

𝕂

.
On définit sur

𝕂

l'addition

+ ˙

et la multiplication . à l'aide des tables suivantes :

+	0	1
0	0	1
1	1	0

.	0	1
0	0	0
1	0	1

On remarque que la multiplication sur

𝕂

est la multiplication des réels, que ces opérations sont associatives, commutatives et que la multiplication sur

𝕂

est distributive par rapport à l'addition sur

𝕂

; ces propriétés ne sont pas à démontrer.

On définit également :

la somme $A + ˙B$ de deux matrices $A = (a_(ij))_(1 ⩽ i ⩽ p; 1 ⩽ j ⩽ n)$ et $B = (b_(ij))_(1 ⩽ i ⩽ p; 1 ⩽ j ⩽ n)$ appartenant à $𝕄_(p, n)(𝕂)$ par :

ù A + ˙B = (c_(ij))_(1 ⩽ i ⩽ p; 1 ⩽ j ⩽ n), où c_(ij) = a_(ij) + ˙b_(ij)

le produit $ε.A$ d'une matrice $A = (a_(ij))_(1 ⩽ i ⩽ p; 1 ⩽ j ⩽ n)$ et d'un élément $ε$ appartenant respectivement à $𝕄_(p, n)(𝕂)$ et $𝕂$ par:

ε.A = (ε.a_(ij))_(1 ⩽ i ⩽ p; 1 ⩽ j ⩽ n)

le produit $A \times ˙B$ de deux matrices $A = (a_(ij))_(1 ⩽ i ⩽ p; 1 ⩽ j ⩽ n)$ et $B = (a_(ij))_(1 ⩽ i ⩽ n; 1 ⩽ j ⩽ m)$ appartenant respectivement à $𝕄_(p, n)(𝕂)$ et $𝕄_(n, m)(𝕂)$ , par :

ù A \times ˙B = (c_(ij))_(1 ⩽ i ⩽ p; 1 ⩽ j ⩽ m), où c_(ij) = a_(i1) \cdot b_(1j) + ˙\dots + ˙a_(in) \cdot b_(nj)

Pour toute matrice

A

appartenant à

𝕄_(p, n)(𝕂)

et toute colonne

X

appartenant à

𝕄_(n, 1)(𝕂)

, le produit

A \times ˙X

est ainsi bien défini.
On admet que la loi + ainsi définie sur

𝕄_(p, n)(𝕂)

est une opération commutative, associative, qu'elle admet un élément neutre à savoir la matrice nulle ayant

p

lignes et

n

colonnes et dont tous les éléments sont nuls;
on note

O

cette matrice et cela quelles que soient les valeurs de

n

p

.
On admet également que

\times ˙

est distributive par rapport à

+ ˙

.
Dans leur copie les candidats pourront omettre les points sur les signes + et × .
On remarque que pour toute matrice

A

appartenant à

𝕄_(p, n)(𝕂)

:
(

𝒢^') A + ˙O = A, A + ˙A = O

On appelle code toute partie non vide

𝒞

𝕄_(n, 1)(𝕂)

telle que :

\forall(x, y) \in 𝒞^2, x + ˙y \in 𝒞

On considère les quatre colonnes $x_1 = (1; 1; 0; 1; 0), x_2 = (1; 1; 1; 0; 0), x_3 = (0; 0; 1; 1; 0), x_4 = (1; 0; 0; 0; 0)$ appartenant à $𝕄_(5, 1)(𝕂)$ puis l'ensemble $𝒞 = {ε_1 ⋅ x_1 + ˙ε_2 ⋅ x_2 + ˙ε_3 ⋅ x_3 + ˙ε_4 ⋅ x_4, (ε_1, ε_2, ε_3, ε_4) ∈ 𝕂^4}$ .
a) Montrer que $𝒞$ est un code.

Déterminer tous les éléments de

𝒞

à l'aide de

x_1, x_2, x_4

.
b) Existe-t-il une famille (

u_1, u_2

) d'éléments de

𝒞

telle que

{ε_1 ⋅ u_1 + ˙ε_2 ⋅ u_2, (ε_1, ε_2) ∈ 𝕂^2}

soit égal à

𝒞

?
c) Montrer que:

ε_1 \cdot x_1 + ε_2 \cdot x_2 + ε_4 \cdot x_4 = O \Rightarrow ε_1 = ε_2 = ε_4 = 0

On dit qu'une famille

(u_1, \dots, u_q)

d'éléments de

𝕄_(p, n)(𝕂)

est

𝕂

-libre lorsque:

\forall(ε_1, \dots, ε_q) \in 𝕂^q, ε_1 \cdot u_1 + ˙\dots + ˙ε_q \cdot u_q = O \Rightarrow ε_1 = \dots = ε_q = 0

Dans le cas contraire, on dit que la famille

(u_1, \dots, u_q)

est

𝕂

-liée.
On dit qu'une famille (

u_1, \dots, u_p

) dont les éléments appartiennent à un code

𝒞

est une

𝕂

-base de

𝒞

lorsqu'elle est une famille

𝕂

-libre et lorsque pour tout élément

x

𝒞

il existe (

ε_1, \dots, ε_p

) appartenant à

𝕂^p

tel que

x = ε_1.u_1 + ˙\dots + ˙ε_p.u_p

.
(Dans leur copie, les candidats pourront omettre la lettre

𝕂

dans les expressions manipulées

𝕂

-libre,

𝕂

- base, sans en oublier le sens particulier.)
Dans la suite de cette partie

n

désignera un entier naturel supérieur ou égal à 2.
2) Pour tout

x = (x_1; ⋮; x_n)

y = (y_1; ⋮; y_n)

appartenant à

𝕄_(n, 1)(𝕂), d(x, y)

est le nombre d'entiers

i

appartenant à

{1, \dots, n}

tels que

x_i \neq y_i

.
a) Montrer que:

\forall(x, y) \in (M_(n, 1)(𝕂))^2, d(x, y) = d(x + ˙y, O)

.
b) Montrer que:

\forall(x, y, z) \in (M_(n, 1)(𝕂))^3, d(x, z) ⩽ d(x, y) + d(y, z)

.
3) Soit

𝒞

un code non réduit à

{O}

.
a) Montrer que

𝒞

admet une

𝕂

-base. On pourra considérer, après avoir justifié son existence, le cardinal maximum d'une famille

𝕂

-libre formée d'éléments de

𝒞

.
b) - Montrer que si (

u_1, \dots, u_p

) est une

𝕂

-base d'un code

𝒞

, alors tout élément de

𝒞

s'écrit de manière unique sous la forme

ε_1 \cdot u_1 + \dots + ε_p \cdot u_p

En déduire le cardinal de $𝒞$ en fonction du cardinal d'une de ses $𝕂$ -bases.
c) Montrer que toutes les $𝕂$ -bases de $𝒞$ ont le même cardinal.
d) On suppose que $p$ est le cardinal d'une $𝕂$ -base de $𝒞$ et que ( $v_1, \dots, v_p$ ) est une famille $𝕂$ -libre de $𝒞$ , montrer que ( $v_1, \dots, v_p$ ) est une $𝕂$ -base de $𝒞$ .

On suppose dans cette question que $1 ⩽ p ⩽ n$ et on note $I_p$ la matrice à $p$ lignes et $p$ colonnes dont tous les éléments sont nuls excepté les éléments diagonaux qui sont égaux à 1 .
On suppose également que $Q$ est une matrice appartenant à $𝕄_(p, n)(𝕂)$ telle que $p$ colonnes de $Q$ sont égales aux $p$ colonnes distinctes de $I_p$ .
On définit l'ensemble $𝒞_Q = {x ∈ 𝕄_(n, 1)(𝕂), Q × ˙x = O}$ .
a) Montrer que $𝒞_Q$ est un code.
b) Montrer que pour tout $(x_1, \dots, x_n)$ appartenant à $𝕂^n$ il existe une permutation $σ$ de ${1, \dots, n}$ telle que: $Q \times ˙(x_1; ⋮; x_n) = (I_p, P) \times ˙(x_(σ(1)); ⋮; x_(σ(n)))$ où $P$ est une matrice appartenant à $𝕄_(p, n - p)(𝕂)$ .
(Dans la notation habituelle d'une matrice par blocs utilisée ci-dessus, la $k$ -ième ligne de $(I_p, P)$ est formée de la $k$ -ième ligne de $I_p$ suivie de la $k$ -ième ligne de $P$ .)
c) En déduire le nombre d'éléments de $𝒞_Q$ et le cardinal d'une de ses $𝕂$ -bases.
d) On suppose dans cette sous-question que $Q$ est la matrice ( $B I_p$ ) où $B$ est une matrice appartenant à $𝕄_(p, n - p)(𝕂)$ . Montrer que les colonnes de la matrice $((I_(n - p))/B)$ constituent une base de $𝒞_Q$ .
e) Si $A$ est une partie non vide de $ℕ, MinA$ désigne le plus petit élément de $A$ .

On suppose que

r

est un entier strictement supérieur à 1 , que toute famille formée de

r - 1

colonnes de

Q

est une famille

𝕂

-libre de

𝕄_(p, 1)(𝕂)

et qu'il existe une famille

𝕂

-liée formée de

r

colonnes de

Q

. Montrer que dans ces conditions

r = Min{d(x, O), x ∈ 𝒞_Q∖{O}}

Partie III. Un code correcteur d'erreurs

Dans cette partie, on suppose que l'entier

p

est supérieur ou égal à 2 et on pose

n = 2^p - 1

. On considère une matrice

H

dont les colonnes sont les

n

éléments non nuls de

𝕄_(p, 1)(𝕂)

et on définit :

𝒞_H = {u ∈ 𝕄_(n, 1)(𝕂), H × ˙u = O}

Déterminer le cardinal des $𝕂$ -bases de $𝒞_H$ .
Montrer que: $Min{d(u, v), (u, v) ∈ 𝒞_H^2$ et $u \neq v} = 3$ .
Pour tout $v$ appartenant à $𝕄_(n, 1)(𝕂)$ , on définit $B_v = {u ∈ 𝕄_(n, 1)(𝕂), d(u, v) ⩽ 1}$ .
a) Déterminer le cardinal de $B_v$ .
b) Montrer que si $v$ et $w$ sont deux éléments distincts de $𝒞_H$ , alors $B_v \cap B_w = \emptyset$ .
c) Montrer que $⋃_(v \in 𝒞_H)B_v = 𝕄_(n, 1)(𝕂)$ .
Soit $z$ appartenant à $𝕄_(n, 1)(𝕂)∖𝒞_H$ .
a) Montrer qu'il existe un seul élément $v$ appartenant à $𝒞_H$ tel que $d(z, v) = 1$ ; cet élément $v$ est noté $Φ(z)$ .
b) Montrer qu'il existe un seul élément $e$ appartenant à $𝕄_(n, 1)(𝕂)$ tel que $d(e, O) = 1$ et $H \times ˙z = H \times ˙e$ . Comparer $Φ(z)$ et $z + e$ .
Dans cette question et dans celle-ci uniquement on suppose que $p = 3$ , donc $n = 7$ , et on choisit pour $H$ la matrice $H_1 = (1, 0, 1, 1, 1, 0, 0; 1, 1, 0, 1, 0, 1, 0; 1, 1, 1, 0, 0, 0, 1)$ .
matrice $H_1 = (1, 1, 0, 1, 0, 1, 0; 1, 1, 1, 0, 0, 0, 1)$ .
a) Montrer que $𝒞_(H_1)$ a pour K-base $(c_1, c_2, c_3, c_4)$ où $: c_1 = (1; 0; 0; 0; 1; 1; 1), c_2 = (0; 1; 0; 0; 0; 1; 1), c_3 = (0; 0; 1; 0; 1; 0; 1), c_4 = (0; 0; 0; 1; 1; 1; 0)$ .
b) On suppose qu'on veut transmettre (par sémaphore, radio ou internet ...) un message consistant en la suite de quatre symboles égaux à 0 ou $1 : η_1, η_2, η_3, η_4$ .
Au lieu de transmettre dans l'ordre ces quatre symboles, on calcule $y = η_1.c_1 + ˙η_2.c_2 + ˙η_3.c_3 + ˙η_4.c_4$ et ce sont les sept éléments de cette colonne qui sont transmis dans l'ordre (de haut en bas).
On suppose que les composantes de la colonne $y^*$ reçues sont dans l'ordre: $0, 1, 0, 0, 1, 1, 0$ et qu'il y a une seule erreur dans la transmission, c'est à dire qu'une seule composante de $y^*$ est fausse.

Déterminer la valeur exacte des quatre nombres

η_1, η_2, η_3, η_4

, (on utilisera le produit

H_1 x˙y^*

).
c) On suppose qu'ayant transmis une colonne

z

, appartenant à

𝒞_(H_1)

, on a reçu la colonne

z^*

comportant deux erreurs. Montrer que le calcul de

H_1 x˙z^*

permet de s'apercevoir qu'il y a effectivement des erreurs mais ne permet pas de connaître les deux composantes qui sont fausses.

Partie IV. Distinguere falsum vero

Dans cette partie on utilise les mêmes notations que dans la partie III, en particulier

p

est un entier naturel supérieur ou égal à 2 et

n = 2^p - 1

Pour tout $k$ appartenant à ${1, \dots, n}$ , on considère l'écriture de $k$ en base deux: $k = \sum_(i = 1)^p ε_(ik)2^(i - 1)$ et on prend alors pour matrice $H$ la matrice $H_2 = (ε_(ik))_(1 ⩽ i ⩽ p; 1 ⩽ k ⩽ n)$ .
On considère $n - p$ éléments $η_1, \dots, η_(n - p)$ appartenant à $𝕂$ . On veut transmettre le message formé par la ligne $(η_1, \dots, η_(n - p))$ . Comme dans la question précédente, on commence par calculer la colonne $y = η_1.d_1 + \dots + η_(n - p).d_(n - p)$ où ( $d_1, \dots, d_(n - p)$ ) est une base de $𝒞_(H_2)$ et c'est cette colonne qui est transmise.
On désigne le message reçu par la colonne $y^*$ et on suppose qu'il y a une seule erreur pendant la transmission.
On calcule alors $H_2 \times ˙y^* = (x_1; ⋮; x_p)$ et on pose $k = \sum_(i = 1)^p x_i 2^(i - 1)$ .
Montrer que l'erreur s'est produite à la composante numéro $k$ de $y$ .
On suppose dans cette question que $p = 3$ et $n = 7$ .
a) On pose :

d_1 = (1; 0; 0; 0; 0; 1; 1), d_2 = (0; 1; 0; 0; 1; 0; 1), d_3 = (0; 0; 1; 0; 1; 1; 0), d_4 = (0; 0; 0; 1; 1; 1; 1)

Déterminer la matrice

H_2

et montrer que (

d_1, d_2, d_3, d_4

) est une

𝕂

-base de

𝒞_(H_2)

b) Les deux célèbres mathématiciens Primus et Secundus concourent au calcul d'une nouvelle constante universelle qu'ils appellent

ζ

. Primus pense avoir trouvé les trois premiers chiffres significatifs

x, y

z

(en base dix) de

ζ

et s'empresse de les transmettre à Secundus. Afin de minimiser les risques d'erreur au cours de la transmission et de s'assurer la possibilité de les détecter et les corriger, Primus et Secundus adoptent la démarche suivante:

1^\circ

) Chacun des chiffres

0, \dots, 9

a été écrit en base deux à quatre positions. Ainsi 5 est représenté par 0101 et 9 par 1001. Donc le chiffre

x

est écrit

x_4 x_3 x_2 x_1, y

est écrit

y_4 y_3 y_2 y_1, z

est écrit

z_4 z_3 z_2 z_1

, ainsi par exemple

x = x_1 + x_2 \cdot 2 + x_3 \cdot 2^2 + x_4 \cdot 2^3

2^\circ

) Primus transmet les 3 colonnes :

x_1 \cdot d_1 + x_2 \cdot d_2 + x_3 \cdot d_3 + x_4 \cdot d_4, y_1 \cdot d_1 + y_2 \cdot d_2 + y_3 \cdot d_3 + y_4 \cdot d_4, z_1 \cdot d_1 + z_2 \cdot d_2 + z_3 \cdot d_3 + z_4 \cdot d_4

(

d_1, d_2, d_3

d_4

ont été définies ci-dessus et sont bien sûr connues de Secundus).
Évidemment Primus ne se trompe pas dans ses calculs mais la transmission est sujette à erreurs : on a constaté dans la pratique qu'il y a une erreur au plus par colonne transmise.
Secundus réceptionne une liste où les trois colonnes reçues sont écrites bout à bout, soit le message suivant:

111011010000110010111

Quel est probablement le nombre que Primus et Secundus semblent en fait sur le point de découvrir?
c) Secundus décide d'écrire un programme en Pascal qui permet de retrouver à partir des colonnes reçues les chiffres envoyés par Primus. Comment Secundus peut-il procéder?

Pas de description pour le moment

Commentaires• BCE Maths approfondies HEC ECS 2004

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...

Explorer les annales

Téléchargements

Description

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

BANQUE COMMUNE D'EPREUVES ECRITES POUR LE HAUT ENSEIGNEMENT COMMERCIAL

Concepteur : ECOLE DES HAUTES ETUDES COMMERCIALES

OPTION SCIENTIFIQUE

MATHEMATIQUES I

SUR LA TRANSMISSION DE MESSAGES

Partie I. L'opération Δ sur les parties d'un ensemble

Partie II. Une autre algèbre linéaire

Partie III. Un code correcteur d'erreurs

Partie IV. Distinguere falsum vero

Commentaires• BCE Maths approfondies HEC ECS 2004

Commentaires• BCE Maths approfondies HEC ECS 2004

Partie I. L'opération $Δ$ sur les parties d'un ensemble