WikiPrépaLivrets

ENS Informatique Fondamentale (Maths Info) MP 2010Sujet

Pas encore noté
Logo concours ENS

Explorer les annales

BanqueX-ENSAnnée2010FilièreMPMatièreMathématiques-Informatique
Annales X-ENS MP Mathématiques-InformatiqueX-ENS MP 2010MP Mathématiques-InformatiqueMathématiques-Informatique 2010

Téléchargements

Télécharger le sujet (PDF)
Lire en ligneLaTeXWord
  • Corrigé : pas encore disponible
  • Rapport du jury : non disponible

Ces sujets peuvent vous intéresser

Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.

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

Filière MP (groupe I)
Épreuve commune aux ENS de Paris, Lyon et Cachan

MATHÉMATIQUES - INFORMATIQUE

Durée : 4 heures

Les calculatrices ne sont pas autorisées.
Le sujet porte sur la résolution de systèmes d'équations linéaires dans les entiers. La première partie traite de la résolution d'une équation dans ℤ. La seconde partie étudie la résolution d'un système d'équations dans ℕ. La troisième partie porte sur le nombre de Frobenius. La quatrième et dernière partie est consacrée à l'étude d'une borne inférieure sur le nombre de Frobenius. Les quatre parties sont largement indépendantes. En particulier, la deuxième partie est indépendante des autres.
L'usage des calculatrices est interdit.

Préambule

ℤ représente l'ensemble des entiers relatifs, ℕ l'ensemble des entiers positifs, ℕ^∗ l'ensemble des entiers strictement positifs et ℝ l'ensemble des réels. Soient a, b, d des entiers relatifs, d non nul. On dit que d divise a s'il existe k ∈ ℤ tel que a = kd. Le plus grand diviseur commun de a et b, noté pgcd(a, b) est l'entier d ⩾ 1 tel que d divise a et d divise b et tel que pour tout diviseur d^′ de a et b, d^′ divise d. Plus généralement, étant donnés a_1, …, a_n ∈ ℤ, le plus grand diviseur commun des a_i, 1 ⩽ i ⩽ n, noté pgcd(a_1, …, a_n) est l'entier d ⩾ 1 tel que d divise chacun des a_i, 1 ⩽ i ⩽ n, et tel que pour tout diviseur d^′ de chacun des a_i, d^′ divise d.
Si A est une matrice de taille m × k, le coefficient ( i, j ), où i est l'indice de ligne et j l'indice de colonne, 1 ⩽ i ⩽ m, 1 ⩽ j ⩽ k, de la matrice A est noté A_(i, j). Si u est un vecteur de taille k, la i ème coordonnée de u, 1 ⩽ i ⩽ k, est notée u_i. La matrice identité de taille k × k est notée I_k. Une matrice de taille 1 × k pourra être appelée vecteur même si ses coefficients ne sont pas dans un corps.
Si A et B sont deux ensembles, on note A∖B l'ensemble formé de A privé des éléments de B.
Algorithmes : certaines questions demandent de donner un algorithme. Pour ces questions, on ne demande pas de fournir du pseudo-code mais de décrire l'algorithme en français. La question 2.5 illustre une présentation possible.

Partie 1 : Résolution d'une équation linéaire dans ℤ

Étant donnés a, b deux entiers strictement positifs, on appelle reste de la division euclidienne de a par b, noté r(a, b) l'entier r tel que 0 ⩽ r < b et a = kb + r pour un certain entier k ∈ ℕ. On rappelle que l'algorithme d'Euclide, permettant de calculer pgcd(a, b), est défini à l'aide des suites (u_n) et (v_n) de la manière suivante :
− u_0 = a et v_0 = b
  • Si v_n ≠ 0, on définit u_(n + 1) = v_n et v_(n + 1) = r(u_n, v_n)
  • Si v_n = 0, alors l'algorithme s'arrête et renvoie u_n.
