Modèle de concours : CNC 2011 Mathématiques II (TSI) — Concours National Commun

Ce modèle est l'épreuve de Mathématiques II du Concours National Commun (CNC) 2011, filière TSI, concours d'admission aux grandes écoles d'ingénieurs (présidence : INPT). Durée : 4 heures, calculatrice interdite ; l'énoncé fait 4 pages. Deux problèmes : le premier étudie la transformation de Fourier discrète Φ_p et l'algorithme de transformée rapide (FFT) ; le second relie les racines doubles de X³ − 3aX + 2b à la courbe paramétrée (t², t³) (parabole semi-cubique) et à sa courbe orthoptique. Voici une correction proposée.

💡 À retenir : la matrice de Φ_p est la matrice de Vandermonde M = (w^ij) et M⁻¹ = (1/p)·M̄ ; la FFT coûte de l'ordre de p·log₂p opérations contre p² pour Hörner. Pour X³ − 3aX + 2b, le discriminant vaut −108(b² − a³).

Premier problème — Transformation de Fourier discrète

Notation : w = w_p = e^2iπ/p ; ainsi y_k = Σ_j=0^p−1 x_jw^jk.

1^ère partie — Quelques propriétés de Φ_p

1.1.1. Φ_p(x) = 0 ⟺ P_x(w^k) = 0 pour k = 0,…,p−1. Les nombres 1, w, …, w^p−1 sont les p racines p-ièmes de l'unité, deux à deux distinctes. Un polynôme de degré ≤ p − 1 ayant p racines distinctes est nul. Donc Φ_p(x) = 0 ⟺ P_x = 0 (la réciproque est évidente).

1.1.2. Chaque y_k dépend linéairement de x : Φ_p est un endomorphisme de ℂ^p. Par 1.1.1, Ker Φ_p = {x ; P_x = 0} = {0}. Un endomorphisme injectif d'un espace de dimension finie est bijectif : Φ_p est un automorphisme.

1.2.1. Φ_p(e_j) = (w^jk)_{0≤k≤p−1}, donc m_i,j = w^ij.

1.2.2. m_i,j = (wⁱ)^j : M est la matrice de Vandermonde de (1, w, …, w^p−1), de déterminant Π_{0≤i<j≤p−1}(w^j − wⁱ) ≠ 0 car les wⁱ sont distincts. M est inversible, donc Φ_p est un automorphisme.

1.3.1. Posons q = w^i−j.
• Si i = j : q = 1 et la somme vaut p.
• Si i ≠ j : 0 < |i − j| ≤ p − 1, donc q ≠ 1 et q^p = 1 ; somme géométrique : (1 − q^p)/(1 − q) = 0.
Ainsi Σ_k=0^p−1 w^(i−j)k = p·δ_i,j.

1.3.2. |y_k|² = y_kȳ_k = Σ_i,j x_ix̄_jw^(i−j)k (car w̄ = w⁻¹). En sommant sur k et avec 1.3.1 :
Σ_k|y_k|² = Σ_i,j x_ix̄_j·pδ_i,j = p Σ_k|x_k|² (égalité de Parseval).
Si Φ_p(x) = 0, alors Σ|x_k|² = 0, donc x = 0 : Φ_p est injective.

1.4.1. (M̄M)_i,j = Σ_k w^−ikw^kj = Σ_k w^(j−i)k = pδ_i,j (1.3.1). Donc M̄M = pI_p.

