Mines Maths 2 MP 2010

Thème de l'épreuve Dénombrement de certaines matrices binaires
Principaux outils utilisés matrices, dénombrement, intégrales généralisées, séries entières
Mots clefs matrices binaires

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


A 2010 MATH. II MP
ÉCOLE DES PONTS PARISTECH,
SUPAÉRO (ISAE), ENSTA PARISTECH,
TÉLÉCOM PARISTECH, MINES PARISTECH,
MINES DE SAINT-ÉTIENNE, MINES DE NANCY,
TÉLÉCOM BRETAGNE, ENSAE PARISTECH (F ILIÈRE MP),
ÉCOLE POLYTECHNIQUE (F ILIÈRE TSI).
CONCOURS 2010
SECONDE ÉPREUVE DE MATHÉMATIQUES
Filière MP
(Durée de l'épreuve : 4 heures)
L'usage d'ordinateur ou de calculette est interdit.
Sujet mis à la disposition des concours :
C YCLE I NTERNATIONAL, ENSTIM, TELECOM INT, TPE-EIVP.

Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
MATHÉMATIQUES II - MP.
L'énoncé de cette épreuve comporte 4 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.

Dénombrements de certaines matrices binaires
Soit n un entier Ê 2. On note Mn (R ) l'espace vectoriel des matrices réelles
à n lignes et n colonnes. On appelle matrice binaire de taille n une matrice
A  Mn (R ) dont tous les coefficients sont égaux à 0 ou à 1. L'élément d'une 
telle
matrice situé sur la i -ième ligne et la j -ième colonne est dit en position (i 
, j ), où
1 É i É n et 1 É j É n.
On désigne par U n l'ensemble des matrices binaires de taille n comportant
exactement deux 1 dans chaque ligne et exactement deux 1 dans chaque colonne.
L'exemple suivant :

1 0 0 1

0 1 1 0

0 1 0 1
1 0 1 0
est une matrice de U 4 .
On note u n le cardinal de U n , et on pose par convention u 0 = 1 et u 1 = 0.
La partie D est indépendante des parties B et C.

A. Questions préliminaires
1) Exhiber toutes les matrices de U n pour n = 2 et 3, et déterminer les valeurs
correspondantes de u n . (Dans le cas n = 3, on pourra raisonner sur la
position des éléments nuls dans chacune de ces matrices.)
Soit X 0 le vecteur de R n dont tous les coefficients sont égaux à 1 et J la 
matrice
de Mn (R ) dont tous les coefficients sont égaux à 1.
2) Si A  U n , montrer que X 0 est un vecteur propre de A. Quelle est la valeur
propre associée ?
Soit H n l'ensemble des éléments de U n comportant un 1 en position (1,1). On
note h n le cardinal de H n .
3) Calculer la somme de toutes les matrices de U n en fonction de h n et de J .

B. Étude du cardinal de U n
4) Établir la relation u n = n2 h n pour tout n Ê 2. (On pourra s'aider des deux
questions précédentes.)
Soit K n l'ensemble des éléments de H n comportant un 1 en position (1,2) et un
1 en position (2,1). On note k n le cardinal de K n .
2

5) Pour tout n Ê 2, établir une relation donnant h n en fonction de k n et de
(n - 1)2 .

6) En examinant les possibilités pour le coefficient situé en position (2,2),
démontrer la relation k n = u n-2 + h n-1 pour tout n Ê 4.
un
On pose w n =
pour tout n  N .
(n!)2
7) Déduire de ce qui précède une relation de récurrence pour la suite (u n )nN ,
puis pour la suite (w n )nN .
8) Prouver que w n  [0, 1] pour tout n  N , et que la série de terme général
w n diverge. Que
en déduire pour le rayon de convergence de la
X peut-on
n
série entière w n x ?
On pose W (x) =

X

n=0

w n x n pour tout x ] - 1, 1[.

9) Donner une équation différentielle vérifiée par W et en déduire une 
expression de W (x) en fonction de x.