Question 1.1. Soit N l'indice tel que v_N = 0.
(a). Montrer que u_N = pgcd(a, b).
(b). Montrer qu'il existe p, q ∈ ℤ tels que u_N = ap + bq.
Soient a_1, …, a_n ∈ ℤ, b ∈ ℤ des entiers relatifs. On dit que l'équation
a_1 x_1 + … + a_n x_n = b
a une solution dans ℤ s'il existe u_1, …, u_n ∈ ℤ tels que a_1 u_1 + … + a_n u_n = b.
Question 1.2. Soient a_1, …, a_n ∈ ℤ, n ⩾ 2 et b ∈ ℤ. Soit a^′ = pgcd(a_1, a_2). Montrer que l'équation a_1 x_1 + a_2 x_2 + … + a_n x_n = b a une solution dans ℤ si et seulement si l'équation a^′ x^′ + a_3 x_3 + … + a_n x_n = b a une solution dans ℤ. En déduire que a_1 x_1 + a_2 x_2 + … + a_n x_n = b a une solution dans ℤ si et seulement si pgcd(a_1, …, a_n) divise b.
En particulier, l'équation a_1 x_1 + a_2 x_2 + … + a_n x_n = pgcd(a_1, …, a_n) a toujours une solution dans ℤ (théorème de Bézout).
Question 1.3. Proposer un algorithme qui prend en entrée une équation a_1 x_1 + a_2 x_2 + … + a_n x_n = b et renvoie :
  • "pas de solution" s'il n'y a pas de solution dans ℤ,
  • donne une solution (dans ℤ ) lorsqu'il en existe une.
On supposera donnée une fonction pgcd_(et) qui prend en entrée deux entiers a, b ∈ ℕ et qui renvoie d, p, q tels que d = pa + qb et d = pgcd(a, b).
Question 1.4. Trouver une solution dans ℤ de l'équation 10x_1 − 15x_2 + 7x_3 = 3.

Partie 2 : Base des solutions dans ℕ d'un système d'équations linéaires

Soit A une matrice de taille m × k à coefficients dans ℤ. L'ensemble des solutions dans ℕ de l'équation AX = 0, noté S(A), est l'ensemble des vecteurs X ∈ ℕ^k tels que AX = 0. Une base de S(A) est un ensemble de vecteurs de ℕ^k tel que tout vecteur de S(A) s'écrive comme une combinaison linéaire à coefficients entiers positifs d'éléments de la base.
Étant donnés deux vecteurs U, V ∈ ℕ^k, on écrit U ⩽ V si et seulement si U_i ⩽ V_i pour tout 1 ⩽ i ⩽ k.
Question 2.1. Montrer que la relation ⩽ est un ordre sur les vecteurs de ℕ^k.
On considère l'ensemble H(A) des solutions non nulles dans ℕ de l'équation AX = 0, minimales pour l'ordre ⩽, c'est-à-dire
H(A) = {X ∈ S(A), X ≠ 0|(Y ∈ S(A) et Y ⩽ X) ⇒ (Y = X ou Y = 0)}.
Question 2.2. Montrer que H(A) est fini.
Question 2.3. Montrer que H(A) est une base de S(A).
Question 2.4. Montrer que toute base de S(A) contient H(A).
On s'intéresse à la détermination de H(A). Une contrainte est un triplet formé d'une matrice M carrée de taille k × k à coefficients dans ℕ, d'une matrice A de taille m × k à coefficients dans ℤ et d'un ensemble I ⊆ {1, …, k}.
La contrainte associée à ( M, A, I ) est notée C(M, A, I). L'ensemble des solutions, noté Sol(C(M, A, I)), d'une contrainte C(M, A, I) est défini par
Sol(C(M, A, I)) = {Mu|Au = 0 et u ∈ ℕ^k et ∀i ∈ I, u_i = 0}.
Ainsi S(A) est l'ensemble des solutions de la contrainte C(ld_k, A, ∅). Par convention, on appellera matrice vide la matrice de taille 0 × k, notée ε. L'ensemble des solutions, noté Sol(C(M, ε, I)), associé à C(M, ε, I) est défini par
Sol(C(M, ε, I)) = {Mu|u ∈ ℕ^k et ∀i ∈ I, u_i = 0}.
On dit qu'une contrainte C(M, A, I) est en forme résolue si A est la matrice vide. Étant donné un ensemble E de contraintes, l'ensemble des solutions de E est Sol(E) = ∪ _(C ∈ E)Sol(C).
On définit L_(i, j) la matrice carrée telle que le coefficient ( p, q ) de L_(i, j) vaut 1 si p = q ou si (p, q) = (i, j) et vaut 0 sinon.
Nous allons étudier un algorithme Transf décrit ci-dessous, qui transforme un ensemble de contraintes en un ensemble de contraintes en forme résolue.
Transf(E) =
E si pour tout C ∈ E, C est en forme résolue.
Sinon, choisir C(M, A, I) ∈ E qui n'est pas en forme résolue. Si les A_(1, i), i ∉ I ne sont pas tous de même signe, choisir i, j ∉ I tels que A_(1, i)A_(1, j) = min_(p, q)A_(1, p)A_(1, q) < 0; calculer Transf ((E∖{C(M, A, I)}) ∪ {C(ML_(i, j), AL_(i, j), I), C(ML_(j, i), AL_(j, i), I)}). Sinon, soit A_(1, ∗) la première ligne de A. On peut écrire A sous la forme A = [A_(1, ∗); A^′]. Soit I^′ = I ∪ {j|A_(1, j) ≠ 0}. Calculer Transf ((E∖{C(M, A, I)}) ∪ {C(M, A^′, I^′)}).
Question 2.5. Soit E un ensemble fini de contraintes. Montrer que Transf (E) renvoie toujours un résultat en un nombre fini d'étapes.
Question 2.6. Montrer que si E est un ensemble de contraintes et Transf(E) = E^′ alors Sol(E) = Sol(E^′).
Question 2.7. En déduire un algorithme pour déterminer H(A).
Question 2.8. Soit A = [0, − 1, 0, 1; 1, 0, 1, − 3]. Déterminer H(A).

