ENS Informatique Fondamentale (Maths Info) MP PC 2005Sujet et corrigé

L'usage de calculatrices électroniques de poche à alimentation autonome, non imprimantes et sans document d'accompagnement, est autorisé. Cependant, une seule calculatrice à la fois est admise sur la table ou le poste de travail, et aucun échange n'est autorisé entre les candidats.

Soit un entier n ≥ 2. On note ( e_1…, e_n ) la base canonique de ℝ^n ( e_i est le vecteur ligne qui a toutes ses coordonnées nulles, sauf la i-ème qui vaut 1 ). On pose aussi e = e_1 + ⋯ + e_n(e = (1, …, 1)).

On considère M_(p, q)(ℝ), l'ensemble des matrices réelles de taille p × q. Une sous-matrice dans M_(a, b)(ℝ), a ≤ p, b ≤ q, est obtenue en choisissant a lignes et b colonnes et tous les coefficients qui sont sur ces lignes et colonnes dans la matrice de départ. Par exemple

Une matrice carrée Q de M_(n, n)(ℝ) est une matrice de permutation s'il existe une permutation σ de {1, …, n} telle que ∀j ∈ {1, …, n}, Q_(σ(j), j) = 1 et Q_(i, j) = 0 si i ≠ σ(j). On notera cette matrice Q(σ) dans la suite. Ainsi, si x = (x_1, …, x_n) ∈ ℝ^n, xQ(σ) = (x_(σ(1)), …, x_(σ(n))). Attention, dans la suite du sujet, on sera souvent amené à faire des produits matriciels de la forme vecteur-ligne × matrice.

On note 𝔻^n = {x ∈ ℝ^n|x_1 ≥ x_2 ≥ ⋯ ≥ x_n}. Si x ∈ ℝ^n, on note x^↓ le vecteur des coordonnées de x triées dans l'ordre décroissant. Plus formellement, x^↓ est le seul vecteur dans 𝔻^n qui est de la forme xQ pour une matrice de permutation Q. Par exemple, dans ℝ^4, si x = (3, − 8, 1, 1), alors x^↓ = (3, 1, 1, − 8).

On définit la relation ≼ de la façon suivante. Soient x, y ∈ ℝ^n, y≼x si

Par exemple, si y = (2, − 2, − 5, 2) et x = (3, − 8, 1, 1), alors y^↓ = (2, 2, − 2, − 5), x^↓ = ( 3, 1, 1, − 8 ), et les sommes partielles vérifient:

ce qui implique y≼x.

Question 1.1. Vérifier que ≼ n'est pas une relation d'ordre sur ℝ^n mais en est une sur 𝔻^n.
Question 1.2. Montrer que y≼x si et seulement si

Question 1.3. Montrer que si x ∈ ℝ^n avec ∑_(i = 1)^n x_i = n, alors e≼x.

Une matrice réelle carrée P = (P_(ij)) ∈ M_(n, n)(ℝ) est une matrice doublement stochastique si toutes ses composantes sont positives et si les sommes sur les lignes et sur les colonnes valent toutes un:

Question 2.1. Soit P une matrice doublement stochastique. Montrer que 1 est valeur propre de P. Soient P_1 et P_2 deux matrices doublement stochastiques, montrer que P_1 P_2 est aussi doublement stochastique.

Question 2.2. Soit P une matrice de M_(n, n)(ℝ). Montrer que si xP≼x pour tout x ∈ ℝ^n, alors P est doublement stochastique (on regardera l'effet de P sur les vecteurs e et e_i ).

Question 2.3. Soit P une matrice doublement stochastique. Soient x, y ∈ ℝ^n tels que y = xP. Montrer qu'il existe une matrice doublement stochastique P^′ telle que y^↓ = x^↓P^′. Montrer que y≼x.

Soit λ ∈ ℝ, 0 ≤ λ ≤ 1, et Q une matrice de permutation. Une ( λ, Q )-transformation est une application linéaire de ℝ^n → ℝ^n de la forme suivante: x → xT, avec T la matrice T = λI + (1 − λ)Q, où I est la matrice identité.

Question 2.4. Soit x ∈ ℝ^n. Exprimer les coordonnées de xT en fonction de celles de x lorsque Q est la matrice d'une transposition (c'est-à-dire une permutation qui échange seulement deux coordonnées).