1.4.2. M⁻¹ = (1/p)·M̄, de coefficients w^−ij/p. (Formule d'inversion : x_j = (1/p)Σ_k y_kw^−jk.)

2^ème partie — Un peu d'algorithmique

p = 2ⁿ, b = (a₀, a₂, …), c = (a₁, a₃, …). On utilise w_p/2 = w_p² et w_p^p/2 = e^iπ = −1. Dans la boucle, l'indice imprimé « k + p/1 » est une coquille : il faut lire α_k+p/2, comme dans la question 2.1.1.

2.1.1. Au début de l'étape k, E = w_p^k (E part de 1 et est multiplié par w_p à chaque tour). Donc :
F_k = w_p^kγ_k ; α_k = β_k + w_p^kγ_k ; α_k+p/2 = β_k − w_p^kγ_k.

2.1.2. Soit Φ_p(a) = (y₀,…,y_p−1). En séparant indices pairs et impairs, pour tout k :
y_k = Σ_j=0^p/2−1 a_2jw_p^2jk + w_p^k Σ_j=0^p/2−1 a_2j+1w_p^2jk = Σ_j a_2jw_p/2^jk + w_p^kΣ_j a_2j+1w_p/2^jk.
• Pour 0 ≤ k ≤ p/2 − 1 : y_k = β_k + w_p^kγ_k = α_k.
• Pour k + p/2 : w_p/2^j(k+p/2) = w_p/2^jk (car w_p/2^p/2 = 1) et w_p^k+p/2 = −w_p^k, donc y_k+p/2 = β_k − w_p^kγ_k = α_k+p/2.
Donc Φ_p(a) = (α₀, …, α_p−1).

2.2.1. Pour n = 1 : a₀ + a₁ et a₀ − a₁, soit s₁ = 2 additions (une soustraction compte comme une addition) et r₁ = 0 multiplication.
Pour n ≥ 2 : calcul de Φ_2ⁿ⁻¹(b) et Φ_2ⁿ⁻¹(c) (2s_n−1 additions, 2r_n−1 multiplications), puis 2ⁿ⁻¹ tours de boucle comptant chacun 2 additions (α_k, α_k+p/2) et 2 multiplications (F et E) :
s_n = 2s_n−1 + 2ⁿ, r_n = 2r_n−1 + 2ⁿ.
Variante : si l'on considère que les puissances w_p^k sont toutes connues (la mise à jour E := w_p·E n'est alors pas comptée), r_n = 2r_n−1 + 2ⁿ⁻¹.

