Mines Mathématiques 1 PC 2018Sujet, corrigé et rapport du jury

Q: Sur quels chapitres porte le sujet de maths 1 PC Mines-Ponts 2018 ?

Le sujet porte sur les probabilités discrètes, la combinatoire, l'algèbre linéaire et l'analyse asymptotique, à travers la démonstration du théorème de Komlós sur l'inversibilité d'une matrice aléatoire.

Q: Quelles erreurs le jury a-t-il le plus relevées sur ce sujet de maths 1 PC Mines-Ponts 2018 ?

Le jury relève une maîtrise insuffisante de la notion d'équivalent, des probabilités incohérentes (supérieures à 1), et un argument central d'algèbre linéaire sur les sous-espaces (question 12) resté quasiment non traité.

Q: Ce sujet de maths 1 PC Mines-Ponts 2018 est-il difficile ?

Oui, le rapport le qualifie explicitement d'un peu difficile, tout en soulignant qu'il ne s'appuie que sur le programme de première année.

Q: Ce sujet de Mines-Ponts PC 2018 est-il faisable en première année ?

Le rapport indique que le sujet s'appuie exclusivement sur le programme de première année, mais le signale comme un défaut du sujet car cela l'a rendu plus difficile que prévu pour les candidats de seconde année.

Théorème de Komlos

Pas encore noté

Explorer les annales

BanqueMines Année2018 FilièrePC MatièreMathématiques

Annales Mines PC Mathématiques Mines 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

Le théorème de Komlós : inversibilité d'une matrice aléatoire de Rademacher

