%!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 à Vincent Leroy pour le sujet
%Tapuscrit : Denis Vergès 
\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}}
\usepackage[left=3.5cm, right=3.5cm, top=3cm, bottom=3cm]{geometry}
\newcommand{\vect}[1]{\overrightarrow{\,\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)$}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{fancyhdr}
\hypersetup{%
pdfauthor = {APMEP},
pdfsubject = {BTS SIO obligatoire},
pdftitle = {Polynésie  - 11 mai 2015},
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{mai  2015}}
\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\\[5pt] 11  mai 2015 - Services informatiques aux organisations}}

\vspace{0,25cm}

\textbf{Épreuve obligatoire}
  
\end{center}

\vspace{0,25cm}

{\large \textbf{Exercice 1 \hfill 10 points}}

\bigskip

\textbf{Partie 1}

\medskip

Une entreprise européenne de vente de matériel informatique anticipe l'évolution des ventes de
claviers souples dans les années à venir. Elle souscrit le contrat suivant avec son fournisseur :

\smallskip

\setlength\parindent{8mm}
\begin{itemize}
\item l'entreprise s'engage à commander initialement 500~claviers, et à augmenter sa commande
de 100~unités par semestre (un semestre dure 6 mois) ;
\item de son côté, le fournisseur s'engage à vendre chaque clavier souple 9 euros au début du
contrat, et à multiplier ce prix par 0,95 chaque semestre.
\end{itemize}
\setlength\parindent{0mm}

\medskip

Au bout de $n$ semestres, $n$ étant un entier naturel quelconque, on note $u_n$ le nombre de claviers
souples achetés par l'entreprise, et $p_n$ le prix unitaire d'un clavier souple, exprimé en euro.

Ainsi, $u_0 = 500$ et $p_0 = 9$.

\medskip

\begin{enumerate}
\item 
	\begin{enumerate}
		\item Calculer $u_1$ et $u_2$.
		\item Déterminer la nature de la suite $\left(u_n\right)$ et exprimer $u_n$ en fonction de $n$.
	\end{enumerate}
\item  
	\begin{enumerate}
		\item Calculer $p_1$ et $p_2$ en arrondissant les résultats au centième.
		\item Déterminer la nature de la suite $\left(p_n\right)$ et exprimer $p_n$ en fonction de $n$.
	\end{enumerate}
\item  Déterminer le prix unitaire $p_n$ d'un clavier, arrondi au centime d'euro, lorsque l'entreprise en
commandera \np{1000}.
\item  L'entreprise et le fournisseur conviennent que le contrat sera rompu lorsque le prix unitaire d'un
clavier souple sera inférieur à 5~euros.
	
Déterminer le nombre d'années qui engagent l'entreprise et son fournisseur. Justifier.
\item  En honorant le contrat, l'entreprise dépense chaque semestre une somme, en euro, égale au
produit du nombre de claviers commandés par leur prix unitaire.
	
Déterminer la dépense de l'entreprise pour les 5~premières années, c'est-à-dire pour les
semestres numérotés de $0$ à $9$.
\end{enumerate}

\bigskip

\textbf{Partie 2}

\medskip

Le fournisseur doit livrer 5~entreprises. Le réseau de transport est représenté par le graphe orienté
donné ci-dessous où l'entrepôt du fournisseur est noté $F$, et les entreprises sont notées $A$, $B$, $C$, $D$, $E$.

\begin{center}
\psset{unit=0.6cm,arrowsize=3pt 3}

\begin{pspicture}(-0.5,-0.5)(8.5,4.5)
\cnodeput(0,4){C}{$C$}\cnodeput(4,4){B}{$B$}\cnodeput(8,4){A}{$A$}
\cnodeput(0,0){D}{$D$}\cnodeput(4,0){F}{$F$}\cnodeput(8,0){E}{$E$}
\ncarc{->}{C}{B}\ncarc{->}{B}{C}
\ncarc{->}{B}{A}
\ncarc{->}{C}{D}\ncarc{->}{D}{C}
\ncarc{->}{F}{B}\ncarc{->}{B}{F}
\ncarc{->}{F}{D}\ncarc{->}{E}{F}
\ncarc{->}{A}{E}\ncarc{->}{B}{A}
\ncarc{->}{F}{A}
\end{pspicture}
\end{center}

\begin{enumerate}
\item Écrire la matrice d'adjacence $M$ de ce graphe en considérant les sommets notés $A$, $B$, $C$, $D$, $E$, et $F$ dans cet ordre.
\item  Le fournisseur souhaite livrer chacune des entreprises. Il part de son entrepôt.
	\begin{enumerate}
		\item Existe-t-il un chemin hamiltonien d'origine $F$ dans ce graphe ? Si oui, citer un tel chemin.
		\item Interpréter le résultat relativement aux possibilités de livraison.
	\end{enumerate}
