\documentclass[10pt]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[version=4]{mhchem}
\usepackage{stmaryrd}
\usepackage{bbold}

\title{ECOLE DES HAUTES ETUDES COMMERCIALES \\
 E.S.C.P. - E.A.P. \\
 ECOLE SUPERIEURE DE COMMERCE DE LYON }

\author{}
\date{}


\begin{document}
\maketitle
CONCOURS D'ADMISSION SUR CLASSES PREPARATOIRES

\section*{OPTION SCIENTIFIQUE}
\section*{MATHEMATIQUES II}
Mardi 16 Mai 2000, de 8h. à 12h.

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.

Le problème consiste en l'analyse d'un algorithme de tri et l'étude de sa complexité.\\
On note \(\ln x\) le logarithme népérien d'un réel strictement positif \(x\) et \(\log _{2} x\) son logarithme en base 2 . On rappelle que \(\log _{2} x=\frac{\ln x}{\ln 2}\).

\section*{Partie I: Étude d'une suite réelle}
Dans cette partie la lettre \(n\) désignera toujours un entier naturel au moins égal à 2 .\\
On considère la suite \(\left(u_{k}\right)_{k \in \mathbb{N}^{*}}\) définie par son premier terme \(u_{1}\) et vérifiant, pour tout \(n\), la relation de récurrence : \(u_{n}=n-1+\frac{2}{n} \sum_{i=1}^{n-1} u_{i}\).

\begin{enumerate}
  \item a) Calculer \(u_{2}\) et \(u_{3}\) en fonction de \(u_{1}\).\\
b) Montrer que, pour tout \(n\) au moins égal à 3 , on a : \(n u_{n}-(n+1) u_{n-1}=2 n-2\).
  \item Pour tout entier naturel \(k\) non nul, on pose : \(v_{k}=\frac{u_{k}}{k+1}\).\\
a) Pour tout \(n\) au moins égal à 3 , exprimer \(v_{n}-v_{n-1}\) en fonction de \(n\).\\
b) Déterminer deux réels \(\alpha\) et \(\beta\) vérifiant, pour tout réel \(x\) non nul et distinct de -1 , l'égalité:
\end{enumerate}

\[
\frac{2 x-2}{x(x+1)}=\frac{\alpha}{x}+\frac{\beta}{x+1}
\]

c) Pour tout \(n\), établir l'égalité : \(v_{n}=2 \sum_{k=2}^{n} \frac{1}{k}+\frac{u_{1}}{3}-2+\frac{4}{n+1}\).\\
3) Pour tout \(n\), on pose \(h_{n}=\sum_{k=2}^{n} \frac{1}{k}\) et \(z_{n}=\frac{1}{n}-\ln \left(\frac{n}{n-1}\right)\).\\
a) Calculer \(u_{n}\) en fonction de \(h_{n}, u_{1}\) et \(n\).\\
b) Prouver l'égalité : \(h_{n}=\sum_{k=2}^{n} z_{k}+\ln n\).\\
c) Déterminer la nature de la série de terme général \(z_{n}\).\\
d) En déduire un équivalent de \(h_{n}\) quand \(n\) tend vers l'infini.\\
e) Déterminer un équivalent de \(u_{n}\) quand \(n\) tend vers l'infini.