Le problème démontre le théorème de Komlós (1967) : une matrice aléatoire dont les coefficients valent indépendamment +1 ou -1 est inversible avec une probabilité tendant vers 1 quand sa taille tend vers l'infini. La démonstration combine des inégalités sur les coefficients binomiaux, un argument déterministe d'algèbre linéaire, un résultat combinatoire sur les anti-chaînes (théorème d'Erdös-Littlewood-Offord) et une notion d'universalité.

1A. Coefficients binomiauxpremière annéeInégalités et équivalents sur les coefficients binomiaux centraux.
2B. Dimension 2première annéeÉtude de l'espérance, de la variance et de la probabilité de non-inversibilité pour n = 2.
3C. Quelques bornespremière annéeMajoration de la probabilité de non-inversibilité par un argument déterministe d'algèbre linéaire.
4D. Théorème de Erdös-Littlewood-Offordpremière annéeRésultat combinatoire sur les anti-chaînes et inégalité d'anti-concentration.
5E. Universalitépremière annéeArgument final combinant anti-concentration et algèbre linéaire pour conclure la démonstration.

Difficile. Le rapport indique explicitement que malgré son intérêt mathématique, le sujet s'est révélé un peu difficile, tout en s'appuyant exclusivement sur le programme de première année.

Ce qu'a observé le jury

5 erreurs relevées

Équivalent mal maîtrisé (Q2) · Probabilités incohérentes (Q7) · Argument déterministe clé rarement vu (Q12)

Le sujet abordait un grand nombre de notions du programme (probabilités, combinatoire, analyse asymptotique, algèbre linéaire), ce qui semble avoir déconcerté une bonne partie des candidats. Peu de questions étaient réellement délicates ou vraiment simples, mais beaucoup demandaient un soin particulier dans la rédaction, sur un ensemble assez long.

Les erreurs les plus sanctionnées

1
Équivalent mal maîtrisé (Q2)Q2
Beaucoup de candidats maîtrisent mal la notion d'équivalent et remplacent abusivement la partie entière de n/2 par n/2 sans justification.
« on remplace sans vergogne »
2
Probabilités incohérentes (Q7)Q7
Certaines copies aboutissent à des probabilités strictement supérieures à 1 sans que les candidats ne s'en étonnent.
« on conseille aux candidats de prendre un peu de recul ! »
3
Argument déterministe clé rarement vu (Q12)Q12
L'énoncé d'algèbre linéaire sur les sous-espaces contenant peu de vecteurs à coordonnées ±1, pourtant central dans la démonstration, a été très peu traité.
« Question rarement traitée. »
4
Argument combinatoire sur les anti-chaînes (Q17)Q17
Le résultat combinatoire reliant le cardinal d'une anti-chaîne aux coefficients binomiaux n'a été maîtrisé que par les meilleures copies.
« Cette question combinatoire difficile n’a été bien traitée que dans les meilleures copies. »
5
Question quasiment jamais résolue (Q13)Q13
Cette question, qui demande de construire un vecteur à coordonnées entières orthogonal à une famille donnée, s'est révélée particulièrement délicate dans le temps imparti.
« elle est à vrai dire assez difficile à résoudre »

Ce qui a été bien réussi

L'épreuve a mis en évidence un nombre significatif de très bonnes copies et un lot important de copies satisfaisantes ayant traité correctement une petite moitié des questions.
Les questions simples ont permis à la plupart des candidats qui les ont abordées de récupérer quelques points.

Conseils du jury

Apprendre son cours de manière réfléchie plutôt que de manipuler les objets mathématiques de façon automatique.
Face à un sujet difficile, bien traiter une partie des questions plutôt que de produire des réponses creuses sur l'ensemble du sujet.
Soigner la rédaction en probabilités autant que dans les autres parties des mathématiques.
Pratiquer régulièrement le calcul de majorations et d'estimations asymptotiques, au cœur d'une grande part du 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

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH, MINES SAINT-ÉTIENNE, 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.

Notations :

Si $x$ est un nombre réel on note $[x]$ sa partie entière, c'est-à-dire le plus grand entier relatif qui est inférieur ou égal à $x$ .
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^n$ à l'espace des matrices lignes $M_(1, n)(R)$ et on notera $⟨x, y⟩$ le produit scalaire canonique des deux vecteurs, soit

⟨x, y⟩ = \sum_(j = 1)^n x_j y_j

les

x_j, y_j

étant les composantes de

x, y

respectivement.

Si $V$ est un sous-ensemble de $R^n$ on note $Vect(V)$ l'espace vectoriel engendré par $V$ . On note $V^⊥$ l'orthogonal de $V$ , c'est-à-dire l'ensemble des vecteurs $y$ tels que $\forallx \in V, ⟨x, y⟩ = 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! \sim _(n \to + \infty)\sqrt(2πn)(n/e)^n

Définition 1 (Espace de Rademacher) Si n,

q \in N^*

, on note

Ω_(q, n) = {ω = (ω_(i, j), 1 ≤ i ≤ q, 1 ≤ j ≤ n) tels que ω_(i, j) = ± 1, ∀i, j}

Pour tout

i \in {1, \dots, q}

j \in {1, \dots, n}

, on introduit la variable aléatoire

M_(i, j)

telle que

M_(i, j) : Ω_(q, n), ⟶ { − 1, 1}; ω, ⟼ ω_(i, j)

On munit

Ω_(q, n)

de la probabilité uniforme

P

. Cela signifie que les variables aléatoires (

M_(i, j), 1 \leq i \leq q, 1 \leq j \leq n

) sont indépendantes et de même loi:

P(M_(i, j) = 1) = 1/2 = P(M_(i, j) = - 1)

q = n

, on note

M^((n))

la matrice aléatoire

M^((n)) = (M_(1, 1), \dots, M_(1, n); ⋮, ⋮; M_(n, 1), \dots, M_(n, n))

On note

L_1^((n)), \dots, L_n^((n))

les vecteurs lignes de

M^((n))

. Par construction, ce sont des vecteurs 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)

lim_(n \to \infty)P(detM^((n)) = 0) = 0

A Coefficients binomiaux

Soit $n \in N^*$ : montrer que l'application

k ⟼ (n/k)

est croissante sur

{0, \dots, [n/2]}

