Mines Maths 1 MP 2018

Thème de l'épreuve Lemme de Fekete et théorème d'Erdös-Szekeres
Principaux outils utilisés variables aléatoires, suites numériques, dénombrement, combinatoire, développements limités
Mots clefs Fekete, suites sous-additives, Erdös-Szekeres, limites inférieure et supérieure d'une suite, comportement asymptotique d'une suite aléatoire

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


CONCOURS MINES
COMMUN... PONTS
..

ECOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES SAINT-ETIENNE, MINES NANCY,
IMT Atlantique, ENSAE PARISTECH.

Concours Centrale-Supélec (Cycle International),
Concours Mines--Télécom, Concours Commun TPE / EIVP.

CONCOURS 2018
PREMIÈRE ÉPREUVE DE MATHÉMATIQUES

Durée de l'épreuve : 3 heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.

Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :

MATHÉMATIQUES I - MP

L'énoncé de cette épreuve comporte 5 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.

Lemme de Fekete et théorème de Erdôs--Szekeres

Le but de ce problème est d'étudier quelques applications probabilistes du
lemme de sous-additivité de Fekete et du théorème de Erdôs--Szekeres.

Dans tout le problème, (Q,d,P) désigne un espace probabilisé. On note
P(A) la probabilité d'un événement A et on note E(X ) l'espérance (si elle 
existe)
d'une variable aléatoire réelle discrète X définie sur (Q, .szi , P).

A. Préliminaires

Les deux questions de cette partie sont indépendantes.

Soit n un entier naturel non nul.

1) Montrer que pour toute variable aléatoire X réelle à valeurs dans {l, . . ., 
n}
et pour tout m EUR {1, . .., n},

E(X) $ m-- 1 + nP(X ? m).
2) À l'aide d'une comparaison entre une somme et une intégrale, montrer

que

nln(n)-- n+l< Zln(k).

En déduire l'inégalité

B. Le lemme de sous--additivité de Fekete

Soit u : (un)neN* une suite réelle bornée. Pour tout n EUR N*, on note Un :
{u,c ; k 2 n}. On définit les suites u : OE,JneN* etü : (ün)neN* par les 
formules

=inf(Un) et un=sup(Un).

3) Justifier que u et Ü sont bien définies. Montrer qu'elles sont monotones
puis qu'elles convergent.

Pour toutes suites réelles v : (un)neN* et w : (wn)neN*, on dit que 1) est plus
petite que w, et on note v 5 w, si pour tout n EUR N*, on a un S w... De façon
équivalente, on dit aussi que w est plus grande que 1).

4) Montrer que Ü est la plus petite suite (au sens de 5) qui est décroissante
et plus grande que tt. Montrer de même que E est la plus grande suite (au
sens de $) qui est croissante et plus petite que u.

Dans toute la suite du problème, on appelle limite inférieure li_m et limite 
supé--
rieure lim les limites suivantes :

lim un: lim un et lim un: lim un
n-->+oo ïl-*+OO_ n-->+oo n-->+oo

5) Si 1) = (un) new est une autre suite réelle bornée plus grande que u, com--
parer les limites de ü et de ?.

6) Montrer que ü et E sont adjacentes si et seulement si u converge. En ce
cas, que peut--on dire des limites des trois suites u, ü et H ?

On dit qu'une suite réelle u = (un) neN* est sous--additive si pour tous i, j 
dans N*,
ona ui+j S ui+ uj.

Dans le reste de cette partie on ne suppose plus que la suite u est bornée, 
mais on
suppose que u est positive et sous-additive.

7) Soit m et n deux entiers naturels non nuls tels que m > 211. On note q le
quotient et r le reste de la division euclidienne de m par n. Montrer que

um 5 (q_ 1)un+ un+r

et en déduire l'inégalité

u... < m--n--r un+max{un,un+l,...,u2n_l}
m m n m '
, . . um , . *
8) En déduire que la suite -- est bornee, puis que pour tout n EUR N ,
m meN*
.-- um un
11m -- < --.
m-->+oo m n
. un
9) En conclure que la suite (--) converge.
ïl nEN*

C. Une application probabiliste

Soit x un nombre réel et (X n) neN* une suite de variables aléatoires réelles 
mutuel-
lement indépendantes et de même loi. Pour tout n EUR N* on note Yn la variable
aléatoire réelle définie par

1 n
Yn=--ZXk.
"k=1

10) Montrer que si P(X1 < x) = 1, alors pour tout n EUR N*, P(Yn < x) = 1 et que
si P(X1 > x) > 0, alors pour tout n EUR N*, P(Yn > x) > 0.

1 1) Soit m et n deux entiers naturels non nuls. Montrer l'inclusion d'événe--
ments suivante :

