WikiPrépaLivrets

X ENS Mathématiques A MP 2016Sujet, corrigé et rapport du jury

Pas encore noté
Faisable en Sup
Logo concours X-ENS

Explorer les annales

BanqueX-ENSAnnée2016FilièreMPMatièreMathématiques
Annales X-ENS MP MathématiquesX-ENS MP 2016MP MathématiquesMathématiques 2016

Téléchargements

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

Présentation du sujet

Difficile
Simplexes entiers : matrices à coefficients entiers, volume, points intérieurs et équivalence
Afficher ou masquer la section

Le sujet étudie les simplexes (volume, points entiers intérieurs, équivalence) à l'aide de matrices à coefficients entiers. La première partie construit le formalisme de GLn(Z) et une forme triangulaire par opérations sur les colonnes, la deuxième minore le nombre de points entiers intérieurs d'un simplexe, et la troisième montre qu'à équivalence près il n'existe qu'un nombre fini de simplexes entiers ayant un nombre donné de points intérieurs. Une quatrième partie de l'énoncé, hors épreuve, démontre les théorèmes admis.

  1. 1Première partie : matrices à coefficients entiersInverse à coefficients entiers, caractérisation de GLn(Z), matrice de première colonne donnée et de déterminant égal au pgcd, puis réduction triangulaire par multiplication par une matrice de GLn(Z).
  2. 2Deuxième partie : simplexes, volume et points intérieursCompacité et convexité d'un simplexe, intérieur, volume par déterminant, exemples de grands simplexes sans point entier et minoration du nombre de points entiers intérieurs.
  3. 3Troisième partie : équivalence de simplexesInvariance du volume et des points entiers par équivalence, réduction à un cube borné et finitude des classes à nombre de points intérieurs fixé.
  4. 4Quatrième partie (hors épreuve)Démonstration des deux théorèmes admis dans les parties précédentes, notamment par récurrence sur la dimension.

Difficile. Le jury note que les nombreuses définitions nouvelles ont gêné les candidats, que les questions 10b et 10c n'ont quasiment pas été traitées et que la troisième partie a été abordée dans peu de copies ; la moyenne est de 8,31.

L'épreuve en chiffres

Moyenne 8,31 / 20 · écart-type 3,35 · 1 521 copies · où vous situez-vous ?
Afficher ou masquer la section
Moyenne
8,31/ 20
Écart-type
3,35
Copies
1 521
moyenne 8,3105101520
Deux tiers des copies environ (moyenne ± écart-type)

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

Source : rapport du jury. 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
Z traité comme un corps · Inverse et déterminant mal maîtrisés · Définition de GLn(Z) mal lue
Afficher ou masquer la section

Les définitions nouvelles ont demandé un effort d'adaptation, et beaucoup de candidats ont appliqué à des matrices entières des propriétés valables seulement sur un corps. La rédaction est jugée généralement médiocre, en particulier celle des récurrences demandées par l'énoncé. Une erreur d'énoncé à la question 6, repérée par une poignée de candidats seulement, a été notée avec clémence et n'a pas pesé sur l'évaluation.