C. Équivalent d'une suite de coefficients d'un développement
en série entière
Cette partie permet d'obtenir un équivalent de u n pour n  +. Soit  un
réel et  un réel > 0. On considère la fonction  définie pour x ] - 1, 1[ par la
formule :
e x
(x) =
·
(1 - x)
R
On note (t ) = 0 x t -1 e -x dx la fonction Gamma définie pour tout réel t > 0 ;
p
on rappelle que ( 21 ) =  et que (t + 1) = t (t ) pour tout t > 0.
X
10) Montrer que (x) est la somme d'une série entière
n x n pour tout
x ] - 1, 1[.
11) Montrer que si x ] - 1, 1[, on peut écrire :
1
(1 - x)

=

X

an x n

n=0

où l'on exprimera les coefficients a n en fonction de n!, () et (n + ).
n
pour tout n  N , où l'on a posé :
12) En déduire que n =
n! ()
Z
n =
u -1 e -u ( + u)n du.
0

3

13) On fixe a  R tel que a > ||. A l'aide des variations de la fonction
u 7 e -u ( + u)n
¯R a
¯
définie pour tout
Ê -, montrer que ¯ 0 u -1 e -u ( + u)n du ¯ est négliR u -1
geable devant a u
e -u ( + u)n du quand n  +.
qu'il existe a > || tel que n soit équivalent à l'intégrale
14) En
R déduire
-u
( + u)n+-1 du quand n  +.
a e
15) En conclure que les suites n et e  (n + ) sont équivalentes.
On revient sur la suite (u n )nN définie au début du problème.
16) Établir un équivalent de n , puis de u n quand n  +. On prendra soin
de simplifier l'équivalent trouvé de u n en utilisant la formule de Stirling.

D. Étude de rang
Dans cette partie, on cherche à déterminer le rang r n du système constitué
des u n matrices de U n , considérées comme des éléments de Mn (R ). On rappelle
que X 0 est le vecteur de R n dont tous les coefficients sont égaux à 1, et que 
J est
la matrice de Mn (R ) dont tous les coefficients sont égaux à 1.
17) Calculer r n pour n = 2 et 3. (Dans le cas n = 3, on pourra considérer les
matrices J - A, où A  U 3 .)
On considère l'espace vectoriel Vn des matrices A  Mn (R ) telles que X 0 soit 
à la
fois un vecteur propre pour A et pour sa transposée tA.
18) Montrer que U n  Vn et comparer les valeurs propres de A et de tA associées 
à X 0 lorsque A  Vn .
19) Déterminer la dimension de Vn . (On pourra considérer une base orthonormée 
de R n dont un des vecteurs est colinéaire à X 0 .) En déduire une
majoration sur r n .
Pour n Ê 3, soit A une matrice de U n comportant des 1 en positions (1, 1) et 
(2, 2)
et des 0 en positions (1, 2) et (2, 1).
20) Montrer qu'il existe une matrice B de U n telle que A - B ne comporte que
des éléments nuls, sauf en positions (i , j ) pour i É 2 et j É 2. En déduire
que si r n désigne le rang du système constitué de toutes les matrices U -V
où U ,V  U n , on a r n Ê (n - 1)2 .
21) Conclure.

F IN DU PROBLÈME
4

Extrait du corrigé obtenu par reconnaissance optique des caractères



Mines Maths 2 MP 2010 -- Corrigé
Ce corrigé est proposé par Sophie Rainero (Professeur en CPGE) ; il a été relu
par Pauline Tan (ENS Cachan) et Benoît Chevalier (ENS Ulm).

Ce problème, mêlant dénombrement, analyse et algèbre, porte sur les matrices
binaires, c'est-à-dire à coefficients dans {0 ; 1}, et plus précisément sur 
l'ensemble
noté Un de celles d'ordre n dont la somme des coefficients de chaque ligne et 
chaque
colonne vaut 2. Il se compose de quatre parties.
· Dans la première, on établit des résultats utiles dans la suite. On détermine
en particulier un vecteur propre commun à toutes les matrices de Un puis
on calcule la somme de tous les éléments de Un .
· La deuxième partie commence par des questions assez fines de dénombrement,
qui aboutissent à une relation de récurrence satisfaite par la suite (un )nN
des
des ensembles Un . On étudie ensuite la somme de la série entière
P cardinaux
un xn /(n!)2 à l'aide d'une équation différentielle.

· La troisième partie a pour finalité d'établir un équivalent du cardinal de Un
quand n tend vers l'infini. On y exprime les coefficients de la série entière
introduite précédemment, à l'aide de la fonction , et on obtient des équivalents
de ces coefficients.