2.2.2. En divisant par 2ⁿ : s_n/2ⁿ = s_n−1/2ⁿ⁻¹ + 1, suite arithmétique de premier terme s₁/2 = 1, d'où s_n = n·2ⁿ. De même r_n/2ⁿ = r_n−1/2ⁿ⁻¹ + 1 avec r₁ = 0, d'où r_n = (n − 1)·2ⁿ.
Total : s_n + r_n = (2n − 1)2ⁿ, soit avec n = log₂p : p(2 log₂p − 1) opérations.
(Variante : r_n = (n − 1)2ⁿ⁻¹, total (3n − 1)2ⁿ⁻¹ = p(3 log₂p − 1)/2 ; dans les deux cas, de l'ordre de p·log₂p.)

2.3.1. Le schéma de Hörner effectue, pour chacun des p − 1 niveaux de parenthèses, une multiplication par λ et une addition : p − 1 multiplications et p − 1 additions, soit 2(p − 1) opérations.

2.3.2. Il faut évaluer P_a en p points w_p^k : p(p − 1) additions et p(p − 1) multiplications, soit 2p(p − 1) opérations (plus au plus p − 2 multiplications pour former les puissances w_p^k, négligeables).

2.3.3. Hörner : de l'ordre de 2p² opérations ; algorithme récursif (FFT) : de l'ordre de 2p·log₂p. Comme log₂p = o(p), l'algorithme récursif est le plus rapide pour p grand. Exemple p = 1024 (n = 10) : 19·1024 = 19 456 opérations contre 2·1024·1023 = 2 095 104, soit environ 100 fois moins.

Deuxième problème — Racines de X³ − 3aX + 2b et courbe (t², t³)

1^ère partie

1.1. x ↦ P_a,b(x) est continue (polynomiale) sur ℝ, tend vers −∞ en −∞ et vers +∞ en +∞ (terme dominant x³). Il existe donc A < B avec P(A) < 0 < P(B), et le théorème des valeurs intermédiaires donne une racine réelle dans [A, B].

1.2.1. t racine double : P(t) = 0 et P'(t) = 3t² − 3a = 0, d'où a = t². Puis t³ − 3t³ + 2b = 0, d'où b = t³. La somme des trois racines est 0 (coefficient de X² nul), donc la troisième racine est −2t :
P_a,b = (X − t)²(X + 2t) (vérification : (X² − 2tX + t²)(X + 2t) = X³ − 3t²X + 2t³). Comme (a,b) ≠ (0,0), t ≠ 0 et −2t ≠ t : t est exactement double.

1.2.2. Si a³ = b² avec (a,b) ≠ (0,0) : a³ = b² ≥ 0 et a = 0 imposerait b = 0, donc a > 0. Posons t = b/a : t² = b²/a² = a³/a² = a et t³ = t·t² = (b/a)·a = b. Donc P_a,b = (X − t)²(X + 2t) : t = b/a est racine double.

1.3. • Si (a,b) = (0,0) : P = X³, racine triple 0, et (0,0) = (0², 0³).
• Si (a,b) ≠ (0,0) et P a une racine au moins double t : par 1.2.1, (a,b) = (t², t³).
• Réciproquement, si (a,b) = (t², t³), P = (X − t)²(X + 2t) admet t comme racine au moins double.
Donc Γ = {(t², t³) ; t ∈ ℝ} (c'est aussi l'ensemble {a³ = b²}).

1.4.1. Écrivons P = (X − c)(X² + cX + q) = X³ + (q − c²)X − cq. Par identification, q = x₁x₂ = c² − 3a, et x₁ + x₂ = −c. Alors :
• (c − x₁)(c − x₂) = c² − c(x₁ + x₂) + x₁x₂ = 3(c² − a) (c'est P'(c), réel) ;
• (x₁ − x₂)² = (x₁ + x₂)² − 4x₁x₂ = c² − 4(c² − 3a) = −3(c² − 4a).
D'où Δ = −3[(c − x₁)(c − x₂)]²(c² − 4a) = −27(c² − a)²(c² − 4a). Lorsque x₁, x₂ sont complexes conjugués, (c − x₁)(c − x₂) = |c − x₁|² et Δ = −3|c − x₁|⁴(c² − 4a).
En fonction de b² − a³ : de c³ − 3ac + 2b = 0 on tire b = c(3a − c²)/2, donc, avec u = c² :
4(b² − a³) = u(3a − u)² − 4a³ = u³ − 6au² + 9a²u − 4a³ = (u − a)²(u − 4a).
Ainsi (c² − a)²(c² − 4a) = 4(b² − a³) et Δ = −108(b² − a³).
Comparaison : [(c − x₁)(c − x₂)]²(c² − 4a) = 36(b² − a³) : ces deux quantités sont de même signe. De plus (a,b) ∉ Γ, donc c est racine simple, P'(c) = 3(c² − a) ≠ 0 : le facteur carré est strictement positif, et c² − 4a a le signe de b² − a³ (tous deux non nuls).

1.4.2. x₁, x₂ sont les racines de X² + cX + (c² − 3a), de discriminant δ = −3(c² − 4a). Elles sont non réelles ⟺ δ < 0 ⟺ c² − 4a > 0 ⟺ b² > a³ (1.4.1). Donc P n'a qu'une racine réelle (c) si et seulement si b² > a³.
Si b² < a³ : δ > 0, x₁ et x₂ sont réelles et distinctes (et distinctes de c, puisque (a,b) ∉ Γ) : P a trois racines réelles distinctes.

2^ème partie — La courbe γ(t) = (t², t³)

2.1. f et g sont polynomiales, donc γ est de classe C^∞. γ(−t) = (t², −t³) est le symétrique de γ(t) par rapport à l'axe (Ox) : (Ox) est axe de symétrie de Γ ; on étudie la courbe pour t ≥ 0 puis on symétrise.

2.2. γ'(t) = (2t, 3t²), γ''(t) = (2, 6t) ; det(γ'(t), γ''(t)) = 2t·6t − 3t²·2 = 6t² ≠ 0 pour t ≠ 0 : γ(t) est birégulier.
En t = 0 : γ'(0) = (0,0), point stationnaire. γ''(0) = (2,0) et γ'''(0) = (0,6) sont indépendants : p = 2 (pair), q = 3 (impair) : γ(0) = (0,0) est un point de rebroussement de première espèce, de tangente (Ox).

2.3. Pour t₀ ≠ 0, la tangente est dirigée par γ'(t₀) = t₀(2, 3t₀), donc par (2, 3t₀) : 3t₀(x − t₀²) − 2(y − t₀³) = 0, soit
D_γ(t0) : 3t₀x − 2y = t₀³.
En t₀ = 0 la tangente est (Ox), d'équation y = 0, que la même formule donne encore : elle vaut pour tout t₀ ∈ ℝ.