Les erreurs les plus sanctionnées

  1. 1
    Z traité comme un corps5a

    Des propriétés des matrices réelles ou complexes sont utilisées sans précaution pour des matrices entières ; certains croient que Z^n est un espace vectoriel ou affirment qu'une famille est liée sans préciser le cadre.

  2. 2
    Inverse et déterminant mal maîtrisés1a, 1b

    L'expression de l'inverse à l'aide de la comatrice est souvent ignorée, et le lien entre inverse entier et déterminant égal à ±1 est justifié par un raisonnement vague.

  3. 3
    Définition de GLn(Z) mal lue2a, 2b

    Beaucoup confondent GLn(Z) avec l'intersection de GLn(R) et Mn(Z), oublient une inclusion ou proposent en 2b une preuve qui n'utilise pas l'hypothèse.

  4. 4
    Erreurs de signe et vérifications oubliées4a, 4b

    Le calcul du déterminant par blocs comporte de très nombreuses erreurs de signe, et le caractère entier de la matrice construite n'est souvent pas vérifié.

  5. 5
    Récurrences mal rédigées5d

    L'hérédité est souvent déclarée évidente, et la propriété à démontrer n'est pas énoncée ; le jury valorise pourtant une récurrence proprement écrite.

    « la très mauvaise qualité de la rédaction des démonstrations par récurrence »
  6. 6
    Fermés, compacts et images7a, 7b

    Les propriétés des images directes et réciproques de fermés et de compacts par une application continue sont confondues.

    « l’image d’un fermé par une application continue n’est pas toujours un fermé. »

Ce qui a été bien réussi

  • La question de cours 3 sur les opérations élémentaires a été globalement bien réussie.
  • Les exemples de la question 8a sont en général corrects.
  • Certains candidats ont convenablement réussi les questions 11 et 12, plus accessibles.
  • Les candidats qui ont signalé l'erreur de la question 6 ont été récompensés.

Conseils du jury

  • Signaler sur la copie toute erreur ou ambiguïté repérée dans l'énoncé.
  • Ne pas se limiter aux questions faciles : les questions difficiles ont un coefficient plus élevé.
  • Rédiger les récurrences en entier, en énonçant la propriété et en justifiant l'hérédité.
  • Préciser le cadre (Z, Q, R) dans lequel on parle de liberté ou d'espace vectoriel.
  • Donner une preuve élémentaire et complète à la hauteur de la question posée, même pour un point qui semble évident.

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

ÉCOLE POLYTECHNIQUE - ÉCOLES NORMALES SUPÉRIEURES

COMPOSITION DE MATHÉMATIQUES - A - (XLCR)