({Y... ; x}n{%knîn X,, ; x}) c {y... >x}
=m+l

et en déduire l'inégalité
P(Ym+n > x) > P(Y... > x)P(Yn > x).

12) Démontrer la convergence de la suite

((P(Yn ; x)) )neN*

D. Le théorème de Erdôs--Szekeres

Si r est un entier naturel non nul, on note EUR = (! 1, . . . , EUR T) une 
liste de nombres
réels de longueur r; cette liste est croissante si & S [2 S EUR EUR... 
décroissante
si 61 > [2 > > &. Une liste !' de longueur p EUR {1,...,r} est extraite de ! 
s'il
existe 19 indices strictement croissants il < i2 < < i ,, dans {1,..., r} tels 
que
!'= (f,--l,...Æip).

Soit 19 et q deux entiers naturels non nuls et a : (al, a2, . . . , apq+1) une 
liste
de longueur pq + 1 de nombres réels deux--à--deux distincts qui représentent les
valeurs de pq + 1 jetons numérotés 1,2, . ..,pq + 1.

On range successivement les jetons en piles de gauche à droite par le procédé
suivant :

° le jeton n°1 de valeur al débute la première pile;

° si az > al, alors on pose le jeton n°2 de valeur az sur le jeton n°1 ;
sinon on crée une nouvelle pile avec ce jeton n°2, située à droite de la
première pile ;

° lors des étapes suivantes, disposant du jeton n°k de valeur ok, on le dé--
pose sur la première pile en partant de la gauche telle que ak est supérieur
àla valeur du jeton au sommet de la pile, si une telle pile existe ;
sinon on crée une nouvelle pile avec ce jeton, située à droite des précé--
dentes.

En suivant ce procédé avec tous les jetons, on obtient plusieurs piles de
jetons, chaque pile ayant des valeurs rangées dans l'ordre croissant du bas vers
le haut.

Par exemple, avec la liste
a : (1,4,2,3,7,6,5,9, 10,8)

dans cet ordre, on obtient de gauche à droite les trois piles suivantes :

10

»---q>\1oe
mwoeoe

5

13) À l'aide d'un raisonnement par récurrence sur le nombre 3 de piles, mon--
trer qu'à l'issue du processus, pour tout jeton de valeur z de la dernière
pile, il existe une liste 19 : (bl, . . . , b,) de réels extraite de la liste a 
vérifiant :

° 19 est décroissante et de longueur 3;
° pour tout i EUR {1, . . . , s} le jeton n°i de valeur 19,-- est dans la 
i--ème pile
en partant de la gauche ;
° 19, = z.
Par exemple, avec la liste a = (l, 4, 2, 3, 7, 6, 5, 9, 10, 8) on a une liste 
extraite
b = (7, 6, 5).

14) En déduire que la liste a admet au moins une liste extraite croissante de
longueur ;? + 1 ou une liste extraite décroissante de longueur q + 1.

E. Comportement asymptotique d'une suite aléatoire

Soit n un entier naturel supérieur ou égal à 2. On note S,, l'ensemble des
permutations de {1,2, . . . , n}. Chaque élément 0 EUR S,, est noté par la 
liste de ses
n images (a(l),a(2),...,a(n)).

Soit B une variable aléatoire à valeurs dans S,, de loi uniforme, c'est-à--dire
que pour tout 0 EUR 8 ,,, on a P(B : a) = 1/ Card(S ,,). On définit la variable 
aléa--
toire A à valeurs dans S,, en posant, pour tout au EUR 9,

A(w) = (B(w)(l),...,B(w)(n)).

On note également, pour tout k EUR {1, . . . , n}, Ak(w) : B(w) (lc). Enfin, on 
considère
les variables aléatoires réelles C,, et D,, définies par:

- C,, est la longueur de la plus longue liste croissante extraite de A ;

- D,, est la longueur de la plus longue liste décroissante extraite de A.

15) Les variables aléatoires réelles A1,A2,...,A,, sont-elles mutuellement
indépendantes ?

16) Soit k EUR {I, . . ., n} et s = (31, . . . , sk) une liste croissante de 
longueur k d'élé--
ments de {1,...,n}. On note AS l'événement : « la liste (Asl,...,Ask) est

1
croissante ». Montrer que P(As) : Ë'

17) Démontrer que CH et Du ont la même loi. Démontrer alors, à l'aide du
résultat de la question 14, que :

E(Cn) > %.

18) Démontrer que pour tout k EUR {1, . . . , n},

... > ... < @

n / \ k! .

19) Soit n un entier naturel non nul et a un réel strictement supérieur à 1.
Justifier qu'il existe un entier naturel non nul k tel que k -- 1 < ae\/ñ S lc.

