A2018 – MATH I PC

ÉCOLE DES PONTS PARISTECH,

ISAE-SUPAERO, ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT Atlantique, ENSAE PARISTECH.

Concours Centrale-Supélec (Cycle International),

Concours Mines-Télécom, Concours Commun TPE/EIVP.

CONCOURS 2018

PREMIÈRE ÉPREUVE DE MATHÉMATIQUES

Durée de l’épreuve : 3 heures

L’usage de la calculatrice et de tout dispositif électronique est interdit.

Les candidats sont priés de mentionner de façon apparente

sur la première page de la copie :

MATHÉMATIQUES I - PC

L’énoncé de cette épreuve comporte 6 pages de texte.

Si, au cours de l’épreuve, un candidat repère ce qui lui semble être une erreur
d’énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les
raisons des initiatives qu’il est amené à prendre.
 Théorème de Komlós

Notations :

— Si x est un nombre réel on note [x] sa partie entière, c’est-à-dire le plus grand
entier relatif qui est inférieur ou égal à x.

— On appelle cardinal de l’ensemble fini E le nombre de ses éléments, que l’on

note |E|.

— On note P(E) l’ensemble des parties de l’ensemble E.

— Dans tout le problème on identifiera Rn à l’espace des matrices lignes M1,n (R) et
on notera Èx, yÍ le produit scalaire canonique des deux vecteurs, soit
n
ÿ
Èx, yÍ = xj yj ,
j=1

les xj , yj étant les composantes de x, y respectivement.

— Si V est un sous-ensemble de Rn on note Vect(V) l’espace vectoriel engendré par V.

On note V ‹ l’orthogonal de V, c’est-à-dire l’ensemble des vecteurs y tels que ’x œ
V, Èx, yÍ = 0.

— Si M est une matrice carrée de nombres réels, on note det(M ) son déterminant.

Dans tout le problème on pourra utiliser librement la formule de Stirling que l’on
rappelle : 3 4n
Ô n
n! ≥næ+Œ 2fin .
e

Définition 1 (Espace de Rademacher) Si n, q œ Nú , on note

Ó ! " Ô
q,n = Ê = Êi,j , 1 Æ i Æ q, 1 Æ j Æ n tels que Êi,j = ±1, ’i, j .

Pour tout i œ {1, · · · , q} et j œ {1, · · · , n}, on introduit la variable aléatoire Mi,j telle
que

Mi,j : q,n ≠æ {≠1, 1}

Ê ‘≠æ Êi,j .

On munit q,n de la probabilité uniforme P. Cela signifie que les variables aléatoires
(Mi,j , 1 Æ i Æ q, 1 Æ j Æ n) sont indépendantes et de même loi :

1
P(Mi,j = 1) = = P(Mi,j = ≠1).
2

1
Si q = n, on note M (n) la matrice aléatoire
Q R
M1,1 ··· M1,n
c .. .. d .
M (n) =a . . b
Mn,1 . . . Mn,n

(n) (n)
On note L1 , · · · , Ln les vecteurs lignes de M (n) . Par construction, ce sont des vec-
teurs aléatoires indépendants et de même loi.

Le but du problème est de démontrer, qu’ainsi construite, une matrice aléatoire est
inversible avec forte probabilité quand n est grand :
1 2
Théorème 1 (Komlós) limnæŒ P det M (n) = 0 = 0.

A Coefficients binomiaux
1. Soit n œ Nú : montrer que l’application
A B
n
k ‘≠æ
k

est croissante sur {0, · · · , [n/2]}. En déduire que pour tout k œ {0, · · · , n},
A B A B
n n
Æ ·
k [n/2]

A B
n
2. Trouver un équivalent de quand n tend vers l’infini. En déduire qu’il existe
[n/2]
un entier n0 tel que pour n Ø n0 ,
A B
n 2n
ÆÔ · (1)
[n/2] n

3. Montrer que pour tout entier non nul n et tout k œ {0, · · · , n},
A B
n k≠1
2 Æ nk .
k