2.4. f(t) = t² : décroissante sur ]−∞,0], croissante sur [0,+∞[, minimum 0 en 0. g(t) = t³ : croissante sur ℝ (g' = 3t² ≥ 0).

Branches infinies : quand t → ±∞, x → +∞ et |y| → +∞, avec y/x = t → ±∞ : branches paraboliques de direction (Oy).

2.5. Tracé (parabole semi-cubique y² = x³, x ≥ 0) :
• γ(0) = (0,0), rebroussement, tangente (Ox) ;
• γ(1) = (1,1), tangente 3x − 2y = 1 (pente 3/2) ;
• γ(−1) = (1,−1), tangente −3x − 2y = −1, soit y = (1 − 3x)/2 (pente −3/2) ;
La courbe part de l'origine tangentiellement à (Ox), en « bec » pointé vers la gauche, avec une branche supérieure (t > 0) et une branche inférieure (t < 0) symétriques, qui s'écartent de plus en plus vite vers le haut et vers le bas (y = ±x^3/2).

3^ème partie

3.1.1. γ(t) ∈ D_γ(t0) ⟺ 3t₀t² − 2t³ = t₀³ ⟺ 2t³ − 3t₀t² + t₀³ = 0. Comme t₀ est racine double (point de tangence), on factorise :
2t³ − 3t₀t² + t₀³ = (t − t₀)²(2t + t₀).
L'autre solution est t₁ = −t₀/2 ≠ t₀ (t₀ ≠ 0) ; t ↦ γ(t) étant injective (t ↦ t³ l'est), γ(t₁) est l'unique autre point d'intersection.

3.1.2. Par 3.1.1, t_n+1 = −t_n/2 (et t_n ≠ 0 pour tout n par récurrence) : suite géométrique de raison −1/2, t_n = (−1/2)ⁿt₀ → 0. Par continuité de γ, γ(t_n) → γ(0) = (0,0), le point de rebroussement ; les points sont alternativement au-dessus et au-dessous de (Ox).

3.2.1. Les tangentes sont dirigées par (2, 3t) et (2, 3t') (y compris pour t = 0, où (2,0) dirige (Ox)). Elles sont perpendiculaires ⟺ 4 + 9tt' = 0 ⟺ tt' = −4/9.

3.2.2. Supposons (x,y) sur D_γ(t) et D_γ(t') avec tt' = −4/9 (donc t ≠ t') :
3tx − 2y = t³ et 3t'x − 2y = t'³. Par différence : 3x(t − t') = t³ − t'³, d'où 3x = t² + tt' + t'².
Puis 2y = 3tx − t³ = t(t² + tt' + t'²) − t³ = tt'(t + t'), d'où y = −(2/9)s avec s = t + t'.
Et t² + t'² = s² − 2tt' = s² + 8/9, donc x = (s² + 8/9 − 4/9)/3 = s²/3 + 4/27.
Avec s = −9y/2 : x − 4/27 = (81y²/4)/3 = 27y²/4, soit y² = (4/27)(x − 4/27), c'est la relation (1).

3.2.3. Soit (x,y) vérifiant (1) ; posons s = −9y/2. Le trinôme T² − sT − 4/9 a pour discriminant s² + 16/9 > 0 : il a deux racines réelles t, t' avec t + t' = s et tt' = −4/9. Les tangentes en γ(t) et γ(t') sont perpendiculaires (3.2.1) donc sécantes, et d'après les calculs de 3.2.2 leur point commun a pour coordonnées y' = −2s/9 = y et x' = s²/3 + 4/27 = 27y²/4 + 4/27 = x (par (1)). Elles passent donc par (x,y).

3.3.1. 𝒫 : y² = (4/27)(x − 4/27). Avec X = x − 4/27, on a y² = 2pX et p = 2/27 : 𝒫 est une parabole (courbe orthoptique de Γ), d'axe (Ox), de sommet S(4/27, 0), de paramètre p = 2/27, de foyer F(5/27, 0) (X = p/2 = 1/27) et de directrice x = 1/9 (X = −p/2), tournée vers les x croissants.

3.3.2. (X − 2)²(X + 4) = (X² − 4X + 4)(X + 4) = X³ − 12X + 16. ✓
γ(t) ∈ 𝒫 ⟺ t⁶ = (4/27)(t² − 4/27) ⟺ 729t⁶ − 108t² + 16 = 0. Avec X = 9t² : X³ − 12X + 16 = 0 ⟺ (X − 2)²(X + 4) = 0. Comme X ≥ 0, X = 2, soit t² = 2/9, t = ±√2/3.
Points d'intersection : (2/9, 2√2/27) et (2/9, −2√2/27). La racine X = 2 étant double, Γ et 𝒫 sont tangentes en ces deux points.

3.3.3. Sur le graphique de Γ, on trace la parabole 𝒫, symétrique par rapport à (Ox), de sommet (4/27 ≈ 0,15 ; 0), ouverte vers la droite. Près de l'axe elle est à droite du rebroussement de Γ ; elle touche Γ en (2/9 ≈ 0,22 ; ±2√2/27 ≈ ±0,10), puis pour x plus grand elle reste entre les deux branches de Γ, qui s'écartent beaucoup plus vite (y ∼ ±x^3/2 contre y ∼ ±0,38√x).