Partie 3 : Problème de Frobenius

Dans cette partie, on suppose que a_1, …, a_n ∈ ℕ sont des entiers positifs tels que a_i ⩾ 2, 1 ⩽ i ⩽ n. On dit qu'un entier b est représentable comme une combinaison linéaire positive de a_1, …, a_n s'il existe des entiers x_i ⩾ 0, 1 ⩽ i ⩽ n, tels que a_1 x_1 + a_2 x_2 + … + a_n x_n = b.
Question 3.1. Soit b un entier. Les deux propositions suivantes sont-elles équivalentes? Justifier la réponse.
i) b est représentable comme une combinaison linéaire positive de a_1, …, a_n.
ii) pgcd(a_1, …, a_n) divise b.
Question 3.2. On suppose pgcd(a_1, …, a_n) = 1. Montrer qu'il existe un entier N tel que pour tout entier b ⩾ N, b est représentable comme une combinaison linéaire positive de a_1, …, a_n.
On suppose désormais que pgcd(a_1, …, a_n) = 1. On note g(a_1, …, a_n) le plus grand entier non représentable comme combinaison linéaire positive de a_1, …, a_n. Le nombre g(a_1, …, a_n) est appelé nombre de Frobenius.
Question 3.3. Soient a, b ⩾ 2, pgcd(a, b) = 1. Soit T l'ensemble des entiers représentables comme une combinaison linéaire positive de a et b.
(a). Montrer que ab − a − b ∉ T.
(b). Montrer que pour tout entier k, il existe v_1 ∈ ℤ et v_2 ∈ ℕ tel que v_2 < a et k = v_1 a + v_2 b.
(c). Montrer que pour tout entier i ⩾ 1, ab − a − b + i ∈ T.
(d). En déduire que le nombre de Frobenius associé à a et b est g(a, b) = ab − a − b.
Soient a, b, c ∈ ℤ. On dit que a est congru à b modulo c, noté a ≡ bmodc, s'il existe k ∈ ℤ tel que a = b + ck.
Question 3.4. Soient a_1, …, a_n ∈ ℕ, n ⩾ 2 des entiers positifs. Pour tout ℓ ∈ ℕ, on définit t_ℓ le plus petit entier positif congru à ℓ modulo a_n et représentable comme une combinaison linéaire positive de a_1, …, a_(n − 1). Montrer que
g(a_1, …, a_n) + a_n = max_(ℓ ∈ {0, …, a_n − 1}){t_ℓ}.
Si A et B sont deux parties de ℝ^d, l'ensemble A + B est l'ensemble des u + v avec u ∈ A et v ∈ B. Si t est un réel, tA est l'ensemble des tu, u ∈ A. S'il existe un réel positif t tel que ℝ^d = tA + B, on définit le rayon couvrant de A par rapport à B par
μ(A, B) = inf{t ∈ ℝ^+|ℝ^d = tA + B}.
On considère L = {(x_1, …, x_(n − 1))|x_i ∈ ℤ et ∑_(i = 1)^(n − 1)a_i x_i ≡ 0moda_n} et S = {(x_1, …, x_(n − 1))|x_i ∈ ℝ, x_i ⩾ 0 et ∑_(i = 1)^(n − 1)a_i x_i ⩽ 1}.
Question 3.5. Montrer que ℤ^(n − 1) ⊆ (g(a_1, …, a_n) + a_n)S + L.
Question 3.6. Montrer que μ(S, L) existe et que μ(S, L) ⩽ g(a_1, …, a_n) + a_1 + ⋯ + a_n.
Question 3.7. Montrer que g(a_1, …, a_n) + a_n est le plus petit réel positif t tel que tS + L contienne ℤ^(n − 1).
Question 3.8. Montrer que μ(S, L) = g(a_1, …, a_n) + a_1 + ⋯ + a_n.