\item  On donne la matrice $M^3 = \begin{pmatrix}
1& 1& 0	& 1	& 0	&0\\
2& 0& 4 & 0	&1	&3\\
1& 3& 0 & 3	&1	&0\\
1&0	&2	& 0	&0	&1\\
1&0	& 2	& 0	&1	&1\\
1&3	& 0	& 3	&1	&1 \end{pmatrix}$.
	\begin{enumerate}
		\item Dans le contexte de l'exercice, interpréter le coefficient 2 situé sur la quatrième ligne et la troisième colonne de la matrice $M^3$.
		\item Combien existe-t-il de chemins de longueur 3 issus du sommet $D$ dans ce graphe ? Justifier puis citer ces chemins.
		\item Le fournisseur doit maintenant effectuer une livraison, depuis l'entrepôt, dans quatre
entreprises en commençant par l'entreprise $D$.
		
Montrer que, pour effectuer cette livraison sans repasser par une entreprise déjà livrée, le
fournisseur n'a qu'un seul chemin possible.
		
Expliquer la démarche et préciser ce chemin.
	\end{enumerate}
\end{enumerate}
 
\vspace{0,5cm}

{\large\textbf{Exercice 2 \hfill 5 points}}

\bigskip

Dans cet exercice on note $\Rightarrow$ le connecteur binaire d'implication.

Étant donnée une proposition $P$, on note $\overline{P}$ sa négation.

On admet la propriété suivante, démontrée par le mathématicien du XVII\up{e} siècle Pierre de Fermat :

\begin{center}
\begin{tabularx}{0.8\linewidth}{|X|}\hline
\textbf{Propriété (1) :}\\
Soit $p$ un entier naturel.\\
Si $p$ est un nombre premier alors pour tout entier naturel $a$ :\\
\multicolumn{1}{|c|}{$p$ divise $a^p - a$.}\\ \hline
\end{tabularx}
\end{center}

Dans la suite de l'exercice, $p$ est un entier naturel. On définit les prédicats suivants :

\setlength\parindent{10mm}
\begin{itemize}
\item[$\bullet~~$] $P(p)$ : $p$ est un nombre premier.
\item[$\bullet~~$] $Q(p)$ : $\forall a \in  \N,\: \: p$ divise $a^p - a$.
\end{itemize}
\setlength\parindent{0mm}
 
Les négations des prédicats $P(p)$ et $Q(p)$ sont notées respectivement $\overline{P(p)}$ et $\overline{Q(p)}$.

\medskip