\section*{Partie II: Étude d'une suite de variables aléatoires}
A. On considère un espace probabilisé dont la probabilité est notée \(\mathbf{P}\), une variable aléatoire \(Z\), définie sur cet espace, prenant un nombre fini de valeurs réelles notées \(z_{1}, z_{2}, \ldots, z_{p}\) et un événement \(A\) de probabilité non nulle.\\
On note \(\mathbf{E}(Z / A)\) l'espérance de la variable aléatoire \(Z\) pour la probabilité conditionnelle sachant \(A\), i.e.

\[
\mathbf{E}(Z / A)=\sum_{i=1}^{p} z_{i} \mathbf{P}\left(\left[Z=z_{i}\right] / A\right)
\]

Soit ( \(A_{1}, A_{2}, \ldots, A_{q}\) ) un système complet d'événements tous de probabilité non nulle. Prouver l'égalité :

\[
\mathbf{E}(Z)=\sum_{j=1}^{q} \mathbf{P}\left(A_{j}\right) \mathbf{E}\left(Z / A_{j}\right)
\]

B. Toutes les variables aléatoires considérées dans cette sous-partie sont définies sur un même espace probabilisé dont la probabilité est notée \(\mathbf{P}\).\\
On considère une suite \(\left(I_{n}\right)_{n \in \mathbb{N}^{*}}\) de variables aléatoires telle que, pour tout \(n\) non nul, \(I_{n}\) suit la loi uniforme sur l'ensemble \(\{1,2, \ldots, n\}\) des entiers compris, au sens large, entre 1 et \(n\).\\
D'autre part, on considère une suite \(\left(X_{n}\right)_{n \in \mathbb{N}^{*}}\) de variables aléatoires ayant les propriétés suivantes:

\begin{itemize}
  \item \(X_{1}\) est la variable constante égale à 0
  \item pour tout entier naturel \(n\) au moins égal à 2 , les lois conditionnelles de \(X_{n}\) sachant \(\left[I_{n}=1\right]\) et de \(X_{n}\) sachant \(\left[I_{n}=n\right]\) sont toutes deux égales à la loi de \(n-1+X_{n-1}\)
  \item pour tout entier naturel \(n\) au moins égal à 3 et tout entier \(i\) tel que \(2 \leqslant i \leqslant n-1\), la loi conditionnelle de \(X_{n}\) sachant \(\left[I_{n}=i\right]\) est égale à la loi de \(n-1+Z_{n, i}+T_{n, i}\) où \(Z_{n, i}\) et \(T_{n, i}\) sont deux variables aléatoires indépendantes, \(Z_{n, i}\) ayant même loi que \(X_{i-1}\) et \(T_{n, i}\) ayant même loi que \(X_{n-i}\).
\end{itemize}

Par exemple, on a :\\
\(\mathbf{P}\left(\left[X_{6}=9\right] /\left[I_{6}=1\right]\right)=\mathbf{P}\left(\left[X_{5}=4\right]\right)\) et aussi \(\mathbf{P}\left(\left[X_{6}=9\right] /\left[I_{6}=3\right]\right)=\mathbf{P}\left(\left[Z_{6,3}+T_{6,3}=4\right]\right)\) ce qui, compte tenu des hypothèses, s'écrit : \(\mathbf{P}\left(\left[X_{6}=9\right] /\left[I_{6}=3\right]\right)=\sum_{j} \mathbf{P}\left(\left[X_{2}=j\right]\right) \mathbf{P}\left(\left[X_{3}=4-j\right]\right)\), la somme étant étendue aux valeurs convenables de l'entier \(j\).

\begin{enumerate}
  \item a) Montrer que \(X_{2}\) est une variable aléatoire presque sûrement constante égale à 1 .\\
b) Établir les égalités: \(\mathbf{P}\left(\left[X_{3}=2\right]\right)=\frac{1}{3}\) et \(\mathbf{P}\left(\left[X_{3}=3\right]\right)=\frac{2}{3}\). Calculer l'espérance de \(X_{3}\) qu'on notera \(U_{3}\).
  \item Déterminer la loi de \(X_{4}\) et calculer son espérance qu'on notera \(U_{4}\).
  \item En procédant par récurrence, montrer que, pour tout entier naturel \(n\) non nul, \(X_{n}\) prend, presque sûrement, des valeurs entières inférieures ou égales à \(\frac{n(n-1)}{2}\).
  \item Soit \(n\) un entier naturel au moins égal à 2 . On note \(U_{n}\) l'espérance de \(X_{n}\).\\
a) À l'aide des résultats de la sous-partie \(\mathbf{A}\), établir l'égalité : \(U_{n}=n-1+\frac{2}{n} \sum_{i=1}^{n-1} U_{i}\).\\
b) À l'aide de la partie \(\mathbf{I}\), donner l'expression de \(U_{n}\) en fonction de \(n\) ainsi qu'un équivalent de \(U_{n}\) quand \(n\) tend vers l'infini.
  \item Pour tout entier naturel \(n\) non nul, on note \(\alpha_{n}\) la plus petite valeur (entière) prise par la variable \(X_{n}\) avec une probabilité non nulle.\\
