WikiPrépaLivrets

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

Pas encore noté
Logo concours X-ENS

Explorer les annales

BanqueX-ENSAnnée2019FilièrePCMatièreMathématiques
Annales X-ENS PC MathématiquesX-ENS PC 2019PC MathématiquesMathématiques 2019

Téléchargements

Télécharger le sujet (PDF)
Corrigé
Rapport du juryLire en ligneLaTeXWord

Présentation du sujet

Difficulté moyenne
Inégalités sur les polynômes, lois binomiales et reconstruction d'un signal bruité
Afficher ou masquer la section

Le sujet démontre d'abord plusieurs inégalités : un principe du maximum pour les polynômes sur le disque unité par des matrices unitaires, puis une minoration pour les polynômes à coefficients dans {-1, 0, 1}. Il établit ensuite une majoration d'une probabilité impliquant des lois binomiales, et utilise enfin ces résultats pour montrer qu'on peut reconstruire une suite de 0 et de 1 à partir d'observations bruitées.

  1. 1PréliminairesNorme euclidienne sur C^n, matrices unitaires et norme subordonnée d'une matrice diagonale ou semblable par une matrice unitaire.
  2. 2Première partie : Théorème 1Le maximum du module d'un polynôme sur le disque unité fermé est atteint sur le cercle unité, démontré à l'aide d'une matrice unitaire.
  3. 3Deuxième partie : Théorème 2Minoration du module d'un polynôme à coefficients dans {-1, 0, 1} sur un arc du cercle unité, à l'aide d'un produit de polynômes.
  4. 4Troisième partie : Théorème 3Majoration exponentielle d'une probabilité portant sur une somme de variables de Bernoulli indépendantes, par une étude de fonction et l'inégalité de Markov appliquée à une exponentielle.
  5. 5Quatrième partie : reconstruction d'un signal bruitéModèle d'observation bruitée d'une suite de 0 et de 1, calculs de modules et d'espérances, puis nombre d'observations suffisant pour reconstruire la source.

Difficulté moyenne. Le jury décrit une progression lente et un découpage très détaillé en questions intermédiaires, les parties étant de difficulté similaire sauf la dernière, nettement plus difficile.

Ce qu'a observé le jury

6 erreurs relevées
Préliminaires simples mal traités · Résultat démontré à moitié · Calcul matriciel fautif
Afficher ou masquer la section

La progression de difficulté était lente et le découpage détaillé facilitait de nombreuses questions, la dernière partie étant nettement plus difficile car elle introduisait un nouveau contexte. Le jury regrette un manque de rigueur sur des questions élémentaires, mais salue les efforts de rédaction d'une grande partie des candidats. Environ 75 % des candidats traitent le même lot de questions, et la différence se fait sur quelques questions plus longues.

Les erreurs les plus sanctionnées

  1. 1
    Préliminaires simples mal traitésQ2, Q3, Q4

    Des questions sans difficulté particulière ont été mal traitées par un nombre trop important de candidats, et la question 4, pourtant peu originale, a posé des difficultés considérables.

  2. 2
    Résultat démontré à moitiéQ5

    Pour montrer qu'une matrice est unitaire, beaucoup vérifient une seule des deux conditions et s'arrêtent là.

  3. 3
    Calcul matriciel fautifQ6

    Fautes nombreuses de calcul matriciel, alors qu'une simple récurrence suffisait, et manque de rigueur sur la multiplication par une matrice diagonale.

    « Cette question a donné lieu à une nombre incroyablement important de fautes de calcul matriciel. »
  4. 4
    Confusion entre module et normeQ7, Q8

    Beaucoup confondent |·| et ||·||, ce qui explique le très faible taux de réussite des questions 7 et 8.

  5. 5
    Hypothèse restrictive non levéeQ11

    Plusieurs candidats prouvent le Théorème 2 en gardant l'hypothèse a0 = 1 sans savoir s'en affranchir.

  6. 6
    Cas oubliés et calcul de moduleQ14, Q15.b

    Pour le Théorème 3, il ne fallait pas oublier les cas p = q et p > q. En quatrième partie, le calcul de module initial a été mal traité par un grand nombre.

Ce qui a été bien réussi

  • La question 1 a été correctement traitée par la très grande majorité des candidats.
  • L'inégalité de la question 9 a été montrée correctement par la plupart des candidats.
  • Les questions 12.a, 12.b et 12.c ont été plutôt bien traitées.
  • Le calcul de la question 13.b a été mené correctement par une grande partie des candidats.
  • Le nombre de copies très mal écrites est en diminution.