(Durée : 4 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Toute affirmation doit être clairement et complètement justifiée.
Soit n ⩾ 1 un entier. On appelle point entier de ℝ^n un point dont toutes les coordonnées sont entières, c'est-à-dire un point de ℤ^n. Si K est une partie de ℝ^n, on note K^∘^∘ son intérieur. On appelle points entiers de K (resp. points entiers intérieurs) les points de K ∩ ℤ^n (resp. les points de ^∘K ∩ ℤ^n ). On note respectivement Card(K ∩ ℤ^n) et Card(K^∘ ∩ ℤ^n), le nombre (éventuellement infini) de points entiers de K et de son intérieur ^∘K.
Soit h_β l'homothétie de rapport β ∈ ℝ (centrée en 0 ), on note βK = h_β(K) l'image de K par h_β. Si τ_x est la translation de vecteur x ∈ ℝ^n, on note K − x = τ_(− x)(K) l'image de K par τ_(− x).
Si M = (m_(ij)) est une matrice de M_n(ℝ), m_(ij) est le coefficient de la i-ème ligne et de la j-ème colonne.
On note ( x_1|⋯|x_n ) la matrice de M_n(ℝ) dont les colonnes sont les vecteurs x_1, …, x_n ∈ ℝ^n. On note I_n la matrice identité de M_n(ℝ) et E_(ij) la matrice de M_n(ℝ) dont tous les coefficients sont nuls sauf celui de la i-ème ligne et j-ème colonne qui vaut 1 .
On note M_n(ℤ) l'ensemble des matrices de M_n(ℝ) dont tous les coefficients sont entiers.
On note ⌊a⌋ la partie entière d'un réel a : c'est le plus grand entier inférieur ou égal à a; et {a} = a − ⌊a⌋ ∈ [0, 1[ la partie fractionnaire de a. On note ⌋a⌊ le plus grand entier strictement inférieur à a.
Pour des entiers a_1, …, a_k non tous nuls, on note pgcd(a_1, …, a_k) le plus grand entier (strictement positif) qui divise tous les a_i.

Première partie

  1. Soit M ∈ M_n(ℝ) une matrice inversible et à coefficients entiers.
1a. Montrer que M^(− 1) est à coefficients rationnels.
1b. Montrer l'équivalence des propositions suivantes:
i) M^(− 1) est à coefficients entiers.
ii) detM vaut 1 ou -1 .
Dans la suite, on note GL_n(ℤ) l'ensemble des matrices carrées de taille n à coefficients entiers et de déterminant ± 1. C'est un sous-groupe de GL_n(ℝ). On remarque que pour i ≠ j et c ∈ ℤ, la matrice I_n + cE_(ij) appartient à GL_n(ℤ).
2. Soit M = (x_1|⋯|x_n) ∈ GL_n(ℝ).
2a. Montrer que M ∈ GL_n(ℤ) si et seulement si M(ℤ^n) = ℤ^n.
2b. Montrer l'équivalence des propositions suivantes:
i) M ∈ GL_n(ℤ).
ii) Les points entiers du parallélépipède P = {∑_(i = 1)^n t_i x_i|∀i ∈ {1, …, n}, t_i ∈ [0, 1]} sont exactement les 2^n points ∑_(i = 1)^n ε_i x_i, où ε_i ∈ {0, 1} pour tout i ∈ {1, …, n}.
3. Pour tout α dans ℝ et pour tous entiers i et j distincts compris entre 1 et n, décrire l'effet sur une matrice carrée M de taille n de la multiplication à gauche par I_n + αE_(ij). Même question pour la multiplication à droite.
4. Soient n ⩾ 2 et a_1, …, a_n des entiers non tous nuls. Le but de cette question est de montrer qu'il existe une matrice de M_n(ℤ) dont la première colonne est ( a_1, …, a_n ) et de déterminant le pgcd(a_1, …, a_n). Pour cela on raisonne par récurrence sur n.
Soit N ∈ M_(n − 1)(ℤ) une matrice dont la première colonne est (a_2, …, a_n). Étant donnés u, v ∈ ℚ, on considère la matrice
M = (a_1, 0, ⋯, 0, u; va_2; N, va_3; ⋮; va_n)
4a. Exprimer detM en fonction dedetN, u et v.
4b. On suppose que les a_2, …, a_n sont non tous nuls et que detN = pgcd(a_2, …, a_n). Montrer que l'on peut choisir u, v de sorte que M réponde à la question.
4c. Conclure la récurrence.
5. Soit M ∈ M_n(ℤ), de déterminant non nul. On souhaite montrer qu'il existe une matrice A dans GL_n(ℤ) telle que MA soit triangulaire supérieure et en notant MA = (c_(ij)), on ait les inégalités 0 < c_(11) et 0 ⩽ c_(ij) < c_(ii) pour tous i, j ∈ {1, …, n} tels que i < j.
5a. On note M = (x_1|⋯|x_n). Soient x_1^′, …, x_n^′ les éléments de ℤ^(n − 1) obtenus en prenant les (n − 1) dernières coordonnées de x_1, …, x_n.
Montrer qu'il existe a_1, …, a_n dans ℚ, non tous nuls, tels que ∑_(i = 1)^n a_i x_i^′ = 0. Montrer que l'on peut choisir les a_i entiers et premiers entre eux dans leur ensemble.
5b. Montrer qu'il existe une matrice A_1 dans GL_n(ℤ) telle que la première colonne de C~ = MA_1 ait tout ses coefficients c~_(i1) nuls sauf le premier c~_(11) que l'on peut prendre strictement positif.
5c. En considérant pour tout j = 2, …, n la division euclidienne c~_(1j) = q_j c~_(11) + r_j, 0 ⩽ r_j < c~_(11), montrer que l'on peut supposer c~_(11) > c~_(1j), quitte à changer A_1.
5d. Conclure par récurrence.
6. Soit M ∈ M_n(ℤ), de déterminant non nul. Montrer qu'il existe une matrice A dans GL_n(ℤ) telle que AM soit triangulaire inférieure et en notant AM = (c_(ij)), on ait l'inégalité 0 ⩽ c_(ij) < c_(jj) pour tous i, j ∈ {1, …, n} tels que j < i.