. En déduire que pour tout

k \in {0, \dots, n}

(n/k) \leq (n/([n/2]))

Trouver un équivalent de $(n/([n/2]))$ quand $n$ tend vers l'infini. En déduire qu'il existe un entier $n_0$ tel que pour $n \geq n_0$ ,

(n/([n/2])) \leq (2^n)/(\sqrtn).

Montrer que pour tout entier non nul $n$ et tout $k \in {0, \dots, n}$ ,

(n/k)2^(k - 1) \leq n^k

On note (

e_i, 1 \leq i \leq n

) la base canonique de

R^n

v = \sum_(i = 1)^n e_i

. On identifie

Ω_(1, n)

et le sous-ensemble de

R^n

{∑_(i = 1)^n ω_i e_i, (ω_1, ⋯, ω_n) ∈ Ω_(1, n)}.

Pour tout $i \in {1, \dots, n}$ , exprimer $e_i$ en fonction de $v$ et $v - 2e_i$ . En déduire que $Vect(Ω_(1, n)) = R^n$ .

B Dimension 2

Déterminer l'espérance de $detM^((2))$ .
Montrer que la variance de $detM^((2))$ est égale à 2 .
Calculer $P(detM^((2)) = 0)$ .

C Quelques bornes

On suppose dorénavant

n \geq 2

.
8. Quelle est la probabilité que les deux premières lignes de

M^((n))

soit égales ou opposées?

En déduire que

P(detM^((n)) = 0) \geq 2^(1 - n)

n \geq 2

.
9. Soient

l_1, \dots, l_n

des vecteurs non nuls de

R^n

. Montrer que ces vecteurs sont liés si et seulement si, il existe

j \in {1, \dots, n - 1}

tel que

l_(j + 1) ∈ Vect({l_1, ⋯, l_j})

En déduire que

P(detM^((n)) = 0) \leq \sum_(j = 1)^(n - 1)P(L_(j + 1)^((n)) \in Vect(L_1^((n)), \dots, L_j^((n)))).

Soit

H

un sous-espace vectoriel de

R^n

de dimension

d

. On rappelle que

H^⊥

est un sous-espace vectoriel de dimension

n - d

et que

(H^⊥)^⊥ = H

.
10. Montrer alors qu'il existe des réels (

α_(i, j), 1 \leq i \leq n - d, 1 \leq j \leq n

) tels que

x = (x_1, \dots, x_n) \in H ⟺ (α_(1, 1), \dots, α_(1, n); ⋮, ⋮; α_(n - d, 1), \dots, α_(n - d, n))(x_1; ⋮; x_n) = (0; ⋮; 0).

En utilisant le pivot de Gauss, montrer qu'il existe $1 \leq i_1 < \dots < i_d \leq n$ tel que pour tout $(y_1, \dots, y_d) \in R^d$ il existe un unique $x = (x_1, \dots, x_n) \in H$ tel que $x_(i_k) = y_k$ pour $k = 1, \dots, d$ .
En déduire que

P(L_1^((n)) \in H) \leq 2^(d - n),

puis que pour tout

j \in {1, \dots, n - 1}

P(L_(j + 1)^((n)) \in Vect(L_1^((n)), \dots, L_j^((n)))) \leq 2^(j - n).

Indication : on pourra utiliser la conséquence suivante de la formule des probabilités totales

P(L_(j + 1)^((n)) \in Vect(L_1^((n)), \dots, L_j^((n)))); = \sum_(l_1, \dots, l_j \in Ω_(1, n))P(L_(j + 1)^((n)) \in Vect(l_1, \dots, l_j)|, L_1^((n)) = l_1, \dots, L_j^((n)) = l_j); \times P(L_1^((n)) = l_1, \dots, L_j^((n)) = l_j)

et l'indépendance des vecteurs lignes.
Soit

q < n

ω \in Ω_(q, n)

. On note

l_1, \dots, l_q

