WikiPrépaLivrets

Mines Mathématiques 2 MP MPI 2024Sujet, corrigé et rapport du jury

5,0(1 vote)
Faisable en Sup
Logo concours Mines

Explorer les annales

BanqueMinesAnnée2024FilièreMP/MPIMatièreMathématiques
Annales Mines MP/MPI MathématiquesMines MP/MPI 2024MP/MPI MathématiquesMathématiques 2024

Téléchargements

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

Présentation du sujet

Difficile
Phénomènes de seuil dans les graphes aléatoires et matrices d'adjacence
Afficher ou masquer la section

Le sujet porte sur les graphes. Une première partie étudie algébriquement les matrices d'adjacence (similitude, diagonalisabilité, rang, polynôme caractéristique d'une étoile et d'une double étoile). Les deux parties suivantes, indépendantes de la première, définissent des graphes aléatoires et établissent des fonctions de seuil, d'abord pour la présence d'une arête, puis pour la présence d'une copie d'un graphe fixé.

  1. 1Partie I : propriétés algébriques des matrices d'adjacencepremière et deuxième annéeSimilitude des matrices associées à deux indexations, diagonalisabilité, rang, polynôme caractéristique d'une étoile puis d'une double étoile.
  2. 2Partie II : une première fonction de seuilpremière annéeInégalités de Markov et de Bienaymé-Tchebychev, loi binomiale du nombre d'arêtes et fonction de seuil associée.
  3. 3Partie III : fonction de seuil de la copie d'un graphepremière annéeDénombrement des copies d'un graphe fixé, calcul d'espérance et de moment d'ordre 2, puis fonction de seuil pour la propriété « contenir une copie de G0 ».

Difficile. Le jury juge le sujet plutôt difficile, sauf la deuxième partie, en raison du grand nombre de notions et notations introduites et du niveau d'abstraction ; plusieurs questions ne sont réussies que dans quelques pour cent des copies.

L'épreuve en chiffres

Moyenne 11,01 / 20 · écart-type 4,83 · 5 100 présents · où vous situez-vous ?
Afficher ou masquer la section
Moyenne
11,01/ 20
Écart-type
4,83
Présents
5 100
Coefficient
5
Durée
4 h
moyenne 11,0105101520
Deux tiers des copies environ (moyenne ± écart-type)

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

Source : document officiel du concours, épreuve du 14 mai 2024. 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
Notion de matrices semblables mal connue · Théorème spectral cité sans ses hypothèses · Lien entre polynôme caractéristique, trace et rang
Afficher ou masquer la section

Le sujet de quatre heures, long de 8 pages, introduisait beaucoup de définitions et un cadre abstrait d'indexation des sommets qui a perturbé les candidats. Le jury a été tolérant sur les subtilités de la partie I, mais très sévère dans les parties de probabilités, où les réponses non justifiées ou faites au hasard ont été lourdement sanctionnées. La présentation s'est améliorée, mais la rédaction a globalement déçu.

Les erreurs les plus sanctionnées

  1. 1
    Notion de matrices semblables mal connueQ1, Q5

    Des candidats croient semblables deux matrices de même rang, trace ou déterminant, ou confondent similitude et équivalence. Peu expliquent simplement que les deux matrices représentent le même endomorphisme dans deux bases.

  2. 2
    Théorème spectral cité sans ses hypothèsesQ2

    41 % des candidats n'ont pas précisé que le théorème spectral s'applique aux matrices symétriques réelles.

  3. 3
    Lien entre polynôme caractéristique, trace et rangQ6, Q7, Q9

    Beaucoup ne relient pas le coefficient de X^(n-1) à la trace, ou se trompent de signe. Pour obtenir le rang, il fallait mentionner la multiplicité de 0, la diagonalisabilité et le théorème du rang.

  4. 4
    Probabilités non justifiéesQ10, Q13

    Oublier les variables X_{i,j} et leur indépendance divisait les points par deux. Beaucoup confondent produit et somme de probabilités ; seuls 26 % répondent correctement à Q10.

    « toute réponse non justifiée, même juste, a en général obtenu la note 0 »
  5. 5
    Inégalités de cours mal citéesQ11, Q12

    L'inégalité de Markov doit être énoncée avec ses hypothèses et la variable doit être à valeurs dans N. Les renvois vagues au cours ne rapportent rien.

  6. 6
    Passage à la limite dans une inégalitéQ15, Q22

    On ne passe à la limite dans une inégalité qu'après avoir prouvé l'existence des limites. En Q22, E((X)^2) est souvent confondu avec (E(X))^2.

