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