Mines Maths 1 PSI 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 - PSI

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 [oe] 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 '" <33, y) = ZOEjyja j=1 les OEj, yj étant les composantes de m, 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 Voe 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 :
" TL
n! Nn_>+oo 27rn (--) .
e

Définition 1 (Espace de Rademaeher) Sin, q E N*, on note

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

Pour touti E {l, - -- ,q} et j EUR {1, - ---- ,n}, on introduit la variable 
aléatoire M... telle
que
Mjflj ! Qq,n _) {--1,1}
au r--> co...».

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

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

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

M1,1 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_,oeP(detM(n) = 0) = 0.

A Coefficients binomiaux

1. Soit n E N* : montrer que l'application

... (Z)

est croissante sur {D, -- ---- , [n/2l}. En déduire que pour tout [EUR E {O, -- 
-- -- ,n},
n < n . k _ ln/2l 2. Trouver un équivalent de ( ) quand n tend vers l'infini. En déduire qu'il existe n [ra/2] un entier no tel que pour n 2 no, n 2" (wa) î ? ... 3. Montrer que pour tout entier non nul n et tout [EUR E {O, -- -- -- ,n}, " k--1 k 2 < n . On note (e,-, 1 S i S n) la base canonique de R" et v = ZÎ=1 ei. On identifie QLn et le sous--ensemble de R" " {Zwi 61, (001, ' ' ' 7wn) EUR Ql,n} ' i=1 4. Pour tout i E {l, -- - -- ,n}, exprimer e,- en fonction de v et v -- 2e,-. En déduire que Vect(Q1,n) = 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?) = 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 A, -- - -- ,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 Vect({l1, - ° - ,lj}). En déduire que n--1 P(det M(") = 0) g 2 P(LÊË1 e Vect(Lgn>7 . .. ,Lg")))_ (2)

j=1

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

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

06171 . . . OZLn fil 0
oe=(oe1,------,oen)efi<=> ; ; ; =
an--d,1 - - - an--d,n mn 0
11. En utilisant le pivot de Gauss, montrer qu'il existe 1 S il < < id S n tel que pour tout (y1, -- --- ,yd) EUR Rd il existe un unique 513 = (1171, -- ---- ,x") E "H tel que oeik =yk pour k= 1,----- ,d. 12. En déduire que P(LY" @ %) $ $*", puis que pour tout j EUR {1,- --- , n -- 1}, P (LW ... & Vect(Lâ"), . ... ,L(."))) < 2j--". (3) Indication : on pourra utiliser la conséquence suivante de la formule des probabilités totales P(LÊOE, @ Vect(Lâ"), . ... , Lg"))) = 2 P(Läïä e vec...1,... , t) | L3") = l , LE") = 'J') 11,----,ljeQ... >< P(LY" = [l, . ... , Lg") = l,») et l'indépendance des vecteurs lignes. Soit q < n et ou E 9%". On note ll, - -- , lq ses vecteurs lignes. 13. Montrer que l'on peut trouver un vecteur non nul orthogonal a Vect(li, i = 1, -- -- - , q) qui soit a coordonnées dans Z. D Théorème de Erdôs-Littlewood-Ofibrd 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--chaine si denoe é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 EUR {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 n 2" |Ak| S <[n/2l) S fia la deuxième inégalité ayant lieu pour n assez grand. Définition 3 Soit A une anti--chaine et A E A, de cardinal noté lA|. On note SA, \ l'ensemble des bijeeti0ns o de {1, -- ---- ,n} dans lui--même telles que la restriction de a a {1,------ , |Al} soit une bijection de {1, -- ---- , |Al} dans A. 15. Quel est le cardinal de S A ? 16. Soit B E A avec B % A. Montrer que SA m 53 = (Ô. 17. En déduire que si ak désigne, pour k: S n, le nombre d'éléments de A de cardinal k, alors n 2 ÎÏ g1. =() k 18. Montrer que "" 5 (ln/21) ' Soitv= v1,----,vn ER"telqueuZl,pourt0utj=l,---,n.SiAC 1,-----,n 3 on pose 5A = 2 "j -- 2 % jeA jEURAC où AC est le complémentaire de A dans {l, - -- - , n}. 19. Montrer que si A C B C {1,------ ,n}, A # B, alors sB--sAZ2. 20. Soit J un intervalle ouvert de R de longueur 2 : montrer que si n est assez grand alors 1 P(< Lg"), @ > e J) S --_

\/ñ
Montrer que cette propriété reste vraie si l'on suppose seulement que pour tout
j EUR{1,...,TL}, "'le 1-

Indicati0n : construire une bijection entre 91,7, et l'ensemble des parties de 
{l, -- - -- , 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 1117". L'ensemble V est dit k-um'versel si pour tous les 
k--uplets
1 Sj1 e{L---.n}k weflm i=l m=l
jl<... O.

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

n--1
215
2 P(LÊOE1 EUR Vect(Lgn),-w , Lÿ")) S " -- (6)
j=n_tn+1 lnn
Indication : on distinguera les cas selon que Vect(L@, - --- , 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 (75... 
n 2 l).

FIN DU PROBLÈME