a) Soit \(n\) et \(k\) deux entiers naturels, l'entier \(n\) étant au moins égal à 3 .
\end{enumerate}

Montrer que \(\mathbf{P}\left(\left[X_{n}=k\right]\right)\) est nul si et seulement si les nombres \(\mathbf{P}\left(\left\lfloor n-1+X_{n-1}=k\right\rfloor\right)\) et \(\mathbf{P}\left(\left[n-1+Z_{n, i}+T_{n, i}=k\right]\right)\) (l'entier \(i\) variant de 2 à \(n-1\) ) sont nuls.\\
En déduire que \(\alpha_{n}\) est au moins égal au minimum des nombres \(n-1+\alpha_{n-1}, n-1+\alpha_{1}+\alpha_{n-2}\), \(n-1+\alpha_{2}+\alpha_{n-3}, \ldots, n-1+\alpha_{n-2}+\alpha_{1}\).\\
b) On considère la fonction \(g\) définie, pour tout \(x\) strictement positif, par \(g(x)=x \log _{2} x-2 x+2\).\\
i) Montrer que \(g\) est convexe. Pour tout couple d'entiers ( \(i, n\) ) tel que \(2 \leqslant i \leqslant n-1\), en déduire l'inégalité : \(g(i)+g(n+1-i) \geqslant 2 g\left(\frac{n+1}{2}\right)\).\\
ii) Pour tout entier naturel \(n\) non nul, établir l'inégalité : \(g(n+1)-g(n) \leqslant \log _{2}(n+1)\). En traitant à part les cas \(n=1\) et \(n=2\), montrer que, pour tout entier naturel \(n\) non nul, on a : \(g(n+1)-g(n) \leqslant n-1\).\\
6) En procédant par récurrence, établir, pour tout entier naturel \(n\) non nul, l'inégalité:

\[
\alpha_{n} \geqslant(n+1) \log _{2}(n+1)-2 n
\]

\section*{Partie III : Étude d'un algorithme de tri}
A. On considère un entier naturel \(n\) non nul et un ensemble \(E=\left\{e_{1}, e_{2}, \ldots, e_{n}\right\}\) où \(e_{1}, e_{2}, \ldots, e_{n}\) sont des réels vérifiant \(e_{1}<e_{2}<\ldots<e_{n}\). On munit l'ensemble des permutations de \(E\) de la probabilité uniforme notée \(\mathbf{P}\). On considère les \(n\) variables aléatoires \(T_{1}, T_{2}, \ldots, T_{n}\) qui, à toute permutation \(\sigma\) de \(E\), associent les images des éléments de \(E\) par \(\sigma\), i.e. \(T_{1}(\sigma)=\sigma\left(e_{1}\right), T_{2}(\sigma)=\sigma\left(e_{2}\right), \ldots, T_{n}(\sigma)=\sigma\left(e_{n}\right)\), et on note \(T\) le vecteur aléatoire ( \(T_{1}, T_{2}, \ldots, T_{n}\) ). Pour toute liste ( \(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n}\) ) d'éléments distincts de \(E\) on a donc

\[
\mathbf{P}\left(\left[T=\left(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n}\right)\right]\right)=\frac{1}{n!}
\]

\begin{enumerate}
  \item Déterminer la loi de la variable aléatoire \(T_{1}\).
  \item On suppose \(n\) au moins égal à 2 . Pour toute permutation \(\sigma\) de \(E\) on note \(T_{1}^{\prime}(\sigma)\) le premier élément de la liste \(\left(\sigma\left(e_{1}\right), \sigma\left(e_{2}\right), \ldots, \sigma\left(e_{n}\right)\right)\) inférieur à \(\sigma\left(e_{1}\right)=T_{1}(\sigma)\) si un tel élément existe et \(T_{1}^{\prime}(\sigma)=0\) sinon, \(T_{2}^{\prime}(\sigma)\) le deuxième élément inférieur à \(\sigma\left(e_{1}\right)\) si un tel deuxième élément existe et \(T_{2}^{\prime}(\sigma)=0\) sinon, etc., \(T_{n-1}^{\prime}(\sigma)\) le \((n-1)\)-ième élément inférieur à \(\sigma\left(e_{1}\right)\) si un tel \((n-1)\)-ième élément existe et \(T_{n-1}^{\prime}(\sigma)=0\) sinon.\\
