CONCOURS COMMUN MINES PONTS MPSI-2018

MATHÉMATIQUES 1
Corrigé par Taoufiki said

A. Préliminaires
1. Soient X une variable aléatoire à valeurs dans {1, ..., n} et m ∈ {1, ..., n}.

m−1
X n
X
E(X) = kP (X = k) + kP (X = k)
k=1 k=m
m−1
X n
X
≤ (m − 1)P (X = k) + nP (X = k)
k=1 k=m
m−1
X Xn
= (m − 1) P (X = k) +n P (X = k)
k=1 k=m
| {z } | {z }
≤1 =P (X≥m)

≤ m − 1 + nP (X ≥ m)

2. Soit n ∈ N∗ . On a :
Z n n Z
X k
n ln n − n + 1 = [t ln t − t]n1 = ln tdt = ln tdt
1 k=2 k−1
n Z
X k n
X n
X
≤ ln kdt = ln k = ln k
k=2 k−1 k=2 k=1

Par suite :
 n n  n 
= exp n ln( ) = exp (n ln(n) − n)
e e
≤ exp (n ln(n) − n + 1)
n
!
X
≤ exp ln k
k=1
= exp(ln(n!)) = n!

1
 B. Le lemme de sous-additivité de Fekete
3. Pour tout n ∈ N∗ , l’ensemble Un est borné est non vide, donc il admet une
borne supérieure et une borne inférieure.
On a : Un+1 ⊆ Un , donc

un+1 = sup Un+1 ≤ sup Un = un
un+1 = inf Un+1 ≥ inf Un = un
d’où u est % et u est &. Elles sont respctivement majorée et minorée car
pour tout n ∈ N∗ , on a
u1 ≤ un ≤ un ≤ u1
D’où la convergence de u et u.
4. • Pour tout n ∈ N∗ , un ≤ sup Un = un et u est & , donc u est une suite
décroissante plus grande que u.

• Soit v une suite décroissante plus grande que u. Pour n ∈ N∗ , on a

∀k ≥ n , uk ≤ vk ≤ vn ( car v &)
donc un = sup Un ≤ vn , ceci pour tout n ∈ N∗ , d’où u est la plus petite
suite qui est décroissante et plus grande que u.
De même façon, on montre que u est la plus grande suite qui est croissante
et plus petite que u ( ou bien en utilisant le fait que u = −(−u) ).
5. Soit n ∈ N∗ . On a :
∀k ≥ n , uk ≤ vk ≤ v k ≤ v n
donc un = sup{uk , k ≥ n} ≤ v n , ceci pour tout n ∈ N∗ , d’où
lim un = lim un ≤ lim v n = lim vn
n→+∞ n→+∞ n→+∞ n→+∞

par passage à la limite.

6. Comme u est & et u est % donc u et u sont adjacentes si et seulement si
lim(u − u) = 0.
Supposons que lim(u − u) = 0 et montrons que u est convergente :
Soit ε > 0. Par définition de la limite, il existe N ∈ N∗ tel que
∀n > N , 0 ≤ un − un = |un − un | < ε
Soit (k, k 0 ) ∈ N∗2 tel que k, k 0 > N . Posons n = min(k, k 0 ) > N et supposons
que uk ≥ uk0 ( k et k 0 jouent un rôle symétrique ). On a :
|uk − uk0 | = uk − uk0 ≤ un − un < ε

2
 La suite u est donc de Cauchy, donc elle est convergente.
Supposons la convergence de u vers un réel l et montrons que
lim(u − u) = 0 :
Soit ε > 0. Par définition de la limite, il existe N ∈ N∗ tel que

∀n > N , l − ε < un < ε + l

Soit n ∈ N∗ tel que n > N . Pour tout k ≥ n , on a :

l − ε < uk < ε + l

donc l − ε < un ≤ un ≤ ε + l, d’où la suite u est convergente vers l.

De même, on montre que u converge vers l, puis, on en déduit que

lim(u − u) = 0

7. Comme qn + r = m ≥ 2n alors (q − 1)n ≥ n − r > 0 donc q > 1.

Par sous-additivité, on a

um ≤ un(q−1) + un+r

on vérifie par une récurrence facile que la sous-additivité entraîne

u(q−1)n ≤ (q − 1)un

d’où um ≤ (q − 1)un + un+r .

En divisant par m et en utilisant la définition de (q, r), on obtient
um un un+r
≤ (q − 1). +
m m m
m − n − r un un+r
= . +
n m m
m − n − r un max{un , ..., u2n−1 }
≤ . +
m n m