· Dans la quatrième partie, on calcule le rang de la famille Un d'abord pour des
petites valeurs de n puis dans le cas général, en utilisant des raisonnements
d'algèbre linéaire et de dénombrement.
C'est un sujet intéressant, d'autant plus qu'il aborde des domaines variés du
programme de MPSI et MP (allant du dénombrement à la réduction en base 
orthonormée en passant par les séries entières et les intégrales généralisées). 
Les parties de
dénombrement sont amusantes et peuvent sembler plus faciles que celles 
d'analyse.
Néanmoins, il faut se méfier des questions pour lesquelles l'intuition du 
résultat vient
aisément, sans que l'on ait établi une démonstration rigoureuse : seuls les 
candidats ayant défini proprement des bijections pour établir les égalités des 
cardinaux
obtiennent la totalité des points. Dans l'ensemble, les questions d'analyse 
sont classiques, à l'exception peut-être de la question 14 qui nécessite des 
majorations assez
délicates pour démontrer l'équivalence demandée.

Indications
A. Questions préliminaires
3 Étudier les cas n = 2 et n = 3 pour avoir une idée du résultat. Puis, pour 
chaque
couple (i, j)  [[ 1 ; n ]]2 , introduire l'application qui échange les lignes 1 
et i et
les colonnes 1 et j d'une matrice de Un .
B. Étude du cardinal de Un
4 Calculer Sn X0 de deux manières en utilisant les questions 2 et 3.
5 Partitionner l'ensemble Hn en (n - 1)2 sous-ensembles en fonction des 
positions
comportant un 1 sur la première ligne et la première colonne.
6 Suivre l'indication de l'énoncé. Établir une bijection entre Un-2 et 
l'ensemble des
matrices de Kn qui comportent un 1 en position (2, 2) d'une part, entre Kn-1 et
l'ensemble des matrices de Kn qui comportent un 0 en position (2, 2) d'autre 
part.
7 Utiliser les résultats des questions 4, 5 et 6.
8 Procéder par l'absurde pour démontrer que

P
wn diverge.

9 Faire appel à la relation de récurrence trouvée à la question 7.
C. Équivalent d'une suite de coefficients
d'un développement en série entière
11 Utiliser le développement en série entière d'une fonction usuelle et la 
formule
satisfaite par la fonction  rappelée dans l'énoncé.
14 Se servir du résultat de la question 13 et majorer la différence des deux 
intégrales
qui doivent être équivalentes à l'aide d'une intégration par parties.
15 Utiliser le résultat de la question 14 et faire apparaître (n+) par un 
changement
de variable affine.
16 Appliquer ce qui précède avec  = -1/2 et  = 1/2.
D. Étude de rang
17 Suivre l'indication de l'énoncé. Que peut-on dire de la somme des 
coefficients
d'une relation de dépendance linéaire de U3 ?
18 Si  est une valeur propre de A associée au vecteur propre X0 , calculer  t 
X0 X0
de deux façons.
19 En notant P la matrice de passage de la base canonique de Rn à une base 
orthonormée dont le premier vecteur est colinéaire à X0 , vérifier qu'une 
matrice B est
t
dans Vn si et seulement si P B P a une certaine forme.
20 Pour minorer rn , construire une famille libre de (n - 1)2 matrices en 
adaptant
la construction de B avec d'autres lignes et d'autres colonnes.

Les conseils du jury
Commençons par quelques remarques générales sur le sujet issues du rapport
du jury. Dans celui-ci, le rapporteur compare une épreuve de mathématiques
à « une sorte de jeu de piste dans lequel, partant d'une question souvent
simple, l'auteur s'efforce d'orienter le candidat vers la réponse en 
fournissant une série d'indices qui doivent lui permettre de se diriger à 
l'aide de ses
connaissances du cours et de sa perspicacité. » À l'opposé de toute incitation
au « bachotage stérile dont sont accusées régulièrement les classes 
préparatoires », le sujet propose une « continuité dans la réflexion », 
contribuant ainsi
« à la mise en oeuvre [des] connaissances, au développement de l'esprit 
scientifique et à l'initiation à la démarche de recherche. » Dans cet objectif 
figurent
« plusieurs questions ponctuelles » permettant « aux étudiants désorientés de
faire au moins valoir leur connaissance du cours et leur capacité à résoudre
des exercices particuliers » et « de nombreuses questions ouvertes » mobilisant 
les « capacités de réflexion [des candidats] pour faire usage des informations 
[...] fournies par les questions précédentes du problème. » En conclusion,
le rapport explique les qualités attendues chez les étudiants pour réussir cette
épreuve. « Ce problème a donné à de nombreux candidats l'opportunité de
faire montre de la connaissance de leur cours et ils en ont été récompensés.
Mais plus encore l'ont été ceux qui ont su suivre quelques bouts du chemin
qui leur était tracé en faisant le lien entre les différentes questions. »