Partie 4 : Dénumérants et borne inférieure sur le nombre de Frobenius

On considère a_1, …, a_n ∈ ℕ^∗ et m ∈ ℕ^∗ des entiers strictement positifs. Le dénumérant d(m, a_1, …, a_n) est le nombre de solutions dans ℕ de l'équation ∑_(i = 1)^n a_i x_i = m, c'est-à-dire le cardinal de l'ensemble
{(x_1, …, x_n)|x_i ∈ ℕ et ∑_(i = 1)^n a_i x_i = m}
On considère la fonction f : ] − 1, 1[ → ℝ définie par
f(x) = 1/((1 − x^(a_1))(1 − x^(a_2))⋯(1 − x^(a_n)))
Question 4.1. Montrer que f est développable en série entière et que son développement est f(x) = ∑_(i = 0)^∞d(i, a_1, …, a_n)x^i.
Question 4.2. Donner une formule explicite pour d(m, 1, 2).
On suppose désormais fixés a_1, …, a_n ∈ ℕ^∗ des entiers strictement positifs.
Étant donnés b_1, …, b_n ∈ ℕ, on considère B(b_1, …, b_n) le rectangle n-dimensionnel formé de l'ensemble des points x ∈ ℝ^n tels que b_i a_i ⩽ x_i < (b_i + 1)a_i. Étant donné r ∈ ℝ^+, on considère la pyramide P(r) formée de l'ensemble des vecteurs x ∈ (ℝ^+)^n tels que x_1 + ⋯ + x_n ⩽ r.
Question 4.3. Montrer que P(m) ⊆ ⋃_(b_1 a_1 + ⋯ + b_n a_n ⩽ m)B(b_1, …, b_n).
On définit d^′(m, a_1, …, a_n) = ∑_(i = 0)^m d(i, a_1, …, a_n), le nombre de solutions dans ℕ de l'inégalité ∑_(i = 1)^n a_i x_i ⩽ m.
On pose p_n = ∏_(i = 1)^n a_i et s_n = ∑_(i = 1)^n a_i.
Question 4.4. Montrer que (m^n)/(n!p_n) ⩽ d^′(m, a_1, …, a_n) ⩽ ((m + s_n)^n)/(n!p_n).
On pose g_n = g(a_1, …, a_n).
Question 4.5. On considère la fonction f : ]0, + ∞[ → ]0, + ∞[ définie par f(y) = ((y + g_n + s_n)^n)/y. Montrer que f(y) > n!p_n.
Question 4.6. Montrer que g(a_1, …, a_n) ⩾ (n − 1)/n((n − 1)!∏_(i = 1)^n a_i)^(1/(n − 1)) − ∑_(i = 1)^n a_i.
Fin de l'épreuve.

Pas de description pour le moment