Ly ée Carnot Samedi 2 avril 2005

ECS 4  Mathématiques
A. Troes h

Devoir Surveillé no 8

Exer i e (20 points)  Soit f l'endomorphisme de R3 [X ℄ déni par :

P 00 (0) (X 2

0
1 1
f (P ) = P (3) (0) (X 3 X2 2X ) 3X ) + 2XP (0) + 2P (0):
6 2

1. Vérier que la formule i-dessus dénit ee tivement un endomorphisme de R3 [X ℄.

2. Déterminer la matri e A = [f ℄B de f dans la base B = (1; X; X 2
; X 3 ) de R3 [ X ℄ .
3. Montrer que B 0 = (1; X; X (X 1); X (X 1)(X 2)) est une base de R3 [X ℄.
4. Exprimer la matri e de passage P de la base B à la base B0 .
5. Exprimer la matri e B B
= [f ℄ 0 de f dans la base B 0 .
6. Cal uler B n ; en déduire An .

Problème  Sur la transmission de messages (HEC 2004, option s ientique, mathématiques I)

Le but de e problème est de onstruire un système permettant de déte ter et de orriger 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 M sur les parties d'un ensemble (15 points)
Dans ette partie, on onsidère un ensemble E = fe1 ; : : : ; en g ayant n éléments. La diéren e symétrique de
deux parties quel onques A et B de E , notée A M B , est l'ensemble des éléments de E qui appartiennent à l'une
et pas à l'autre. On admet que l'opération M est ommutative et asso iative. On sait que pour toute partie A
de E :
A M ; = A;
M A = ;: A

Pour toutes parties A et B de E , on pose d(A; B ) = Card(A M B ).

1. (a) Pour toute partie A de E , déterminer d(A; ;) et d(A; E ).
(b) Montrer que pour toutes parties A et B de E : d(A; B ) = d(A M B; ;):
2. On sait qu'on peut représenter une partie A de E par le n-uplet (x1 ; : : : ; xn ) en posant :

8i 2 f1; : : : ; ng; xi = 1 si ei appartient à A, et 0 sinon.

(a) Les parties A, B , A M B étant représentées respe tivement par (x ; : : : ; xn ), (y ; : : : ; yn ) et (z ; : : : ; zn ),
1 1 1
onstruire pour un entier i xé appartenant à f1; : : : ; ng, une table à deux lignes et deux olonnes
donnant les valeurs de zi en fon tion des valeurs de xi et yi .
Comparer zi et jxi yi j.
(b) Montrer que pour toutes parties A, B et C de E , d(A; C ) 6 d(A; B ) + d(B; C ).

Partie II  Une autre algèbre linéaire (30 points)

On onsidère l'ensemble K = f0; 1g et Mp;n (K ) désigne l'ensemble des matri es à p lignes et n olonnes dont
les oe ients appartiennent. à K .
On dénit sur K l'addition + et la multipli ation
à l'aide des tables suivantes :
.
+ 0 1
0 1
0 0 1 0 0 0
1 1 0 1 0 1

On remarque que la multipli ation sur K est la multipli ation des réels, que es opérations sont asso iatives,
ommutatives et que la multipli ation sur K est distributive par rapport à l'addition sur K ; es propriétés ne
sont pas à démontrer.
On dénit également :

1
 .
 la somme A + B de deux matri es A = (ai;j )16i6p et B = (bi;j )1 i p 6 6 appartenant à Mp;n (K ) par :
1 6j6n 1 6j6n
. .
A + B = ( i;j )16i6p ; où i;j = ai;j + bi;j
1 6j6n
 le produit "
A d'une matri e A = (ai;j )16i6p et d'un élément appartenant respe tivement à Mp;n (K ) et
1 6j6n
K par :


" A = (" ai;j )16i6p

1 6j6n
.
 le produit A  B de deux matri es A = (ai;j )1 i p 6 6 et B = (bi;j )16i6n appartenant respe tivement à
1 6j6n 1 6j6m
Mp;n (K ) et Mn;m (K ), par :
. . .
A  B = ( i;j ) 6i6p ; 1 où i;j

= ai;1 b1;j +


+ ai;n
bn;j
1 6j6m
.
Pour toute matri e A appartenant à Mp;n (K ) et toute olonne X appartenant à Mn;1 (K ), le produit A  X
est ainsi bien déni. .
On admet que la loi + ainsi dénie sur Mp;n (K ) est une opération ommutative, asso iative, qu'elle admet un
élément neutre à savoir la matri e nulle ayant p lignes et n olonnes et dont tous les éléments . sont nuls ; on
note 0 ette matri
. e, et ela quelles que soient les valeurs de n et p. On admet également que  est distributive
par rapport à +.
Dans leur opie, les andidats pourront omettre les points sur les signes +. et . .
On remarque que pour toute matri e A appartenant à Mp;n (K ) : A + 0 = A; A + A = 0:
On appelle ode toute partie non vide C de Mn;1 (K ) telle que : 8(x; y ) 2 C 2 ; x + y 2 C :
0 1 0 1 0 1 0 1
1 1 0 1
B
B 1 C
C B
B 1 C
C B
B 0 C
C B
B 0 C
C
1. On onsidère les quatre olonnes x1 = B
B 0 C
C , x2 = B
B 1 C
C , x 3 = B
B 1 C
C, x 4 = B
B 0 C
C appartenant à
 1 A  0 A  1 A  0 A
0 0 0 0
. . .
M5;1 (K ), puis l'ensemble C = f"1
x1 + "2
x2 + "3
x3 + "4
x4 ; ("1 ; "2 ; "3; "4 ) 2 K g. 4

[(On pourra utiliser la notation C = Ve tK (x1 ; x2 ; x3 ; x4 ).)℄

(a) Montrer que C est un ode.
Déterminer tous les éléments de C à l'aide de x1 , x2 , x4 .
.
(b) Existe-t-il une famille (u1 ; u2 ) d'éléments de C telle que f"1
u1 + "2
u2 ; ("1 ; "2 ) 2 K 2 g soit égal à C ?
. .
( ) Montrer que : "1
x1 + "2
x2 + "4
x4 = 0 =) "1 = "2 = "4 = 0.
On dit qu'une famille (u1 ; : : : ; uq ) d'éléments de Mp;n (K ) est K -libre lorsque :
. .
8(" ; : : : ; "q ) 2 K
1
q

; "1 u 1 +


+ "q
uq = 0 =) " 1 =


= "q = 0:
Dans le as ontraire, on dit que la famille (u1 ; : : : ; uq ) est K -liée.
On dit qu'une famille (u1 ; : : : ; up ) dont les éléments appartiennent à un ode C est une K -base de C lorsqu'elle
est une famille K -libre et lorsque pour tout élément x de C , il existe ("1 ; : : : ; "p ) appartenant à K p tel que
. .


x = "1 x1 +


+ "p
xp :
(Dans leur opie, les andidats pourront omettre la lettre K dans les expressions manipulées K -libre, K -base,
sans en oublier le sens parti ulier.)
Dans la suite de ette partie, n désignera un entier naturel supérieur ou égal à 2.
0 1 0 1
x1 y1
2. Pour tout x =
B
 .. C
A et y =
B
 .. C
A appartenant à Mn; (K ), d(x; y ) est le nombre d'entiers i
. . 1

xn yn
appartenant à f1; : : : ; ng tels que xi 6= yi .
.
(a) Montrer que : 8(x; y ) 2 (Mn; (K )) ; d(x; y ) = d(x + y; 0).
1
2

(b) Montrer que : 8(x; y; z ) 2 (Mn; (K )) ; d(x; z ) 6 d(x; y ) + d(y; z ).

1
3

3. Soit C un ode non réduit à f0g.

(a) Montrer que C admet une K -base. On pourra onsidérer, après avoir justié son existen e, le ardinal
maximum d'une famille K -libre formée d'éléments de C .

2
 (b) i. Montrer que si (u1 ; : : : ; up ) est une K -base d'un ode C , alors tout élément de C s'é rit de manière
. .
unique sous la forme "1
u1 +


+ "p
up .
ii. En déduire le ardinal de C en fon tion du ardinal d'une de ses K -bases.
( ) Montrer que toutes les K -bases de C ont le même ardinal.
(d) On suppose que p est le ardinal d'une K -base de C et que (v1 ; : : : ; vp ) est une famille K -libre de C ,
montrer que (v1 ; : : : ; vp ) est une K -base de C .
4. On suppose dans ette question que 1 6 p 6 n, et on note Ip la matri e à p lignes et p olonnes dont tous
les éléments sont nuls ex eptés les éléments diagonaux qui sont égaux à 1.
On suppose également que Q est une matri e appartenant à Mp;n (K ) telle que p olonnes de Q sont
égales aux p olonnes distin tes de Ip .
.
On dénit l'ensemble CQ = fx 2 Mn;1 (K ); Q  x = 0g:
(a) Montrer que CQ est un ode.
0 existe
(b) Montrer qu'il 1 une permutation 0  de1f1; : : : ; ng telle que pour tout (x1 ; : : : ; xn ) appartenant à
x1 x(1)
B C B C
. .
P)   Mp;n
.. ..
Kn : Q  . A = (Ip . A, où P est une matri e appartenant à p (K ).
xn x(n)
(Dans la notation habituelle d'une matri e par blo s utilisée i-dessus, la k -ième ligne de (Ip P ) est
formée de la k -ième ligne de Ip suivie de la k -ième ligne de P .)
( ) En déduire le nombre d'éléments de CQ et le ardinal d'une de ses K -bases.
(d) On suppose dans ette sous-question que Q est la matrie (B Ip), où B est une matri e appartenant
à Mp;n p (K ). Montrer que les olonnes de la matri e
In p
B
onstituent une base de CQ .

(e) Si A est une partie non vide de N , min A désigne le plus petit élément de A.
On suppose que r est un entier stri tement supérieur à 1, que toute famille formée de r 1 olonnes
de Q est une famille K -libre de Mp;1 (K ) et qu'il existe une famille K -liée formée de r olonnes de Q.
Montrer que dans es onditions, r = minfd(x; 0); x 2 CQ n f0gg:
Partie III  Un ode orre teur d'erreurs (30 points)
Dans ette partie, on suppose que l'entier p est supérieur ou égal à 2 et on pose n = 2p 1. On onsidère une
matri e H dont les olonnes sont les n éléments non nuls de Mp;1 (K ) et on dénit :
.
CH = fu 2 Mn; (K ); H  u = 0g:
1

1. Déterminer le ardinal des K -bases de CH .

2. Montrer que : minfd(u; v ); (u; v ) 2 CH
2
et u 6= v g = 3.
3. Pour tout v appartenant à Mn;1 (K ), on dénit Bv = fu 2 Mn;1 (K ); d(u; v ) 6 1g.
(a) Déterminer le ardinal de Bv .
(b) Montrer que si v et w sont deux éléments distin ts de CH , alors Bv \ Bw = ;.
[
( ) Montrer que Bv = Mn;1 (K ).
v2CH
4. Soit z appartenant à Mn;1 (K ) n CH .
(a) Montrer qu'il existe un seul élément v appartenant à CH tel que d(z; v ) = 1 ; et élément v est noté
'(z ).
. .
(b) Montrer qu'il existe un seul élément e appartenant à Mn;1 (K ) tel que d(e; 0) = 1 et H  z = H  e.
.
Comparer '(z ) et z + e.
0 et dans elle- i uniquement
5. Dans ette question 1 on suppose que p = 3, don n = 7, et on hoisit pour H
1 0 1 1 1 0 0 0 1 0 1 0 1 0 1
la matri e H1  A: 1 0 0 0
= 1 1 0 1 0 1 0
B
B 0 C
C B
B 1 C
C B
B 0 C
C B
B 0 C
C
1 1 1 0 0 0 1
B
B 0 C
C B
B 0 C
C B
B 1 C
C B
B 0 C
C
(a) Montrer que CH1 a pour K -base ( 1 ; 2; 3; 4) , où B
1 =B 0 C
C, B
2 =B 0 C
C, B
3 =B 0 C
C, B
4 =B 1 C
C.
B
B 1 C
C B
B 0 C
C B
B 1 C
C B
B 1 C
C
 1 A  1 A  0 A  1 A
1 1 1 0

3
 (b) On suppose qu'on veut transmettre (par sémaphore, radio ou internet...) un message onsistant en
la suite de quatre symboles égaux à 0 ou. 1 : 1 , .2 , 3 , 4 .. Au lieu de transmettre dans l'ordre es
quatre symboles, on al ule y = 1
1 + 2
2 + 3
3 + 4
4 , et e sont les sept éléments de
ette olonne qui sont transmis dans l'ordre (de haut en bas). On suppose que les omposantes de la
olonne 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,
'est-à-dire qu'une seule omposante de y  est fausse. .
Déterminer la valeur exa te des quatre nombres 1 , 2 , 3 , 4 , (on utilisera le produit H1  y  ).
( ) On suppose qu'ayant transmis une olonne z appartenant à CH , on a reçu la olonne z  omportant
.
deux erreurs. Montrer que le al ul de H1  z  permet de s'aper evoir qu'il y a ee tivement des
erreurs mais ne permet pas de onnaître les deux omposantes qui sont fausses.

Partie IV  Distinguere falsum vero (25 points)

Dans ette partie on utilise les mêmes notations que dans la partie III, en parti ulier p est un entier naturel
supérieur ou égal à 2 et n = 2p 1.
X
p
1. Pour tout k appartenant à f1; : : : ; ng, on onsidère l'é riture de k en base deux : k = "i;k 2i 1
, et on
i=1
prend alors pour H la matri e H2 = ("i;k )1 i p66 .
1 6k6n
On onsidère n p éléments 1 ; : : : ; n p appartenant à K . On veut transmettre le message formé par
la ligne (1


n p ). Comme dans la question pré édente, on ommen e par al uler la olonne
. .
y = 1
d1 +


+ n p
dn p , où (d1 ; : : : ; dn p ) est une base de CH2 , et 'est ette olonne qui est
transmise. On désigne le message reçu par la0olonne 1 y et on suppose qu'il y a une seule erreur pendant
x1
B C
. X i 1 p
la transmission. On al ule alors H2  y  =  ... A, et on pose k = xi 2 .
xp i=1
Montrer que l'erreur s'est produite à la omposante numéro k de y .
2. On suppose dans ette question que p = 3 et n = 7.
(a) On pose : 0 1 0 1 0 1 0 1
1 0 0 0
B
B 0 C
C B
B 1 C
C B
B 0 C
C B
B 0 C
C
B
B 0 C
C B
B 0 C
C B
B 1 C
C B
B 0 C
C
d1 = B
B 0 C
C ; d2 = B
B 0 C
C ; d3 = B
B 0 C
C ; d4 = B
B 1 C
C :
B
B 0 C
C B
B 1 C
C B
B 1 C
C B
B 1 C
C
 1 A  0 A  1 A  1 A
1 1 0 1

Déterminer la matri e H2 et montrer que (d1 ; d2 ; d3 ; d4 ) est une K -base de CH2 .

(b) Les deux élèbres mathémati iens Primus et Se undus on ourent au al ul d'une nouvelle onstante
universelle qu'ils appelle  . Primus pense avoir trouvé les trois premiers hires signi atifs x, y et z
(en base dix) de  et s'empresse de les transmettre à Se undus. An de minimiser les risques d'erreur
au ours de la transmission et de s'assurer la possibilité de les déte ter et de les orriger, Primus et
Se undus adoptent la démar he suivante :
 Cha un des hires 0; : : : ; 9 a été é rit en base deux à quatre positions. Ainsi 5 est représenté par
0101 et 9 par 1001. Don le hire x est é rit x4 x3 x2 x1 , y est é rit y4 y3 y2 y1 , z est é rit z4 z3 z2 z1 ;
ainsi par exemple x = x1 + x2
2 + x3
22 + x4
23 .
 Primus. transmet. les 3. olonnes : . . . . . .




x1 d1 + x2 d2 + x3 d3 + x4 d4 ;




y1 d1 + y2 d2 + y3 d3 + y4 d4 ;


z1 d1 + z2 d2 + z3 d3 + z4 d4 :



(d1 , d2 , d3 et d4 ont été dénies i-dessus et sont bien sûr onnues de Se undus).
Évidemment Primus ne se trompe pas dans ses al uls mais la transmission est sujette à erreurs :
on a onstaté dans la pratique qu'il y a une erreur au plus par olonne transmise.
Se undus ré eptionne une liste ou les trois olonnes reçues sont é rites bout à bout, soit le message
suivant :
111011010000110010111:

Quel est probablement le nombre que Primus et Se undus semblent en fait sur le point de dé ouvrir ?
( ) Se undus dé ide d'é rire un programme en Pas al qui permet de retrouver à partir des olonnes
reçues les hires envoyés par Primus. Comment Se undus peut-il pro éder ?