q
On note (ei , 1 Æ i Æ n) la base canonique de Rn et v = ni=1 ei . On identifie 1,n et le
sous-ensemble de Rn I n J
ÿ
Êi ei , (Ê1 , · · · , Ên ) œ 1,n .
i=1

4. Pour tout i œ {1, · · · , n}, exprimer ei en fonction de v et v ≠ 2ei . En déduire que

Vect( 1,n ) = Rn .

2
B Dimension 2
5. Déterminer l’espérance de det M (2) .

6. Montrer que la variance de det M (2) est égale à 2.

1 2
7. Calculer P det M (2) = 0 .

C Quelques bornes
On suppose dorénavant n Ø 2.

8. Quelle est la probabilité que les deux premières lignes de M (n) soit égales ou
opposées ?
1 2
En déduire que P det M (n) = 0 Ø 21≠n si n Ø 2.

9. Soient l1 , · · · , ln des vecteurs non nuls de Rn . Montrer que ces vecteurs sont liés si
et seulement si, il existe j œ {1, · · · , n ≠ 1} tel que

lj+1 œ Vect({l1 , · · · , lj }).

En déduire que
1 2 n≠1
ÿ 1 2
(n) (n) (n)
P det M (n) = 0 Æ P Lj+1 œ Vect(L1 , · · · , Lj ) . (2)
j=1

Soit H un sous-espace vectoriel de Rn de dimension d. On rappelle que H‹ est un

sous-espace vectoriel de dimension n ≠ d et que (H‹ )‹ = H.

10. Montrer alors qu’il existe des réels (–i,j , 1 Æ i Æ n ≠ d, 1 Æ j Æ n) tels que
Q RQ R Q R
–1,1 . . . –1,n x1 0
c .. .
.. b a .. b = a ... d
d c . d c
x = (x1 , · · · , xn ) œ H ≈∆ a . b.
–n≠d,1 . . . –n≠d,n xn 0

11. En utilisant le pivot de Gauss, montrer qu’il existe 1 Æ i1 < · · · < id Æ n tel
que pour tout (y1 , · · · , yd ) œ Rd il existe un unique x = (x1 , · · · , xn ) œ H tel que
xik = yk pour k = 1, · · · , d.

12. En déduire que

(n)
P(L1 œ H) Æ 2d≠n ,
puis que pour tout j œ {1, · · · , n ≠ 1},
1 2
(n) (n) (n)
P Lj+1 œ Vect(L1 , · · · , Lj ) Æ 2j≠n . (3)

3
 Indication : on pourra utiliser la conséquence suivante de la formule des probabilités
totales
1 2
(n) (n) (n)
P Lj+1 œ Vect(L1 , · · · , Lj )
ÿ 1 2
(n) (n) (n)
= P Lj+1 œ Vect(l1 , · · · , lj ) | L1 = l1 , · · · , Lj = lj
l1 ,··· ,lj œ 1,n

(n) (n)
◊ P(L1 = l1 , · · · , Lj = lj )

et l’indépendance des vecteurs lignes.

Soit q < n et Ê œ q,n . On note l1 , · · · , lq ses vecteurs lignes.

13. Montrer que l’on peut trouver un vecteur non nul orthogonal à Vect(li , i = 1, · · · , q)
qui soit à coordonnées dans Z.

D Théorème de Erdös-Littlewood-Offord
Définition 2 Soit n un entier non nul. Soit A un sous-ensemble de P({1, · · · , n}). On
dit que A est une anti-chaîne si deux éléments distincts A, B quelconques de A sont
incomparables, c’est-à-dire tels que A n’est pas inclus dans B et B n’est pas inclus dans
A.

Commençons par un exemple. Soit k œ {1, · · · , n} et Ak l’ensemble des parties de

{1, · · · , n} de cardinal k.

14. Montrer que Ak est une anti-chaîne et que

A B
n 2n
|Ak | Æ ÆÔ ,
[n/2] n

la deuxième inégalité ayant lieu pour n assez grand.

