X ENS Mathématiques PC 2018Sujet, corrigé et rapport du jury

Pas encore noté

Explorer les annales

BanqueX-ENS Année2018 FilièrePC MatièreMathématiques

Annales X-ENS PC Mathématiques X-ENS PC 2018 PC Mathématiques Mathématiques 2018

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Rapport du jury Lire en ligne LaTeX Word

Présentation du sujet

Difficile

Matrices à coefficients 1 et -1 : écart maximal entre nombres de 1 et de -1, inégalité de Hoeffding et formule de Stirling

Le sujet étudie les matrices carrées dont tous les coefficients valent 1 ou -1, et l'écart maximal entre le nombre de 1 et de -1 obtenu en changeant le signe de certaines lignes et colonnes. Après des cas particuliers, il majore cet écart par une méthode probabiliste fondée sur l'inégalité de Hoeffding, puis le minore par un calcul d'espérance. Il démontre ensuite la formule de Stirling par des intégrales et termine sur l'écart minimal.

1Partie I : cas particuliersCardinal de l'ensemble des matrices, parité et symétrie de S(A), cas n = 2 et caractérisation des matrices de rang 1.
2Partie II : un majorant probabilisteInégalité de Markov, inégalité de Hoeffding pour une somme de variables uniformes sur {-1, 1} et majoration de M(n) par une matrice aléatoire.
3Partie III : un minorantRéécriture de g_A, calcul d'une espérance à l'aide de coefficients binomiaux et de la formule de Pascal, puis équivalent par la formule de Stirling.
4Partie IV : démonstration de la formule de StirlingCalcul de l'intégrale I_n, changement de variable, étude d'une fonction de deux variables et passage à la limite par convergence dominée.
5Partie V : l'écart minimalMajoration de m(A) en adaptant les méthodes des parties II et III.

Difficile. La moyenne est de 7,9 sur 20 et plus de la moitié des candidats français obtient entre 4 et 8 ; la dernière partie, nettement plus difficile, n'a été abordée que par une fraction infime des candidats.

L'épreuve en chiffres

Moyenne 7,9 / 20 · écart-type 3,07 · 1 272 présents · où vous situez-vous ?

Moyenne: 7,9/ 20
Écart-type: 3,07
Présents: 1 272

Deux tiers des copies environ (moyenne ± écart-type)

Où je me situe ?

Votre note sur 20 à ce sujet, en conditions de concours.

Source : document officiel du concours. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.

Ce qu'a observé le jury

6 erreurs relevées

Preuves incomplètes dans la partie I · Cas général et proportion · Inégalités classiques mal appliquées

Le sujet progressait lentement en difficulté, avec des parties de niveau comparable sauf la dernière, et un découpage très détaillé en questions intermédiaires. Environ 75 % des candidats traitent le même lot de questions ; ceux qui se distinguent réussissent quelques questions longues demandant un raisonnement en plusieurs étapes. Le jury salue les efforts de rédaction mais regrette un manque de rigueur sur des calculs élémentaires.

Les erreurs les plus sanctionnées

1
Preuves incomplètes dans la partie II.2, I.3, I.5
Peu prouvent l'inclusion stricte en I.2 malgré l'indication, une partie ne montre qu'une inclusion en I.3, et l'implication (a) ⇒ (b) de I.5 est rarement justifiée.
2
Cas général et proportionI.4, I.6
Le calcul de S(A) dans le cas général est l'une des questions les moins bien traitées ; en I.6, il fallait se ramener à la proportion de matrices de rang 1.
3
Inégalités classiques mal appliquéesII.1
Beaucoup appliquent de travers une inégalité de convexité ou sur le logarithme, ou raisonnent avec des développements limités en négligeant les petits o. Les séries entières donnaient une solution simple.
4
Indépendance des variables non établieII.4
Les preuves sont souvent incomplètes : indépendance non prouvée, lois non déterminées ou nombre de variables non indiqué.
5
Résultat donné atteint par des égalités approximativesIII.3.a
Pour une égalité donnée par l'énoncé, il faut mettre en avant les étapes clés ; la formule de Pascal suffisait.
« Le résultat attendu étant donné, le correcteur s’attend évidemment à ce que les points importants du raisonnement soient clairement mis en avant »
6
Stirling et changement de variableIII.4.b, IV.1, IV.2
La simplification par la formule de Stirling est souvent incorrecte et beaucoup ratent le changement de variable dans l'intégrale ; certains se trompent même sur la valeur classique de I_n.

Ce qui a été bien réussi

La plupart des candidats répondent correctement à la question I.1.
La très grande majorité prouve l'inclusion de la question I.2.
Le calcul de S(I) et S(J) en I.4 est l'une des questions les mieux réussies.
La question IV.1 a été bien traitée par la plupart des candidats.

Conseils du jury