\begin{enumerate}
\item \emph{Les trois questions suivantes sont à choix multiple. Pour chacune d'elles, recopier la seule
bonne réponse. Une réponse fausse ou une absence de réponse n'ôte pas de point.}

\medskip

	\begin{enumerate}
		\item Soit $a$ et $b$ deux entiers naturels, avec $b$ différent de $0$.
		
Si le reste de la division euclidienne de $a$ par $b$ est égal à $0$ alors :
		
\medskip
\begin{tabularx}{\linewidth}{*{2}{@{$\bullet$~}X}}
$b$ divise $a$ ; & $b$ est un multiple de $a$ ; \\ $a$ divise $b$ ; & $a$ est un diviseur de $b$.\\
\end{tabularx}
\medskip

		\item Le prédicat $\overline{Q(p)}$ peut être exprimé par :

\medskip
\begin{tabularx}{\linewidth}{*{2}{@{$\bullet$~}X}}
$\forall  a \notin \N,\:\: p$ \:divise $a^p - a$ ;&$\forall  a \in \N,\:\: p$ \:ne divise pas $a^p - a$ ;\\
$\exists a \in \N, \: p$ divise $a^p - a$ ;&$\exists a \in \N, \: p$ ne divise pas $a^p - a$ 
\end{tabularx}
\medskip

		\item Soient $P$ et $Q$ deux propositions. Une proposition équivalente à $P \Rightarrow Q$ est :

\medskip
\begin{tabularx}{\linewidth}{*{4}{@{$\bullet$~}X}}
$\overline{Q} \Rightarrow \overline{P}$ ; & $\overline{Q} \Rightarrow P$ ;& $\overline{P} \Rightarrow \overline{Q}$ ;&$\overline{P} \Rightarrow Q$.
\end{tabularx}
\medskip
	\end{enumerate}
\item La propriété (1) permet d'affirmer que la proposition \og $\forall p \in  \N,\:\: P(p) \Rightarrow Q(p)$ \fg{} est vraie.
	
On s'intéresse dans cette question à l'entier $p = \np{2701}$. On donne les résultats suivants :
	
\begin{center}
\begin{tabularx}{\linewidth}{|m{3.5cm}|*{8}{>{\centering \arraybackslash}X|}}\hline	
$a$& 0& 1& 2& 3& 4& 5& 6& 7\\ \hline
Reste de la division euclidienne de $a^{\np{2701}} -  a$  par \np{2701}&0&0&0&0&0&\np{1961}&0&\np{1965}\\ \hline
\end{tabularx}
\end{center}

	\begin{enumerate}
		\item Donner la valeur de vérité de $Q(\np{2701})$. Justifier à l'aide du tableau ci-dessus.
		\item \np{2701} est-il un nombre premier ? Justifier.
	\end{enumerate}
\end{enumerate}

\vspace{0,5cm}

{\large\textbf{Exercice 3 \hfill 5 points}}

\bigskip

Alice et Bob veulent échanger des messages privés sur un canal public qui peut être espionné. Pour
cela ils choisissent un nombre premier $p$ qu'ils se communiquent par le canal public, puis calculent
une clé secrète commune $K$ par un protocole nommé \og protocole de Diffie-Hellman \fg. Cette clé
secrète, qui est un entier naturel, leur permettra ensuite de coder les messages qu'ils s'enverront.

\medskip

Pour le calcul de cette clé secrète, Alice et Bob commencent par échanger un nombre entier $g$ par le
canal public.

Ensuite Alice choisit pour elle-même un entier naturel $a$, et Bob choisit pour lui-même un entier
naturel $b$.

\medskip

Les entiers $g$, $a$ et $b$ seront utilisés par Alice et par Bob pour déterminer la valeur de l'entier $K$,
selon un protocole qui utilise des congruences modulo l'entier premier $p$.

Ce protocole est décrit dans les questions qui suivent, d'abord de façon générale avec des écritures
littérales, puis avec des calculs numériques qui seront effectués avec les valeurs :

\[p = \np{2741},\quad  g = 14,\quad  a = 3\quad  \text{et}\quad  b = 12.\]

\medskip

\begin{enumerate}
\item \textbf{Calcul d'un entier \boldmath$x$\unboldmath par Alice}

Alice doit déterminer l'unique entier $x$ vérifiant $0 \leqslant  x \leqslant p - 1$ et $g^a \equiv x \quad(\text{mod}~p)$.

Déterminer cet entier $x$ en prenant $p = \np{2741}, g = 14$ et $a = 3$, c'est-à-dire déterminer l'entier $x$ vérifiant les conditions : $0 \leqslant x \leqslant \np{2740}$ et $14^3 \equiv  x \quad(\text{mod}~ \np{2741}$).
\item \textbf{Calcul d'un entier \boldmath$y$\unboldmath par Bob}

Bob doit déterminer l'unique entier $y$ vérifiant $0 \leqslant y \leqslant p - 1$ et $g^b \equiv  y \quad(\text{mod}~ p)$.

Déterminer cet entier $y$, en prenant $p = \np{2741},\: g = 14$ et $b = 12$, c'est-à-dire déterminer l'entier $y$ vérifiant les conditions : $0 \leqslant y \leqslant \np{2740}$ et $14^{12} \equiv y\quad (\text{mod}~ \np{2741}$).

(Pour le calcul de la puissance douzième, on pourra utiliser l'égalité 

$14^{12} = 14^6 \times 14^6$ et
remarquer que $14^6 \equiv 9\quad (\text{mod}~\np{2741}$).)

À ce niveau, en utilisant un canal public, Alice transmet à Bob le nombre $x$ qu'elle a calculé, et Bob
transmet à Alice le nombre $y$ qu'il a calculé.
\item \textbf{Calcul de la clé \boldmath$K$\unboldmath par Bob}

Bob peut calculer l'entier $K$ en utilisant les conditions $0  \leqslant K \leqslant p - 1$ et 

$x^b \equiv  K\quad (\text{mod}~ p)$.

Déterminer cet entier $K$, avec les valeurs $p = \np{2741}$ et $b = 12$.

\medskip

\emph{On admet qu'Alice peut retrouver le même entier $K$ en utilisant les conditions $0 \leqslant K \leqslant p - 1$ et $y^a \equiv  K\quad (\text{mod}~ p$), avec les valeurs $p = \np{2741}$ et $a = 3$.}
\end{enumerate}
\end{document}