\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc}%ATTENTION codage en utf8 ! \usepackage{fourier} \usepackage[scaled=0.875]{helvet} \renewcommand{\ttdefault}{lmtt} \usepackage{amsmath,amssymb,makeidx,stmaryrd} \usepackage[normalem]{ulem} \usepackage{fancybox} \usepackage{tabularx} \usepackage{ulem} \usepackage{dcolumn} \usepackage{textcomp} \usepackage{stmaryrd} \usepackage{lscape} \newcommand{\euro}{\eurologo{}} \usepackage[dvips]{color} \usepackage{pstricks,pst-plot,pst-text,pst-tree} \usepackage[left=3.5cm, right=3.5cm, top=2cm, bottom=3cm]{geometry} \newcommand{\vect}[1]{\overrightarrow{\,\mathstrut#1\,}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\D}{\mathbb{D}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\C}{\mathbb{C}} \renewcommand{\theenumi}{\textbf{\arabic{enumi}}} \renewcommand{\labelenumi}{\textbf{\theenumi.}} \renewcommand{\theenumii}{\textbf{\alph{enumii}}} \renewcommand{\labelenumii}{\textbf{\theenumii.}} \def\Oij{$\left(\text{O},~\vect{\imath},~\vect{\jmath}\right)$} \def\Oijk{$\left(\text{O},~\vect{\imath},~\vect{\jmath},~\vect{k}\right)$} \def\Ouv{$\left(\text{O},~\vect{u},~\vect{v}\right)$} \usepackage{fancyhdr} \usepackage{hyperref} \hypersetup{% pdfauthor = {APMEP}, pdfsubject = {CAPES 2015 }, pdftitle = {Épreuve 2 avril 2015}, allbordercolors = white, pdfstartview=FitH} \usepackage[french]{babel} \usepackage[np]{numprint} \begin{document} \setlength\parindent{0mm} \rhead{\textbf{A. P{}. M. E. P{}.}} \lhead{\small Épreuve 2} \lfoot{\small{CAPES externe 2015}} \rfoot{\small{}} \pagestyle{fancy} \thispagestyle{empty} \marginpar{\rotatebox{90}{\textbf{A. P{}. M. E. P{}.}}} \begin{center} {\Large \textbf{CAPES externe session 2015 Épreuve 2}} \vspace{0,5cm} {\Large \textbf{Problème \no 1}} \end{center} \vspace{0,5cm} \emph{Notations} On note $\N$ l'ensemble des entiers naturels, $\N*$ l'ensemble des entiers naturels non nuls et $\Z$ l'ensemble des entiers relatifs. \medskip Soient $p$ et $q$ deux entiers relatifs tels que $p \leqslant q$, on note $\llbracket p,~q\rrbracket$ l'ensemble des entiers relatifs $k$ tels que $p \leqslant k \leqslant q$. \medskip \textbf{Préambule} \medskip Ce problème a pour objet l'étude de deux méthodes de chiffrement, \medskip À chaque lettre de l'alphabet est associé Un unique entier compris entré 0 et 25 de la façon suivante : à la lettre A est associé 0, à la lettre B est associé 1, \ldots , à la lettre Z est associé 25. Cet entier est appelé rang de la lettre. \bigskip \textbf{Partie A. - Un chiffrement monographique} \medskip L'objectif de cette partie est de démontrer les théorèmes de Bézout, puis de Gauss, et de mettre en œuvre ces théorèmes dans le chiffrement proposé. \medskip \textbf{I.} Soient $a$ et $b$ des entiers relatifs non nuls. \begin{enumerate} \item Montrer que s'il existe des entiers relatifs $u$ et $v$ tels que $au + bu = 1$, alors $a$ et $b$ sont premiers entre eux. \item On veut à présent prouver que la réciproque de cette propriété est vraie. On suppose que $a$ et $b$ sont premiers entre eux et on considère l'ensemble $\mathcal{E}$ des entiers relatifs de la forme $au + bu$ où $u$ et $v$ sont des entiers relatifs. \begin{enumerate} \item Montrer que l'ensemble $\mathcal{E} \cap \N^{*}$ admet un plus petit élément, que l'on notera $n_0$. \item Démontrer que le reste de la division euclidienne de $a$ (respectivement $b$) par $n_0$ vaut $0$. \item Conclure. \end{enumerate} \item Énoncer le théorème ainsi démontré. \end{enumerate} \textbf{II.} À l'aide du théorème précédent, démontrer que, pour tous les entiers relatifs non nuls $a,\: b$ et $c$, si $a$ divise $bc$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$. \textbf{III.} Chiffrement lettre à lettre \begin{enumerate} \item Un exemple. -- Dans cette question, on décide de coder chaque lettre d'un mot par un nombre $y$ défini comme suit : \emph{si $x$ est le rang de la lettre à coder, $y$ est le reste de la division euclidienne de $58x$ par $369$}. \begin{enumerate} \item Coder le mot GAUSS. \item Proposer une activité de classe sur tableur permettant, à partir du codage des 26 lettres de l'alphabet de décoder le mot de 6 lettres qui se cache derrière la suite de nombres : \[290\quad 232\quad 248\quad 327\quad 0\quad 364\] (Dans cette question, le décodage effectif n'est pas demandé; il le sera à la question \textbf{III. 3. c.}) \end{enumerate} \item Principe général du chiffrement lettre à lettre. -- On se donne un couple d'entiers naturels $(n,~e)$ vérifiant les conditions suivantes : \setlength\parindent{5mm} \begin{itemize} \item[$\bullet~~$] L'entier $n$ est supérieur ou égal à 26. \item[$\bullet~~$] Les entiers $n$ et $e$ sont premiers entre eux. \end{itemize} \setlength\parindent{0mm} Chaque lettre est alors codée de la façon suivante : \emph{si $x$ est le rang de la lettre à coder, $y$ est le reste de la division euclidienne de $ex$ par $n$}. \begin{enumerate} \item Démontrer qu'il existe un entier naturel $f$ tel que $fe \equiv 1\:\: (\text{mod}\: n)$. \item Démontrer que la connaissance de $f$ permet de retrouver $x$ à partir de $y$. On dit que $f$ est une clé de décodage associée à la clé de codage $(n,~e)$. \end{enumerate} \item Un procédé de construction d'une clé de codage et d'une clé de décodage associée : \setlength\parindent{5mm} \begin{itemize} \item[$\bullet~~$]On choisit quatre entiers naturels $a,\: b,\: c,$ et $d$ supérieurs ou égaux à 3. \item[$\bullet~~$]On pose : $M = ab -1,\: e = cM + a,\: f = dM + b$ et $n = \dfrac{ef - 1}{M}$. \end{itemize} \setlength\parindent{0mm} \begin{enumerate} \item Vérifier que $(n,~e)$ est une clé de codage et que $f$ est une clé de décodage associée. \item Calculer $n,\: e$, et $f$ lorsque $a = 3,\: b = 4,\: c = 5$ et $d = 6$. \item Un mot de 6 lettres a été codé à l'aide de la clé définie à la question précédente : \[290\quad 232\quad 248\quad 327\quad 0\quad 364\] Décoder ce mot. \end{enumerate} \item Ensemble des clés de décodage associées à une clé de codage donnée. -- On revient au cas général où $n$ est un entier naturel supérieur ou égal à 26 et e un entier naturel premier avec n et on se propose de déterminer l'ensemble des couples $(u,~v)$ d'entiers relatifs tels que $nu + ev = 1$. L'algorithme d'Euclide, qui permet de déterminer le PGCD de deux entiers naturels non nuls, assure l'existence d'un entier naturel $N$ strictement supérieur à 1 et de deux suites finies $\left(r_k\right)_{k \in \llbracket 1,~N \rrbracket}$ et $\left(q_k\right)_{k \in \llbracket 1,~N \rrbracket}$ telles que : \setlength\parindent{5mm} \begin{itemize} \item[$\bullet~~$]La suite $\left(r_k\right)_{k \in \llbracket 1,~N \rrbracket}$ est strictement décroissante. \item[$\bullet~~$]$r_0 = n,\: r_1 = e$ et $r_{N+1} = 0$. \item[$\bullet~~$]$\forall k \in \llbracket 1,~N\rrbracket,\: r_{k-1} = r_kq_k + r_{k+1}$. \end{itemize} \setlength\parindent{0mm} \begin{enumerate} \item Que vaut $r_N$ ? \item Démontrer qu'il existe deux suites d'entiers relatifs $\left(u_k\right)_{k \in \llbracket 0,~N \rrbracket}$ et $\left(v_k\right)_{k \in \llbracket 0,~N \rrbracket}$ vérifiant, pour tout $k \in \llbracket 0,~N \rrbracket$, \[r_k = nu_k +ev_k.\] \item En déduire une clé de décodage associée à la clé de codage $(n,~e)$. \item On met en oeuvre cette méthode à l'aide d'un tableur à partir de la clé de codage (369,~58) : \begin{center} \begin{tabularx}{0.8\linewidth}{|c|*{4}{>{\centering \arraybackslash}X|}}\hline &A&B&C&D\\ \hline 1&$r$&$q$&$u$&$v$\\ \hline 2&369&&1 &0\\ \hline 3&58&6&0&1\\ \hline 4&21&2&1&$- 6$\\ \hline 5&16&1&$- 2$&13\\ \hline \end{tabularx} \end{center} Quelle formule a-t-on saisie dans la cellule C4 pour que, tirée en bas et à droite, elle permette de déterminer les valeurs des termes des deux suites $\left(u_k\right)$ et $\left(v_k\right)$ ? \item Déterminer un couple $(u,~v)$ d'entiers relatifs tels que 369u + 58v = l et une clé de décodage associée à la clé de codage (369,~58). \item Déterminer l'ensemble des couples $(u,~ v)$ d'entiers relatifs tels que $369u + 58v = 1$ et l'ensemble des clés de décodage associées à la clé de codage (369,~58). \end{enumerate} \end{enumerate} \bigskip \textbf{Partie B. - Chiffrement de Hill} \medskip L'objectif de cette partie est de retrouver quelques résultats sur les matrices carrées d'ordre 2 à coefficients réels, puis de les appliquer au chiffrement de Hill. \medskip La matrice nulle d'ordre 2 est notée $O_2$ et la matrice unité d'ordre 2 est notée $I_2$. \medskip Pour tout entier naturel n non nul, si P et Q sont deux matrices carrées d'ordre 2 dont les coefficients respectifs $p_{i,~j}$ et $q_{i,~j}$ appartiennent à $\Z$, on dit qu'elles sont congrues modulo $n$ et on note $P \equiv Q (\text{mod}\: n)$ lorsque \[\forall (i,~j) \in \{1,~2\}, \quad p_{i,~j} \equiv q_{i,~j} (\text{mod}\: n).\] De même, on dit que les vecteurs colonnes à coefficients dans $Z$ \[X = \begin{pmatrix}x\\y\end{pmatrix}\quad \text{et}\quad X' = \begin{pmatrix}x'\\y'\end{pmatrix}\] sont congrus modulo $n$ et on note $X \equiv X' (\text{mod}\: n)$ lorsque $x \equiv x' (\text{mod} \:n)$ et $y \equiv y'(\text{mod}\: n)$. Dans toute cette partie, la matrice $A$ est définie par $A = \begin{pmatrix}a &b\\ c&d\end{pmatrix}$ où $a,\: b,\: c$ et $d$ désignent quatre réels. \textbf{I. Questions de cours} \begin{enumerate} \item Donner la définition d'une matrice inversible et démontrer l'unicité de son inverse. \item Établir que $A^2 - (a + d)A + (ad - bc)I_2 = O_2$. \item Démontrer que la matrice $A$ est inversible si et seulement si $ad - bc \ne 0$. \end{enumerate} \textbf{II.} Dans cette question, on suppose que $a,\: b,\: c$ et $d$ sont des entiers relatifs. \begin{enumerate} \item Donner un exemple de matrice inversible à coefficients dans $\Z$, mais dont l'inverse n'a pas tous ses coefficients dans $\Z$. \item Énoncer une condition suffisante pour que la matrice $A$ soit inversible et que son inverse $A^{-1}$ soit à coefficients dans $\Z$. \item Quelle notion mathématique (qui ne figure pas dans les programmes de lycée) permet de prouver que cette condition est nécessaire ? Proposer une démonstration du résultat. \end{enumerate} \textbf{III.} La méthode étudiée ci-après utilise un chiffrement par blocs de 2 lettres pour coder un mot comportant un nombre pair de lettres : \setlength\parindent{5mm} \begin{itemize} \item[$\bullet~~$]On choisit quatre entiers naturels non nuls $a,\: b,\: c$ et $d$. \item[$\bullet~~$]On note $x$ le rang de la première lettre du bloc et $y$ le rang de la deuxième lettre du bloc. \item[$\bullet~~$]On définit les entiers $x'$ et $y'$ de la manière suivante : \[(S)\quad \left\{\begin{array}{l c l} x'& =&ax + by\\ y'& =&cx + dy \end{array}\right.\] \item[$\bullet~~$]Le rang de la première lettre du bloc codé est le reste modulo 26 de $x'$ ; le rang de la deuxième lettre du bloc codé est le reste modulo 26 de $y'$. \end{itemize} \setlength\parindent{0mm} Un tel chiffrement est dit digraphique. \medskip \begin{enumerate} \item Traduire le système (5) par une relation matricielle à l'aide de la matrice A qui est appelée matrice de codage. \item On donne : $a = 4,\: b = 3,\: c = 5$ et $d = 4$. \begin{enumerate} \item Coder le mot BEZOUT. \item En détaillant les étapes, décoder le mot suivant : \[S\quad F\quad X\quad M\quad O\quad J\] \end{enumerate} \item On donne à présent a = 3, b = 2, c = 1 et d = 3. On souhaite décoder le mot suivant : \[A\quad K\quad X\quad O\quad U\quad E\quad V\quad H\quad D\quad L\] \begin{enumerate} \item Démontrer qu'il existe un unique entier $u$ compris entre 0 et 2.5 tel que \[7u \equiv 1 \quad (\text{mod} \:26).\] \item On note $A$ la matrice de codage associée aux entiers $a,\: b,\: c$ et $d$. Déterminer une matrice $B$, à coefficients entiers relatifs, telle que $uBA \equiv I_2\:\: (\text{mod}\: 26)$. \item Décoder le mot en détaillant la démarche pour le premier bloc de deux lettres. \end{enumerate} \item À quelle condition sur $a,\: b,\: c$ et $d$ peut-on décoder tout mot comportant un nombre pair de lettres ? \end{enumerate} \vfill \begin{flushright}\textbf{Tournez la page S. V. P.}\end{flushright} \newpage \begin{center} \textbf{\large Problème \no 2} \end{center} Notations On note $\N$ l'ensemble des entiers naturels et $\N^{*}$ l'ensemble des entiers naturels non nuls. \medskip Soient $p$ et $q$ deux entiers relatifs tels que $p \leqslant q$, on note $\llbracket p,~ q\rrbracket$ l'ensemble des entiers relatifs $k$ tels que $p \leqslant k \leqslant q$. \medskip \textbf{Partie A} \medskip Une urne contient des boules rouges et des boules noires. On désigne par $n$ un entier naturel non nul et on considère l'expérience aléatoire consistant à effectuer $n$ tirages avec remise. On attribue à chaque tirage d'une boule noire (échec) la valeur $0$ et à chaque tirage d'une boule rouge (succès) la valeur 1. On peut modéliser cette expérience à l'aide d'un arbre comportant $2^n$ chemins. Ces chemins sont des $n$-uplets dont chaque composante appartient à l'ensemble $\{0,~ 1\}$. Par exemple, si $n = 4$, un des $2^4 = 16$ chemins est (0,~0,~1,~0). \medskip \textbf{I.} On suppose dans cette question que $n = 4$. \medskip \begin{enumerate} \item Écrire la liste des 16 chemins. \item Parmi ces chemins, combien y en a-t-il qui contiennent exactement 2 fois l'élément 1 ? \item Parmi les chemins contenant exactement 2 fois l'élément l, combien yen a-t-il contenant 1 à la première place ? À la deuxième place ? À la troisième place ? À la quatrième place ? \end{enumerate} \textbf{II.} On revient au cas général où $n \in \N^{*}$ et on se donne $k \in \llbracket 0,~ n\rrbracket$. \emph{Dans les questions $II. 1, II. 2$ et $II. 3$, pour tout entier $p \in \llbracket 0,~ n\rrbracket$, l'entier $\binom{n}{p}$ est défini comme au lycée : il s'agit donc du nombre de chemins de l'arbre correspondant à $n$ tirages et réalisant exactement $p$ succès. En particulier ; on n'aura pas recours dans ces trois questions à l'expression des coefficients binomiaux à l'aide de factorielles.} \medskip \begin{enumerate} \item Démontrer que $\displaystyle\binom{n}{k} = \displaystyle\binom{n}{n - k}$. \item On suppose dans cette question que $k \ne 0$. En exprimant de deux manières différentes le nombre de $(n + 1)$-uplets contenant $k$ fois l'élément 1, démontrer que \[\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}.\] \item Pour $1 \leqslant k \leqslant n$, on se propose de démontrer l'égalité \[k\binom{n}{k} = n\binom{n-1}{k-1}.\] On considère une matrice $A$ à $n$ colonnes dont chacune des $\binom{n}{k}$ lignes est l'un des chemins conduisant à $k$ succès et $n - k$ échecs. \begin{enumerate} \item Calculer la somme des éléments d'une ligne de la matrice. \item Soit $j \in \llbracket 1,~n\rrbracket$. Que représente la somme des éléments de la $j$-ème colonne de la matrice $A$ ? \item Conclure. \end{enumerate} \item Dans l'enseignement supérieur, on définit, pour tout entier $p \in \llbracket 0,~n\rrbracket$, l'entier $\binom{n}{p}$ comme étant le nombre de parties à $p$ éléments d'un ensemble à $n$ éléments. \begin{enumerate} \item Justifier la cohérence de cette définition avec celle qui est donnée au lycée. \item Démontrer que $\displaystyle\binom{n}{k} = \dfrac{n!}{k!(n - k)!}$. \item Retrouver par le calcul les résultats des questions \textbf{II. 2} et \textbf{II. 3}. \end{enumerate} \end{enumerate} \textbf{III.} On note $\theta$ la proportion de boules rouges dans l'urne et $X$ la variable aléatoire égale au nombre de boules rouges (succès) obtenues à l'issue des $n$ tirages. Identifier la loi de $X$ et, en utilisant la question \textbf{II. 3} ainsi que la formule du binôme, calculer son espérance. \textbf{Partie B} \medskip Un point se déplace sur un axe gradué. Il se trouve au départ à l'origine et son déplacement à chaque étape est déterminé par le résultat du lancer d'une pièce équilibrée : \setlength\parindent{5mm} \begin{itemize} \item[$\bullet~~$] Si on obtient pile, son abscisse augmente de 1. \item[$\bullet~~$] Si on obtient face, son abscisse diminue de 1. \end{itemize} \setlength\parindent{0mm} On note $D_n$ le nombre de fois où la pièce est tombée sur pile au cours des $n$ premiers lancers et $X_n$ l'abscisse du point à l'issue du $n$-ième lancer. \medskip \textbf{I.} \begin{enumerate} \item Donner la loi de la variable aléatoire $X_n$. \item Reconnaître la loi de la variable aléatoire $D_n$. \item Exprimer $X_n$ à l'aide de $D_n$. \item Calculer l'espérance de $X_n$. Interpréter le résultat. \end{enumerate} \textbf{II.} \begin{enumerate} \item Que vaut la probabilité $P\left(X_n = 0\right)$ lorsque $n$ est impair? \item Calculer la probabilité $P\left(X_{2n} = 0\right)$. \end{enumerate} \textbf{III.} \begin{enumerate} \item L'algorithme suivant utilise une fonction \texttt{alea}() qui renvoie à chaque appel un nombre aléatoire selon la loi uniforme sur l'intervalle [0~;~1] : \begin{center} \begin{tabular}{>{\texttt}l} entrer($n$)\\ $x \leftrightarrow 0$\\ pour $k$ allant de $1$ à $n$\\ \hspace{1cm}si \texttt{alea}() $> 0,5$ alors\\ \hspace{1.7cm} $x\leftrightarrow x+1$\\ \hspace{1cm}sinon\\ \hspace{1.7cm} $x\leftrightarrow x - 1$\\ \hspace{1cm}finsi\\ finpour\\ retourner$(x)$\\ \end{tabular} \end{center} À quoi correspond la valeur renvoyée par cet algorithme ? \item Écrire un deuxième algorithme, obtenu en modifiant l'algorithme donné, de façon à ce qu'il renvoie le nombre de passages à l'origine à l'issue de $n$ lancers. \item Écrire un troisième algorithme, obtenu en modifiant l'algorithme donné, de façon à ce qu'il renvoie la fréquence d'apparition de l'événement $X_n = 0$ au cours de la répétition de \np{1000} séries de $n$ lancers. \item Comment un professeur peut-il exploiter ces algorithmes devant une classe ? \end{enumerate} \textbf{IV.} Soit $n \in \N^{*}$. Dans cette question, on s'intéresse à la position du point à l'issue de $2n$ lancers et au nombre de passages à l'origine entre le premier et le $2n$-ième lancer. \medskip \begin{enumerate} \item Expliquer pourquoi, à l'issue de ces $2n$ lancers, l'abscisse du point ne peut être qu'un entier relatif pair compris entre $-2n$ et $2n$. \item Soit $k \in \llbracket 0~;~\rrbracket$. Calculer la probabilité qu'à l'issue de ces $2n$ lancers, l'abscisse du point soit égale à $2k$. \item On note $C_n$ la variable aléatoire égale au nombre de passages à l'origine entre le premier et le $2n$-ième lancer. Calculer l'espérance E$\left(C_n\right)$ de la variable aléatoire $C_n$ et montrer par récurrence sur $n$ que, pour tout entier $n \geqslant 1$, \[\text{E}\left(C_n\right) = \dfrac{2n + 1}{4^n}\binom{2n}{n} - 1.\] On pourra utiliser la variable aléatoire $\Omega_k$ égale à 1 si l'abscisse du point à l'issue du $k$-ième lancer est nulle et égale à $0$ sinon. \end{enumerate} \end{document}