X Maths PC 2000

ÉCOLE POLYTECHNIQUE
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2000 FILIÈRE PC

PREMIÈRE COMPOSITION DE MATHÉMATIQUES

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

***

On se propose d'étudier une famille de polynômes (polynômes de Krawtchouk) et 
une famille de
matrices (matrices d'adjacence du schéma d'association de Hamming) dont les 
propriétés sont
liées, et applicables àla théorie des codes détecteurs et correcteurs d'erreurs 
dans la transmission
de l'information. (Ces applications ne sont pas abordées dans le problème.)

Les deuæ premières parties sont indépendantes.

***

Dans tout le problème, N désigne un entier naturel non nul.

On prend par convention O! = 1. Si n et le sont des entiers naturels, on pose

Première partie

1. Pour tout k EUR Z, on définit le polynôme 901EUR de la variable X par

1 . .
ËÎ H (X--z) Slk>0
'09'5k--1
"(X): 1 sik=0
0 sik<0. Évaluer (pk (j) pour chaque entier naturel j. 2. Pour tout entier n tel que 0 S n S N, on définit le polynôme Pn de la variable X par N Pn(X) = Z(--1)kflPk(X)fin--k(N -- X)- k=0 a) Calculer P0, P1 et P2. b) Calculer le degré et le coefficient dominant du polynôme Pn. c) Montrer que, pour chaque entier j tel que 0 5 j S N, . " j N --j ... = 2<--1>k(k)(n_k) .

k=0

3. Pour tout entier j tel que 0 5 j 5 N, on considère la fonction fj de la 
variable réelle u,
définie par

N
W) = 2 BMW .
n=0
Montrer que fj(u) = (1 -- u)j(1 + u)N_Ï . \

4. On considère la fonction F de deux variables réelles u et v, définie par

N
F(u,v) = 2 = 2 (N)P(j)Q(J') .

j=0 3

3.) Montrer que < | > est un produit scalaire sur RN [X ]

b) Montrer que (Pn)05ng N est une base orthogonale de R N [X ] muni de ce 
produit scalaire.

2

6. Montrer que, pour tout entier ... tel que 1 5 m 5 N -- 1,
(m + 1)Pm+1(X) -- (N -- 2X)P...(X) + (N -- m+ 1)Pm_1(X) = () .

du '

[On calculera de deux manières différentes le coefficient de um dans (l -- u2)

Deuxième partie

On pose E = {l, 2, . . . , N } et l'on désigne par 'P(E) l'ensemble des parties 
de E. Pour chaque
partie I de E, on note CardI le cardinal de I. Si I et J sont des parties de E, 
on pose

d(I, J) = Card(I A J) ,

où I A J est l'ensemble des points de la réunion I U J qui n'appartiennent pas 
à l'intersection
I D J.

7.a) À quelle condition a--t-on d(I , J ) = 0? À quelle condition a--t-on d(I , 
J) = 1 ?
b) Montrer que d(I A J, I) = Card J.

8. Soient I et J deux parties de E. On pose d(I , J ) = k. Calculer le nombre 
fy'-° de parties A
de E telles que d(I,A) = 1 et d(J, A) = j.

Troisième part ie

On utilise dans cette partie les notations et les résultats des deux premières 
parties.

On suppose 'P(E) muni d'un ordre total _-5. On a donc P(E) = {11,12,.... ,12N} 
où
115125...512N.

Pour tout entier naturel n, on définit une matrice carrée réelle à 2N lignes

An : ((An)pq)lsp52N par

15q52N
1 si d(I ,I ) = n
(An)pq : {O . p q
s1non.

On note ] la matrice identité à 2N lignes.
9.a) Que vaut An pour n > N ? Expliciter A0.

b) Montrer que pour tout entier m tel que 1 5 m 5 N -- 1,
A1Am = (N -- m + 1)A...-1 + (m + 1)Am+1 .

1
10. On pose A : 5(NJ -- A1). Montrer par récurrence sur n que, pour tout entier 
n tel que
0 S n S N,
A" = P,,(A) ,

où les polynômes Pn sont ceux définis et étudiés dans la première partie.

11. Soit i un entier tel que 0 S i S N. Montrer que, si I E P(E) est tel que 
Card] : i, alors
pour tout entier j tel que 0 5 j 5 N,

Pj(i)= Z (_1)Card(IñJ)_

JE'P(E)
Card J=j

12.a) Soient I, J, K E P(E). Montrer que

(_1)Card((mJ)nK) : (_1)Card(InK)(_1)Card(JñK) .

b) Soient I, J E P(E). Montrer que

2 (_1)Card(IñK)(_l)card(_jnK) : 2N si I : J
KGP(E) 0 sinon .

13. Pour tout entier k tel que 0 5 k 5 N, on pose

1 N
Bk = ëÏ\Ï Z Pk(n)An .
n=0

a) Montrer que

(Bk)2=Bk
BkBg=0 SiË%k.

[On pourra utiliser les résultats des questions 11. et 12.].
b) Déterminer la trace et le rang de chaque matrice Bk.
14.3) Pour chaque entier n tel que 0 S n S N, trouver les valeurs propres de la 
matrice A...

b) Déterminer la dimension des sous--espaces propres de la. matrice A1.