\documentclass[10pt]{article} \usepackage[french]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{graphicx} \usepackage[export]{adjustbox} \graphicspath{ {./images/} } \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage[version=4]{mhchem} \usepackage{stmaryrd} \usepackage{caption} \usepackage{bbold} \usepackage{mathrsfs} \begin{document} \captionsetup{singlelinecheck=false} \section*{Cricome} \section*{CONCOURS D'ADMISSION 2023} \includegraphics[max width=\textwidth, alt={}, center]{f05620b4-6f5d-4233-8de2-2e1cb5548d8f-1_646_379_762_199}\\ prepa\\ \includegraphics[max width=\textwidth, alt={}, center]{f05620b4-6f5d-4233-8de2-2e1cb5548d8f-1_70_241_657_898} \section*{Mathématiques Appliquées Série ECG} Lundi 17 avril 2023 de 8h00 à 12h00\\ Durée : 4 heures Candidats bénéficiant de la mesure "Tiers-temps " : 8h00-13h20 L'énoncé comporte 6 pages. \section*{CONSIGNES} Tous les feuillets doivent être identifiables et numérotés par le candidat.\\ Aucun document n'est permis, aucun instrument de calcul n'est autorisé.\\ Conformément au règlement du concours, l'usage d'appareils communiquants ou connectés est formellement interdit durant l'épreuve.\\ Les candidats sont invités à soigner la présentation de leur copie, à mettre en évidence les principaux résultats, à respecter les notations de l'énoncé et à donner des démonstrations complètes - mais brèves - de leurs affirmations.\\ 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.\\ Ce document est la propriété d'ECRICOME, le candidat est autorisé à le conserver à l'issue de l'épreuve.\\ Le candidat dispose d'une annexe Python en page 7. Dans les questions faisant intervenir des instructions en langage Python, on prendra soin d'importer les bibliothèques nécessaires lors de leur première utilisation.\\ Pour traiter les questions d'informatique, les candidats sont invités à se référer à l'annexe fournie en fin de sujet. Its ne sont pas limités à l'utilisation des seules fonctions mentionnées dans cette annexe. \section*{Exercice 1} Soit \(n\) un entier naturel non nul.\\ Une urne contient \(n\) boules indiscernables au toucher et numérotées de 1 à \(n\). On tire une boule au hasard dans l'urne. Si cette boule tirée porte le numéro \(k\), on place alors dans une seconde urne toutes les boules suivantes : une boule numérotée 1 , deux boules numérotées 2 , et plus généralement pour tout \(j \in \llbracket 1, k \rrbracket, j\) boules numérotées \(j\), jusqu'à \(k\) boules numérotées \(k\). Les boules de cette deuxième urne sont aussi indiscernables au toucher. On effectue alors un tirage au hasard d'une boule dans cette seconde urne.\\ Et on note \(X\) la variable aléatoire égale au numéro de la première boule tirée et on note \(Y\) la variable aléatoire égale au numéro de la deuxième boule tirée. \begin{enumerate} \item Reconnaitre la loi de \(X\) et donner son espérance et sa variance. \item Déterminer \(Y(\Omega)\). \item Soit \(k \in[1, n]\).\\ (a) On suppose que l'événement \([X=k]\) est réalisé. \end{enumerate} Déterminer, en fonction de \(k\), le nombre total de boules présentes dans la seconde urne.\\ (b) Pour tout entier \(j\) de \(\llbracket 1, n \rrbracket\), exprimer \(P_{[X=k]}(Y=j)\) en fonction de \(k\) et \(j\). On distinguera les cas \(j \leqslant k\) ou \(j \geqslant k+1\).\\ 4. (a) Déterminer deux réels \(a\) et \(b\) tels que, pour tout entier naturel \(k\) non nul, \[ \frac{1}{k(k+1)}=\frac{a}{k}+\frac{b}{k+1} . \] (b) En déduire que, pour tout élément \(j\) de \(Y(\Omega)\), \[ P(Y=j)=\frac{2(n+1-j)}{n(n+1)} . \] \begin{enumerate} \setcounter{enumi}{4} \item Justifier que \(Y\) admet une espérance et montrer que \(E(Y)=\frac{n+2}{3}\). \item Les variables aléatoires \(X\) et \(Y\) sont-elles indépendantes? \item (a) Montrer que \(E(X Y)=\frac{(n+1)(4 n+5)}{18}\).\\ (b) En déduire que \(\operatorname{Cov}(X, Y)=\frac{n^{2}-1}{18}\). \item (a) Écrire une fonction en langage Python, nommée seconde\_urne, prenant en entrée un entier naturel k non nul, et renvoyant une liste contenant 1 élément valant 1,2 éléments valant \(2, \ldots, j\) éléments valant \(j, \ldots\), jusqu'à \(k\) éléments valant \(k\).\\ Par exemple, l'appel de seconde\_urne (4) renverra \([1,2,2,3,3,3,4,4,4,4]\).\\ (b) Recopier et compléter la fonction en langage Python suivante pour qu'elle prenne en entrée un entier naturel n non nul, et qu'elle renvoie une réalisation du couple de variables aléatoires ( \(X, Y\) ). \end{enumerate} \begin{verbatim} import numpy.random as rd def simul_XY(n): X = urne2 = seconde_urne(__.__) nb = len(urne2) i = rd.randint(0, nb) Y = __---- return X, Y \end{verbatim} (c) On considère la fonction en langage Python suivante, prenant en entrée un entier naturel n non nul. \begin{verbatim} def fonction(n): liste = [0]*n for i in range(10000): j = simul_XY(n)[1] liste[j-1] = liste[j-1] + 1/10000 return liste \end{verbatim} Quelles valeurs les éléments de la liste renvoyée permettent-ils d'estimer?\\ 9. Dans toute cette question, on suppose \(n=20\). On simule 50 réalisations du couple de variables aléatoires \((X, Y)\) à l'aide de la fonction simul\_XY définie à la question 8b). On représente alors les valeurs obtenues sous forme d'un nuage de points, où les valeurs des réalisations de \(X\) sont représentées en abscisse et les valeurs des réalisations de \(Y\) en ordonnée. On trace également, sur la même figure, la droite de régression linéaire associée à ce nuage de points.\\ (a) Déterminer par un calcul une valeur approchée des coordonnées du point moyen du nuage de points. Quel théorème de probabilités permet de justifier cette approximation?\\ (b) Parmi les figures représentées ci-dessous, en justifiant soigneusement votre réponse, indiquer celle qui correspond au nuage de points et à la droite de régression linéaire étudiés.\\ \includegraphics[max width=\textwidth, alt={}, center]{f05620b4-6f5d-4233-8de2-2e1cb5548d8f-3_455_556_1142_431}\\ \includegraphics[max width=\textwidth, alt={}, center]{f05620b4-6f5d-4233-8de2-2e1cb5548d8f-3_454_557_1138_1100}\\ \includegraphics[max width=\textwidth, alt={}, center]{f05620b4-6f5d-4233-8de2-2e1cb5548d8f-3_450_549_1662_433} \begin{figure}[h] \begin{center} \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{f05620b4-6f5d-4233-8de2-2e1cb5548d8f-3_433_557_1675_1100} \end{center} \end{figure} \section*{Exercice 2} On considère la fonction \(f\) définie sur \(] 0,+\infty[\) par : \[ \forall x \in|0,+\infty|, \quad f(x)=\frac{e^{\frac{\pi}{2}}}{\sqrt{x}} \] On rappelle que \(2\varepsilon\), on répète les opérations suivantes. \end{itemize} On considère le milieu \(c\) du segment \([a, b]\). Par monotonie de \(f\) sur \(] 0,1\) ], en distinguant les cas \(f(c) \leqslant n\) et \(f(c)>n\), on peut déterminer si \(u_{n}\) appartient à l'intervalle \([a, c]\) ou à l'intervalle \([c, b]\).\\ Selon le cas, on met alors à jour la valeur de \(a\) ou de \(b\) pour se restreindre au sous-intervalle approprié. \begin{itemize} \item On renvoie finalement la valeur \(\frac{a+b}{2}\), qui constitue une valeur approchée de \(u_{n}\) à \(\varepsilon\) près. \end{itemize} Recopier et compléter la fonction en langage Python suivante, prenant en entrée un entier n supérieur ou égal à 2 et un réel strictement positif eps, et renvoyant une valeur approchée de \(u_{n}\) à eps près en appliquant l'algorithme décrit ci-dessus. \begin{verbatim} import numpy as np def approx_u(n, eps): a = 0 b = 1 while _-_-------: c = (a+b)/2 if np.exp(c/2)/np.sqrt(c) < n: else else: return (a+b)/2 \end{verbatim} (b) Écrire une fonction en langage Python, nommée sp , prenant en entrée un entier N supérieur ou égal à 2 et un réel strictement positif eps et renvoyant une valeur approchée de la somme \(\sum_{n=2}^{N} u_{n}\) à eps près.\\ On pourra faire appel à la fonction approx\_u définie à la question précédente. Exercice 3 \section*{Partie 1} On considère la matrice \(A=\left(\begin{array}{cccc}1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1\end{array}\right)\). On note \(f\) l'endomorphisme de \(\mathbb{R}^{4}\) représenté par la matrice \(A\) dans la base canonique \(\mathscr{C}=\left(e_{1}, e_{2}, e_{3}, e_{4}\right)\) de \(\mathbb{R}^{4}\). \begin{enumerate} \item On considère les vecteurs suivants de \(\mathbb{R}^{4}\) : \end{enumerate} \[ u_{1}=(-1,1,0,1), \quad u_{2}=(0,-1,1,0), \quad u_{3}=(0,1,1,0), \quad u_{4}=(1,0,0,1) . \] On note \(\mathscr{B}=\left(u_{1}, u_{2}, u_{3}, u_{4}\right)\).\\ (a) Montrer que \(\mathscr{B}\) est une base de \(\mathbb{R}^{4}\).\\ (b) Déterminer la matrice représentative de \(f\) dans la base \(\mathscr{B}\).\\ (c) En déduire une matrice \(P\) de \(\mathscr{M}_{4}(\mathbb{R})\) inversible et une matrice \(T\) de \(\mathscr{M}_{4}(\mathbb{R})\) triangulaire telles que \(A=P T P^{-1}\).\\ 2. (a) Calculer \(A^{2}\) et \(A^{3}\), puis vérifier que \(A^{3}=4 A^{2}-4 A\).\\ (b) Montrer par récurrence que, pour tout entier naturel \(n\) non nul, il existe deux réels \(a_{n}\) et \(b_{n}\) tels que \[ A^{n}=a_{n} A^{2}+b_{n} A . \] vérifiant, pour tout entier naturel \(n\) non nul, \(a_{n+1}=4 a_{n}+b_{n}\) et \(b_{n+1}=-4 a_{n}\).\\ 3. (a) Montrer que, pour tout entier naturel \(n\) non nul, \[ a_{n+2}=4 a_{n+1}-4 a_{n} . \] (b) Déterminer, pour tout entier naturel \(n\) non nul, une expression de \(a_{n}\) en fonction de \(n\).\\ (c) En déduire, pour tout entier naturel \(n\) non nul, une expression de \(b_{n}\) en fonction de \(n\).\\ 4. Montrer que, pour tout entier naturel \(n\) non nul, \[ A^{n}=\left(\begin{array}{cccc} 2^{n-1} & 0 & 0 & 2^{n-1} \\ (n+1) 2^{n-2} & 2^{n-1} & 2^{n-1} & (n-1) 2^{n-2} \\ (n+1) 2^{n-2} & 2^{n-1} & 2^{n-1} & (n-1) 2^{n-2} \\ 2^{n-1} & 0 & 0 & 2^{n-1} \end{array}\right) . \] \section*{Partie 2} Soient \(p\) un entier naturel non nul et \(G\) un graphe non pondéré orienté à \(p\) sommets. On note \(s_{0}, s_{1}, \ldots, s_{p-1}\) les sommets de \(G\).\\ 5. (a) Rappeler la définition de la matrice d'adjacence du graphe \(G\).\\ (b) Soient \(n\) un entier naturel non nul, \(i\) un entier de \(\llbracket 1, p \rrbracket\) et \(j\) un entier de \(\llbracket 1, p \rrbracket\). Rappeler sans justification l'interprétation du coefficient situé à la ligne \(i\) et à la colonne \(j\) dans la matrice \(M^{n}\), où \(M\) est la matrice d'adjacence du graphe \(G\).\\ 6. Dans cette question uniquement, on suppose que \(p=4\) et que la matrice d'adjacence du graphe \(G\) est la matrice \(A=\left(\begin{array}{llll}1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1\end{array}\right)\) étudiée dans la partie 1.\\ (a) Représenter les sommets et les arêtes du graphe \(G\) sous forme d'un diagramme.\\ (b) Le graphe \(G\) est-il connexe? Justifier votre réponse.\\ (c) Soit \(n\) un entier naturel non nul. Déterminer le nombre de chemins de longueur \(n\) menant du \(s_{3}\) au sommet \(s_{0}\).\\ 7. Dans cette question et les suivantes, on revient au cas général décrit au début de la partie 2. Soit \(s\) un sommet de \(G\). On dit que le sommet \(t\) est un voisin de \(s\) quand \(s \neq t\) et ( \(s, t\) ) est une arrête du graphe. Comme le graphe est orienté, si \(t\) est un voisin de \(s\), alors \(s\) n'est pas forcément un voisin de \(t\).\\ On appelle liste d'adjacence du graphe \(G\), une liste de \(p\) sous-listes telle que, pour tout entier \(k\) de \(\llbracket 0, p-1 \rrbracket\), la sous-liste située à la position \(k\) contient tous les numéros des sommets voisins de \(s_{k}\).\\ Par exemple, la liste d'adjacence du graphe étudié à la question 6 est : \[ L=[[0,3],[0,1,2],[0,1,2],[0,3]] \] Écrire une fonction en langage Python, nommée matrice\_vers\_liste, prenant en entrée la matrice d'adjacence A d'un graphe \(G\) (définie sous forme de liste de listes) et renvoyant la liste d'adjacence de \(G\).\\ 8. On cherche à écrire une fonction en langage Python permettant d'obtenir la longueur du plus court chemin menant d'un sommet de départ \(s_{i}\) à chaque sommet du graphe \(G\).\\ On souhaite pour cela appliquer un algorithme faisant intervenir les variables suivantes: \begin{itemize} \item Une liste distances à \(p\) éléments, où l'élément situé à la position \(k\) sera égal, à la fin de l'algorithme, à la longueur du plus court chemin menant du sommet de départ \(s_{i}\) au sommet \(s_{k}\). \item Une liste a\_explorer contenant tous les sommets restant à traiter. \item Une liste marques contenant tous les sommets déjà traités. \end{itemize} Nous donnons ci-dessous la description de l'algorithme : \begin{itemize} \item Initialisation des trois listes décrites ci-dessus : \item Initialement, chaque élément de la liste distances est égal à \(p\), à l'exception du sommet \(s_{i}\) auquel on affecte la distance 0 . \item La liste marques ne contient initialement que le numéro du sommet de départ \(s_{i}\), \item la liste a\_explorer ne contient initialement que le numéro du sommet de départ \(s_{i}\). \item Tant que la liste a\_explorer n'est pas vide, on répète les opérations suivantes : \item Nommer s le premier sommet de la liste a\_explorer, et le retirer de cette liste. \item Pour chaque voisin v du sommet \(\mathrm{s}:\) si v n'est pas dans la liste marques, on l'ajoute à la liste marques, on l'ajoute à la fin de la liste a\_explorer, et on lui affecte une distance égale à distances[s]+1.\\ (a) On considère le graphe orienté \(G\) étudié à la question 6 . \end{itemize} Donner la valeur de la liste distances à l'issue de l'exécution de l'algorithme décrit ci-dessus, lorsqu'on l'applique au graphe \(G\) en choisissant \(s_{1}\) comme sommet de départ.\\ (b) Recopier et compléter la fonction suivante, prenant en entrée la liste d'adjacence L du graphe \(G\) et le numéro i0 du sommet de départ \(s_{i}\), et renvoyant la liste distances après exécution de l'algorithme décrit ci-dessus. \begin{verbatim} def parcours(L, i0): p = len(L) distances = \end{verbatim} \(\_\_\_\_\) \begin{verbatim} distances[i0] = 0 a_explorer = \end{verbatim} \(\_\_\_\_\) \begin{verbatim} marques = ----------- while s = \end{verbatim} \begin{center} \includegraphics[max width=\textwidth, alt={}]{f05620b4-6f5d-4233-8de2-2e1cb5548d8f-6_24_140_1970_655} \end{center} \begin{verbatim} for v in __---------: if v not in marques: marques.append(v) ---------- ---------- return distances \end{verbatim} (c) Modifier la fonction précédente pour qu'elle renvoie la liste de tous les sommets \(s\) pour lesquels il existe un chemin menant du sommet de départ \(s_{i}\) au sommet \(s\). \section*{Annexe - Fonctions Python utiles} \section*{Manipulation de listes} On suppose que L désigne une liste à n éléments. \begin{itemize} \item L'opérateur de concaténation +, appliqué entre deux listes, renvoie la liste obtenue en plaçant les éléments de la seconde liste à la suite de ceux de la première liste.\\ Par exemple, \([1,2,5]+[4,3]\) renvoie la liste \([1,2,5,4,3]\). \item L'opérateur *, appliqué entre une liste L et un entier n , renvoie la liste obtenue en concaténant n fois la liste L avec elle-même.\\[0pt] Par exemple, [1, 4, 2] *3 renvoie la liste [1, 4, 2, 1, 4, 2, 1, 4, 2]. \item La fonction len prend en argument d'entrée une liste et renvoie le nombre d'éléments dans cette liste. \item La commande L.append(x) permet d'inclure l'élément \(x\) à la fin de la liste \(L\). \item Pour tout entier i entre 0 et \(n-1, \mathrm{~L}[\mathrm{i}]\) désigne l'élément d'indice i de la liste L (les indices commencent à 0 ). \item Pour tout entier i entre 0 et \(n-1\), la commande del L[i] retire de la liste L l'élément situé à la position i. Par exemple, à l'issue des instructions\\ \(\mathrm{L}=[5,4,8,1]\)\\[0pt] del L[1]\\ la liste L vaut \([5,8,1]\). \end{itemize} \section*{La librairie numpy} \begin{itemize} \item Exemple d'importation : import numpy as np. \item Les opérations \(+,-, *, /, * *\), lorsqu'elles sont possibles, peuvent être réalisées entre deux tableaux Numpy de dimensions compatibles et agissent alors coefficient par coefficient. \item Les fonctions np.sqrt (racine carrée), np.abs (valeur absolue), np.log (logarithme népérien) et np.exp (fonction exponentielle) s'appliquent à une quantité numérique ou à un tableau Numpy de nombres. Dans ce dernier cas, les fonctions sont appliquées à chaque élément du tableau donné en argument d'entrée. \end{itemize} La bibliothèque numpy.random \begin{itemize} \item Exemple d'importation : import numpy.random as rd. \item La fonction rd.random, appelée sans argument d'entrée, renvoie une réalisation aléatoire de la loi uniforme sur l'intervalle \([0,1[\). Il est également possible de spécifier les dimensions d'un tableau Numpy en argument d'entrée pour obtenir un tableau dont les coefficients sont des réalisations indépendantes de la loi uniforme sur \([0,1[\). \item La fonction rd.randint prend en entrée deux entiers \(n\) et \(p\) (avec \(p>n\) ) et renvoie une réalisation aléatoire de la loi uniforme discrète sur \(\llbracket n, p-1 \rrbracket\). \end{itemize} \end{document}