Question 2.5. Soient x, y ∈ 𝔻^n avec y≼x et x ≠ y. Montrer qu'il existe une ( λ, Q )transformation T_1 de la forme décrite en 2.4 telle que le vecteur x^′ = xT_1 vérifie y≼x^′ et le cardinal de l'ensemble {i|x_i^′ = y_i} est strictement plus grand que le cardinal de {i|x_i = y_i}.

Question 2.6. Soient x, y ∈ ℝ^n. Déduire des questions précédentes que y≼x si et seulement si, il existe P, matrice doublement stochastique, telle que y = xP.

Question 2.7. Écrire un programme Transf (x, y) (dans un langage de haut niveau, comme par exemple celui employé à la question 3.6 ) qui construit une matrice T_1 répondant à la question 2.5.

Remarque: le programme Transf (x, y) est la brique de base d'un programme qui construirait, pour tout couple y≼x, une matrice P telle que y = xP. La construction d'un tel programme n'est pas demandée.

Question 2.8. Soit M une matrice dans M_(n, n)(ℝ). Montrer que:

M contient une sous-matrice nulle de taille s × t avec s + t = n + 1.
(On pourra faire une récurrence sur n pour le sens ⇒.)
Question 2.9. Montrer que si P est une matrice doublement stochastique, alors il existe une permutation σ de {1, …, n} telle que P_(σ(1), 1)P_(σ(2), 2)⋯P_(σ(n), n) > 0.

Soit c = min(P_(σ(1), 1), P_(σ(2), 2), …, P_(σ(n), n)). Montrer que si c ≠ 1 alors P − cQ(σ) est de la forme μR, avec μ ∈ ℝ et R doublement stochastique.

Question 2.10. (Théorème de Birkhoff) Soit P une matrice doublement stochastique. Déduire des questions précédentes qu'il existe un nombre fini k de matrices de permutations, Q_1, …, Q_k et des réels positifs α_1, …, α_k avec α_1 + ⋯ + α_k = 1 tels que P = α_1 Q_1 + ⋯ + α_k Q_k. De plus, montrer que l'on peut choisir k ≤ n^2 − n + 1.

Question 2.11. En déduire la construction de l'ensemble des vecteurs y tels que y≼x pour compléter la figure 1 (dans ℝ^3, en projection orthogonale à ( 1, 1, 1 )) avec x = (1, 0, 3).

Un graphe fini G = (X, E) est formé d'un ensemble fini X de sommets et d'un ensemble E de paires (ensembles à deux éléments) {x, y} avec x, y ∈ X, appelées arêtes. Un graphe est souvent représenté par des points du plan pour les sommets et des liens entre sommets pour les arêtes. Une coloration des arêtes de G avec n couleurs est une application c : E → {1, …, n} telle que les couleurs de deux arêtes e_1 et e_2 ayant un sommet en commun sont différentes:
e_1 ∩ e_2 ≠ ∅ ⇒ c(e_1) ≠ c(e_2). Un graphe est dit (p_1, …, p_n)-coloriable si on peut colorier ses arêtes avec n couleurs, en utilisant p_i fois la couleur i, pour i = 1, …, n. La figure 2 donne un exemple de coloration des arêtes d'un graphe avec 3 couleurs. Ce graphe est (3, 3, 2)-coloriable (la couleur 1 est utilisée 3 fois, la couleur 2,3 fois et la couleur 3,2 fois).

