%!TEX encoding = UTF-8 Unicode \documentclass[10pt]{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} \usepackage{fancybox} \usepackage{graphicx} \usepackage{tabularx} \usepackage[normalem]{ulem} \usepackage{pifont} \usepackage{textcomp} \newcommand{\euro}{\eurologo} %Merci à J. Decorsière pour le sujet %Tapuscrit : Denis Vergès relu par François Hache \usepackage{pst-plot,pst-text,pst-node,pst-tree} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\D}{\mathbb{D}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\C}{\mathbb{C}} \setlength{\textheight}{23,5cm} \newcommand{\vect}[1]{\mathchoice% {\overrightarrow{\displaystyle\mathstrut#1\,\,}}% {\overrightarrow{\textstyle\mathstrut#1\,\,}}% {\overrightarrow{\scriptstyle\mathstrut#1\,\,}}% {\overrightarrow{\scriptscriptstyle\mathstrut#1\,\,}}} \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)$} \setlength{\voffset}{-1,5cm} \usepackage{fancyhdr} \usepackage{hyperref} \usepackage{fancyhdr} \hypersetup{% pdfauthor = {APMEP}, pdfsubject = {BTS SIO obligatoire}, pdftitle = {Polynésie - 12 mai 2016}, allbordercolors = white, pdfstartview=FitH} \usepackage[frenchb]{babel} \usepackage[np]{numprint} \begin{document} \setlength\parindent{0mm} \rhead{\textbf{A. P{}. M. E. P{}.}} \lhead{\small Brevet de technicien supérieur Polynésie} \lfoot{\small{Services informatiques aux organisations\\ épreuve obligatoire}} \rfoot{\small{12 mai 2016}} \renewcommand \footrulewidth{.2pt} \pagestyle{fancy} \thispagestyle{empty} \marginpar{\rotatebox{90}{\textbf{A. P{}. M. E. P{}.}}} \begin{center} {\Large \textbf{\decofourleft~Brevet de technicien supérieur Polynésie~\decofourright\\12 mai 2016 - Services informatiques aux organisations}} \vspace{0,25cm} \textbf{Épreuve obligatoire} \end{center} \vspace{0,25cm} {\large \textbf{Exercice 1 \hfill 8 points}} \bigskip Un administrateur réseau met en place une stratégie logique de maintenance en cinq étapes : A, B, C, D et E. Il a noté dans un tableau la dépendance immédiate des étapes les unes par rapport aux autres, en fonction de la logique d'enchainement des étapes. Par exemple, selon lui, il est logique d'enchainer immédiatement l'étape B après l'étape A, ou de répéter l'étape A si nécessaire, mais il n'est pas logique d'effectuer immédiatement les étapes C, D et E après l'étape A. \begin{center} \begin{tabularx}{0.95\linewidth}{|m{4cm}|*{5}{>{\centering \arraybackslash}X|}}\hline Étapes &A &B &C &D &E\\ \hline Étapes qui peuvent suivre immédiatement &A, B &B, C &D &C &A, D, E\\ \hline \end{tabularx} \end{center} \medskip \begin{enumerate} \item Dessiner le graphe orienté G de sommets A, B, C, D, E, dont les arêtes orientées sont données par le tableau des successeurs ci-dessus. \item Donner la matrice d'adjacence $M$ associée au graphe orienté G. \item Combien y a-t-il de chemins de longueur 2 d'origine E dans le graphe orienté G ? Justifier. \item Combien y a-t-il de chemins de longueur 2 d'extrémité finale C dans le graphe orienté G ? Justifier. \smallskip On donne les matrices suivantes : \[\small{M^3 = \begin{pmatrix}1 &3 &2 &1 &0\\0 &1 &2 &1 &0\\0 &0 &0 &1 &0\\0 &0 &1 &0 &0\\3 &3 &2 &2 &1\end{pmatrix}\quad M^4 = \begin{pmatrix} 1 &4 &4 &2 &0\\0 &1 &2 &2 &0\\0 &0 &1 &0 &0\\0 &0 &0 &1& 0\\4 &6 &5 &3 &1\end{pmatrix}\quad \text{et}\: M^5 = \begin{pmatrix} 1 &5 &6 &4 &0\\0 &1 &3 &2 &0\\0 &0 &0 &1 &0\\0 &0 &1 &0 &0\\5 &10 &9 &6 &1\end{pmatrix}.}\] \item Combien y a-t-il de circuits de longueur 4 dans le graphe? Justifier. \item On désigne par $\widehat{M}$ la matrice d'adjacence de la fermeture transitive du graphe orienté G. \begin{enumerate} \item Déterminer $\widehat{M}$. \item Dans la matrice $\widehat{M}$, interpréter la valeur du coefficient de la ligne 1 et colonne 4, et celui de la ligne 1 et colonne 5. \end{enumerate} \end{enumerate} \vspace{0,5cm} {\large \textbf{Exercice 2 \hfill 5 points}} \bigskip Un administrateur réseau gère le parc d'une petite entreprise qui comprend 9 ordinateurs. Chaque ordinateur possède une adresse de carte réseau, dite adresse MAC (Media Access Control) unique. Cette adresse est composée de 6 nombres entiers compris entre 0 et 255 séparés par des \og : \fg. Chacun des 6 nombres est codé en hexadécimal. \bigskip \textbf{Partie A} \medskip \begin{enumerate} \item Pourquoi un nombre de 0 à 255 est-il codé en binaire sur un octet ? \item En hexadécimal, avec combien de chiffres au maximum peut-on coder un entier de 0 à 255 ? Justifier. \item Un ordinateur a l'adresse MAC suivante : 00~:~FF~:~B4~:~A9~:~96~:~11. Traduire en binaire et en décimal le nombre d'écriture hexadécimale (B4)$_{16}$. \end{enumerate} \bigskip \textbf{Partie B} \medskip L'administrateur a assigné une adresse IP (Internet Protocol) à chaque ordinateur à l'aide d'un logiciel installé sur le serveur. Il obtient le tableau suivant: \begin{center} \begin{tabularx}{0.9\linewidth}{|*{3}{>{\centering \arraybackslash}X|}}\hline Adresse MAC& \No de l'ordinateur &Adresse IP\\ \hline 00~:~FF~:~B4~:~A9~:~96~:~11 &1 &172.16.0.21\\ \hline 00~:~FF~:~B4~:~B0~:~45~:~1A &2 &172.16.0.22\\ \hline 00~:~FF~:~B4~:~00~:~C5~:~DE &3 &172.16.0.23\\ \hline 00~:~EE~:~B5~:~01~:~32~:~C4 &4 &172.16.0.24\\ \hline 00~:~EE~:~B5~:~01~:~32~:~C5 &5 &172.16.0.25\\ \hline 00~:~EE~:~B5~:~01~:~32~:~C6 &6 &172.16.0.26\\ \hline 00~:~FF~:~B4~:~00~:~C5~:~DF &7 &172.16.0.27\\ \hline 00~:~FF~:~B4~:~00~:~02~:~98 &8 &172.16.0.28\\ \hline 00~:~EE~:~B5~:~01~:~34~:~CA &9 &172.16.0.29\\ \hline \end{tabularx} \end{center} On considère l'application $f$ qui, à un numéro d'ordinateur, associe la dernière partie de l'adresse IP. Cette dernière partie est un entier variant de 2 à 255. %\[f :\: \{1~;~21~;~31~;~41~;~51~;~61~;~71~;~81~;~9\} \longmapsto \{21~;~31~;~\ldots1~;~255\}.\] \[f :\: \left\lbrace 1~;~2~;~3~;~4~;~5~;~6~;~7~;~8~;~9 \rule{0pt}{9pt}\right\rbrace \longmapsto \left\lbrace 2~;~3~;~\ldots~;~255\rule{0pt}{9pt}\right\rbrace.\] Par exemple, $f(1) = 21$. \medskip \begin{enumerate} \item Justifier le fait que cette application est injective. \item Cette application est-elle surjective ? Justifier. \item À la suite d'une opération informatique, le poste dont l'adresse MAC est 00~:~FF~:~B4~:~00~:~C5~:~DF obtient l'adresse IP suivante : 172.16.0.23. Les autres postes gardent leur adresse IP précédente. On a alors une nouvelle application %$g : \:\{11~;~21~;~31~;~41~;~51~;~61~;~71~;~81~;~9\} \longmapsto \{21~;~31~;~\ldots1~;~255\}$. \[g : \:\left\lbrace 1~;~2~;~3~;~4~;~5~;~6~;~7~;~8~;~9\rule{0pt}{9pt}\right\rbrace \longmapsto \left\lbrace 2~;~3~;~\ldots~;~255\rule{0pt}{9pt}\right\rbrace.\] L'application $g$ est-elle injective ? Justifier. \end{enumerate} \vspace{0,5cm} {\large \textbf{Exercice 3 \hfill 7 points}} \bigskip Le jeu du Juniper Green ou jeu des diviseurs et multiples a été créé par Richard Porteous, enseignant à l'école de Juniper Green. Il se joue à deux. Une fois qu'on a fixé un entier $N > 1$, les deux joueurs choisissent alternativement un entier entre 1 et $N$ compris selon les règles suivantes : \setlength\parindent{8mm} \begin{itemize} \item[$\bullet~~$] le joueur 1 choisit un entier $n_1$ compris entre 1 et $N$ ; \item[$\bullet~~$]le joueur 2 choisit un entier $n_2$ compris entre 1 et $N$, multiple ou diviseur de $n_1$ qui n'a pas encore été joué ; \item[$\bullet~~$]le joueur 1 choisit un entier $n_3$ compris entre 1 et $N$, multiple ou diviseur de $n_2$, qui n'a pas encore été joué ; \item[$\bullet~~$]etc. \end{itemize} \setlength\parindent{0mm} \medskip Chaque entier entre 1 et $N$ ne peut apparaître au plus qu'une fois. Le perdant est celui qui ne peut plus jouer. Exemple avec $N = 20$ : \begin{center} \begin{tabularx}{\linewidth}{|l|*{10}{>{\centering \arraybackslash}X|c|}}\hline Joueur 1&6 & &9 & &2 & &4 & &1 & &perdu\\ \hline Joueur 2& &3 & &18 & &8 & &16 & &17 &\\ \hline \end{tabularx} \end{center} \setlength\parindent{8mm} \begin{itemize} \item[$\bullet~~$]le joueur 1 choisit 6 ; \item[$\bullet~~$]le joueur 2 choisit 3 qui divise 6.; \item[$\bullet~~$]le joueur 1 choisit 9 qui est bien un multiple de 3 ; \item[$\bullet~~$]etc. \end{itemize} \setlength\parindent{0mm} \smallskip À partir d'une partie, on crée un identifiant. L'identifiant est la suite d'entiers joués alternativement par les deux joueurs. Par exemple avec $N = 20$ et à partir de 6, l'identifiant créé peut être (6, 3, 9, 18, 2, 8, 4, 16, 1, 17). \medskip \begin{enumerate} \item \begin{enumerate} \item On choisit $N = 14$. Reproduire et compléter le tableau suivant avec une solution possible. \begin{center} \begin{tabularx}{\linewidth}{|l|*{6}{>{\centering \arraybackslash}X|}c|}\hline Joueur 1& 1&&6&&\ldots&&perdu\\ \hline Joueur 2&&2&&12&&\ldots&\\ \hline \end{tabularx} \end{center} \item Donner l'identifiant qui correspond à cette solution. \end{enumerate} \item Pour gagner la partie, les joueurs ont besoin de connaître les diviseurs et les multiples des différents nombres. Ils utilisent pour cela les décompositions en facteurs premiers. \begin{enumerate} \item Donner la décomposition en produit de facteurs premiers de \np{2262} en faisant apparaître la démarche. \item En déduire tous les diviseurs de \np{2262}. \end{enumerate} \item Lorsqu'un nombre premier apparaît dans la liste des nombres composant l'identifiant, quelles sont les possibilités pour le nombre suivant ? \item On suppose que $N = 14$. Montrer que si la liste commence par 11, alors il est possible que cette liste ne contienne que trois nombres. \item Pour que la partie dure plus longtemps, il faut éviter que l'identifiant soit trop court. On impose alors que le premier entier $q$ de la liste vérifie : \setlength\parindent{8mm} \begin{itemize} \item[$\bullet~~$]$q$ n'est pas un nombre premier ou \item[$\bullet~~$]$q$ vérifie $q \leqslant \sqrt{N}$. \end{itemize} \setlength\parindent{0mm} Sous ces conditions et pour $N = 14$, donner les valeurs possibles du premier entier $q$ de la liste. \end{enumerate} \end{document}