X/ENS Maths PC 2018

ÉCOLE POLYTECHNIQUE ­ ÉCOLES NORMALES SUPÉRIEURES
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

FILIÈRE

CONCOURS D'ADMISSION 2018

PC

COMPOSITION DE MATHÉMATIQUES ­ (XEULC)
(Durée : 4 heures)

L'utilisation de calculatrices n'est pas autorisée pour cette épreuve.
Toute affirmation doit être clairement et complètement justifiée.

Ce sujet s'intéresse aux matrices carrées de taille n dont tous les 
coefficients sont égaux à 1
ou à -1, et en particulier à la différence maximale entre le nombre de 1 et le 
nombre de -1 que
l'on peut obtenir, si l'on s'autorise à multiplier certaines lignes et colonnes 
d'une telle matrice
par -1.
La partie I s'intéresse à quelques cas particuliers. La partie II montre que 
pour certaines
matrices, cette différence maximale est beaucoup plus petite que n2 . La partie 
III propose au
contraire un minorant à cette différence maximale. La partie IV propose une 
démonstration de la
formule de Stirling utilisée dans la partie III, et rappelée ci-dessous. Enfin, 
la partie V s'intéresse
à la différence minimale entre le nombre de 1 et le nombre de -1.
Les quatre premières parties sont largement indépendantes.

Rappels
La formule de Stirling énonce un équivalent à n!, à savoir
 n n

.
2n
n! 
n
e
On admet par ailleurs la valeur de l'intégrale de Gauss
Z +

x2
e- 2 dx = 2 .
-

Notations
Pour n et k entiers strictement positifs, on notera Mn,k (R) l'espace vectoriel 
des matrices
réelles à n lignes et k colonnes. On notera également Mn (R) = Mn,n (R) 
l'espace vectoriel des
1

matrices carrées de taille n. On notera tM la transposée d'une matrice M  Mn,k 
(R). On identifiera l'espace vectoriel Rn à l'espace vectoriel Mn,1 (R) des 
matrices colonnes à n coordonnées.
En particulier, l'espace vectoriel des nombres réels est identifié à M1 (R).
On étend les notations précédentes aux parties de R : si K est une partie de R, 
on notera par
exemple Mn,k (K) le sous-ensemble de Mn,k (R) constituée des matrices dont tous 
les coefficients
sont à valeurs dans K. Le sujet s'intéressera tout particulièrement à Mn ({-1, 
1}), l'ensemble des
matrices carrées de taille n dont tous les coefficients sont égaux à 1 ou à -1. 
Si A  Mn ({-1, 1}),
on notera
t
XAY | (X, Y )  ({-1, 1}n )2 ,

S(A) :=

M (A) := max S(A).
Pour n > 1, on notera également

M (n) := min {M (A), A  Mn ({-1, 1})} .
Dans tout le sujet, (, A, P) désigne un espace probabilisé sur lequel seront 
définies les différentes variables aléatoires intervenant dans les parties II 
et III. On admettra que toutes les
variables aléatoires introduites peuvent bien être construites sur cet espace. 
On notera P(E) la
probabilité d'un événement E  , et E[X] l'espérance d'une variable aléatoire X 
sur (, A, P)
à valeurs réelles.

Partie I
1. Quel est le cardinal de Mn ({-1, 1}) ? Cet ensemble est-il un sous espace 
vectoriel de
Mn (R) ?
2. Montrer que pour toute matrice A dans Mn ({-1, 1}), l'ensemble S(A) est 
inclus dans
{-n2 , . . . , n2 }. Montrer que l'inclusion est stricte (on pourra penser à un 
argument de
parité), et montrer que S(A) est un ensemble symétrique, au sens où un entier k 
est dans
S(A) si et seulement si -k est dans S(A).
3. Soit A et B dans Mn ({-1, 1}). On suppose qu'il existe des matrices 
diagonales C et D
ne contenant que des 1 et des -1 sur la diagonale, telles que B = CAD. Montrer 
que
S(A) = S(B).
4. Dans cette question seulement, on suppose n = 2, et on note
I=

1 1
1 1

et

J=

1 1
.
1 -1

Calculer S(I) et S(J), et en déduire S(A) pour tout A  M2 ({-1, 1}).
5. Soit A  Mn ({-1, 1}). Montrer que les affirmations suivantes sont 
équivalentes :
(a) n2  S(A).
(b) Il existe X et Y dans {-1, 1}n tels que A = X t Y .
(c) A est une matrice de rang 1.
6. En déduire la proportion, parmi les matrices de Mn ({-1, 1}), des matrices A 
qui vérifient
n2  S(A).
2

Partie II
Soit k un entier strictement positif et U1 , . . . , Uk une suite de k 
variables aléatoires à valeurs
dans {-1, 1}, indépendantes et de loi uniforme. On note également
Sk =

