Mines Maths 1 PSI 2018

Thème de l'épreuve Théorème de Komlos
Principaux outils utilisés matrices, probabilités, espaces vectoriels
Mots clefs déterminant, existence, équivalent

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


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

Extrait du corrigé obtenu par reconnaissance optique des caractères


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