BCE Maths appliquées ESSEC ECE 2011, épreuve 2Sujet, corrigé et rapport du jury

Epreuve de maths appliquées - ECE 2011

Pas encore noté

Explorer les annales

BanqueBCE Année2011 FilièreECE MatièreMathématiques

Annales BCE ECE Mathématiques BCE ECE 2011 ECE Mathématiques Mathématiques 2011

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Rapport du jury Lire en ligne LaTeX Word

Source du document : annales-prepa.fr

Description

Annale de maths appliquées BCE ESSEC pour la filiere ECE, session 2011.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

BANQUE COMMUNE D'EPREUVES

CONCOURS D'ADMISSION DE 2011
Code épreuve :
Concepteur : ESSEC
287

OPTION ECONOMIQUE

MATHEMATIQUES II

Lundi 9 mai de 8 h à 12 h

Abstract

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies. Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs. Ils ne doivent faire usage d'aucun document. L'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée. Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.

Une question que se pose un joueur de cartes est de savoir combien de fois il est nécessaire de battre les cartes pour que le paquet soit convenablement mélangé. Ce problème décrit un procédé très élémentaire pour mélanger les cartes et propose de répondre alors à cette question.

Considérons un jeu de

N

cartes numérotées de

C_1

C_N

et disposées en un paquet sur une table. Un joueur bat les cartes et repose le paquet sur la table. Le résultat du mélange est une permutation de ces

N

cartes.
Notations et Rappel: on note

S_N

l'ensemble des permutations possibles pour ce paquet de

N

cartes et on rappelle que

card(S_N) = N!

On se place dans un espace probabilisé (

Ω, A, P

) avec

Ω = S_N, A = P(S_N)

l'ensemble des parties de

S_N

P

l'équiprobabilité sur

Ω

. Pour toute variable aléatoire

X

on notera

E(X)

V(X)

l'espérance et la variance de

X

lorsqu'elles existent.

On considère qu'un paquet est convenablement mélangé lorsque toutes les permutations sont équiprobables, c'est-à-dire lorsque pour toute permutation

σ

S_N

la probabilité que le tas de cartes se trouve dans la configuration

σ

vaut

1/N

Vocabulaire et notations:

Une carte située au sommet de la pile est dite en position

n^\circ1

, celle qui se trouve immédiatement en dessous est dite en position

n^\circ2

, etc. Ainsi une carte située en position

n^\circN

désigne la carte située en bas de la pile. On prendra garde à bien distinguer la position d'une carte dans le paquet du numéro qu'elle porte.

Partons d'un tas de cartes rangées initialement dans l'ordre suivant:
pour tout

i

élément de

[ [1, N] ]

, la carte

C_i

se trouve en position

i

.
Ainsi, à l'instant initial, la carte

C_1

se trouve sur le dessus du paquet alors que

C_N

se trouve donc tout en dessous du paquet.

Pour

k

élément de

[ [1, N] ]

, on appelle insertion à la

k

-ième place l'opération qui consiste à prendre la carte située au-dessus du paquet et à l'insérer entre la

k

-ième et la (

k + 1

)-ième place. Une insertion à la première place ne change pas l'ordre des cartes. Une insertion à la

N

-ième place consiste à faire glisser la carte située au-dessus du paquet pour la mettre sous le paquet.

Le battage par insertions du jeu de cartes consiste à effectuer une suite d'insertions aléatoires, en choisissant, à chaque instant, au hasard uniformément dans

{1, \dots, N}

la place à laquelle l'insertion a lieu, indépendamment des insertions précédentes.
Les instants successifs d'insertions seront notées

1, 2, \dots, n, \dots

, l'instant initial est

n = 0

.
Notations. Nous notons :