Lire intégralement le sujet avant de commencer.
Énoncer entièrement les théorèmes, vérifier toutes leurs hypothèses et ne pas omettre de quantificateurs.
Mettre en évidence les points clés d'une démonstration et citer proprement les questions utilisées.
Traiter avec soin les premières questions, puis quelques questions plus longues plutôt que de survoler le sujet.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

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

n^2

. 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! \sim _(n \to \infty)\sqrt(2πn)(n/e)^n.

On admet par ailleurs la valeur de l'intégrale de Gauss

\int_(- \infty)^(+ \infty)e^(- (x^2)/2)dx = \sqrt(2π)

Notations

Pour

n

k

entiers strictement positifs, on notera

M_(n, k)(ℝ)

l'espace vectoriel des matrices réelles à

n

lignes et

k

colonnes. On notera également

M_n(ℝ) = M_(n, n)(ℝ)

l'espace vectoriel des
matrices carrées de taille

n

. On notera

^t M

la transposée d'une matrice

M \in M_(n, k)(ℝ)

. On identifiera l'espace vectoriel

ℝ^n

à l'espace vectoriel

M_(n, 1)(ℝ)

des matrices colonnes à

n

coordonnées. En particulier, l'espace vectoriel des nombres réels est identifié à

M_1(ℝ)

On étend les notations précédentes aux parties de

ℝ

: si

K

est une partie de

ℝ

, on notera par exemple

M_(n, k)(K)

le sous-ensemble de

M_(n, k)(ℝ)

constituée des matrices dont tous les coefficients sont à valeurs dans

K

. Le sujet s'intéressera tout particulièrement à

M_n({ − 1, 1})

, l'ensemble des matrices carrées de taille

n

dont tous les coefficients sont égaux à 1 ou à -1 . Si

A ∈ M_n({ − 1, 1})

, on notera

S(A), :={^t XAY|(X, Y) ∈ ({ − 1, 1}^n)^2}; M(A), :=maxS(A)

Pour

n ⩾ 1

, on notera également

M_–(n):=min{M(A), A ∈ M_n({ − 1, 1})}.

Dans tout le sujet, (

Ω, A, ℙ

) 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

ℙ(E)

la probabilité d'un événement

E \subset Ω

, et

𝔼[X]

l'espérance d'une variable aléatoire

X

sur

(Ω, A, ℙ)

à valeurs réelles.

Partie I

Quel est le cardinal de $M_n({ − 1, 1})$ ? Cet ensemble est-il un sous espace vectoriel de $M_n(ℝ)?$
Montrer que pour toute matrice $A$ dans $M_n({ − 1, 1})$ , l'ensemble $S(A)$ est inclus dans ${ − n^2, …, n^2}$ . 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)$ .
Soit $A$ et $B$ dans $M_n({ − 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)$ .
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)

S(J)

, et en déduire

S(A)

pour tout

A ∈ M_2({ − 1, 1})

.
5. Soit

A ∈ M_n({ − 1, 1})

. Montrer que les affirmations suivantes sont équivalentes :
(a)

n^2 \in S(A)

.
(b) Il existe

X

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

M_n({ − 1, 1})

, des matrices

A

qui vérifient

n^2 \in S(A)

Partie II

Soit

k

un entier strictement positif et

U_1, \dots, U_k

une suite de

k

variables aléatoires à valeurs dans

{ - 1, 1}

, indépendantes et de loi uniforme. On note également

S_k = \sum_(i = 1)^k U_i

Soit $φ : ℝ \to ℝ$ la fonction définie par $φ(λ) = ln(𝔼[e^(λU_1)])$ . Établir que

\forallλ \in ℝ, φ(λ) ⩽ (λ^2)/2

Soit $t \in ℝ$ . Montrer que pour tout $λ > 0$ , on a l'inégalité

ℙ(S_k ⩾ t) ⩽ exp(kφ(λ) - λt)

En déduire l'inégalité de Hoeffding pour $S_k$ : pour tout $t > 0$ , on a

ℙ(S_k ⩾ t) ⩽ exp(- (t^2)/(2k))

On introduit maintenant une variable aléatoire uniforme

C : Ω → M_n({ − 1, 1})

. Pour

ω \in Ω

, on note

C_(i, j)(ω)

les coefficients de la matrice

C(ω)

.
4. Soient

X = (x_1, \dots, x_n)

Y = (y_1, \dots, y_n)

deux vecteurs quelconques dans

{ − 1, 1}^n

. Montrer que

(x_i y_j C_(i, j))_(1 ⩽ i, j ⩽ n)

est une famille de

n^2

variables aléatoires à valeurs dans

{ - 1, 1}

, indépendantes et de loi uniforme.
5. Montrer que pour tout

t ⩾ 0

, on a

ℙ(M(C) ⩾ tn^(3/2)) ⩽ exp(- ((t^2)/2 - 2ln2)n)

On rappelle la notation $M_–(n) = min{M(A)|A ∈ M_n({ − 1, 1})}$ . Montrer que pour tout $n ⩾ 1$ , on a

M_-(n) ⩽ 2\sqrt(ln2)n^(3/2).

Indication : on pourra commencer par montrer que pour tout

