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