$T_1$ le premier instant où la carte située sur le dessus du paquet est glissée en dernière position, c'est-à-dire le premier instant où la carte $C_N$ se trouve remontée de la position $N$ à la position $N - 1$ ,
$T_2$ le premier instant où la carte $C_N$ se trouve remontée en position $N - 2$ ,
et plus généralement, pour $i$ dans $[ [1, N - 1] ], T_i$ le premier instant où la carte $C_N$ atteint la position $N - i$ .
On posera également $Δ_1 = T_1$ et $\foralli \in [ [2, N - 1] ], Δ_i = T_i - T_(i - 1)$ .
Enfin, on notera $T = T_(N - 1) + 1$ .

On admet que les conditions de l'expérience permettent de faire l'hypothèse que les variables aléatoires

(Δ_i)_(i \in [ [1, N - 1] ])

sont indépendantes.

Description d'un exemple. Dans le tableau ci-dessous, nous décrivons les résultats d'une expérience faite sur un paquet de

N = 4

cartes. La première ligne du tableau indique les instants

n

, la deuxième ligne indique les positions d'insertions, et dans la dernière ligne figure la configuration du paquet à l'instant

n

	instant n	0	1	2	3	4	5	6	7
	insertion en place k		3	2	4	1	3	4	2
Configuration	position 1	$C_1$	$C_2$	$C_3$	$C_2$	$C_2$	$C_1$	$C_4$	$C_2$
du	position 2	$C_2$	$C_3$	$C_2$	$C_1$	$C_1$	$C_4$	$C_2$	$C_4$
paquet	position 3	$C_3$	$C_1$	$C_1$	$C_4$	$C_4$	$C_2$	$C_3$	$C_3$
	position 4	$C_4$	$C_4$	$C_4$	$C_3$	$C_3$	$C_3$	$C_1$	$C_1$

Pour cette expérience, on a les résultats

T_1(ω) = 3, T_2(ω) = 5

T_3(ω) = 6

T(ω) = 7

Partie 1 - Description et premiers résultats

Justifier que $\foralli \in [ [2, N - 1] ]T_i = Δ_1 + Δ_2 + \dots + Δ_i$ .

Que représente l'intervalle de temps

Δ_i

?
2) Loi de

Δ_1

Déterminer pour tout entier

n \in ℕ, P(Δ_1 > n)

et reconnaître la loi de

Δ_1

.
3) Soit

i \in [ [2, N - 1] ]

. Loi de

Δ_i

.
(a) Établir que pour tout entier

n \in ℕ

, on a

P(Δ_i > n) = ((N - i)/N)^n

. En déduire que

Δ_i

suit une loi usuelle que l'on précisera.
(b) En déduire

E(Δ_i) = N/i

V(Δ_i) = N(N - i)/(i^2)

.
4) Loi de

T_2

. Soit

n \geq 2

.
(a) Démontrer que

P(T_2 = n) = \sum_(k = 1)^(n - 1)P(Δ_2 = n - k)P(Δ_1 = k)

.
(b) Justifier que

\sum_(k = 1)^(n - 1)((1 - 1/N)/(1 - 2/N))^k = N(1 - 1/N)[((1 - 1/N)/(1 - 2/N))^(n - 1) - 1]

.
(c) En déduire que l'on a:

P(T_2 = n) = 2/N[(1 - 1/N)^(n - 1) - (1 - 2/N)^(n - 1)]

.
5) À l'instant

T_2

, la carte

C_N

est située en position

N - 2

et deux cartes se trouvent sous elle qui ont été insérées aux instants

T_1

T_2

.
Que valent alors les probabilités, qu'à l'instant

T_2

:
(a) la carte insérée à l'instant

T_1

soit en place

N - 1

et celle insérée à l'instant

T_2

en place

N

?
(b) la carte insérée à l'instant

T_2

soit en place

N - 1

et celle insérée à l'instant

T_1

en place

N

?
6) À l'instant

T_3

, la carte

C_N

est située en position

N - 3

et trois cartes, insérées aux instants

T_1, T_2

T_3

, se trouvent sous elle. On note alors, pour

i ∈ {1, 2, 3}, a_i

la position de la carte ayant été insérée à l'instant

