X/ENS Maths PC 2018

Thème de l'épreuve Étude de matrices à coefficients dans {-1,1}
Principaux outils utilisés algèbre linéaire, probabilités, analyse, combinatoire
Mots clefs matrice, rang, inégalité de Hoeffding

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


ÉCOLE POLYTECHNIQUE ­ ÉCOLES NORMALES SUPÉRIEURES ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES FILIÈRE CONCOURS D'ADMISSION 2018 PC COMPOSITION DE MATHÉMATIQUES ­ (XEULC) (Durée : 4 heures) L'utilisation de calculatrices n'est pas autorisée pour cette épreuve. Toute affirmation doit être clairement et complètement justifiée. Ce sujet s'intéresse aux matrices carrées de taille n dont tous les coefficients sont égaux à 1 ou à -1, et en particulier à la différence maximale entre le nombre de 1 et le nombre de -1 que l'on peut obtenir, si l'on s'autorise à multiplier certaines lignes et colonnes d'une telle matrice par -1. La partie I s'intéresse à quelques cas particuliers. La partie II montre que pour certaines matrices, cette différence maximale est beaucoup plus petite que n2 . La partie III propose au contraire un minorant à cette différence maximale. La partie IV propose une démonstration de la formule de Stirling utilisée dans la partie III, et rappelée ci-dessous. Enfin, la partie V s'intéresse à la différence minimale entre le nombre de 1 et le nombre de -1. Les quatre premières parties sont largement indépendantes. Rappels La formule de Stirling énonce un équivalent à n!, à savoir n n . 2n n! n e On admet par ailleurs la valeur de l'intégrale de Gauss Z + x2 e- 2 dx = 2 . - Notations Pour n et k entiers strictement positifs, on notera Mn,k (R) l'espace vectoriel des matrices réelles à n lignes et k colonnes. On notera également Mn (R) = Mn,n (R) l'espace vectoriel des 1 matrices carrées de taille n. On notera tM la transposée d'une matrice M Mn,k (R). On identifiera l'espace vectoriel Rn à l'espace vectoriel Mn,1 (R) des matrices colonnes à n coordonnées. En particulier, l'espace vectoriel des nombres réels est identifié à M1 (R). On étend les notations précédentes aux parties de R : si K est une partie de R, on notera par exemple Mn,k (K) le sous-ensemble de Mn,k (R) constituée des matrices dont tous les coefficients sont à valeurs dans K. Le sujet s'intéressera tout particulièrement à Mn ({-1, 1}), l'ensemble des matrices carrées de taille n dont tous les coefficients sont égaux à 1 ou à -1. Si A Mn ({-1, 1}), on notera t XAY | (X, Y ) ({-1, 1}n )2 , S(A) := M (A) := max S(A). Pour n > 1, on notera également M (n) := min {M (A), A Mn ({-1, 1})} . Dans tout le sujet, (, A, P) désigne un espace probabilisé sur lequel seront définies les différentes variables aléatoires intervenant dans les parties II et III. On admettra que toutes les variables aléatoires introduites peuvent bien être construites sur cet espace. On notera P(E) la probabilité d'un événement E , et E[X] l'espérance d'une variable aléatoire X sur (, A, P) à valeurs réelles. Partie I 1. Quel est le cardinal de Mn ({-1, 1}) ? Cet ensemble est-il un sous espace vectoriel de Mn (R) ? 2. Montrer que pour toute matrice A dans Mn ({-1, 1}), l'ensemble S(A) est inclus dans {-n2 , . . . , n2 }. Montrer que l'inclusion est stricte (on pourra penser à un argument de parité), et montrer que S(A) est un ensemble symétrique, au sens où un entier k est dans S(A) si et seulement si -k est dans S(A). 3. Soit A et B dans Mn ({-1, 1}). On suppose qu'il existe des matrices diagonales C et D ne contenant que des 1 et des -1 sur la diagonale, telles que B = CAD. Montrer que S(A) = S(B). 4. Dans cette question seulement, on suppose n = 2, et on note I= 1 1 1 1 et J= 1 1 . 1 -1 Calculer S(I) et S(J), et en déduire S(A) pour tout A M2 ({-1, 1}). 5. Soit A Mn ({-1, 1}). Montrer que les affirmations suivantes sont équivalentes : (a) n2 S(A). (b) Il existe X et Y dans {-1, 1}n tels que A = X t Y . (c) A est une matrice de rang 1. 6. En déduire la proportion, parmi les matrices de Mn ({-1, 1}), des matrices A qui vérifient n2 S(A). 2 Partie II Soit k un entier strictement positif et U1 , . . . , Uk une suite de k variables aléatoires à valeurs dans {-1, 1}, indépendantes et de loi uniforme. On note également Sk = k X Ui . i=1 ! 1. Soit : R R la fonction définie par () = ln E[eU1 ] . Établir que R, () 6 2 . 2 2. Soit t R. Montrer que pour tout > 0, on a l'inégalité P(Sk > t) 6 exp(k() - t). 3. En déduire l'inégalité de Hoeffding pour Sk : pour tout t > 0, on a 2 t . P(Sk > t) 6 exp - 2k On introduit maintenant une variable aléatoire uniforme C : Mn ({-1, 1}). Pour , on note Ci,j () les coefficients de la matrice C(). 4. Soient X = (x1 , . . . , xn ) et Y = (y1 , . . . , yn ) deux vecteurs quelconques dans {-1, 1}n . Montrer que (xi yj Ci,j )16i,j6n est une famille de n2 variables aléatoires à valeurs dans {-1, 1}, indépendantes et de loi uniforme. 5. Montrer que pour tout t > 0, on a P(M (C) > tn 3/2 2 t - 2 ln 2 n . ) 6 exp - 2 6. On rappelle la notation M (n) = min {M (A) | A Mn ({-1, 1})} . Montrer que pour tout n > 1, on a M (n) 6 2 ln 2 n3/2 . Indication : on pourra commencer par montrer que pour tout > 0, il existe une matrice A dans Mn ({-1, 1}) telle que ! M (A) 6 2 ln 2 + n3/2 . Partie III Dans cette partie, on établit un minorant non trivial pour M (n). 1. Pour A = (ai,j )16i,j6n Mn ({-1, 1}) et Y = (yi )16i6n {-1, 1}n , on note gA (Y ) = max tXAY | X {-1, 1}n . Montrer que la fonction gA peut se réécrire gA (Y ) = n X n X i=1 j=1 3 ai,j yj . 2. On introduit maintenant une variable aléatoire uniforme Z : {-1, 1}n . Pour , on note Zi () les coordonnées de Z(). Montrer que pour tout A = (ai,j )16i,j6n Mn ({-1, 1}), on a n n X 1 X n |n - 2k|, i {1, . . . , n}, E ai,j Zj = n 2 k j=1 où !n k k=0 désigne le coefficient binomial. En déduire n n X n E [gA (Z)] = n |n - 2k|. 2 k k=0 3. (a) Montrer que pour m {0, . . . , n - 1}, on a m X k=0 n-1 n . =n (n - 2k) m k (b) En déduire que pour toute A Mn ({-1, 1}), E [gA (Z)] = où n2 désigne la partie entière de n2 n - 1 , 2n-1 n2 n 2. 4. (a) Montrer que M (n) > n2 n - 1 . 2n-1 n2 (b) Montrer ensuite, à l'aide de la formule de Stirling rappelée en préambule, que ce minorant est équivalent à Cn quand n tend vers l'infini, pour des constantes C et > 0 que l'on explicitera. Comparer au majorant de M (n) obtenu à la question 6 de la partie II. Partie IV Dans cette partie, on établit la formule de Stirling à l'aide d'une étude d'intégrales. 1. Pour n N, on pose In = Z + xn e-x dx. 0 Déterminer par récurrence In pour tout n N. 2. Montrer que pour n > 1, on a n n Z + x n -xn dx. In = n 1+ e e n - n 3. Soit U l'ouvert de R2 défini par U := {(t, x) R2 | t > 0 et x > -t}, et soit f la fonction définie sur U par f (t, x) = t2 ln(1 + 4 x ) - tx. t (a) Montrer que pour (t, x) U , on a x60 f (t, x) 6 - x2 . 2 (b) Pour x > 0, montrer que l'on a t > 1, f (t, x) 6 f (1, x). Pour cela, on pourra commencer par écrire certaine fonction F que l'on étudiera. f t (t, x) sous la forme tF (x/t) pour une 4. Déduire des questions précédentes la formule de Stirling. Partie V Dans cette dernière partie, on fixe A Mn ({-1, 1}) et on note m(A) := min(S(A) N). 1. Pour Y {-1, 1}n , montrer que l'on a min tXAY | X {-1, 1}n 6 n et en déduire m(A) 6 n. 2. En s'inspirant de la question précédente et des méthodes développées dans les parties II et III, montrer que l'on a également p m(A) 6 2n ln(2n). 5

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


 X/ENS Maths PC 2018 -- Corrigé Ce corrigé est proposé par Philippe Bouafia (professeur à l'ENSEA) ; il a été relu par Hervé Diet (professeur agrégé) et Guillaume Batog (professeur en CPGE). Dans ce problème, on étudie la différence maximale, notée M(A), entre le nombre de 1 et de -1 que l'on peut obtenir en partant d'une matrice carrée initiale A de dimension n × n à coefficients dans {-1, 1}, et en multipliant certaines de ses lignes et colonnes par -1. · La première partie vise à se familiariser avec les objets du problème, par exemple en étudiant le cas n = 2, qui peut se traiter « à la main ». La fin de cette partie étudie sous quelles conditions il est possible d'éliminer tous les -1 d'une matrice A de taille quelconque en multipliant certaines lignes et colonnes par -1. · Dans les deuxième et troisième parties, on s'intéresse à l'évolution asymptoMin M(A). De manière assez surprenante, tique de la quantité M(n) = AMn ({-1,1}) on utilise des méthodes probabilistes pour résoudre ce problème de nature purement combinatoire. · La quatrième partie est indépendante du reste du problème : on y démontre la célébrissime formule de Stirling, qui donne un équivalent de n ! lorsque n +, par des méthodes qui couvrent à peu près le programme d'analyse : formules intégrales, calcul différentiel à plusieurs variables, théorème de convergence dominée, etc. · Enfin, la dernière partie est moins guidée. Elle reprend essentiellement toutes les méthodes des parties précédentes pour étudier le problème dual de l'écart minimal entre le nombre de 1 et de -1 que l'on peut obtenir en multipliant certaines lignes ou colonnes de A par -1. Ce problème fait intervenir des parties extrêmement variées du programme : combinatoire, probabilités, analyse, algèbre linéaire, et même, de manière implicite, des espaces vectoriels normés. Il contient nombre de questions astucieuses (sans être infaisables) qui le rendent formateur. Indications Partie I I.3 Montrer que DY parcourt {-1, 1}n lorsque Y parcourt {-1, 1}n. I.4 Pour le calcul de S(A), essayer de se ramener au cas des matrices I et J par des opérations du type « multiplication d'une ligne ou d'une colonne par + - 1 ». I.5 Montrer les équivalences (a) (b) et (b) (c). I.6 Pour toute matrice A Mn ({-1, 1}) de rang 1, compter le nombre de couples 2 t (X, Y) ({-1, 1}n) tels que A = X Y. Partie II II.2 Appliquer l'inégalité de Markov. II.3 Appliquer la question II.1, puis le résultat de la question II.2 pour une valeur judicieusement choisie de . II.5 Exprimer {M(C) > tn3/2 } comme une union d'événements dont on pourra majorer la probabilité grâce à la question II.3. II.6 Si un événement est de probabilité non nulle, alors il est non vide. Partie III III.2 Utiliser une loi binomiale. n n-1 n-1 III.3.a Montrer que (n - 2k) =n -n . k k k-1 III.3.b Reprendre le résultat de la question III.2 et distinguer les k selon que n - 2k soit positif ou négatif. III.4.a Revenir à la définition de l'espérance pour calculer E(gA (Z)). Partie IV IV.3.b Montrer que la fonction partielle t 7 f (t, x) est décroissante sur [ 1 ; + [ en considérant sa dérivée. n Z + x 1+ e -x n dx à l'aide du IV.4 Déterminer la limite de l'intégrale n - n théorème de convergence dominée. Partie V V.1 Remarquer que, si u et v sont deux réels dont l'un est positif et l'autre négatif, alors |u + v| 6 max(|u| , |v|). Montrer que, pour tout (z1 , . . . , zn ) Rn , on peut construire pas à pas une n P suite finie x1 , . . . , xn {-1, 1} telle que xi zi 6 max (|z1 | , . . . , |zn |). i=1 V.2 Introduire > 0 et une variable aléatoire Z à valeurs dans {-1, 1}n comme dans la question III.2, puis montrer que ! n p P P Max ai,j Zj 6 2n ln(2n) + > 0 i[[ 1 ; n ]] j=1 en s'inspirant des méthodes de la deuxième partie. Partie I Donnons-nous une matrice A Mn ({-1, 1}) ainsi que deux vecteurs X et Y dans {-1, 1}n. Notons que t X AY = n P n P xi yj ai,j i=1j=1 est la somme des éléments de la matrice (xi yj ai,j )16i,j6n , obtenue à partir de A en multipliant pour tout i [[ 1 ; n ]] la ie ligne par xi , et pour tout j [[ 1 ; n ]] la j e colonne par yj . Pour se forger une intuition, on peut penser à l'image suivante. Plutôt qu'à une matrice A à coefficients dans {-1, 1}, pensons à un damier de taille n×n rempli de jetons bifaces noirs et blancs, et dont les faces visibles sont initialement données par la matrice A (1 pour blanc et -1 pour noir). À chaque tour, vous avez le droit de retourner tous les jetons d'une ligne ou bien d'une t colonne, comme au jeu Othello. La quantité X AY représente alors l'avance qu'ont les blancs par rapport aux noirs, si l'on a retourné toutes les lignes i pour lesquelles xi = -1, et toutes les colonnes j pour lesquelles yj = -1. Si l'on poursuit cette image, la quantité M(A) représente l'avance maximale que peuvent atteindre les blancs en jouant de manière optimale. Une question naturelle se pose : est-il possible d'atteindre une configuration sans jetons noirs ? Autrement dit, peut-on avoir M(A) = n2 ? Cette question sera résolue à la fin de la première partie. I.1 Un élément de Mn ({-1, 1}) est déterminé par ses n2 coefficients pris dans l'ensemble {-1, 1} de cardinal 2 d'où 2 Card Mn ({-1, 1}) = 2n De manière plus formelle, la phrase « un élément de Mn ({-1, 1}) est déterminé par ses n2 coefficients pris dans {-1, 1} » signifie que l'application n2 Mn ({-1, 1}) - {-1, 1} : (ai,j ) 7- (a1,1 , a1,2 , . . ., a2,1 , a2,2 , . . ., . . . ) | {z } | {z } ligne 1 ligne 2 est bijective. On en déduit que les ensembles de départ Mn ({-1, 1}) et 2 d'arrivée {-1, 1}n ont le même cardinal, et on conclut en notant que 2 2 2 Card {-1, 1}n = (Card {-1, 1})n = 2n . Un tel niveau de précision n'est cependant pas exigé. En combinatoire, l'usage est d'adopter un style de rédaction plus informel que dans les autres branches des mathématiques. Par ailleurs, la matrice nulle n'appartient pas à Mn ({-1, 1}), donc L'ensemble Mn ({-1, 1}) n'est pas un sous-espace vectoriel de Mn (R). I.2 Soit A une matrice de Mn ({-1, 1}) et k S(A). Par définition de S(A), il existe des vecteurs X, Y {-1, 1}n tels que t k = X AY = n P n P ai,j xi yj i=1j=1 Ainsi k est un entier relatif car c'est une somme de 1 et -1. D'après l'inégalité triangulaire, n P n n P n P P |k| 6 |ai,j | |xi | |yj | = 1 = n2 i=1j=1 i=1j=1 Les entiers ai,j xi yj valent -1 ou 1. En particulier, ils sont impairs, de sorte que k s'écrit comme une somme de n2 entiers impairs. Il en découle que k a la même parité que n2 , donc que n. En particulier, si n est pair, alors 1 6 S(A), et si n est impair, alors 0 6 S(A). En conclusion, S(A) est strictement inclus dans {-n2 , . . . , n2 }. Montrons à présent que S(A) est symétrique. Soit k S(A). Il existe des vecteurs t X, Y {-1, 1}n tels que k = X AY. Comme l'ensemble {-1, 1} est stable par multiplication par -1, le vecteur -Y appartient également à {-1, 1}n. Ceci implique que -k = t X A(-Y) S(A). Réciproquement, dans le cas où -k S(A), on déduit de ce qui précède que k = -(-k) S(A). Un entier k est dans S(A) si et seulement si -k est dans S(A). I.3 Notons que l'application ( {-1, 1}n - {-1, 1}n : Y = (y1 , . . . , yn ) 7- DY = (d1,1 y1 , . . . , dn,n yn ) est bien définie. Les coefficients diagonaux de D sont tous dans {-1, 1} et, comme 12 = (-1)2 = 1, on en déduit que D2 est la matrice identité d'où = id . En particulier, est une bijection sur {-1, 1}n. De la même manière, on montre que t l'application : X 7 C X réalise une bijection sur {-1, 1}n. Il vient que k S(B) X, Y {-1, 1}n X, Y {-1, 1}n X, Y {-1, 1}n X , Y {-1, 1}n k S(B) k S(A) t k = X CADY t t k= C X A (DY) t k = (X) A(Y) t k = X AY ( et bijectives) car et sont des bijections sur {-1, 1}n. On conclut S(A) = S(B) I.4 Introduisons deux vecteurs X = (x1 , x2 ) et Y = (y1 , y2 ) de {-1, 1}2 et calculons 1 1 y1 t X IY = x1 x2 = (x1 + x2 )(y1 + y2 ) 1 1 y2 Or la somme x1 + x2 ne peut prendre comme valeurs que -2, 0 ou 2, et il en va de même pour la somme y1 + y2 . Cela implique que S(I) {-4, 0, 4}. Montrons que cette inclusion est en réalité une égalité. L'ensemble S(I) étant symétrique d'après la question I.2, il suffit pour cela de montrer que 0 S(I) et 4 S(I), ce qui se fait par des choix judicieux de vecteurs X et Y : 1 1 1 1 1 1 0= 1 1 et 4= 1 1 1 1 -1 1 1 1 d'où S(I) = {-4, 0, 4}