Par exemple, si\\
\(n=4,\left(e_{1}, e_{2}, e_{3}, e_{4}\right)=(3,5,7,10)\) et \(\left(\sigma\left(e_{1}\right), \sigma\left(e_{2}\right), \sigma\left(e_{3}\right), \sigma\left(e_{4}\right)\right)=(7,10,5,3)\)\\
alors \(T_{1}^{\prime}(\sigma)=5, T_{2}^{\prime}(\sigma)=3\) et \(T_{3}^{\prime}(\sigma)=0\).\\
Soit \(k\) un entier vérifiant \(1 \leqslant k \leqslant n-1\).\\
a) Combien y a-t-il de listes ( \(i_{1}, i_{2}, \ldots, i_{k}\) ) d'entiers vérifiant \(2 \leqslant i_{1}<i_{2}<\ldots<i_{k} \leqslant n\) ?\\
b) Soit ( \(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{k}\) ) une liste d'éléments distincts de \(\left\{e_{1}, e_{2}, \ldots, e_{k}\right\}\). Établir l'égalité:
\end{enumerate}

\[
\mathbf{P}\left(\bigcap_{j=1}^{k}\left[T_{j}^{\prime}=\alpha_{j}\right] \cap\left[T_{1}=e_{k+1}\right]\right)=\frac{1}{n k!}
\]

c) En déduire l'égalité :

\[
\mathbf{P}\left(\bigcap_{j=1}^{k}\left[T_{j}^{\prime}=\alpha_{j}\right] /\left[T_{1}=e_{k+1}\right]\right)=\frac{1}{k!}
\]

où \(\mathbf{P}(A / B)\) désigne la probabilité conditionnelle de \(A\) sachant \(B\).\\
Ainsi la loi conditionnelle de ( \(T_{1}^{\prime}, T_{2}^{\prime}, \ldots, T_{k}^{\prime}\) ) sachant \(\left[T_{1}=e_{k+1}\right]\) est uniforme.\\
B. Dans un programme écrit en langage Pascal on fait les déclarations suivantes :

\begin{verbatim}
const n = «entier naturel non nul fixé par l'utilisateur» ;
type tableau = array [1..n] of integer;
\end{verbatim}

Soit \(T\) une variable de type tableau qu'on suppose constituée d'éléments distincts. Si deb et fin sont deux entiers tels que \(1 \leqslant d e b<f i n \leqslant n\) on dira qu'un élément \(T[k]\) de la liste \((T[d e b], T[d e b+1], \ldots, T[f i n])\) est à sa place dans le sous-tableau \([T[d e b], \ldots, T[f i n]]\) si les éléments \(T[d e b], T[d e b+1], \ldots, T[k-1]\) sont inférieurs à \(T[k]\) et si les éléments \(T[k+1], T[k+2], \ldots, T[f i n]\) sont supérieurs à \(T[k]\) (bien sûr, si \(k=d e b\) ou \(k=f i n\), une seule de ces conditions subsiste).\\
Ainsi, si \(n=4\) et \(T=[3,1,7,5]\) alors \(T[3](=7)\) est à sa place dans le sous-tableau \([T[1], T[2], T[3]](=[3,1,7])\) mais n'est pas à sa place dans le le sous-tableau \([T[2], T[3], T[4]](=[1,7,5])\).\\
On dira que le tableau \(T\) est trié si chacun de ses éléments est à sa place dans \(T\).\\
On suppose qu'on dispose d'une procédure (écrite en langage Pascal) dont l'en-tête est\\
Placer (var T : tableau ; deb, fin : integer ; var pl: integer);\\
qui ne fait rien si fin \(\leqslant d e b\) et qui, si \(1 \leqslant d e b<f i n \leqslant n\), effectue, à l'aide de ( \(f i n-d e b\) ) comparaisons, les opérations suivantes:\\
i) d'une part, elle ne modifie que le sous-tableau \([T[d e b], \ldots, T[f i n]]\) de sorte que les éléments de ce soustableau plus petits que \(T[d e b]\) "ont glissé" (sans permutation entre-eux) à gauche de \(T[d e b]\) et les éléments de ce sous-tableau plus grands que \(T[d e b]\) "ont glissé" (sans permutation entre-eux) à droite de \(T[d e b]\). Ainsi \(T\) [deb] se retrouve à sa place dans le sous-tableau modifié.\\
ii) d'autre part, elle met dans la variable \(p l\) l'indice \(i\) tel que \(T[i]\) reçoit, au cours de la procédure, la valeur qui était stockée dans \(T[\) deb \(]\) avant l'exécution de la procédure.