Définition 3 Soit A une anti-chaîne et A œ A, de cardinal noté |A|. On note SA ,

l’ensemble des bijections ‡ de {1, · · · , n} dans lui-même telles que la restriction de ‡ à
{1, · · · , |A|} soit une bijection de {1, · · · , |A|} dans A.

15. Quel est le cardinal de SA ?

16. Soit B œ A avec B ”= A. Montrer que SA fl SB = ÿ.

17. En déduire que si ak désigne, pour k Æ n, le nombre d’éléments de A de cardinal

k, alors
ÿn
a
A kB Æ 1.
k=0 n
k

4
 18. Montrer que A B
n
|A| Æ .
[n/2]

Soit v = (v1 , · · · , vn ) œ Rn tel que vj Ø 1, pour tout j = 1, · · · , n. Si A µ {1, · · · , n}

on pose ÿ ÿ
sA = vj ≠ vj
jœA jœAc

où Ac est le complémentaire de A dans {1, · · · , n}.

19. Montrer que si A µ B µ {1, · · · , n}, A ”= B, alors

sB ≠ sA Ø 2.

20. Soit J un intervalle ouvert de R de longueur 2 : montrer que si n est assez grand
alors
(n) 1
P(< L1 , v > œ J) Æ Ô ·
n
Montrer que cette propriété reste vraie si l’on suppose seulement que pour tout
j œ {1, · · · , n}, |vj | Ø 1.

Indication : construire une bijection entre 1,n et l’ensemble des parties de {1, · · · , n}.
Construire une anti-chaîne intéressante.

E Universalité
Dans tout ce qui suit, k est un entier inférieur à n.
Définition 4 Soit V µ 1,n . L’ensemble V est dit k-universel si pour tous les k≠uplets
1 Æ j1 < j2 . . . < jk Æ n et tout Ê œ 1,n , il existe v œ V tel que
vjm = Ê1,jm , pour tout m = 1, · · · , k.

21. Soit d œ {1, ..n}. Montrer l’inclusion

Ó Ô
(n) (n)
{L1 , · · · , Ld } non k-universel
€ € d €
‹ k
µ {Mi,jm ”= Ê1,jm }.
(j1 ,··· ,jk )œ{1,··· ,n}k Êœ 1,k i=1 m=1
j1 <...<jk

(n)
(On rappelle que Li = (Mi,1 , · · · , Mi,n )).

(n) (n)
22. Montrer que la probabilité que {L1 , · · · , Ld } ne soit pas k≠universel est majorée
par A B
n k
2 (1 ≠ 2≠k )d .
k

5
 23. En déduire que si d Ø n/2 et k Æ ln n, alors, pour n assez grand,
1
(n) (n)
2 1
P {L1 , · · · , Ld } non k-universel Æ · (4)
n

24. Soit V µ 1,n un ensemble k-universel tel qu’il existe v œ V ‹ \{0} : montrer que v
a au moins k + 1 coordonnées non nulles.

En vertu de la question 13, on peut supposer que les coordonnées de v sont des entiers
relatifs.

25. Montrer que si k est assez grand

1 2 1 2
(n) (n)
P L1 œ Vect(V) Æ P ÈL1 , vÍ = 0 Æ k ≠1/2 . (5)

Soit (tn , n œ N) une suite croissante d’entiers telle que tn /n æ 0.

26. Montrer que si n est assez grand alors n ≠ tn Ø n/2 et

n≠1
ÿ 1
(n) (n) (n)
2 2 tn
P Lj+1 œ Vect(L1 , · · · , Lj ) Æ Ô · (6)
j=n≠tn +1 ln n

(n) (n)
Indication : on distinguera les cas selon que Vect(L1 , · · · , Lj ) est k-universel
ou pas et l’on prendra k = [ln n].

F Théorème de Komlós
27. En déduire le théorème de Komlós.

Indication : on pourra partir de (2) et choisir convenablement une suite (tn , n Ø 1).

Fin du problème