T_i

.
(a) Combien y a-t-il de résultats possibles pour le triplet

(a_1, a_2, a_3)

?
(b) Quelques exemples. Donner les probabilités qu'à l'instant

T_3

:
i) on obtienne

(a_1, a_2, a_3) = (N - 2, N - 1, N)

?
ii) on obtienne

(a_1, a_2, a_3) = (N - 2, N, N - 1)

?
7) Justifier la phrase suivante:
"À partir de l'instant

T

, toutes les configurations du jeu de cartes sont équiprobables."
On retiendra que si on arrête le battage des cartes par insertion exactement à l'instant

T

, on a un paquet convenablement mélangé. Cependant le temps

T

étant aléatoire, il n'est pas possible d'arrêter de battre les cartes à cet instant précis, à moins de marquer la carte

C_N

bien sûr!

Partie 2 - Estimation du nombre d'insertions pour bien mélanger les cartes

Notations : on introduit les suites

(H_n)_(n \geq 1)

(u_n)_(n \in ℕ^*)

définies par :

\foralln \geq 1 H_n = \sum_(k = 1)^n 1/k et u_n = H_n - ln(n)

Espérance et variance de $T$

Justifier que

E(T) = NH_N

et que

V(T) = N^2(\sum_(k = 1)^N 1/(k^2)) - NH_N

.
9) Étude de la suite (

u_n

)
(a) Montrer que pour tout entier

k \geq 1

, on a

1/(k + 1) \leq \int_k^(k + 1)(dt)/t \leq 1/k

.
(b) En déduire successivement:
i) la décroissance de la suite (

u_n

),
ii) l'encadrement:

\foralln \in ℕ^*, ln(n + 1) \leq H_n \leq ln(n) + 1

.
(c) Déduire de ce qui précède que la suite (

u_n

) est convergente et que sa limite, notée

γ

appartient à

[0, 1]

.
10) (a) Établir que

E(T) \sim _(N \to + \infty)Nln(N)

E(T) = Nln(N) + Nγ + o(N)

.
(b) Quelle est la nature de la suite

((V(T))/(N^2))_(N \in ℕ^*)

? (on prendra garde au fait que

V(T)

dépend de

N

).
Justifier qu'il existe une constante

α

, strictement positive, telle que

V(T) \sim _(N \to \infty)αN^2 et V(T) \leq αN^2

Écart à la moyenne

On rappelle l'inégalité de Bienaymé-Chebychev valable pour une variable aléatoire

X

admettant une espérance et une variance :

\forallε > 0 P(|X - E(X)| \geq ε) \leq (V(X))/(ε^2)

Soit

N

fixé et une constante

c

strictement plus grande que 1.
(a) Justifier que

\forallω \in Ω, |T(ω) - Nln(N)| \leq |T(ω) - E(T)| + N

Comparer par une inclusion les événements suivants

(|T - Nln(N)| \geq cN) et (|T - E(T)| \geq N(c - 1))

(b) Démontrer que

P(|T - Nln(N)| \geq cN) \leq α/((c - 1)^2)

où

α

a été définie à la question 10b.
Le nombre

N

étant fixé, que vaut

lim_(c \to + \infty)P(|T - NlnN| \geq cN)

?
12) Démontrer aussi que pour tout

ε > 0

lim_(N \to + \infty)P(|T - Nln(N)| \geq εNln(N)) = 0

On peut traduire ces résultats en disant que l'événement : '

T

s'écarte de

Nln(N)

de manière significative" est un événement asymptotiquement rare.
Pour information, pour un paquet de 32 cartes, on donne

32ln(32) ≃ 110

et pour un paquet de 52 cartes,

52ln(52) ≃ 205

.
13) Simulation informatique. Dans cette question on considère un jeu de

N = 32

cartes.

MODÉLISATION : On définit en PASCAL le TYPE Paquet=ARRAY[1..32] OF INTEGER; Le paquet de
32 cartes est représenté par une variable Jeu de TYPE Paquet rempli initialement d'entiers entre 1 et 32 ; donc, initialement, Jeu[i] contient