Deuxième partie

Soient s_0, s_1, …, s_n des points de ℝ^n tels que les vecteurs s_1 − s_0, s_2 − s_0, …, s_n − s_0 soient linéairement indépendants. On appelle simplexe de sommets s_0, s_1, …, s_n l'ensemble :
S, = {∑_(i = 0)^n t_i s_i|∀i = 0, …, n, t_i ⩾ 0, ∑_(i = 0)^n t_i = 1}; = {s_0 + ∑_(i = 1)^n t_i(s_i − s_0)|∀i = 1, …, n, t_i ⩾ 0, ∑_(i = 1)^n t_i ⩽ 1}.
Si de plus les s_i sont tous des points entiers, on dit que S est un simplexe entier.
On définit le volume du simplexe S de sommets s_0, s_1, …, s_n par
Vol(S):=1/(n!)|det(s_1 − s_0, s_2 − s_0, …, s_n − s_0)|
  1. Soit S le simplexe de sommets s_0, s_1, …, s_n.
7a. Montrer S est un compact convexe de ℝ^n.
7b. Montrer que S^∘ = {∑_(i = 0)^n t_i s_i|∀i = 0, …, n, t_i > 0, ∑_(i = 0)^n t_i = 1}.
En déduire que si 0 ∈ S, alors, pour tout λ ∈ [0, 1[, λS ⊂ S.
7c. Pour i = 0, …, n, on note s^_i = (1, s_i) le point de ℝ^(n + 1) dont les coordonnées sont 1 suivi des coordonnées de s_i. Exprimer |det(s^_0, s^_1, …, s^_n)| en fonction de Vol(S). En déduire que le volume d'un simplexe ne dépend pas de l'ordre des sommets.
8. Soit V ⩾ 0 un réel.
8a. Donner un exemple de simplexe entier de ℝ^2, de volume supérieur ou égal à V, et n'ayant aucun point intérieur entier.
8b. Donner un exemple de simplexe entier de ℝ^3, de volume supérieur ou égal à V, et dont les seuls points entiers sont les sommets.
9. Soit K un compact convexe de ℝ^n tel que 0 ∈ K^∘.
9a. Montrer que l'ensemble des λ ⩾ 0 tels que − λK ⊂ K est un intervalle.
On note
a(K) = sup{λ ⩾ 0| − λK ⊂ K}
9b. Montrer que a(K) < ∞ et que a(K) = max{λ ⩾ 0| − λK ⊂ K}.
9c. Montrer que 0 < a(K) ⩽ 1.
En déduire que a(K) = 1 si et seulement si K est symétrique par rapport à 0 .
On admet le résultat suivant que l'on pourra utiliser sans démonstration pour la suite de cette partie.
Théorème 1. Soit S un simplexe de ℝ^n et k un entier. Si Vol(S) ⩾ k, il existe k + 1 points distincts v_0, …, v_k de S tels que v_i − v_j ∈ ℤ^n quels que soient i et j entre 0 et k.
10. Dans toute cette question, S est un simplexe de ℝ^n tel que 0 ∈ S^∘. On veut montrer que
Card(S^∘ ∩ ℤ^n) ⩾ 2⌊Vol(S)((a(S))/(a(S) + 1))^n⌊ + 1
On pose alors a = a(S), et k = ⌊Vol(S)(a/(a + 1))^n|.
10a. Exprimer, pour β ∈ ℝ^∗ et x ∈ ℝ^n, Vol(βS) et Vol(S − x).
Montrer que pour λ ∈ [0, 1[ suffisamment proche de 1, Vol((λa)/(a + 1)S) > k.
10b. Pour λ comme dans la question précédente, soient v_0, …, v_k les k + 1 points distincts dans (λa)/(a + 1)S vérifiant v_i − v_j ∈ ℤ^n pour tout i, j dont l'existence est assurée par le Théorème 1. Montrer que les points v_i − v_j sont dans λS. En déduire que les v_i − v_j sont dans S^∘.
10c. Montrer qu'il existe un indice j ∈ {0, …, k} tels que les (2k + 1) points 0, ± (v_i − v_j), pour i ∈ {0, …, k}∖{j} soient distincts. En déduire l'énoncé de la question 10, puis que
Card(S^∘^∘ ∩ ℤ^n) ⩾ Vol(S)((a(S))/2)^n

Troisième partie

On dit que deux simplexes S et S^′ de ℝ^n sont équivalents s'il existe un ordre d'énumération des sommets s_0, s_1, …, s_n de S, et s_0^′, s_1^′, …, s_n^′ de S^′, et une matrice A de GL_n(ℤ) tels que A(s_i − s_0) = s_i^′ − s_0^′ pour tout i = 1, …, n.
11. Montrer que deux simplexes entiers S et S^′ sont équivalents si et seulement s'il existe une matrice A ∈ GL_n(ℤ) et un vecteur b ∈ ℤ^n tels que S^′ = A(S) − b.
12. Montrer que le volume, le nombre de points entiers et le nombre de points intérieurs entiers sont les mêmes pour deux simplexes entiers équivalents.
13. Montrer qu'un simplexe entier S est équivalent à un simplexe entier contenu dans le cube [0, n!Vol(S)]^n.
On pourra utiliser la question 6 pour une matrice M bien choisie.
On admet le résultat suivant que l'on pourra utiliser sans démonstration.
Théorème 2. Pour tout entier strictement positif k, il existe une constante strictement positive C(n, k) telle que pour tout simplexe entier S de ℝ^n possédant exactement k points intérieurs entiers, Vol(S) ⩽ C(n, k).
14. Déduire du Théorème 2 que pour tout entier strictement positif k, il n'existe à équivalence près qu'un nombre fini de simplexes entiers de ℝ^n ayant exactement k points intérieurs.

Quatrième partie

Le but de cette partie, qui ne faisait pas partie du sujet du concours, est de démontrer les Théorèmes 1 et 2 énoncés et utilisés dans les deuxième et troisième parties.
15. Soit S un simplexe de ℝ^n et k un entier tel que Vol(S) > k.
15a. Montrer qu'il existe x ∈ [0, 1[^n et (k + 1) éléments de ℤ^n u_0, …, u_k tels que x ∈ S − u_i pour i = 0, …, k.
On pourra étudier les ensembles (u + [0, 1[^n) ∩ S quand u décrit ℤ^n; et admettre le faithors programme de CPGE - que le volume d'un simplexe est sa mesure de Lebesgue, qui est sous-additive.
15b. En déduire l'existence des (k + 1) points v_0, …, v_k qui satisfont aux conditions du Théorème 1 .
15c. Montrer le Théorème 1, c'est-à-dire qu'ici, on suppose seulement que Vol(S) ⩾ k.
16. Soient t_1, …, t_n des réels strictement positifs tels que ∑_(i = 1)^n t_i = 1 et soit N ⩾ n un entier. On souhaite montrer qu'il existe des entiers positifs ou nuls p_1, …, p_n et q tels que
i) 1 ⩽ q ⩽ N^(n − 1),
ii) ∑_(i = 1)^n p_i = q,
iii) |qt_1 − p_1| ⩽ n/N,
iv) pour tout i = 2, …, n, |qt_i − p_i| ⩽ 1/N.
16a. En considérant les vecteurs de coordonnées ({kt_2}, …, {kt_n}) ∈ [0, 1[^(n − 1) quand k décrit {0, …, N^(n − 1)}, montrer qu'il existe des entiers p_2, …, p_n, q ⩾ 0 vérifiant les conditions i) et iv).
16b. Conclure.
17. Le but de cette question est de montrer que quels que soient les entiers strictement positifs n et k, il existe une constante α(k, n) ∈ ]0, 1[ telle que, si t_1, …, t_n sont des réels strictement positifs vérifiant 1 > ∑_(i = 1)^n t_i > 1 − α(k, n), alors il existe des entiers positifs ou nuls p_1, …, p_n ⩾ 0 et q tels que
∑_(i = 1)^n p_i = q > 0, et pour tout i = 1, …, n, (kq + 1)t_i > kp_i
On procède par récurrence sur n.
17а. Traiter le cas n = 1 en montrant que la constante α(k, 1) = 1/(k + 1) convient.
On suppose l'énoncé vrai jusqu'au rang n − 1 ⩾ 1. En particulier, α(k, n − 1) > 0 est définie pour tout k ⩾ 1. On pose pour k ⩾ 1
α(k, n) = 1/(4kN^(n − 1)) où N = 1 + max((4k)/(α(k, n − 1)), 2kn(n + 1)).
On se donne t_1 ⩾ t_2 ⩾ ⋯ ⩾ t_n > 0, et on suppose que ∑_(i = 1)^n t_i = 1 − α avec 0 < α < α(k, n).
17b. Si t_n < α(k, n − 1) − α, établir l'énoncé au rang n.
17c. Si t_n ⩾ α(k, n − 1) − α, appliquer le résultat de la question 16 aux (t_i)/(1 − α), i = 1, …, n. Avec ses notations, montrer que
α(k, n) < min(1/(n + 1), 1/2α(k, n − 1)) et 1 − qkα/(1 − α) ⩾ 1/2.
Conclure en distinguant les cas i ⩾ 2 et i = 1.
18. Soit S un simplexe entier de ℝ^n de sommets 0, s_1, …, s_n ayant exactement k points intérieurs entiers et soit x = ∑_(i = 1)^n t_i s_i un point entier intérieur de S.
18a. Montrer que ∑_(i = 1)^n t_i ⩽ 1 − α(k, n). (On pourra raisonner par l'absurde et construire alors k + 1 points entiers distincts intérieurs à S ).
18b. Montrer que (α(k, n))/(1 − α(k, n))x ∈ (S − x).
18c. En déduire que a(S − x) ⩾ (α(k, n))/(1 − α(k, n)).
19. Conclure la preuve du Théorème 2 .

Questions fréquentes

4 questions
Sur quoi porte le sujet X-ENS maths A MP 2016 ?
Afficher ou masquer la section

Sur quoi porte le sujet X-ENS maths A MP 2016 ?

Sur les simplexes entiers : matrices de GLn(Z), volume d'un simplexe, minoration du nombre de points entiers intérieurs et finitude des classes d'équivalence à nombre de points intérieurs fixé.

Quelle est la moyenne de l'épreuve X-ENS maths A MP 2016 ?

Pour les 1521 candidats français de l'École polytechnique, la note moyenne est de 8,31 avec un écart-type de 3,35.

Y a-t-il une erreur dans le sujet X-ENS maths A MP 2016 ?

Oui. À la question 6, le passage à la transposée donne des inégalités dans le sens opposé à celui demandé. Le jury a noté cette question avec clémence et récompensé ceux qui l'ont signalée.

Quelles erreurs le jury a-t-il le plus relevées en X-ENS maths A MP 2016 ?

L'usage de propriétés valables sur un corps pour des matrices entières, la définition de GLn(Z) mal comprise, des erreurs de signe dans les déterminants, des récurrences mal rédigées et des confusions sur les images de fermés et de compacts.

Pas de description pour le moment