ses vecteurs lignes.
13. Montrer que l'on peut trouver un vecteur non nul orthogonal à

Vect(l_i, i = 1, \dots, q)

qui soit à coordonnées dans

Z

D Théorème de Erdös-Littlewood-Offord

Définition 2 Soit

n

un entier non nul. Soit

A

un sous-ensemble de

P({1, \dots, n})

. On dit que

A

est une anti-chaîne si deux éléments distincts

A, B

quelconques de

A

sont incomparables, c'est-à-dire tels que

A

n'est pas inclus dans

B

B

n'est pas inclus dans

A

Commençons par un exemple. Soit

k \in {1, \dots, n}

A_k

l'ensemble des parties de

{1, \dots, n}

de cardinal

k

.
14. Montrer que

A_k

est une anti-chaîne et que

|A_k| \leq (n/([n/2])) \leq (2^n)/(\sqrtn)

la deuxième inégalité ayant lieu pour

n

assez grand.
Définition 3 Soit

A

une anti-chaîne et

A \in A

, de cardinal noté

|A|

. On note

S_A

, l'ensemble des bijections

σ

{1, \dots, n}

dans lui-même telles que la restriction de

σ

{1, \dots, |A|}

soit une bijection de

{1, \dots, |A|}

dans

A

.
15. Quel est le cardinal de

S_A

?
16. Soit

B \in A

avec

B \neq A

. Montrer que

S_A \cap S_B = \emptyset

.
17. En déduire que si

a_k

désigne, pour

k \leq n

, le nombre d'éléments de

A

de cardinal

k

, alors

\sum_(k = 0)^n(a_k)/((n/k)) \leq 1

Montrer que

|A| \leq (n/([n/2]))

Soit

v = (v_1, \dots, v_n) \in R^n

tel que

v_j \geq 1

, pour tout

j = 1, \dots, n

. Si

A \subset {1, \dots, n}

on pose

s_A = \sum_(j \in A)v_j - \sum_(j \in A^c)v_j

où

A^c

est le complémentaire de

A

dans

{1, \dots, n}

.
19. Montrer que si

A \subset B \subset {1, \dots, n}, A \neq B

, alors

s_B - s_A \geq 2

Soit $J$ un intervalle ouvert de $R$ de longueur 2 : montrer que si $n$ est assez grand alors

P(< L_1^((n)), v>\inJ) \leq 1/(\sqrtn).

Montrer que cette propriété reste vraie si l'on suppose seulement que pour tout

j ∈ {1, ⋯, n}, |v_j| ≥ 1

Indication : construire une bijection entre

Ω_(1, n)

et l'ensemble des parties de