Conseils du jury

  • Lire le sujet en entier avant de commencer.
  • Énoncer entièrement les théorèmes, vérifier toutes leurs hypothèses et mettre en évidence les points clés de la démonstration.
  • Citer proprement les résultats des questions précédentes utilisés.
  • Traiter avec soin quelques questions plus difficiles plutôt que survoler toutes les questions faciles.
  • Ne pas bâcler les premières questions 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.
Afficher ou masquer la section
Sujet en PDF

CONCOURS D’ADMISSION 2019

JEUDI 18 AVRIL 2019-8h00-12h00 FILIERE PC - Epreuve n^∘1

MATHEMATIQUES(XEULC)

Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
Les quatre parties sont indépendantes entre elles.
Dans l'ensemble du sujet, pour répondre à une question, on pourra admettre les résultats des questions précédentes.

Notations

Dans l'ensemble du sujet m et n désignent des entiers strictement positifs. L'ensemble ℂ désigne le corps des nombres complexes. Le module d'un nombre complexe z est noté |z| et son conjugué est noté z¯. On note 𝔻^– = {z ∈ ℂ : |z| ⩽ 1} le disque unité fermé, et 𝕊 = {z ∈ ℂ : |z| = 1}.
On note M_(m, n)(ℂ) l'ensemble des matrices à m lignes et à n colonnes à coefficients dans ℂ et M_n(ℂ) = M_(n, n)(ℂ) l'ensemble des matrices à n lignes et à n colonnes à coefficients dans ℂ. On note I_n la matrice identité de M_n(ℂ). La matrice transposée d'une matrice A ∈ M_(m, n)(ℂ) est notée A^⊤. Si A = (a_(i, j))_(0 ⩽ i ⩽ m − 1; 0 ⩽ j ⩽ n − 1) ∈ M_(m, n)(ℂ), on note A¯^⊤ ∈ M_(n, m)(ℂ) la matrice (a_(j, i)^–)_(0 ⩽ i ⩽ n − 1; 0 ⩽ j ⩽ m − 1).
On dit qu'une matrice U ∈ M_n(ℂ) est unitaire si
UU¯^⊤ = U¯^⊤U = I_n
Les coefficients d'un vecteur x ∈ ℂ^n sont notés x_0, …, x_(n − 1). Un vecteur x ∈ ℂ^n sera vu comme un élément de M_(n, 1)(ℂ). Pour tous x ∈ ℂ^n et y ∈ ℂ^n, la matrice x^⊤y ∈ M_1(ℂ) est identifiée au nombre complexe ∑_(i = 0)^(n − 1)x_i y_i. Nous munissons ℂ^n de la norme ‖‖_2 définie par
∀x ∈ ℂ^n, ‖x‖_2 = (∑_(i = 0)^(n − 1)|x_i|^2)^(1/2)
Si A ∈ M_(m, n)(ℂ), on note
‖A‖ = sup_(x ∈ ℂ^n; ‖x‖_2 = 1)‖Ax‖_2
Par convention, pour A ∈ M_n(ℂ), on pose A^0 = I_n.
Dans tout le sujet, ( Ω, A, ℙ ) désigne un espace probabilisé sur lequel seront définies les différentes variables aléatoires du sujet. On admettra que toutes les variables aléatoires introduites peuvent bien être construites sur cet espace. On notera ℙ(A) la probabilité d'un événement A ⊂ Ω et 𝔼[X] l'espérance d'une variable aléatoire X sur (Ω, A, ℙ) à valeurs réelles.

Préliminaires

Les résultats démontrés ici seront utiles dans la première partie.
  1. Lorsque x ∈ ℂ^n, vérifier que ‖x‖_2^2 = x¯^⊤x.
  2. Soit U ∈ M_n(ℂ) une matrice unitaire. Montrer que ‖Ux‖_2 = ‖x‖_2 pour tout x ∈ ℂ^n.
  3. Si D ∈ M_n(ℂ) est une matrice diagonale dont les coefficients diagonaux sont d_0, …, d_(n − 1), montrer que ‖D‖ = max_(0 ⩽ i ⩽ n − 1)|d_i|.
  4. Soient A, B ∈ M_n(ℂ). On suppose qu'il existe une matrice unitaire U ∈ M_n(ℂ) telle que B = UAU^(− 1). Montrer que ‖A‖ = ‖B‖.

Première partie