i

, c'est à dire que la carte

C_i

est en position

i

. Au cours des insertions, Jeu[i] désigne le numéro de la carte en position numéro

i

. Par exemple, Jeu[i]=10 signifie que la carte

C_(10)

est en position

i

.
On indique à la fin de cette question un extrait de programme à compléter en suivant les questions suivantes:
(a) Écrire la procédure Init permettant de définir une variable Jeu correspondant à la configuration initiale du paquet de cartes.
(b) Compléter la procédure Insertion qui simule une opération d'insertion. On rappelle que la fonction RANDOM (32) permet de tirer un nombre entier au hasard dans l'intervalle

[ [0, 31] ]

.
(c) Que fait la fonction T?
(d) Écrire le programme principal permettant de calculer et d'afficher la moyenne des valeurs prises par la fonction T sur 100 expériences et compléter la ligne de déclaration de variables.

Extrait du programme.

PROGRAM ESSEC2011;
TYPE Paquet=ARRAY[1..32] OF INTEGER;
VAR Jeu:Paquet;
    ............ (à compléter)
PROCEDURE Init( .............)
PROCEDURE Insertion(VAR Jeu:Paquet);
VAR i,k,cartedessus:INTEGER;
BEGIN
    k:= ....... (position où on va insérer la carte du dessus)
    cartedessus:=Jeu[1];
    IF k>1 THEN FOR i :=1 TO k-1 DO Jeu[i] := ....
    Jeu[k] := ....
END;
FUNCTION T(Jeu:Paquet):INTEGER;
VAR n :INTEGER;
BEGIN
    Init(Jeu);
    n:=0;
    WHILE Jeu[1]<>32 DO
    BEGIN
        Insertion(Jeu);
        n:=n+1
    END;
    T:=n
END;
BEGIN { programme principal }
END.

Partie 3 - Distance variationnelle à la loi uniforme

Notations:

On note $π$ l'équiprobabilité sur $S_N$ , c'est-à-dire l'application de $P(S_N)$ dans [ 0,1 ] telle que:

∀A ⊂ S_N π(A) = (card(A))/(N!); en particulier, ∀σ ∈ S_N π({σ}) = 1/(N!)

On note également $μ_n$ la probabilité sur $S_N$ définie comme suit: pour chaque configuration $σ$ de $S_N, μ_n({σ})$ désigne la probabilité qu'à l'instant $n$ le tas de cartes se trouve dans la configuration $σ$ .
On a alors pour pour toute partie $A$ de $S_N, μ_n(A) = ∑_(σ ∈ A)μ_n({σ})$ .
On peut mesurer la qualité du mélange à un instant donné $n$ en estimant l'écart entre $μ_n$ et $π$ . Une distance $d$ entre ces probabilités est définie de la manière suivante:

d(μ_n, π) = max{|μ_n(A) − π(A)|, A ⊂ S_N}

Soient $A$ une partie de $S_N, n \in ℕ^*$ et $E_n$ l'événement: "à l'instant $n$ le paquet de cartes se trouve dans une configuration qui appartient à la partie $A$ ."
(a) Expliquer, en utilisant la question 7, l'égalité suivante : $P_((T \leq n))(E_n) = π(A)$ . En déduire $P(E_n \cap (T \leq n)) = π(A)P(T \leq n)$ .
(b) Établir que $P(E_n \cap (T > n)) \leq P(T > n)$ .
(c) Montrer que

μ_n(A) \leq π(A) + P(T > n)

Soit $A$ une partie de $S_N$ et $n \in ℕ^*$ . On note $A¯$ l'événement contraire de $A$ .
(a) Exprimer $μ_n(A¯) - π(A¯)$ en fonction de $μ_n(A)$ et $π(A)$ .
(b) Déduire des questions précédentes la majoration :