8. On fixe n ∈ N∗ et on pose M = max{un , ..., u2n−1 }. Pour tout m ∈ N∗ tel

que m ≥ 2n, on écrit la division euclidienne par n et on obtient :
um m − n un M
0≤ ≤ . + (∗)
m m n m
La suite m−n un M um



m
. n
+ m m≥2n
converge, donc elle est majorée puis m m≥2n
est bornée, d’où la bornétude de la suite umm m≥1 .

3
 En utilisant Q.5, le passage à la limite supérieure dans l’inégalité (∗) entraîne

um m − n un max{un , ..., u2n−1 }

lim ≤ lim. +
m→+∞ m m→+∞ m n m
m − n un max{un , ..., u2n−1 }
= lim . + ( car convergente : Q.6)
m→+∞ m n m
un
=
n
Ceci pour tout n ∈ N∗ .
9. On pose vn = un
n
pour tout n ∈ N∗ . On a :
um
∀n ∈ N∗ , ∀k ≥ n , lim ≤ vk
m→+∞ m

donc ∀n ∈ N∗ , lim um ≤ v n , ce qui donnera

m→+∞ m

um um
lim ≤ lim
m→+∞ m m→+∞ m

um um
Comme lim ≤ lim , alors la limite supérieure et la limite inférieure
m→+∞ m m→+∞ m
sont égales, ce qui donne la convergence de la suite par Q.6.

C. Une application probabiliste

n
\
0
10. • On suppose que P (X1 < x) = 1 et on pose Ω = (Xi < x).
i=1
Par indépendance, on a
n
\ n
Y
0
P (Ω ) = P ( (Xi < x)) = P (Xi < x)
i=1 i=1

Comme les Xi ont même loi alors, pour tout i = 1, ..., n ,

P (Xi < x) = P (X1 < x)

D’où P (Ω0 ) = (P (X1 < x))n = 1.

Xn
0
Si ω ∈ Ω , alors Xi (ω) < nx donc Yn (ω) < x. On a donc Ω0 ⊆ (Yn < x)
i=1

4
 d’où P (Yn < x) = 1.
n
\
• On suppose que P (X1 ≥ x) > 0. Pour ω ∈ (Xi ≥ x), on a
i=1
n
1X
Yn (ω) = Xi (ω) ≥ x
n i=1
n
\ n
Y
D’où P (Yn ≥ x) ≥ P ( (Xi ≥ x)) = P (Xi ≥ x) = (P (X1 ≥ x))n > 0.
i=1 i=1
m+n
! m
X X
1 1
11. Soit ω ∈ (Ym ≥ x) ∩ n
Xk ≥ x . On a : m
Xk (ω) ≥ x et
k=m+1 k=1
m+n
X
1
n
Xk (ω) ≥ x
k=m+1
m
X m+n
X
donc Xk (ω) ≥ mx et Xk (ω) ≥ nx, d’où Yn+m ≥ x et
k=1 k=m+1
ω ∈ (Yn+m ≥ x).
m+n
X
On en déduit que P ({Yn+m ≥ x}) ≥ P ({Ym ≥ x} ∩ { n1 Xk ≥ x}) Les
k=m+1
m+n
X
1
Xi sont indépendantes donc Ym et n
Xk le sont aussi, puis P ({Ym ≥
k=m+1
m+n m+n
X 1 X
x} ∩ { n1 Xk ≥ x}) = P ({Ym ≥ x}).P ({ Xk ≥ x}) Les Xi ont la
k=m+1
n k=m+1
m+n
X n
X m+n
X
1 1
même loi donc n
Xk et n
Xk ont la même loi, donc P ({ n1 Xk ≥
k=m+1 k=1 k=m+1
x}) = P ({Yn ≥ x}) puis
P ({Yn+m ≥ x}) ≥ P ({Yn ≥ x}).P ({Ym ≥ x})

12. Soit x ∈ R.
Cas 1 : Si P (X1 < x) = 1
1 1
∗
Dans ce cas, on a, pour tout n ∈ N
 , (P (Yn ≥ x))

n = (1 − P (Y < x)) n = 0.
n
1
D’où la convergence de la suite (P (Yn ≥ x)) n .
n∈N∗
Cas 2 : Si 0 ≤ P (X1 < x) < 1
Dans ce cas, on a, pour tout n ∈ N∗ , 0 < P (Yn ≥ x) ≤ 1.
On pose un = −
ln (P (Yn ≥ x)) ≥ 0. Par Q.11, la suite (un ) est sous-
additive, donc unn n∈N∗ est convergente (par Q.9). L’image de cette suite