A. Questions préliminaires
1 Par définition, Un est l'ensemble des matrices réelles à n lignes et n 
colonnes,
à coefficients dans {0 ;1}, comportant exactement deux 1 dans chaque ligne et 
dans
chaque colonne. Notons dès à présent qu'une caractérisation des matrices de Un 
est :
pour toute matrice A  Mn (R), A appartient à Un si, et seulement si, tous ses
coefficients sont dans {0 ;1} et la somme des coefficients de chaque ligne et 
chaque
colonne vaut 2. En particulier, l'ensemble U2 est un singleton car la seule 
matrice
à deux lignes et deux colonnes vérifiant ces conditions est la matrice dont 
tous les
coefficients sont égaux à 1.

1 1
U2 =
1 1
Déterminons maintenant les éléments de U3 . La première ligne d'une matrice
de U3 doit contenir deux 1 et un 0. Précisons d'abord les matrices de U3 dont la
première ligne est (0, 1, 1). La première colonne d'une telle matrice est 
nécessairement
(0, 1, 1). Ainsi, il y a deux possibilités :

0 1 1
0 1 1
1 0 1
1 1 0
et
1 1 0
1 0 1
De même, il y a exactement deux matrices de U3 dont la première ligne est (1, 
0, 1),
puisqu'alors la deuxième colonne ne peut être que (0, 1, 1), ce sont

1 0 1
1 0 1
1 1 0
0 1 1
et
0 1 1
1 1 0

En procédant de la même façon pour les matrices dont la première ligne est (1, 
1, 0),
on conclut que les matrices de U3 sont

0
1
1

1
0
1
En conséquence,

1 1
0 1
1 0

0 1
1 1
1 0

0
1
1

1
1
0

u2 = 1

1 1
1 0
0 1

1 0
0 1
1 1
et

1
1
0

1
0
1

0
1
1
1
1
0

1
0
1

0
1
1

u3 = 6

2 Soit A = (aij )16i,j6n  Un . Notons Y0 = (yi )16i6n = A X0 . Soit i  [[ 1 ; n 
]].
yi =

n
P

j=1

aij × 1 =

n
P

aij

j=1

Comme A est un élément de Un , la somme des coefficients d'une même ligne de A
vaut 2. Par suite, yi = 2 pour tout i  [[ 1 ; n ]]. Ainsi, A X0 = Y0 = 2 X0 . 
Finalement,
X0 étant non nul,
X0 est un vecteur propre de A associé à la valeur propre 2.
Cette question est très classique. Plus généralement, pour tout réel , on
peut démontrer que X0 est un vecteur propre associé à la valeur propre  de
toute matrice dont la somme des coefficients de chaque ligne vaut .
3 Notons Sn la somme de toutes les matrices de Un . Commençons par observer que,
pour n = 2, on trouve

1 1
S2 =
= J = h2 J
1 1
puisque h2 = u2 = 1. Pour n = 3,
S3 = 4 J = h3 J
car h3 = 4 d'après la question 1.
Revenons à présent au cas général. Parmi les un matrices de Un , un nombre hn
d'entre elles comportent un 1 en position (1, 1) et les un -hn autres ont un 0 
dans cette
position. Le coefficient de Sn en position (1, 1) est donc égal à hn . 
Démontrons que les
autres coefficients de Sn ont la même valeur, c'est-à-dire que pour tout couple 
(i, j)
d'entiers compris entre 1 et n, il y a exactement hn matrices de Un qui 
comportent
un 1 en position (i, j). À cette fin, fixons un couple (i, j)  [[ 1 ; n ]]2 et 
introduisons
l'application i,j définie sur Un qui à une matrice A associe la matrice B 
obtenue
à partir de A en échangeant la ligne 1 et la ligne i puis la colonne 1 et la 
colonne j.
Pour tout A  Un , i,j (A) est également dans Un et

i,j i,j (A) = A

On constate ainsi que i,j 2 est égale à l'identité, donc i,j est inversible et 
réalise une
bijection sur l'ensemble fini Un , c'est-à-dire une permutation de Un . Notons 
aussi que