À l'aide du résultat de la question 2, déduire de la question précédente

que
1 2aefi
P(Cn>ae\/Ë) < (--)

a

20) En déduire qu'il existe une suite (en) neN* tendant vers 0 telle que, pour

tout neN*, E C
( ") s(1+n_1/4)e+en.
\/ñ
-- ECn -- EC
En conclure que nlim ( n)existe et que nlim ( n)<
+oo \/ñ +oo \/ñ\

FIN DU PROBLÈME

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



Mines Maths 1 MP 2018 -- Corrigé
Ce corrigé est proposé par Sophie Rainero (professeur en CPGE) ; il a été relu
par Juliette Brun Leloup (professeur en CPGE) et Florian Metzger (docteur en 
mathématiques).

Ce sujet traite :
· du lemme de sous-additivité de Fekete, qui affirme que si (un )nN est une 
suite
réelle sous-additive, c'est-à-dire telle que ui+j 6 ui + uj pour tout (i, j)  N 
2 ,
alors la suite (un /n)nN converge ;
· du théorème d'Erdös-Szekeres : dans une liste de pq + 1 nombres réels 
distincts,
il y a au moins une liste extraite croissante de longueur p + 1 ou une liste
extraite décroissante de longueur q + 1.
Il en donne ensuite des applications probabilistes. Il se compose de cinq 
parties.
· Dans la partie A, on établit deux résultats préliminaires indépendants : une
majoration de l'espérance d'une variable aléatoire à support dans [[ 1 ; n ]] et
une minoration de n!, pour n  N .

· Dans la partie B, on définit les limites inférieure et supérieure d'une suite
bornée et on démontre le lemme de sous-additivité de Fekete. Il s'agit d'un
exercice classique.

· La partie C donne une application probabiliste de ce lemme. On y considère
une suite (Xi )iN de variables aléatoires mutuellement indépendantes et de
même loi. On définit, pour tout n  N ,
Yn =

n
1 P
Xi
n i=1

et on démontre que, pour tout réel x, la suite P(Yn > x)1/n
· La partie D établit le théorème d'Erdös-Szekeres.

nN

converge.

· Enfin, on étudie dans la partie E le comportement asymptotique d'une suite
aléatoire définie à l'aide d'une variable aléatoire à valeurs dans l'ensemble Sn
des permutations de [[ 1 ; n ]].
Les parties A, B et D sont autonomes. La partie E est la plus ardue.
Ce sujet est abordable dès la fin de la MPSI puisqu'il porte sur les suites en
analyse et les variables aléatoires à support fini en probabilités, à 
l'exception de la
partie C qui s'intéresse à des suites de variables aléatoires discrètes dont 
l'étude
n'est effectuée qu'en seconde année. C'est un joli sujet, dans lequel on 
démontre des
résultats intéressants et originaux, en mobilisant finalement assez peu de 
connaissances. Notons cependant que les questions 16, 17 et 20 requièrent une 
bonne maîtrise
technique.

Indications
Partie A
1 Découper en deux la somme définissant E(X).
Partie B
3 Se souvenir que la borne supérieure est le plus petit des majorants.
4 Utiliser la question 3 et considérer une autre suite v décroissante et plus 
grande
que u pour montrer que u est la plus petite.
6 Procéder par double implication. Utiliser le théorème d'encadrement dans un 
sens
et la définition de la limite dans l'autre.
7 Remarquer puis démontrer par récurrence que uab 6 b ua pour tout (a, b)  N 2 .

8 Appliquer la question 7 avec n = 1, puis utiliser les résultats des questions 
5, 6
et 7.
9 Prouver à l'aide des questions 8 et 5 que la limite inférieure de la suite 
(un /n)nN
est supérieure ou égale à sa limite supérieure. Conclure à l'aide du résultat 
de la
question 6.
Partie C
10 Comparer les événements {Yn < x} et {X1 < x}  · · ·  {Xn < x}. Utiliser la
croissance de la probabilité et les propriétés de la suite (Xi )iN . La seconde 
partie
de la question se traite de manière similaire.
11 Utiliser la croissance de la probabilité et les propriétés de la suite (Xi 
)iN .
Remarquer que les variables aléatoires Yn et
P
1 m+n
Xk
n k=m+1
ont la même loi.
12 Distinguer deux cas selon la valeur de P(X1 < x) en se servant de la 
question 10.
Lorsque P(X1 < x) < 1, introduire la suite de terme général - ln(P(Yn > x)) et
se servir des questions 9 et 11 pour conclure.
Partie D
13 Dans l'hérédité, observer que si un jeton j est dans la dernière pile, sa 
valeur est
nécessairement plus petite que celle d'un jeton de l'avant-dernière pile, celui 
qui
était au sommet de cette pile au moment où on a posé le jeton j.
14 Distinguer deux cas selon que le nombre de piles obtenues à la fin du 
processus
est supérieur ou égal à q + 1 ou pas. Dans le premier cas, utiliser la question 
13
et dans le second se demander combien de jetons peut contenir chaque pile.
Partie E
15 Démontrer que les variables aléatoires A1 et A2 ne sont pas indépendantes en
considérant par exemple l'événement {A1 = 1, A2 = 1}.

16 Attention, la liste s doit être strictement croissante, il y a une petite 
erreur dans
l'énoncé. En notant E l'ensemble des permutations  de [[ 1 ; n ]] telles que
(s1 ) < · · · < (sk )
démontrer que

P(As ) = P(B  E) =

Card E
n!

et dénombrer les éléments de E.
17 Introduire la variable aléatoire B =   B où  :  7- ((n), . . . , (1)) et 
justifier
que B est de même loi que B. Définir les variables aléatoires Cn et Dn associées
à B comme Cn et Dn le sont à B.
Pour la minoration de l'espérance, écrire que 2 E(Cn ) = E(Cn ) + E(Dn ) et 
appliquer la question 14 avec p = q = max{k  N | 1 + k 2 6 n}.

18 Utiliser la question 16 et dénombrer les listes strictement croissantes, de 
longueur k, d'éléments de [[ 1 ; n ]].

19 Vérifier que k = -- e n convient. Remarquer que Cn est à valeurs entières
pour majorer la probabilité considérée à l'aide des questions 18 et 2.
20 Observer que la majoration de la question 1 est également valable pour m > 
n+1.
Utiliser les questions 19 et 1 avec  = 1 + n-1/4 et l'entier k  N qui est 
associé
à  dans la question 19.
Faire un développement asymptotique pour justifier que la suite (n )nN tend
vers 0 et conclure à l'aide des questions 3, 5 et 6.

1 Soit X une variable aléatoire à valeurs dans [[ 1 ; n ]]. Comme elle est à 
support
fini, son espérance est bien définie, en tant que somme finie. Soit m  [[ 1 ; n 
]] ; calculons E(X) :
E(X) =

n
P

k P(X = k) =

k=1

Or,

n
P

k P(X = k) +

k=1

m-1
P
k=1

m-1
P

m-1
P

k P(X = k) 6 (m - 1)

k=1

k P(X = k)

k=m

P(X = k) 6 (m - 1)

n
P

k=1

P(X = k) = m - 1

par positivité d'une probabilité et parce que
n
P

(puisque X() = [[ 1 ; n ]])

P(X = k) = 1

k=1
n
P

De plus,

k P(X = k) 6 n

k=m

n
P

P(X = k) = n P(X > m)

k=m

puisque X() = [[ 1 ; n ]]. Finalement, par somme d'inégalités,
m  [[ 1 ; n ]]

E(X) 6 m - 1 + n P(X > m)

2 La fonction définie sur [ 0 ; + [ par x 7- ln(x) est continue, croissante et 
positive. Soit n  N . Pour tout k  N , ln est donc majorée par ln(k + 1) sur le
segment [ k ; k + 1 ]. Ainsi, par croissance de l'intégrale, pour tout k  N ,
Z k+1
Z k+1
ln(t) dt 6
ln(k + 1) dt = (k + 1 - k) ln(k + 1) = ln(k + 1)
k

k

Sommons ces inégalités pour k allant de 1 à n - 1, il vient
Z
n-1
n-1
n
n
P k+1
P
P
P
ln(t) dt 6
ln(k + 1) =
ln(j) =
ln(j)
k=1 k

j=2

k=1

j=1

puisque ln(1) = 0. Ainsi, en vertu de la relation de Chasles,
Z n
Z
n-1
n
P k+1
P
ln(t) dt =
ln(t) dt 6
ln(j)
j=1

k=1 k

1

Il reste à calculer l'intégrale :
Z n
n
ln(t) dt = [t ln(t) - t]1 = n ln(n) - n - ln(1) + 1 = n ln(n) - n + 1
1

n  N

En conclusion,

n ln(n) - n + 1 6

n
P

ln(k)

k=1

Rappelons brièvement comment retrouver une primitive de la fonction continue ln 
sur l'intervalle ] 0 ; + [. Soit x > 0. Alors
Z x
Z x
ln(t) dt =
u(t) v  (t) dt
1

1

en posant u : t 7- ln(t) et v : t 7- t. Les fonctions u et v étant de classe C 1
sur le segment d'intégration, il vient par intégration par parties
Z x
Z x
Z x
x
x
ln(t) dt = [u(t)v(t)]1 -
u (t) v(t) dt = [t ln(t)]1 -
1 dt
1

1

1