5
  1

par la fonction continue exp n’est que la suite (P (Yn ≥ x)) n , d’où sa
n∈N∗
convergence.

D. Le théorème de Erdös-Szekeres
13. • Pour s = 1, il n’y a rien à démontrer.
• Supposons que la propriété est valable jusqu’au rang s et montrons la au
rang s + 1 :
Soit z une valeur de la dernière pile. Il existe une valeur bs dont le jeton est à
la s−ème pile tel que bs > z car sinon on ne va pas mettre le jeton de valeur
z à la (s+1)−ème pile. On pose bs+1 = z et on supprime tous les éléments de
la dernière pile de la liste a sans changer l’ordre des autres, la liste obtenue
sera notée a0 . Si on applique le processus énoncé sur a0 , on va obtenir les s
premières piles du processus initial, l’hypothèse de récurrence entraîne qu’il
existe pour la valeur bs une suite b0 = (b1 , ..., bs ) extraite de a0 , décroissante
telle que bi est la valeur d’un jeton qui se trouve à la i−ème pile. La suite
b = b0 , z répond bien à notre question.
14. Si a possède une liste extraite croissante de longueur p+1, alors c’est ce qu’on
veut, sinon, les p + 1 premiers éléments ne seront pas tous dans la première
pile, soit v1 la première valeur entre eux qui va être dans la deuxième pile.
On a aussi v1 , ap+2 , ..., a2p+1 n’est pas croissante, donc l’une au moins des
valeurs ap+2 , ..., a2p+1 ne sera pas dans la deuxième pile, en itérant, on trouve
que énoncé précédement donnera au moins q + 1 piles, d’où l’existence d’une
suite extraite de a, à q + 1 éléments et décroissante, d’après Q.13.

E. Comportement asymptotique d’une suite aléa-

toire
15. On a P (A1 = 1) = P (B ∈ {σ ∈ Sn , σ(1) = 1}) = (n−1)! n!
= n1
( et de même P (A2 = 1) = n1 ) donc 0 = P (A1 = 1, A2 = 1) 6= P (A1 =
1).P (A2 = 1) d’où les A1 , ..., An ne sont pas indépendantes.
16. P (As ) = P (As1 < ... < Ask ) = P (B ∈ E) avec E = {σ ∈ Sn , σ(s1 ) < ... <
σ(sk )}
Card(E)
donc P (As ) = Card(S n)
. Le choix d’un élément σ ∈ E consiste à choisir
 
n
une k− partie de {1, ..., n} avec possibilité puis l’ordonner et choisir
k
(n − k) éléments deux à deux distincts dans le reste de {1, ..., n} avec (n − k)!

6
 possibilités,  
n n! 1
d’où Card(E) = (n − k)! = k!
, par suite P (As ) = k!
.
k
17. Pour k = 1, ..., n, on note par Eck , l’ensemble de σ ∈ Sn tel que la plus longue
liste croissante extraite de (σ(1), ..., σ(n)), est de longueur k. On note aussi
par Edk , l’ensemble de σ ∈ Sn tel que la plus longue liste décroissante extraite
de (σ(1), ..., σ(n)), est de longueur k. On considère aussi la bijection ϕ qui
associe à chaque σ ∈ Sn , la permutation ϕ(σ) définie par :
ϕ(σ) = (σ(n), ..., σ(1))
On a bien ϕ(Eck ) = Edk donc Card(Eck ) = Card(Edk ).
D’où, pour tout k = 1, ..., n ,
Card(Eck ) Card(Edk )
P (Cn = k) = P (B ∈ Eck ) = = = P (B ∈ Edk ) = P (Dn = k)
n! n!
√
Montrons que E(Cn ) ≥ 2n :
Si n = 1 + pq avec p, q ∈ N∗ , alors, par Le théorème de Erdös-Szekeres, on a
P [(Cn ≥ p + 1) ∪ (Dn ≥ q + 1)] = 1
Par sous-additivité de probabilité, on a :
P (Cn ≥ p + 1) + P (Dn ≥ q + 1) ≥ 1
L’inégalité de Marcov et le fait que Cn et Dn ont même loi permettent d’écrire
1 ≤ P (Cn ≥ p + 1) + P (Dn ≥ q + 1)
E(Cn ) E(Dn )
≤ +
p+1 q+1
 
1 1
= E(Cn ) +
p+1 q+1
√
Si n = k ∈ N∗ − {1} (i.e. n ≥ 4), on pose p = k + 1 et q = k − 1, on a
n = pq + 1 donc
   