{1, \dots, 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 \subset Ω_(1, n)

. L'ensemble

V

est dit

k

-universel si pour tous les

k

-uplets

1 \leq j_1 < j_2\dots < j_k \leq n

et tout

ω \in Ω_(1, n)

, il existe

v \in V

tel que

v_(j_m) = ω_(1, j_m), pour tout m = 1, \dots, k.

Soit $d \in {1, ..n}$ . Montrer l'inclusion

{{L_1^((n)), ⋯, L_d^((n))} non k-universel }; ⊂ ⋃_((j_1, ⋯, j_k) ∈ {1, ⋯, n}^k; j_1 < … < j_k)⋃_(ω ∈ Ω_(1, k))⋂_(i = 1)^d⋃_(m = 1)^k{M_(i, j_m) ≠ ω_(1, j_m)}.

(On rappelle que

L_i^((n)) = (M_(i, 1), \dots, M_(i, n))

).
22. Montrer que la probabilité que

{L_1^((n)), ⋯, L_d^((n))}

ne soit pas

k

-universel est majorée par

(n/k)2^k(1 - 2^(- k))^d

En déduire que si $d \geq n/2$ et $k \leq lnn$ , alors, pour $n$ assez grand,

P({L_1^((n)), ⋯, L_d^((n))} non k-universel) ≤ 1/n

Soit $V \subset Ω_(1, n)$ un ensemble $k$ -universel tel qu'il existe $v ∈ V^⊥∖{0}$ : montrer que $v$ a au moins $k + 1$ coordonnées non nulles.

En vertu de la question 13, on peut supposer que les coordonnées de

v

sont des entiers relatifs.
25. Montrer que si

k

est assez grand

P(L_1^((n)) \in Vect(V)) \leq P(⟨L_1^((n)), v⟩ = 0) \leq k^(- 1/2)

Soit (

t_n, n \in N

) une suite croissante d'entiers telle que

t_n/n \to 0

.
26. Montrer que si

n

est assez grand alors

n - t_n \geq n/2

\sum_(j = n - t_n + 1)^(n - 1)P(L_(j + 1)^((n)) \in Vect(L_1^((n)), \dots, L_j^((n)))) \leq (2t_n)/(\sqrt(lnn))

Indication : on distinguera les cas selon que

Vect(L_1^((n)), \dots, L_j^((n)))

est

k

-universel ou pas et l'on prendra

k = [lnn]

F Théorème de Komlós

En déduire le théorème de Komlós.

Indication : on pourra partir de (2) et choisir convenablement une suite (

t_n, n \geq 1

Fin du problème

Questions fréquentes

4 questions

Sur quels chapitres porte le sujet de maths 1 PC Mines-Ponts 2018 ?

Le sujet porte sur les probabilités discrètes, la combinatoire, l'algèbre linéaire et l'analyse asymptotique, à travers la démonstration du théorème de Komlós sur l'inversibilité d'une matrice aléatoire.

Quelles erreurs le jury a-t-il le plus relevées sur ce sujet de maths 1 PC Mines-Ponts 2018 ?

Le jury relève une maîtrise insuffisante de la notion d'équivalent, des probabilités incohérentes (supérieures à 1), et un argument central d'algèbre linéaire sur les sous-espaces (question 12) resté quasiment non traité.

Ce sujet de maths 1 PC Mines-Ponts 2018 est-il difficile ?

Oui, le rapport le qualifie explicitement d'un peu difficile, tout en soulignant qu'il ne s'appuie que sur le programme de première année.

Ce sujet de Mines-Ponts PC 2018 est-il faisable en première année ?

Le rapport indique que le sujet s'appuie exclusivement sur le programme de première année, mais le signale comme un défaut du sujet car cela l'a rendu plus difficile que prévu pour les candidats de seconde année.

Pas de description pour le moment

Commentaires• Mines Mathématiques 1 PC 2018

Connectez-vous pour participer aux discussions

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

Chargement des commentaires...

Explorer les annales

Téléchargements

Présentation du sujet

Ce qu'a observé le jury

Les erreurs les plus sanctionnées

Ce qui a été bien réussi

Conseils du jury

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH, MINES SAINT-ÉTIENNE, MINES NANCY, IMT Atlantique, ENSAE PARISTECH.

CONCOURS 2018

PREMIÈRE ÉPREUVE DE MATHÉMATIQUES

Durée de l'épreuve : 3 heures

MATHÉMATIQUES I - PC

A Coefficients binomiaux

B Dimension 2

C Quelques bornes

D Théorème de Erdös-Littlewood-Offord

E Universalité

F Théorème de Komlós

Fin du problème

Questions fréquentes

Sur quels chapitres porte le sujet de maths 1 PC Mines-Ponts 2018 ?

Quelles erreurs le jury a-t-il le plus relevées sur ce sujet de maths 1 PC Mines-Ponts 2018 ?

Ce sujet de maths 1 PC Mines-Ponts 2018 est-il difficile ?

Ce sujet de Mines-Ponts PC 2018 est-il faisable en première année ?

Commentaires• Mines Mathématiques 1 PC 2018

Commentaires• Mines Mathématiques 1 PC 2018

Durée de l'épreuve : $3$ heures