Le but de cette partie est de démontrer le résultat suivant.
Théorème 1. Soit f ∈ ℂ[X] un polynôme. Alors
sup_(z ∈ 𝔻^–)|f(z)| = sup_(z ∈ 𝕊)|f(z)|.
Pour cela, on admet le résultat suivant, qui pourra être utilisé sans démonstration.
A) Si M ∈ M_m(ℂ) est une matrice unitaire, il existe une matrice diagonale D ∈ M_m(ℂ), dont tous les coefficients diagonaux ont module 1 , et une matrice unitaire U ∈ M_m(ℂ) telles que M = UDU^(− 1).
Pour démontrer le Théorème 1, on fixe un polynôme f ∈ ℂ[X] de degré n ⩾ 1. On considère un nombre complexe z ∈ 𝔻^– et on définit les matrices M ∈ M_(n + 1)(ℂ) et P ∈ M_(n + 1, 1)(ℂ) par
M = (z, 0, 0, ⋯, 0; √(1 − |z|^2), 0, 0, ⋯, 0; 0, (1, 0, ⋯, 0; 0, 0, 1, ⋱), 0; ⋮, 0, ⋱, ⋱, ⋮; 0, 0, ⋯, 1) = (z, 0, 0, ⋯, 0, √(1 − |z|^2); √(1 − |z|^2), 0, 0, ⋯, 0, − z¯; 0, 0, 0; ⋮, I_(n − 1), ⋮; 0, 0)
et
P = (1; 0; ⋮; 0)
  1. Montrer que M est une matrice unitaire.
  2. Montrer que z^k = P^⊤M^k P pour tout entier 0 ⩽ k ⩽ n.
  3. Montrer que |f(z)| ⩽ ‖f(M)‖.
  4. Démontrer le Théorème 1.

Deuxième partie

Le but de cette partie est de démontrer l'énoncé suivant (on pourra utiliser le Théorème 1).
Théorème 2. Soit n ⩾ 1 un entier et A(z) = ∑_(k = 0)^(n − 1)a_k z^k un polynôme non nul tel que a_k ∈ { − 1, 0, 1} pour tout 0 ⩽ k ⩽ n − 1. Alors pour tout entier L ⩾ 1 on a
sup_(θ ∈ [ − π/L, π/L])|A(e^(iθ))| ⩾ 1/(n^(L − 1)).
Pour démontrer ce résultat, on fixe un entier n ⩾ 1 et A(z) = ∑_(k = 0)^(n − 1)a_k z^k un polynôme tel que a_k ∈ { − 1, 0, 1} pour tout 0 ⩽ k ⩽ n − 1. On fixe également un entier L ⩾ 1.
9. Si z ∈ ℂ vérifie |z| = 1, montrer que |A(z)| ⩽ n.
10. On suppose dans cette question que a_0 = 1, et on pose, pour tout z ∈ ℂ,
F(z) = ∏_(j = 0)^(L − 1)A(ze^((2iπj)/L))
a. Montrer qu'il existe z_0 ∈ ℂ tel que |z_0| = 1 et |F(z_0)| ⩾ 1.
b. Montrer que |F(z_0)| ⩽ n^(L − 1). sup_(θ ∈ [ − π/L, π/L])|A(e^(iθ))|.
11. Démontrer le Théorème 2.

Troisième partie

Le but de cette partie est de démontrer le résultat suivant :
Théorème 3. On fixe p, q ∈ [0, 1]. Soit n ⩾ 1 un entier et soit S_n une somme de n variables aléatoires à valeurs dans {0, 1} mutuellement indépendantes de Bernoulli de paramètre p. Alors
ℙ(|(S_n)/n − q| ⩽ |(S_n)/n − p|) ⩽ e^(− n((p − q)^2)/2)
Pour démontrer ce résultat, on fixe p, q ∈ [0, 1] et (X_i)_(1 ⩽ i ⩽ n) une famille de n variables aléatoires à valeurs dans {0, 1} mutuellement indépendantes de Bernoulli de paramètre p. On pose alors S_n = ∑_(i = 1)^n X_i.
12. Soit g : ℝ_+ → ℝ la fonction définie par g(x) = ln(1 − p + pe^x) pour tout x ⩾ 0.
a. Montrer que g est bien définie et de classe C^2 sur ℝ_+. Pour x ⩾ 0, exprimer g^(′′)(x) sous la forme (αβ)/((α + β)^2), où α et β sont des réels positifs pouvant dépendre de x.
b. Montrer que g^(′′)(x) ⩽ 1/4 pour tout x ⩾ 0.
c. Montrer que
ln(1 − p + pe^x) ⩽ px + (x^2)/8 pour tout x ⩾ 0
  1. On suppose dans cette question que p < q.
    a. Justifier que