1 1 1 1 2E(Cn ) 2E(Cn )
1 ≤ E(Cn ) + = E(Cn ) + ≤ = √
p+1 q+1 k+2 k k n
√ √
Si n ∈ N, on pose p = q = [ n] et n0 = pq + 1. L’étude précédente permet
d’écrire √
p+1 n
E(Cn0 ) ≥ ≥
2 2
√
D’autre part l’inégalité p < n entraîne n0 − 1 = p2 < n donc n0 ≤ n puis
Cn0 ≤ Cn et par suite E(Cn0 ) ≤ E(Cn ) et l’inégalité est établie.

7
18. Notons Lkc = {s ∈ [|1, n|]k , s %}. On a :
ω ∈ (Cn ≥ k) ⇐⇒ ∃s = (s1 , ..., sk ) ∈ Lkc tel que (As1 (ω), ..., Ask (ω)) %
⇐⇒ ∃s = (s1 , ..., sk ) ∈ Lkc tel que ω ∈ As
[
⇐⇒ ω ∈ As
s∈Lkc
 
[ X
D’où P (Cn ≥ k) = P  As  ≤ P (As ).
s∈Lkc s∈Lkc
Le choix d’un s ∈ Lkc
consiste
 à choisir une k−partie de [|1, n|] et l’ordonner,
n
ce qui donne Card(Lkc ) = . Par Q.16, on a ∀s ∈ Lkc , P (As ) = k!1 .
k
D’où  
n
k
P (Cn ≥ k) ≤
k!
√
19. On pose k = −[−αe n].√On suppose que n ≥ 2 (le cas où n = 1 est trivial
), puisque α > 1 alors α ne > 3 donc −k ≤ −4 puis k ≥ 4, par définition
de la partie entière, on a :
√
k − 1 < αe n ≤ k
√
On a P (Cn ≥ αe n) ≤ P (Cn ≥ k − 1), et par Q.18, on a :
 
n
k−1
P (Cn ≥ k − 1) ≤
(k − 1)!
n!
(n−k+1)!
=
((k − 1)!)2
2k−2 
n! e
≤ . (Q.2)
(n − k + 1)!
k−1
1 e √
On a √
α n
< k−1
< 1 et 6 ≤ 2k − 2 ≤ 2αe n donc
 2k−2  2k−2  k−1  2αe√n
e 1 1 1
≤ √ ≤ .
k−1 α n n α
Par suite
 2k−2  2αe√n  2αe√n
n! e n n−1 n−k+2 1 1
. ≤ . ... . ≤
(n − k + 1)! k−1 n n n α α
D’où l’inégalité cherchée.

8
20. • Soit n ∈ N∗ . On pose αn = 1 +√n−1/4 > 1 . Par Q.19, il existe un entier
non nul kn vérifiant kn − 1 < αn e n ≤ kn et aussi
2αn e√n
√

1
P (Cn ≥ kn ) ≤ P (Cn ≥ αn e n) ≤
αn

L’inégalité de Q.1 reste valable même si m > n donc

E(Cn ) ≤ kn − 1 + nP (Cn ≥ kn )

puis
√ √ √
E(Cn ) ≤ αn e n + nP (Cn ≥ kn ) = n[(1 + n−1/4 )e + nP (Cn ≥ kn )]
| {z }
:=εn

D’où
E(Cn )
√ ≤ (1 + n−1/4 )e + εn (∗∗)
n
 2αn e√n
√ 1
Il suffit de montrer que lim n =0:
n→+∞ αn
On a  
1 1 1
αn ln(αn ) = 1/4 + 1/2 + o
n n n1/4
donc √
exp 2e nαn ln(αn ) = exp(2e + o(n1/4 )) exp(n1/4 )

d’où 2αn e√n

√ n1/2

1 1
n = . →0
αn exp(n ) exp(2e + o(n1/4 ))
1/4
 
• L’inégalité (∗∗) entraîne que la suite E(C√n
n
)
est majorée car elle est
n∈N∗
plus petite qu’une suite convergente. Elle est aussi
 minorée
 par 0 car Cn
E(Cn )
prend des valeurs positives, d’où la bornétude de √
n
.
n∈N∗
D’après Q.3, une suite bornée admet une limite supérieure, d’où l’existence
E(Cn )
de limn→+∞ √ . Le passage à la limite supérieure dans (∗∗) et la conver-
n
gence de la suite de droite vers e nous donne l’inégalité cherchée.

Pour vos remarques, contactez moi sur "taoufiki-maths@[Link]