Question 3.1. Soit G un graphe (p_1, p_2)-coloriable avec p_1 > p_2. Montrer que G est aussi ( p_1 − 1, p_2 + 1 )-coloriable.

Question 3.2. Soit (q_1, …, q_n) ∈ ℤ^n ∩ 𝔻^n. Montrer que si q_j > q_i avec 1 ≤ j < i ≤ n, alors (q_1, …, q_j − 1, …, q_i + 1, …, q_n)≼(q_1, …, q_n).

Question 3.3. En déduire que si G est ( p_1, …, p_n )-coloriable, alors G est ( q_1, …, q_n )coloriable dès que (q_1, …, q_n) ∈ ℕ^n et (q_1, …, q_n)≼(p_1, …, p_n). On pourra s'inspirer de la méthode utilisée pour la question 2.5.

Un tournoi T = (X, U) est formé d'un ensemble fini X de n sommets et d'un ensemble U de couples ( x, y ). Pour deux sommets quelconques x et y avec x ≠ y, il y a toujours soit (x, y) ∈ U soit, (y, x) ∈ U, et pas les deux. De plus (x, x) ∉ U. Après numérotation des sommets du tournoi, X = {x_1, …, x_n}, sa matrice d'incidence est une matrice M de M_(n, n)(ℝ), avec

Figure 3: Tournoi à 4 sommets. Les couples (x, y) ∈ U sont représentés par les arcs x → y.

Un tournoi peut représenter une compétition sportive dans laquelle n équipes jouent toutes une fois les unes contre les autres. La présence du couple ( x, y ) dans U signifie que x a gagné contre y. Le score s_i du sommet x_i est le nombre de couples de la forme ( x_i, ⋅ ). Avec
l'interprétation donnée précédemment, c'est le nombre de victoires de l'équipe x_i. Le score s du tournoi T est le vecteur des scores de ses sommets: s = (s_1, …, s_n). La figure 3 montre un tournoi avec un score (3, 1, 1, 1).

Question 3.4. Montrer qu'il existe un tournoi dont le score est ( n − 1, n − 2, …, 1, 0 ).
Question 3.5. Montrer que si (s_1, …, s_n) ∈ ℕ^n est le score d'un tournoi, alors (s_1, …, s_n)≼(n − 1, n − 2, …, 1, 0).

Pour la question qui suit, on considère un vecteur s = (s_1, …, s_n) d'entiers positifs, tels que (s_1, …, s_n)≼(n − 1, n − 2, …, 1, 0) et aussi s_1 ≤ ⋯ ≤ s_n (triés dans l'ordre croissant). L'objet de la question est de proposer un algorithme qui construit un tournoi de score s.
M ∈ M_(n, n)(ℝ) est une matrice initialisée à zéro: M_(i, j) = 0, ∀i, j ∈ {1, …, n}. La procédure Tri (x, i) construit une matrice de permutation Q ∈ M_(n, n)(ℝ) qui trie les i − 1 premières coordonnées de x dans l'ordre croissant et laisse les coordonnées i, i + 1, …, n inchangées. Par exemple, si x = (7, 4, 8, 1, 6, 3) et Q ← Tri(x, 5) alors xQ = (1, 4, 7, 8, 6, 3) (les 4 premières coordonnées sont triées et le reste est inchangé). On considère l'algorithme suivant:
Tournoi ( s )

Pour $i$ décroissant de $n$ à 1 faire \{
    Pour $j$ croissant de 1 à $s_{i}$ faire $\left\{M_{i j} \leftarrow 1 ;\right\}$
    Pour $j$ croissant de $s_{i}+1$ à $i-1$ faire $\left\{M_{j i} \leftarrow 1 ; s_{j} \leftarrow s_{j}-1 ;\right\}$
    $Q \leftarrow$ Tri $(s, i)$;
    $\left.s \leftarrow s Q ; M \leftarrow Q^{-1} M Q ;\right\}$

