Mines Maths 1 PC 2018

CONCOURS MINES
COMMUN... PONTS
..

ECOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES SAINT-ETIENNE, 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 a: est un nombre réel on note [cr] sa partie entière, c'est--à-dire le 
plus grand
entier relatif qui est inférieur ou égal à :r.

-- 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 R" à l'espace des matrices lignes 
M17n(R) et
on notera <:r, y) le produit scalaire canonique des deux vecteurs, soit n j=1 les (L'j, yj étant les composantes de au, y respectivement. -- Si V est un sous--ensemble de R" on note Vect(V) l'espace vectoriel engendré par V. On note Vl l'orthogonal de V, c'est--à--dire l'ensemble des vecteurs y tels que Vw E 17,  = 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:
" '"
n!rvn_>+OO 27Tn -- .
e

Définition 1 (Espace de Rademacher) Sin, q G N'", on note

&... = {w : (co...-, 1 S i S q, 1 S j S n) tels que w... = ::1, Vi,j}.

Pour touti EUR {1,- ---- ,q} et j E {l, -- ---- ,n}, on introduit la variable 
aléatoire M... telle
que

Màj ! Qq,n _) {--1,1}

au l--> w....

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

1
P(M... = 1) = 5 = P(M... = _1).

Si q = n, on note M(") la matrice aléatoire

Mm . . . M1,n
M(") = ; .
M...1 . . . M....
On note Lg"), -- -- , Lg" les vecteurs lignes de M...). 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 :

Théorème 1 (Komlôs) limn_>oe P(detM(") = 0) = 0.

A

1.

. Trouver un équivalent de (

Coefficients binomiaux

Soit n E N* : montrer que l'application

... (Z)

est croissante sur {D, -- ---- , [n/2l}. En déduire que pour tout R E {O, -- -- 
-- ,n},
n n
< . (l'?) _ (ln/2l) l"î2l) quand n tend vers l'infini. En déduire qu'il existe un entier no tel que pour n 2 no, n 2" (wa) S %" ... . Montrer que pour tout entier non nul n et tout k E {O, - -- - ,n}, (Z) 2k_1 S nk. On note (ei, 1 S i S n) la base canonique de R" et u = ZÏ=1 ei. On identifie QLn et le sous--ensemble de R" " {Zwi Gi, (wla' " 7wn) EUR Q1,n} ' i=1 4. Pour tout i E {l, - --- ,n}, exprimer ci en fonction de v et u -- 2ei. En déduire que Vect(QLn) = R'". Dimension 2 5. Déterminer l'espérance de det M (2). 6. Montrer que la variance de det M (2) est égale à 2. 7. Calculer P(det M<2) = O). C Quelques bornes On suppose dorénavant n 2 2. 8. Quelle est la probabilité que les deux premières lignes de M (") soit égales ou opposées? En déduire que P(det M...) = O) 2 21_" si n 2 2. 9. Soient l1, -- - -- ,ln des vecteurs non nuls de R". Montrer que ces vecteurs sont liés si et seulement si, il existe j EUR {1, -- ---- ,n -- 1} tel que lj+1 EUR VBCÈ({Z1,° - ' ,lj}). En déduire que n--1 P(detM("> = 0) g 2 P(LÊÎË1 e Vect(Lâ"), . ... ,LÊ"))). (2)
j=1

Soit H un sous-espace vectoriel de R" de dimension (1. On rappelle que "Hi est 
un
sous--espace vectoriel de dimension n -- d et que ("i--H)l = H.

10. Montrer alors qu7il existe des réels (a...--, 1 S i S n -- d, 1 S j S n) 
tels que

01171 - - - Oan OE1 0
oe=(oe1,-----,oen)e"H<=> ; ; ; =
an--d,1 - - - Gin--dm fin 0
11. En utilisant le pivot de Gauss, montrer qu'il existe 1 S 11 < < id S n tel que pour tout (y1, - --- ,yd) EUR Rd il existe un unique w = (m1, -- --- ,x") E 7--[ tel que oeik =yk pourk=1,--- ,d. 12. En déduire que P(Lâ"> e %) g 2d--",
puis que pour tout j EUR {1, -- --- , n -- 1},

P (LW

... e Vect(Lgn), -- --- ,Lg"))) g 2î--n. (3)

Indication : on pourra utiliser la conséquence suivante de la formule des 
probabilités
totales

P(L e J) S --_

\/ñ
Montrer que cette propriété reste vraie si l'on suppose seulement que pour tout
j EUR{17...7n}7 ll}le 1-

Indication : construire une bi jection entre QLn 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 C Q1,n. L'ensemble V est dit k-universel si pour tous les 
k--uplets
1 Sj1  O.

26. Montrer que si n est assez grand alors n -- t" 2 n/ 2 et

n--1

21EUR
2 P(LÊOE1 e Vect(Lâ"),--u , LÉ")) £ " -- (6)
__ _ lnn
3-n tn+1
Indication : on distinguera les cas selon que Vect(Lân), -- --- , Lgn)) 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 (t... 
n 2 l).

FIN DU PROBLÈME

Mines Maths 1 PC 2018 -- Corrigé
Ce corrigé est proposé par Hervé Diet (professeur agrégé) ; il a été relu par 
Théo
Lenoir (ENS Ulm) et Florian Metzger (docteur en mathématiques).

Ce sujet porte sur l'espace de Rademacher, défini comme le sous-ensemble q,n
de Mq,n (R) constitué des matrices à coefficients dans {-1, 1}. On prouve le 
théorème
de Komlós qui s'énonce ainsi : si M(n) est une variable aléatoire à valeurs 
dans n,n
qui suit la loi uniforme, alors
lim P(det(M(n) ) = 0) = 0

n+

En d'autres termes, une matrice aléatoire est inversible avec forte probabilité 
lorsque
n est grand.
Le sujet fait largement appel aux matrices et aux probabilités. Il se compose de
six parties connectées les unes aux autres.
· La première établit quelques majorations sur les coefficients binomiaux à 
l'aide
de raisonnements classiques (équivalents, récurrences, etc.). Ces majorations
permettront de calculer des limites dans la suite du sujet.
· La partie B étudie de manière exhaustive le cas de la dimension 2.

· La partie C donne quelques bornes sur les probabilités qui seront utilisées 
ultérieurement. Ces résultats sont établis en travaillant sur des espaces 
vectoriels.
· La partie D porte sur des aspects ensemblistes (cardinal, dénombrement) et sur
les anti-chaînes qui sont les sous-ensembles de P({1, ..., n}) dont les éléments
sont incomparables (ni A  B ni B  A si A 6= B). On démontre alors un
théorème d'Erdös-Littlewood-Offord : si v  Rn tel que |vj | 6 1 pour tout
j  [[ 1 ; n ]], si J est un intervalle de R de longueur 2 et si n est assez 
grand,

1
(n)
P hL1 , vi  J 6 
n
(n)

où L1

désigne la première ligne de la matrice aléatoire M(n) .

· Ce théorème est exploité dans la partie E. Cela permet de prouver des 
majorations nécessaires pour la suite.
· La dernière partie est consacrée à la démonstration du théorème de Komlós.
On y exploite tous les résultats établis précédemment.
Le sujet est assez difficile pour la filière PC. Il comporte des raisonnements 
qui
peuvent être déstabilisants et la manipulation des probabilités requiert 
beaucoup de
rigueur. Comme le sujet suit une progression linéaire, il n'est pas judicieux 
de passer
une partie puisqu'elle servira à coup sûr pour la suite. Cela en fait un sujet 
utile en
fin de révision car il couvre nombre de thèmes d'algèbre au programme.

Indications

n
n
1 Étudier le rapport
/
. Étendre la propriété à k > n/2 par symétrie
k+1
k
des coefficients binomiaux.
2 Différencier les cas n pair
puis utiliser la formule de Stirling pour cher et impair

n
cher un équivalent de
.
n/2
3 Traiter le cas k = 0 à part. Faire un raisonnement par récurrence sur k.

4 Prouver que 1,n engendre tous les éléments de la base canonique de Rn .
5 Calculer l'espérance de E(M1,1 ) puis utiliser les propriétés de l'espérance.
6 Appliquer la formule de transfert.
8 Commencer par déterminer les valeurs de
P(Mi,j = Mk,l ) et P(Mi,j = -Mk,l ) avec (i, j) 6= (k, l)
On pourra ensuite poursuivre les calculs et noter que det(M(n) ) = 0 lorsque les
colonnes L1 et L2 sont liées.

9 Utiliser l'équivalence démontrée pour décomposer l'événement det(M(n) ) = 0 .

10 Définir une base de H et la relier aux i,j .

11 La méthode du pivot de Gauss donne les n - d pivots, et les colonnes sans 
pivot
donnent les indices 1 6 j1 < j2 < · · · < jd 6 n. 12 Attention à tourner la page du sujet pour voir les indications. 13 Exploiter la méthode d'orthogonalisation de Gram-Schmidt sans normaliser les vecteurs pour construire le vecteur voulu. 15 Étudier la restriction de  à {1, . . . , |A|}. 17 Utiliser la question précédente pour décomposer l'ensemble A. P P 19 Étudier la différence vj - vj pour montrer qu'il reste au moins un élément jB jA et en déduire une minoration. 20 Prouver d'abord que AJ = {A  P({1, . . . , n}) | sA  J} est une anti-chaîne. 21 Écrire la négation de la définition proposée. 23 Trouver une majoration de la probabilité désirée qui ne dépende que de n. Étudier la limite du produit de ce terme et de n pour conclure. 24 Raisonner par l'absurde sur le nombre de coordonnées non nulles de v. 25 Choisir une suite d'indices 1 6 j1 < j2 < · · · < jk 6 n tels que l'on puisse ramener le problème de 1,n à 1,m et appliquer le résultat de la question 20. 27 Scinder la somme obtenue en deux morceaux, de 1 à n - tn puis de n - tn + 1 à n - 1 et majorer chaque partie. Choisir une suite (tn ) à croissance moins rapide que ( ln n), par exemple (ln n)1/4 . A. Coefficients binomiaux n 1 Soit n  N et k un entier tel que k + 1 6 n/2. Le coefficient binomial est k non nul, ce qui permet de considérer n k+1 n! k!(n - k)! = × (k + 1)!(n - k - 1)! n! n k n-k n+1 = = -1 k+1 k+1 La fonction x 7 1/x est décroissante sur R+ et k +1 est inférieur à n/2 donc à n/2. On en déduit que 1 1 2 >
=
k+1
n/2
n

soit

d'où

n
k+1
2
2
2
  > (n + 1) - 1 = 2 + - 1 = 1 + > 1
n
n
n
n
k

n
L'application k 
7
est croissante sur {0, . . . , n/2}.
k

D'après le résultat précédent, on a

n
j n ko
n
n
 k  0, . . . ,
6
k
n/2
2

n
n
Il suffit alors de remarquer que
=
donc, si k > n/2 alors
k
n-k
jnk
n
n
= n - k < = n - k 6 k>
2
2
2
 
n
car n - k est entier. Par croissance de k 7
sur [[ 0 ; n/2 ]], on obtient
k

jnk
n
n
n
=
6
si k >
k
n-k
n/2
2
La majoration est aussi vraie lorsque k > n/2. En conclusion,
k  {0, . . . , n}

n
n
6
k
n/2

2 Soit n  N, on va faire l'étude selon la parité de n.
· Considérons le cas où n est pair. Soit p  N tel que n = 2p. Alors

(2p)!
n
=
n/2
p!2

On peut maintenant utiliser la formule de Stirling et écrire
 2p

2p

2 × 2p
22p
e
n
=

2p
p
n/2
p
2p
e
et finalement, lorsque n est pair,

 r
2
2n
n

×
n/2

n
· Voyons maintenant le cas n impair. Soit p  N tel que n = 2p + 1 ; alors

jnk 
1
(2p + 1)!
n
2p + 1
= p+
=p
d'où
=
=
n/2
p
2
2
p!(p + 1)!
On peut astucieusement réutiliser le travail précédent en remarquant que
r
(2p + 1)!
2 22p+1
2p + 1 (2p)!
22p
=
·

2
·
=
· 

p!(p + 1)!
p+1
p!2
p

2p

Ainsi, en remarquant que 2p  2p + 1, il vient à nouveau
r

 r
2
22p+1
2
2n
n

·
=
×
n/2

n
2p + 1
En conclusion,

On a

r

r

2
2n
n
× .

n/2 n+ 
n

2
< 1 puisque 2 < . L'équivalent précédent implique alors que 2n n n0  N n > n0
=
6
n/2
n

3 Soit n  N, la propriété attendue se démontre aisément pour k = 0 puisque
 
1
1
n -1
2 = 1 × = < 1 = n0 0 2 2 Montrons par récurrence sur k  {1, . . . , n} que la propriété n k-1 P(k) : 2 6 nk k est vraie pour tout k  {1, . . . , n}. n 0 · P(1) est vraie car 2 = n × 1 = n = n1 . 1 · P(k) = P(k + 1) : supposons que pour tout k  [[ 1 ; n-1 ]] la propriété P(k) est vraie. Alors n! n! 2(n - k) n 2k = 2k = 2k-1 × k+1 (k + 1)!(n - k - 1)! k!(n - k)! k+1