|μ_n(A) - π(A)| \leq P(T > n)

Montrer que $\foralln \in ℕ^*, 0 \leq d(μ_n, π) \leq P(T > n)$ . Déterminer la limite $lim_(n \to + \infty)d(μ_n, π)$ .

Partie 4- Une majoration de $P(T > n)$

Dans cette partie, nous nous intéressons provisoirement à un collectionneur de timbres. Celui-ci reçoit chaque jour une lettre affranchie avec un timbre choisi au hasard uniformément parmi les

N

timbres en vigueur. On étudie ici le nombre de jours que doit attendre le collectionneur pour posséder la collection complète des

N

timbres. Le jour 0 il n'a aucun timbre.
On note alors :

pour tout entier $k \in [ [1, N] ], S_k$ le nombre aléatoire de jours que doit attendre le collectionneur pour que le nombre de timbres différents qu'il possède passe de $k - 1$ à $k$ ,
$S = S_1 + S_2 + \dots + S_N$ , soit la variable aléatoire correspondant au nombre de jours à attendre pour posséder la collection complète des $N$ timbres,
en supposant les $N$ timbres en vigueur numérotés de 1 à $N$ , pour tout $j \in [ [1, N] ], B_j^m$ l'événement "le jour $m$ , le collectionneur n'a toujours pas reçu de lettre affranchie avec le timbre numéro $j$ ."
On admet que les variables aléatoires $(S_k)_(k \in [1, N])$ sont indépendantes.

Déterminer la loi de $S_1$ .
Déterminer pour tout entier $k \in [ [2, N] ]$ la loi de la variable $S_k$ .
En déduire que la variable $S$ suit la même loi de probabilité que la variable $T$ étudiée dans les parties précédentes.
Ce résultat sera utilisé pour estimer la quantité $P(T > n)$ .
Soit $m \in ℕ^*$ .
(a) Exprimer l'événement $(S > m)$ à l'aide des événements $B_1^m, B_2^m, \dots, B_N^m$ .
(b) Que vaut $P(B_j^m)$ pour tout entier $j \in [ [1, N] ]$ ?
(c) On rappelle que pour tout entier $n \geq 2$ et pour toute famille d'événements $A_1, \dots, A_n$ , on a l'inégalité: $P(⋃_(i = 1)^n A_i) \leq \sum_(i = 1)^n P(A_i)$ En déduire $P(S > m) \leq N(1 - 1/N)^m$ .
(a) Montrer que $ln(1 + x) \leq x$ pour tout $x \in ] - 1$ , $+ \infty[$ .
(b) Déduire des résultats précédents la majoration

\forallm \in ℕ, P(T > m) \leq Ne^(- m/N)

On reprend les notations introduites dans la partie précédente.
(a) Soit $c > 0$ fixé. Montrer que pour $n$ entier supérieur ou égal à $NlnN + cN$ on a : $d(μ_n, π) \leq e^(- c)$ .
(b) Application numérique. On estime qu'une distance en variation à la loi uniforme de 0,2 est acceptable.
Avec un jeu de 32 cartes, combien de battages par insertions doit-on faire pour considérer le paquet mélangé de façon acceptable?

Pas de description pour le moment

Commentaires• BCE Maths appliquées ESSEC ECE 2011, épreuve 2

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...

Explorer les annales

Téléchargements

Description

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

BANQUE COMMUNE D'EPREUVES

OPTION ECONOMIQUE

MATHEMATIQUES II

Abstract

Vocabulaire et notations:

Partie 1 - Description et premiers résultats

Partie 2 - Estimation du nombre d'insertions pour bien mélanger les cartes

Partie 3 - Distance variationnelle à la loi uniforme

Notations:

Partie 4- Une majoration de P(T > n)

Commentaires• BCE Maths appliquées ESSEC ECE 2011, épreuve 2

Commentaires• BCE Maths appliquées ESSEC ECE 2011, épreuve 2

Partie 4- Une majoration de $P(T > n)$