ε > 0

, il existe une matrice

A

dans

M_n({ − 1, 1})

telle que

M(A) ⩽ (2\sqrt(ln2) + ε)n^(3/2)

Partie III

Dans cette partie, on établit un minorant non trivial pour

M_-(n)

Pour $A = (a_(i, j))_(1 ⩽ i, j ⩽ n) ∈ M_n({ − 1, 1})$ et $Y = (y_i)_(1 ⩽ i ⩽ n) ∈ { − 1, 1}^n$ , on note

g_A(Y) = max{^t XAY|X ∈ { − 1, 1}^n}

Montrer que la fonction

g_A

peut se réécrire

g_A(Y) = \sum_(i = 1)^n|\sum_(j = 1)^n a_(i, j)y_j|.

On introduit maintenant une variable aléatoire uniforme $Z : Ω → { − 1, 1}^n$ . Pour $ω \in Ω$ , on note $Z_i(ω)$ les coordonnées de $Z(ω)$ . Montrer que pour tout $A = (a_(i, j))_(1 ⩽ i, j ⩽ n) ∈ M_n({ − 1, 1})$ , on a

∀i ∈ {1, …, n}, 𝔼[|∑_(j = 1)^n a_(i, j)Z_j|] = 1/(2^n)∑_(k = 0)^n(n/k)|n − 2k|,

où

(n/k)

désigne le coefficient binomial. En déduire

𝔼[g_A(Z)] = n/(2^n)\sum_(k = 0)^n(n/k)|n - 2k|.

(a) Montrer que pour $m \in {0, \dots, n - 1}$ , on a

\sum_(k = 0)^m(n - 2k)(n/k) = n((n - 1)/m)

(b) En déduire que pour toute

A ∈ M_n({ − 1, 1})

𝔼[g_A(Z)] = (n^2)/(2^(n - 1))((n - 1)/(⌊n/2⌋)),

où

⌊n/2⌋

désigne la partie entière de

n/2

.
4. (a) Montrer que

M_-(n) ⩾ (n^2)/(2^(n - 1))((n - 1)/(⌊n/2⌋)).

(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

α > 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.

Pour $n \in ℕ$ , on pose

I_n = \int_0^(+ \infty)x^n e^(- x)dx

Déterminer par récurrence

I_n

pour tout

n \in ℕ

.
2. Montrer que pour

n ⩾ 1

, on a

I_n = (n/e)^n\sqrtn\int_(- \sqrtn)^(+ \infty)(1 + x/(\sqrtn))^n e^(- x\sqrtn)dx

Soit $U$ l'ouvert de $ℝ^2$ défini par

U:={(t, x) ∈ ℝ^2|t > 0 et x > − t}

et soit

f

la fonction définie sur

U

par

f(t, x) = t^2 ln(1 + x/t) - tx

(a) Montrer que pour

(t, x) \in U

, on a

x ⩽ 0 \Rightarrow f(t, x) ⩽ - (x^2)/2

(b) Pour

x > 0

, montrer que l'on a

\forallt ⩾ 1, f(t, x) ⩽ f(1, x)

Pour cela, on pourra commencer par écrire

(\partialf)/(\partialt)(t, x)

sous la forme

tF(x/t)

pour une certaine fonction

F

que l'on étudiera.
4. Déduire des questions précédentes la formule de Stirling.

Partie V

Dans cette dernière partie, on fixe

A ∈ M_n({ − 1, 1})

et on note

m(A):=min(S(A) \cap ℕ)

Pour $Y ∈ { − 1, 1}^n$ , montrer que l'on a

min{|^t XAY||X ∈ { − 1, 1}^n} ⩽ n

et en déduire

m(A) ⩽ 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

m(A) ⩽ \sqrt(2nln(2n))

Questions fréquentes

4 questions

Sur quoi porte le sujet X-ENS Maths PC 2018 ?

Il porte sur les matrices à coefficients 1 et -1. Il mobilise le calcul matriciel et le rang, les probabilités (inégalités de Markov et de Hoeffding, espérance), le dénombrement et la formule de Stirling démontrée par des intégrales.

Quelle est la moyenne de l'épreuve X-ENS Maths PC 2018 ?

Selon le rapport, la moyenne des 1272 candidats français est de 7,9 avec un écart-type de 3,07. La présentation et la rédaction comptaient pour 2,1 points.

Quelles erreurs le jury a-t-il relevées en X-ENS Maths PC 2018 ?

Des preuves d'inclusion ou d'équivalence incomplètes, des inégalités classiques mal appliquées, une indépendance de variables aléatoires non justifiée et des calculs avec la formule de Stirling souvent faux.

Quelle partie du sujet X-ENS Maths PC 2018 était la plus difficile ?

La partie V, qui demandait d'adapter les raisonnements des parties II et III, était nettement plus difficile ; seule une fraction infime des candidats l'a abordée.

Pas de description pour le moment

Commentaires• X ENS Mathématiques PC 2018

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...