ℙ(|(S_n)/n − q| ⩽ |(S_n)/n − p|) = ℙ(S_n ⩾ (p + q)/2n)
b. Soit X une variable aléatoire de Bernoulli de paramètre p. Pour u > 0, calculer 𝔼(e^(uX)).
c. Montrer que pour tout u > 0,
ℙ(S_n ⩾ (p + q)/2n) ⩽ e^(− n((p + q)/2u − ln(1 − p + pe^u)))
Indication. On pourra admettre que si (Z_i)_(1 ⩽ i ⩽ n) sont n variables aléatoires réelles mutuellement indépendantes et prenant un nombre fini de valeurs, alors 𝔼(∏_(i = 1)^n Z_i) = ∏_(i = 1)^n 𝔼(Z_i).
d. Montrer que ℙ(S_n ⩾ (p + q)/2n) ⩽ e^(− n((p − q)^2)/2).
14. Démontrer le Théorème 3.

Quatrième partie

Dans cette partie, on s'intéresse à la reconstruction d'une suite de 0 ou 1 à partir d'un échantillon d'observations bruitées (on pourra utiliser le Théorème 2 et le Théorème 3).
Plus précisément, étant donné un élément x = (x_0, …, x_(n − 1)) ∈ {0, 1}^n, appelé la source, et un paramètre p ∈ ]0, 1[ fixé, on considère la variable aléatoire O(x) à valeurs dans {0, 1}^n construite comme suit :
  • soient (B_i)_(0 ⩽ i ⩽ n − 1) des variables aléatoires à valeurs dans {0, 1} mutuellement indépendantes de Bernoulli de paramètre p;
  • on note N la variable aléatoire définie par
N = Card({0 ⩽ i ⩽ n − 1 : B_i = 1})
et I_0 < I_1 < ⋯ < I_(N − 1) les éléments de l'ensemble aléatoire {0 ⩽ i ⩽ n − 1 : B_i = 1} rangés dans l'ordre croissant;
  • on pose enfin
O(x) = (O_0(x), O_1(x), …, O_(n − 1)(x)) = (x_(I_0), x_(I_1), …, x_(I_(N − 1)), 0, 0, …, 0) ∈ {0, 1}^n
avec la convention O(x) = (0, 0, …, 0) ∈ {0, 1}^n si N = 0.
La variable aléatoire O(x) est appelée observation bruitée de source x. Ainsi, O(x) est obtenue à partir de x en gardant chaque coordonnée avec probabilité p, indépendamment les unes des autres (complétée par des 0 pour obtenir un vecteur de longueur n ). Par exemple, si x = (x_0, x_1, x_2, x_3, x_4) = (1, 0, 1, 1, 1) et si B_0 = 0, B_1 = 1, B_2 = 0, B_3 = 1, B_4 = 1 (ce qui arrive avec probabilité p^3(1 − p)^2 ), alors O(x) = (O_0(x), O_1(x), …, O_4(x)) = (x_1, x_3, x_4, 0, 0) = (0, 1, 1, 0, 0).
15. Soit θ ∈ [ − π, π].
a. Montrer que cos(θ) ⩾ 1 − (θ^2)/2.
b. Montrer que |(e^(iθ) − (1 − p))/p| ⩽ exp((1 − p)/(2p^2) ⋅ θ^2).
Indication. On pourra calculer |(e^(iθ) − (1 − p))/p|^2.
16. Soit x = (x_0, …, x_(n − 1)) ∈ {0, 1}^n et considérons une observation bruitée
O(x) = (O_0(x), O_1(x), …, O_(n − 1)(x))
de source x.
a. Si 0 ⩽ j ⩽ k ⩽ n − 1, montrer que ℙ(N ⩾ j + 1 et I_j = k) = p(k/j)p^j(1 − p)^(k − j).
b. Montrer que, pour tout 0 ⩽ j ⩽ n − 1, 𝔼[O_j(x)] = p∑_(k = j)^(n − 1)x_k(k/j)p^j(1 − p)^(k − j).
c. Montrer que pour tout w ∈ ℂ,
𝔼[∑_(j = 0)^(n − 1)O_j(x)w^j] = p∑_(k = 0)^(n − 1)x_k(pw + 1 − p)^k
Dans la suite, on pose L_n = ⌊n^(1/3)⌋, où ⌊t⌋ désigne la partie entière d'un nombre réel t.
17. Soient x, y ∈ {0, 1}^n tels que x ≠ y. Posons, pour z ∈ ℂ, A_(x, y)(z) = ∑_(k = 0)^(n − 1)(x_k − y_k)z^k.
a. Justifier l'existence de θ_0 ∈ [ − π/(L_n), π/(L_n)] tel que |A_(x, y)(e^(iθ_0))| ⩾ 1/(n^(L_n − 1)).
b. Démontrer que
∑_(j = 0)^(n − 1)|𝔼[O_j(x)] − 𝔼[O_j(y)]| ⋅ |(e^(iθ_0) − (1 − p))/p|^j ⩾ p/(n^(L_n − 1))
c. Justifier l'existence d'un entier j_n(x, y) tel que 0 ⩽ j_n(x, y) ⩽ n − 1 et
|𝔼[O_(j_n(x, y))(x)] − 𝔼[O_(j_n(x, y))(y)]| ⩾ p/(n^(L_n))exp(− (1 − p)/(2p^2) ⋅ (π^2)/(L_n^2)n)
Dans la suite, on fixe une fois pour toutes un entier n qu'il faut considérer comme étant très grand. Pour chaque couple (x, y) ∈ ({0, 1}^n)^2 tel que x ≠ y, on fixe un entier j_n(x, y) dont l'existence est prouvée dans la question 17c.
Soient T ⩾ 1 et (E^1, E^2, …, E^T) ∈ ({0, 1}^n)^T. Ainsi, pour 1 ⩽ i ⩽ T et 0 ⩽ j ⩽ n − 1, on a E_j^i ∈ {0, 1}. On dit que x est meilleur que y compte tenu de E^1, E^2, …, E^T si
|1/T∑_(i = 1)^T E_(j_n(x, y))^i − 𝔼[O_(j_n(x, y))(x)]| < |1/T∑_(i = 1)^T E_(j_n(x, y))^i − 𝔼[O_(j_n(x, y))(y)]|.
On pose alors R_(n, T)(E^1, E^2, …, E^T) = x si pour tout y ≠ x, x est meilleur que y. Si l'on ne peut pas trouver de tel x on pose R_(n, T)(E^1, E^2, …, E^T) = (0, 0, …, 0).
18. Démontrer que si T_n ⩾ e^(3ln(n)n^(1/3)) alors pour tout x ∈ {0, 1}^n et toute suite
O^1(x), O^2(x), …, O^(T_n)(x)
de T_n variables aléatoires à valeurs dans {0, 1}^n mutuellement indépendantes de même loi que O(x), on a
max_(x ∈ {0, 1}^n)ℙ(R_(n, T_n)(O^1(x), O^2(x), …, O^(T_n)(x)) ≠ x) ⩽ u_n
où (u_n)_(n ⩾ 1) est une suite tendant vers 0 lorsque n tend vers l'infini.
Indication. On pourra commencer par écrire, en le justifiant, que
ℙ(R_(n, T)(O^1(x), O^2(x), …, O^T(x)) ≠ x); ⩽ ∑_(y ∈ {0, 1}^n; y ≠ x)ℙ(x n'est pas meilleur que y compte tenu de O^1(x), O^2(x), …, O^T(x))
On a donc démontré qu'en partant de x ∈ {0, 1}^n inconnu, on peut retrouver x à partir de la donnée d'une suite
O^1(x), O^2(x), …, O^T(x)
de T variables aléatoires à valeurs dans {0, 1}^n mutuellement indépendantes de même loi que O(x) (qui représentent la donnée de T échantillons bruités obtenus à partir d'une même source), avec grande probabilité à partir de e^(3ln(n)n^(1/3)) échantillons différents.

Questions fréquentes

4 questions
Sur quels chapitres porte le sujet X-ENS Maths PC 2019 ?
Afficher ou masquer la section

Sur quels chapitres porte le sujet X-ENS Maths PC 2019 ?

Sur l'algèbre linéaire avec les matrices unitaires et la norme subordonnée, les polynômes à variable complexe, et les probabilités discrètes avec des sommes de variables de Bernoulli indépendantes.

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

Un manque de rigueur sur des questions élémentaires, des démonstrations incomplètes, des fautes de calcul matriciel et une confusion entre module et norme.

Quelle partie du sujet X-ENS Maths PC 2019 est la plus difficile ?

Selon le jury, la quatrième partie sur la reconstruction d'un signal bruité est nettement plus difficile, car elle introduit un nouveau contexte. Ses dernières questions ont été résolues par très peu de candidats.

Comment se démarquer sur le sujet X-ENS Maths PC 2019 ?

Le jury observe qu'environ 75 % des candidats traitent le même lot de questions. Ceux qui font la différence réussissent deux ou trois questions plus longues demandant un raisonnement en plusieurs étapes.

Pas de description pour le moment