Ce qui a été bien réussi

  • La présentation des copies s'est nettement améliorée par rapport aux années précédentes.
  • Les valeurs propres de l'étoile ont en général été bien calculées par ceux qui avaient le polynôme caractéristique (Q7).
  • Les candidats ayant bien traité Q21 ont en général réussi Q22.
  • Les meilleures copies ont calculé le coefficient a_{n-2} en Q6 par trois méthodes différentes.

Conseils du jury

  • Utiliser un brouillon, une encre foncée, écrire lisiblement et encadrer les résultats : un malus a sanctionné les copies mal présentées.
  • Justifier chaque réponse par une phrase en français et citer précisément les résultats du cours utilisés.
  • Faire un dessin de matrice pour clarifier un raisonnement sur les lignes ou les colonnes.
  • Ne pas redémontrer les formules du programme, comme l'espérance et la variance d'une loi binomiale.
  • Rester honnête : signaler qu'un résultat obtenu est faux plutôt que de forcer la conclusion de l'énoncé.

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 DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARIS, TÉLÉCOM PARIS, MINES PARIS, MINES SAINT-ÉTIENNE, MINES NANCY, IMT ATLANTIQUE, ENSAE PARIS, CHIMIE PARISTECH - PSL.

Concours Mines-Télécom, Concours Centrale-Supélec (Cycle International).

CONCOURS 2024

DEUXIÈME ÉPREUVE DE MATHÉMATIQUES

Durée de l'épreuve : 4 heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.
L'énoncé de cette épreuve comporte 8 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.

Phénomènes de seuil dans les graphes

Dans ce problème, n désigne un entier supérieur à 1 .
On désigne par [ [1, n] ] l'ensemble des entiers compris entre 1 et n.
Le groupe symétrique des permutations de [ [1, n] ] est noté S_n.
L'ensemble des matrices carrées d'ordre n à coefficients réels est noté M_n(R).
Le cardinal d'un ensemble fini E sera noté card(E) ou |E|.
Un graphe G est un couple ( S, A ) où :
  • S désigne un ensemble fini non vide d'éléments appelés sommets du graphe G
  • A désigne un ensemble éventuellement vide d'éléments appelés arêtes du graphe G, une arête étant un ensemble {s, s^′} où s et s^′ sont des sommets distincts de S.
    Un sommet n'appartenant à aucune arête est dit isolé.
    Par convention, le graphe vide est le couple d'ensembles vides ( ∅, ∅ ).
    On peut représenter un graphe non vide dans un plan à l'aide :
  • de disques schématisant les sommets du graphe
  • de segments reliant ces disques pour les arêtes du graphe.
Par exemple, on a représenté sur la Figure 1, le graphe G = (S, A) avec :
S = [ [1, 9] ] et A = {{1, 2}, {1, 5}, {1, 6}, {2, 3}, {2, 9}, {2, 8}}
Figure 1 - un graphe à 9 sommets et 6 arêtes
On remarquera que les arêtes sont constituées de deux sommets distincts, ce qui interdit la présence de «boucles» reliant un sommet à lui-même.
De plus, une même arête ne peut être présente plusieurs fois dans un graphe.
Un type de graphe utilisé dans ce problème est l'étoile.
Une étoile de centre s et à d branches avec d entier naturel non nul, est un graphe ( S, A ) où S = {s, s_1, s_2, …, s_d} est de cardinal d + 1, et A est du type
A = {{s, s_1}, {s, s_2}, …, {s, s_d}}
On a représenté Figure 2 une étoile de centre 4 à 5 branches avec S = {1, 3, 4, 5, 6, 8}.
Figure 2 - une étoile à 5 branches
Soient G = (S, A) et G^′ = (S^′, A^′) deux graphes; on dit que :
  • G^′ est inclus dans G si S^′ ⊂ S et A^′ ⊂ A
  • G^′ est une copie de G s'il existe une bijection σ de S^′ dans S telle que :
∀(s^′, t^′) ∈ S^′ × S^′ {s^′, t^′} ∈ A^′ ⟺ {σ(s^′), σ(t^′)} ∈ A
Par exemple, le graphe de la Figure 1 contient plusieurs copies d'étoiles à une branche (correspondant aux segments), plusieurs copies d'étoiles à deux branches, mais aussi une copie d'une étoile à 3 branches (de centre 1) et une copie d'une étoile à 4 branches (de centre 2).
Dans une première partie, on étudie quelques propriétés algébriques des matrices d'adjacence.
On introduit ensuite la notion de fonction de seuil en probabilité des graphes aléatoires.
Les deux parties qui suivent la première partie sont indépendantes de celle-ci, et sont consacrées à l'étude de deux exemples.