k
X

Ui .

i=1

!

1. Soit  : R  R la fonction définie par () = ln E[eU1 ] . Établir que
  R,

() 6

2
.
2

2. Soit t  R. Montrer que pour tout  > 0, on a l'inégalité
P(Sk > t) 6 exp(k() - t).
3. En déduire l'inégalité de Hoeffding pour Sk : pour tout t > 0, on a
 2
t
.
P(Sk > t) 6 exp -
2k
On introduit maintenant une variable aléatoire uniforme C :   Mn ({-1, 1}). 
Pour   , on
note Ci,j () les coefficients de la matrice C().
4. Soient X = (x1 , . . . , xn ) et Y = (y1 , . . . , yn ) deux vecteurs 
quelconques dans {-1, 1}n .
Montrer que (xi yj Ci,j )16i,j6n est une famille de n2 variables aléatoires à 
valeurs dans
{-1, 1}, indépendantes et de loi uniforme.
5. Montrer que pour tout t > 0, on a

P(M (C) > tn

3/2

  2
t
- 2 ln 2 n .
) 6 exp -
2

6. On rappelle la notation M (n) = min {M (A) | A  Mn ({-1, 1})} . Montrer que 
pour tout
n > 1, on a

M (n) 6 2 ln 2 n3/2 .
Indication : on pourra commencer par montrer que pour tout  > 0, il existe une 
matrice
A dans Mn ({-1, 1}) telle que
! 

M (A) 6 2 ln 2 +  n3/2 .

Partie III
Dans cette partie, on établit un minorant non trivial pour M (n).
1. Pour A = (ai,j )16i,j6n  Mn ({-1, 1}) et Y = (yi )16i6n  {-1, 1}n , on note

gA (Y ) = max tXAY | X  {-1, 1}n .
Montrer que la fonction gA peut se réécrire
gA (Y ) =

n X
n
X
i=1 j=1

3

ai,j yj .

2. On introduit maintenant une variable aléatoire uniforme Z :   {-1, 1}n . 
Pour  
, on note Zi () les coordonnées de Z(). Montrer que pour tout A = (ai,j 
)16i,j6n 
Mn ({-1, 1}), on a

n  
n
X
1 X n

|n - 2k|,
i  {1, . . . , n},
E
ai,j Zj = n
2
k
j=1

où

!n 
k

k=0

désigne le coefficient binomial. En déduire
n  
n X n
E [gA (Z)] = n
|n - 2k|.
2
k
k=0

3. (a) Montrer que pour m  {0, . . . , n - 1}, on a
m
X
k=0

n-1
n
.
=n
(n - 2k)
m
k

(b) En déduire que pour toute A  Mn ({-1, 1}),
E [gA (Z)] =
où  n2  désigne la partie entière de

n2 n - 1
,
2n-1  n2 

n
2.

4. (a) Montrer que

M (n) >

n2 n - 1
.
2n-1  n2 

(b) Montrer ensuite, à l'aide de la formule de Stirling rappelée en préambule, 
que ce
minorant est équivalent à Cn quand n tend vers l'infini, pour des constantes C 
et
 > 0 que l'on explicitera. Comparer au majorant de M (n) obtenu à la question 6 
de
la partie II.

Partie IV
Dans cette partie, on établit la formule de Stirling à l'aide d'une étude 
d'intégrales.
1. Pour n  N, on pose
In =

Z

+

xn e-x dx.
0

Déterminer par récurrence In pour tout n  N.

2. Montrer que pour n > 1, on a

 n n  Z + 
x n -xn
dx.
In =
n 
1+ 
e
e
n
- n
3. Soit U l'ouvert de R2 défini par
U := {(t, x)  R2 | t > 0 et x > -t},
et soit f la fonction définie sur U par
f (t, x) = t2 ln(1 +
4

x
) - tx.
t

(a) Montrer que pour (t, x)  U , on a
x60

f (t, x) 6 -

x2
.
2

(b) Pour x > 0, montrer que l'on a
t > 1,

f (t, x) 6 f (1, x).

Pour cela, on pourra commencer par écrire
certaine fonction F que l'on étudiera.

f
t (t, x)

sous la forme tF (x/t) pour une

4. Déduire des questions précédentes la formule de Stirling.

Partie V
Dans cette dernière partie, on fixe A  Mn ({-1, 1}) et on note
m(A) := min(S(A)  N).
1. Pour Y  {-1, 1}n , montrer que l'on a

min tXAY

| X  {-1, 1}n 6 n

et en déduire m(A) 6 n.
2. En s'inspirant de la question précédente et des méthodes développées dans 
les parties II et
III, montrer que l'on a également
p
m(A) 6 2n ln(2n).

5