(une boucle croissante de a à b avec a > b n'est pas exécutée)
Question 3.6. Soit s^′ le vecteur s modifié par le premier passage dans la boucle sur i. Montrer que (s_(n − 1)^′, …, s_1^′)≼(n − 2, n − 3, …, 1, 0). En déduire que l'algorithme Tournoi ( s ) construit la matrice d'incidence M d'un tournoi de score ( s_1, …, s_n ), à une permutation près des indices.

Une fonction réelle f : ℝ^n → ℝ est symétrique si pour toute matrice de permutation Q et tout x ∈ ℝ^n, f(x) = f(xQ).
Une fonction réelle f : ℝ^n → ℝ est croissante (au sens usuel) si ( x_1 ≤ y_1, …, x_n ≤ y_n ) ⇒ f(x_1, …, x_n) ≤ f(y_1…, y_n).
Une fonction réelle f : ℝ^n → ℝ est Schur-croissante si x≼y ⇒ f(x) ≤ f(y). Elle est Schur-décroissante si - f est Schur-croissante.
Soit une fonction réelle f : ℝ^n → ℝ, n > 2 et x ∈ ℝ^(n − 2). On définit f_x : ℝ^2 → ℝ, par f_x(x_1, x_2) = f(x_1, x_2, x).

Question 4.1. Montrer que si f est Schur-croissante, alors f est symétrique. Montrer que f est Schur-croissante si et seulement si elle est symétrique et Schur-croissante en ses deux premiers arguments (autrement dit, f_x est Schur-croissante pour tout x ∈ ℝ^(n − 2), si n > 2 ) (S'inspirer de la méthode utilisée à la question 2.6).

Question 4.2. Soit φ : ℝ^n → ℝ et g : ℝ → ℝ. On définit ψ : ℝ^n → ℝ par ψ(x_1, …, x_n) = φ(g(x_1), …, g(x_n)). Montrer que si φ est croissante au sens usuel et Schur-croissante et si g est convexe, alors ψ est Schur-croissante.

On considère un polygone à n côtés ( n ≥ 3 ) inscrit dans un cercle de rayon 1 centré en O (voir la figure 4 pour le cas n = 6 ). On appelle A_1, …, A_n les n points de contact successifs du polygone avec le cercle (en choisissant le premier point arbitrairement, et en tournant dans le sens trigonométrique). On note θ_i l'angle (en radian) formé par les points A_i, O, A_(i + 1) si 1 ≤ i < n et par les points A_n, O, A_1 pour θ_n.
Question 4.3. Montrer que si le centre du cercle est à l'intérieur du polygone alors l'aire du polygone est une fonction Schur-décroissante des angles θ_1, …, θ_n.
Question 4.4. Montrer que le polygone régulier a la plus grande aire parmi les polygones à n côtés inscrits dans le cercle.

On considère maintenant les polygones à n côtés ( n ≥ 3 ) circonscrits au cercle unité de centre O (voir la figure 5 ). On appelle A_1, …A_n les n points de contacts successifs, dans l'ordre trigonométrique, du polygone avec le cercle (qui sont maintenant les points de tangence au cercle), et θ_i l'angle formé par les points A_i, O, A_(i + 1) si 1 ≤ i < n et par les points A_n, O, A_1 pour θ_n. On note P(θ_1…, θ_n) le polygone ainsi formé.

On note h_r(θ_1, …, θ_n) la longueur de la partie du cercle C(r) (centré en O et de rayon r ) qui reste dans le polygone P(θ_1…, θ_n) (voir la figure 5). En particulier, h_r(θ_1, …, θ_n) = 2πr, si r ≤ 1.

Question 4.5. Montrer que, pour tout r ≥ 0, h_r est une fonction Schur-croissante de ℝ^n dans ℝ.

Question 4.6. En déduire la forme d'un polygone P, circonscrit au cercle unité, dont l'intérieur P^∘ a le plus petit moment de rotation, défini par:

Qu'en est-il pour l'aire?