Partie I - Quelques propriétés algébriques des matrices d'adjacence

Soit G = (S, A) un graphe non vide où |S| = n. Indexer arbitrairement les sommets de 1 à n revient à choisir une bijection (appelée aussi indexation) σ entre [ [1, n] ] et S. On pourra alors noter :
S = {σ(1), σ(2), …, σ(n)}
où σ(i) est le sommet d'index i.
Une indexation σ étant choisie, on définit la matrice d'adjacence M_(G, σ) du graphe G associée à σ comme étant la matrice de M_n(R) dont le coefficient situé sur la i^e ligne et la j^e colonne est :
(M_(G, σ))_(i, j) = {1, si {σ(i), σ(j)} ∈ A; 0, sinon
On remarquera d'une part que la matrice M_(G, σ) est toujours symétrique (car pour tous i et j entiers, {i, j} = {j, i}) et d'autre part que les termes de la diagonale sont tous nuls (pas de boucle dans un graphe).
Voici par exemple la matrice d'adjacence M_(G, id) du graphe G représenté sur la Figure 1 :
Soit ρ une permutation du groupe symétrique S_n et M = (m_(i, j))_(1 ≤ i, j ≤ n) une matrice de M_n(R).
1▹ Montrer que les matrices M et (m_(ρ(i), ρ(j)))_(1 ≤ i, j ≤ n) sont semblables.
En déduire que si G = (S, A) est un graphe non vide, et si σ et σ^′ sont deux indexations de S, alors M_(G, σ) et M_(G, σ^′) sont semblables.
2▹ Justifier qu'une matrice d'adjacence d'un graphe non vide est diagonalisable.
3▹ Montrer qu'une matrice d'adjacence d'un graphe non vide n'est jamais de rang 1.
4▹ Montrer qu'une matrice d'adjacence d'un graphe dont les sommets non isolés forment un graphe de type étoile est de rang 2 et représenter un exemple de graphe dont la matrice d'adjacence est de rang 2 et qui n'est pas du type précédent.
Si G = (S, A) est un graphe non vide et si σ et σ^′ sont des indexations de S, comme les matrices M_(G, σ) et M_(G, σ^′) sont semblables, elles ont même polynôme caractéristique (ce que l'on ne demande pas de démontrer).
On notera χ_G ce polynôme caractéristique commun et on dira que χ_G est le polynôme caractéristique du graphe G.
Par convention, le polynôme caractéristique du graphe vide est le polynôme constant égal à 1 .
5▹ Soit G un graphe et G^′ une copie de G. Justifier que χ_G = χ_(G^′).
6▹ Soit G = (S, A) un graphe avec |S| = n ≥ 2. On note χ_G(X) = X^n + ∑_(k = 0)^(n − 1)a_k X^k.
Donner la valeur de a_(n − 1) et exprimer a_(n − 2) à l'aide de |A|.
7▹ En déduire le polynôme caractéristique d'un graphe à n sommets dont les sommets non isolés forment une étoile à d branches avec 1 ≤ d ≤ n − 1.
Déterminer alors les valeurs et vecteurs propres d'une matrice d'adjacence de ce graphe.
Si G = (S, A) est un graphe non vide et si s appartient à S, on définit le graphe G∖s comme étant le graphe dont l'ensemble des sommets est S∖{s} et l'ensemble des arêtes est constitué des arêtes de A qui ne contiennent pas s. Voici par exemple Figure 3 un graphe G et le graphe G∖2 :
Figure 3 - un graphe G, et le graphe G∖2
Soient G_1 = (S_1, A_1) et G_2 = (S_2, A_2) deux graphes non vides tels que S_1 et S_2 soient disjoints, c'est-à-dire tels que S_1 ∩ S_2 = ∅. Soit s_1 ∈ S_1 et soit s_2 ∈ S_2.
On définit le graphe G = (S, A) avec S = S_1 ∪ S_2 et A = A_1 ∪ A_2 ∪ {{s_1, s_2}}.
8▹ Montrer que :
χ_G = χ_(G_1) × χ_(G_2) − χ_(G_1∖s_1) × χ_(G_2∖s_2)
9▹ Déterminer le polynôme caractéristique de la double étoile à d_1 + d_2 + 2 sommets, constituée respectivement de deux étoiles disjointes à d_1 et d_2 branches, à qui l'on a ajouté une arête supplémentaire reliant les deux centres des deux étoiles.
Quel est le rang de la matrice d'adjacence de cette double étoile?
Dans toute la suite de ce problème, on suppose que n est supérieur à 2 et on notera :
− N l'entier (n/2) = (n(n − 1))/2
  • Ω_n l'ensemble des graphes de sommets S = [ [1, n] ]
  • p_n un réel dépendant de n appartenant à l'intervalle ]0, 1[ et q_n = 1 − p_n.
Pour tous i et j appartenant à S = [ [1, n] ] avec i ≠ j, on note X_({i, j}) l'application de Ω_n dans {0, 1} telle que pour tout G ∈ Ω_n avec G = (S, A) :
X_({i, j})(G) = {1, si {i, j} ∈ A; 0, si {i, j} ∉ A
Ainsi, (X_({i, j}) = 1) = {G ∈ Ω_n|X_({i, j})(G) = 1} est l'ensemble des graphes de Ω_n dont {i, j} est une arête. Réciproquement, on remarquera aussi que pour G = (S, A), on peut écrire
{G} = ⋂_({i, j} ∈ A)(X_({i, j}) = 1)⋂_({i, j} ∉ A)(X_({i, j}) = 0).
On admet l'existence d'une probabilité P sur (Ω_n, P(Ω_n)) telle que les applications X_({i, j}) soient des variables aléatoires de Bernoulli de paramètre p_n et indépendantes. On note E_n = (Ω_n, P(Ω_n), P) l'espace probabilisé ainsi construit.
Autrement dit, pour un graphe G donné appartenant à Ω_n, la probabilité qu'une arête {i, j} soit contenue dans G est p_n, et les arêtes apparaissent dans G de façon indépendante.
10▹ Soit G = (S, A) ∈ Ω_n. Déterminer la probabilité P({G}) de l'événement élémentaire {G} en fonction de p_n, q_n, N et a = card(A).
Retrouver alors le fait que P(Ω_n) = 1.
Dans la suite du problème on étudie la notion de fonction de seuil pour une propriété P_n vérifiée sur une partie des graphes de Ω_n.
Une fonction de seuil pour la propriété P_n est une suite (t_k)_(k ≥ 2) de réels strictement positifs tels que :
  • si p_n = o(t_n) alors la limite, lorsque n tend vers + ∞, de la probabilité pour que la propriété P_n soit réalisée vaut 0
  • si t_n = o(p_n) alors la limite, lorsque n tend vers + ∞, de la probabilité pour que la propriété P_n soit réalisée vaut 1 .

Partie II - Une première fonction de seuil

Section A - Deux inégalités

Soit X une variable aléatoire définie sur un espace probabilisé ( Ω, A, P ) à valeurs dans N et admettant une espérance E(X) et une variance V(X).
11▹ Montrer que P(X > 0) ≤ E(X).
12▹ Montrer que si E(X) ≠ 0, alors P(X = 0) ≤ (V(X))/((E(X))^2).
Indication : on remarquera que (X = 0) ⊂ (|X − E(X)| ≥ E(X)).

Section B - Une fonction de seuil

13▹ Quelle est la loi suivie par la variable aléatoire A_n représentant le nombre d'arêtes d'un graphe de Ω_n ?
14▹ Montrer que si p_n = o(1/(n^2)) au voisinage de + ∞, alors lim_(n → + ∞)P(A_n > 0) = 0.
15▹ Montrer que si 1/(n^2) = o(p_n) au voisinage de + ∞, alors lim_(n → + ∞)P(A_n > 0) = 1.
16▹ En déduire une propriété P_n et sa fonction de seuil associée.

Partie III - Fonction de seuil de la copie d'un graphe

Si G = (S, A) est un graphe, on note s_G (resp. a_G ) le cardinal de S (resp. A ).
Soit G_0 = (S_0, A_0) un graphe particulier fixé. Par commodité d'écriture, on note s_0 = s_(G_0) le cardinal de S_0, a_0 = a_(G_0) le cardinal de A_0 et on suppose que s_0 ≥ 2 et que a_0 ≥ 1.
On va étudier la fonction de seuil de la propriété P_n : «contenir une copie de G_0≫.
On note X_n^0 la variable aléatoire réelle discrète définie sur l'espace probabilisé E_n telle que pour G ∈ Ω_n, l'entier X_n^0(G) est égal au nombre de copies de G_0 contenues dans G.
On introduit :
  • l'ensemble C_0 des copies de G_0 dont les sommets sont inclus dans [ [1, n] ] :
C_0 = {H|H est une copie de G_0 et H = (S_H, A_H) avec S_H ⊂ [ [1, n] ]}
  • pour un graphe H = (S_H, A_H) avec S_H ⊂ [ [1, n] ], la variable aléatoire suivant une loi de Bernoulli X_H définie par :
∀G ∈ Ω_n X_H(G) = {1, si H ⊂ G; 0, sinon
  • le réel ω_0 défini par :
ω_0 = min_(H ⊂ G_0; a_H ≥ 1)(s_H)/(a_H)
17▹ Montrer que
E(X_H) = p_n^(a_H).
18▹ Soit S_0^′ un ensemble fixé de cardinal s_0. On note c_0 le nombre des graphes dont l'ensemble des sommets est S_0^′ et qui sont des copies de G_0.
Exprimer le cardinal de C_0 à l'aide de c_0 et en utilisant un majorant simple de c_0, justifier que le cardinal de C_0 est inférieur à n^(s_0).
19▹ Exprimer X_n^0 à l'aide de variables aléatoires du type X_H, et montrer que:
E(X_n^0) = ∑_(H ∈ C_0)P(H ⊂ G) ≤ n^(s_0)p_n^(a_0)
20▹ En déduire que si p_n = o(n^(− ω_0)), alors lim_(n → + ∞)P(X_n^0 > 0) = 0.
Indication : on pourra introduire H_0 ⊂ G_0 réalisant le minimum donnant ω_0.
On suppose dorénavant que lim_(n → + ∞)(n^(ω_0)p_n) = + ∞.
21▹ Montrer que l'espérance E((X_n^0)^2) vérifie :
E((X_n^0)^2) = ∑_((H, H^′) ∈ C_0^2)P(H ∪ H^′ ⊂ G) = ∑_((H, H^′) ∈ C_0^2)p_n^(2a_0 − a_(H ∩ H^′))
Pour k ∈ [ [0, s_0] ], on note :
Σ_k = ∑_((H, H^′) ∈ C_0^2; s_(H ∩ H^′) = k)P(H ∪ H^′ ⊂ G)
22▹ Montrer que Σ_0 ≤ (E(X_n^0))^2.
23▹ Soit k ∈ [ [1, s_0] ]; montrer que:
Σ_k ≤ ∑_(H ∈ C_0)((s_0)/k)((n − s_0)/(s_0 − k))c_0 p_n^(2a_0)p_n^(− k/(ω_0))
24▹ Justifier que pour tous entiers naturels q et r vérifiant 1 ≤ q ≤ r, on a:
(r/q)r^(− q) ≥ 1/(q!)(1 − (q − 1)/q)^q
et en déduire que pour k ∈ [ [1, s_0] ], on a Σ_k = o((E(X_n^0)^2) lorsque n tend vers + ∞.
25▹ Montrer que lim_(n → + ∞)(V(X_n^0))/((E(X_n^0))^2) = 0 où V(X_n^0) désigne la variance de X_n^0.
26▹ Montrer alors que la suite (k^(− ω_0))_(k ≥ 2) est une fonction de seuil pour la propriété P_n.
27▹ Retrouver le résultat de la question 16▹ et déterminer une fonction de seuil pour la propriété «contenir une copie de l'étoile à d branches» avec d entier fixé supérieur à 1 .

Fin du problème

  1. Les sujets sont la propriété du GIP CCMP. Ils sont publiés sous les termes de la licence
    Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de Modification 3.0 France.
    Tout autre usage est soumis à une autorisation préalable du Concours commun Mines Ponts.

Questions fréquentes

4 questions
Sur quels chapitres porte le sujet Mines Maths 2 MP MPI 2024 ?
Afficher ou masquer la section

Sur quels chapitres porte le sujet Mines Maths 2 MP MPI 2024 ?

Sur les matrices d'adjacence de graphes (similitude, théorème spectral, rang, polynôme caractéristique) puis sur le dénombrement et les probabilités sur un univers fini, avec les inégalités de Markov et de Bienaymé-Tchebychev.

Quelles erreurs le jury a-t-il le plus relevées en Mines Maths 2 MP MPI 2024 ?

La confusion entre matrices semblables et équivalentes, l'oubli des hypothèses du théorème spectral, et surtout des réponses de probabilités sans justification, souvent sanctionnées par la note 0.

Le sujet Mines Maths 2 MP MPI 2024 est-il faisable en première année ?

Selon le jury, seule la première partie fait un peu appel au programme de deuxième année. Les deux autres, sur le dénombrement et les probabilités sur un univers fini, relèvent du programme de première année et sont indépendantes de la première.

L'option informatique ou la filière MPI avantageait-elle en Mines Maths 2 2024 ?

Non. Le jury indique que les notions de graphes utilisées étaient élémentaires et qu'aucune différence de notes n'apparaît entre les deux filières sur les questions théoriques de graphes.

Pas de description pour le moment