Par exemple, si \(T=[12,3,8,10,6,4,5]\) l'instruction \(\operatorname{Placer}(T, 3,6, p l)\) une fois exécutée aura changé \(T\) en \([12,3,6,4,8,10,5]\) et affecté la valeur 5 à la variable \(p l\), alors que l'instruction \(\operatorname{Placer}(T, 3,4, p l)\) aura laissé \(T\) inchangé et affecté la valeur 3 à la variable \(p l\).\\
Par ailleurs on considère la procédure suivante:

\begin{verbatim}
procedure Tri(varT:tableau;deb,fin: integer);
var pl: integer;
begin
    if fin > deb then begin Placer(T, deb, fin,pl);
            if pl > deb then Tri(T, deb,pl-1);
            if pl<fin then Tri(T,pl+1,fin);
        end ;
end ;
\end{verbatim}

\begin{enumerate}
  \item a) L'entier \(i\) étant compris entre 1 et \(n\), quel est l'effet sur la variable \(T\) de l'instruction \(\operatorname{Tri}(T, i, i)\) ?\\
b) Dans cette sous-question on suppose qu'initialement \(T=[2,9,6,1,5]\).
\end{enumerate}

Déterminer la «trace»de l'instruction \(\operatorname{Tri}(T, 1,5)\) en donnant la liste des procédures successives (avec les valeurs de leurs paramètres) qui sont effectuées et en indiquant à chaque fois les affectations des variables pl et \(T\).\\
c) Expliquer succinctement l'effet et le principe de fonctionnement de la procédure Tri en indiquant, en particulier, pourquoi l'algorithme s'arrête.\\
2) On se place à nouveau dans le contexte probabiliste de la sous-partie \(\mathbf{A}\) et, si \(\sigma\) est une permutation de \(E\), on affecte la valeur \(\left[\sigma\left(e_{1}\right), \sigma\left(e_{2}\right), \ldots \sigma\left(e_{n}\right)\right]\) à la variable \(T\) de type tableau, i.e. \(T[1]:=\sigma\left(e_{1}\right), T[2]:=\sigma\left(e_{2}\right), \ldots\), \(T[n]:=\sigma\left(e_{n}\right)\). On note \(X_{n}(\sigma)\) le nombre de comparaisons faites lors des différentes exécutions de la procédure Placer (et seulement au cours de celles-ci) quand on effectue la procédure \(\operatorname{Tr} i(T, 1, n)\).\\
a) À l'aide de la sous-partie \(\mathbf{A}\), montrer que la suite de variables aléatoires \(\left(X_{n}\right)_{n \in \mathbb{N}^{*}}\) vérifie les hypothèses de II.B. En déduire un équivalent de l'espérance de \(X_{n}\) lorsque l'entier naturel \(n\) tend vers l'infini.\\
b) Dans le cas où \(E=\{1,2, \ldots, n\}\), donner (en le commentant de manière succincte) un exemple de tableau nécessitant \(\frac{n(n-1)}{2}\) comparaisons pour être trié.\\
c) Dans le cas où \(E=\{1,2, \ldots, 7\}\), donner de même un exemple de tableau nécessitant 10 comparaisons pour être trié.\\
d) Déterminer une suite d'entiers \(n\) pour lesquels, dans le cas où \(E=\{1,2, \ldots, n\}\), il existe un tableau d'éléments nécessitant \(g(n+1)\) comparaisons pour être trié.


\end{document}