%!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{enumitem}
\usepackage{pifont}
\usepackage{textcomp} 
\newcommand{\euro}{\eurologo}
%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}}
\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}
\hypersetup{%
pdfauthor = {APMEP},
pdfsubject = {BTS},
pdftitle = {Polynésie 10 mai 2017},
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{10 mai  2017}}
\renewcommand \footrulewidth{.2pt}
\pagestyle{fancy}
\thispagestyle{empty}
\marginpar{\rotatebox{90}{\textbf{A. P{}. M. E. P{}.}}}

\begin{center} {\Large \textbf{\decofourleft~BTS Polynésie 10 mai 2017~\decofourright\\Services informatiques aux organisations}}

\vspace{0,25cm}

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

\vspace{0,25cm}

\textbf{Exercice 1 \hfill 11 points}

\medskip

Cinq joueurs, notés A, B, C, 0 et E, jouent régulièrement à un jeu en ligne.

Chaque partie de ce jeu oppose deux adversaires.

Le tableau suivant donne, pour chacun des cinq joueurs, la liste des adversaires qu'il a déjà battus.

\begin{center}
\begin{tabularx}{0.6\linewidth}{|c|>{\centering \arraybackslash}X|}\hline
Le joueur &a déjà battu\\ \hline
A& B, D\\ \hline
B& C\\ \hline
C& B, D\\ \hline
D& E\\ \hline
E& D\\ \hline
\end{tabularx}
\end{center}

Ainsi, par exemple, le joueur C a déjà battu les joueurs B et D.

\medskip

\begin{enumerate}
\item Graphe orienté associé à la situation
	\begin{enumerate}
		\item En considérant le tableau précédent comme un tableau de successeurs, représenter la
situation par un graphe orienté $G$, dans lequel un arc relie un sommet $x$ à un sommet $y$ si le
joueur $x$ a déjà battu le joueur $y$.
		\item Écrire la matrice d'adjacence $M$ du graphe $G$.
		\item Recopier et compléter le tableau des prédécesseurs dans le graphe $G$.
		
\begin{center}
\begin{tabularx}{0.6\linewidth}{|c|>{\centering \arraybackslash}X|}\hline
Le joueur 	&\textbf{a déjà \ldots\ldots}\\ \hline
A			&\\ \hline
B			&\\ \hline
C			&\\ \hline
D			&\\ \hline
E			&\\ \hline
\end{tabularx}
\end{center}

		\item Le graphe $G$ contient-il un circuit ? Contient-il un chemin hamiltonien ? Justifier les réponses.
	\end{enumerate}
\item Dans cette question, on note $J = \{\text{A, B, C, D, E}\}$ l'ensemble des cinq joueurs.
	
On note $V(x~;~y)$ le prédicat : \og le joueur $x$ a déjà battu le joueur $y$ \fg.
	
Ainsi, la valeur $V$(A~;~B) est VRAI, et la valeur de V(B~;~A) est FAUX.

\smallskip
	
On définit trois prédicats:
	
\textbf{P1} : $\forall  x \in J, \exists y \in J$\:, $x \ne y$ et $V (x~;~y)$
	
\textbf{P2} : $\exists x \in J, \exists y \in J$,\: $x \ne y$ et $V(x~;~y)$
	
\textbf{P3} : $\exists y \in J, \forall x \in J$,\: $x \ne y$ et $V(x~;~y)$
	
Associer à chaque prédicat \textbf{P1}, \textbf{P2}, \textbf{P3}, celle des trois phrases suivantes qui lui correspond parmi les phrases suivantes. Aucune justification n'est demandée.

\setlength\parindent{9mm}
\begin{itemize}
\item[$\bullet~~$]\og Il existe un joueur qui a été battu par tous les autres joueurs \fg.
\item[$\bullet~~$]\og Tous les joueurs ont battu au moins un autre joueur \fg.
\item[$\bullet~~$]\og Il existe un joueur qui a battu tous les autres joueurs \fg.
\end{itemize}
\setlength\parindent{0mm}

\item Un joueur reçoit un bonus lorsqu'il vérifie l'un au moins des trois critères suivants :

\setlength\parindent{9mm}
\begin{itemize}
\item[$\bullet~~$] le joueur a participé à 20 parties ou davantage, et il a affronté plusieurs adversaires différents;
\item[$\bullet~~$]le joueur n'a pas affronté plusieurs adversaires différents, et il a obtenu strictement plus de victoires que de défaites ;
\item[$\bullet~~$]le joueur n'a pas obtenu strictement plus de victoires que de défaites, et il a participé à 20 parties ou davantage.
\end{itemize}
\setlength\parindent{0mm}

On définit les variables booléennes $a$, $b$, $c$ de la façon suivante:

\begin{itemize}
\item $a = 1$ si le joueur a participé à 20 parties ou davantage ; $a = 0$ sinon;
\item $b = 1$ si le joueur a affronté plusieurs adversaires différents ; $b = 0$ sinon;
\item $c = 1$ si le joueur a obtenu strictement plus de victoires que de défaites ; $c = 0$ sinon.
\end{itemize}
	\begin{enumerate}
		\item Écrire une expression booléenne $F$ traduisant les conditions permettant à un joueur d'obtenir le bonus.
		\item À l'aide d'un tableau de Karnaugh ou d'un calcul booléen, déterminer une écriture simplifiée de $F$ sous forme d'une somme de deux termes.
		\item En déduire une formulation simplifiée des critères permettant à un joueur d'obtenir le bonus.
	\end{enumerate}
\item On note $S$ la relation \og successeur\fg{} dans le graphe $G$.
	
Ainsi, l'écriture \og $x S y$ \fg{} signifie que $x$ a pour successeur $y$ dans ce graphe.
	
On rappelle les définitions suivantes.
	
\setlength\parindent{9mm}
\begin{itemize}
\item[$\bullet~~$] Une relation binaire $R$ sur un ensemble $E$ est symétrique si pour tous $x$ et $y$ dans $E$ :

\[x\: R\: y \Rightarrow y\: R\: x.\]

\item[$\bullet~~$]Une relation binaire sur un ensemble $E$ est transitive si pour tous $x$, $y$ et $z$ dans $E$ :

\[x\: R\: y \:\text{ et }\: y\: R \:z \Rightarrow x\: R \:z.\]
\end{itemize}
	\begin{enumerate}
		\item La relation $S$ est-elle transitive ? Justifier.
		\item Quel(s) arc(s) faut-il ajouter au graphe pour rendre la relation $S$ symétrique ?
	\end{enumerate}
\end{enumerate}

\vspace{0,5cm}

\textbf{Exercice 2 \hfill 9 points}

\medskip

Le but de cet exercice est d'étudier une façon de parcourir un fichier de $195$ clients, dont les fiches sont numérotées de 0 à 194.

\smallskip

\emph{Les deux parties peuvent être traitées de manière indépendante}

\smallskip

\textbf{Partie A - Étude d'une suite}

\medskip

On considère la suite $\left(u_n\right)$ définie par 

\[u_0 = 5 \:\text{et, pour tout entier naturel }\:n : u_{n+1} = 3u_n + 4.\]

\begin{enumerate}
\item Déterminer $u_1$ et $u_2$.
\item Justifier que la suite $\left(u_n\right)$ n'est ni arithmétique ni géométrique.
\item On considère la suite $\left(v_n\right)$ définie pour tout entier naturel $n$ par : $v_n = u_n + 2$.
	\begin{enumerate}
		\item Déterminer $v_0$,  $v_1$ et $v_2$.
		\item Justifier que $\left(v_n\right)$ est une suite géométrique dont on précisera la raison.
		\item Déterminer une expression de $v_n$ en fonction de $n$.
	\end{enumerate}
\item En déduire, que pour tout entier naturel $n$, on a : $u_n = 7 \times 3^n - 2$.
\end{enumerate}

\bigskip

\textbf{Partie B - Étude d'un mode de parcours du fichier}

\medskip

Pour tout entier naturel $n$, on note $w_n$ le reste de la division euclidienne de $7\times 3^n - 2$ par $195$.

On a ainsi, en particulier : $w_n \equiv 7\times 3^n - 2 $\:\text{ modulo }\:$195$.

On parcourt le fichier à l'aide de la suite $\left(w_n\right)$ en déplaçant un curseur de la façon suivante :

\setlength\parindent{9mm}
\begin{itemize}
\item[$\bullet~~$]initialement, le curseur est positionné sur la fiche numéro 5, qui correspond à la valeur $w_0$ ;
\item[$\bullet~~$]le curseur se déplace ensuite sur la fiche numéro 19, qui correspond à la valeur $w_1$ ;
\item[$\bullet~~$]plus généralement, après $n$ déplacements, le curseur est positionné sur la fiche dont le numéro correspond à la valeur de $w_n$.
\end{itemize}
\medskip

\begin{enumerate}
\item Justifier que $w_5 = 139$.
\item Justifier que $3^{13} \equiv  3$ modulo $195$. En déduire que $w_{13} = 19$.
\item Soit $n$ un entier naturel quelconque.
	\begin{enumerate}
		\item Démontrer que $w_{n+13} - w_{n+1} \equiv 7 \times 3^n\left(3^{13} - 3\right)$ modulo $195$.
		\item En déduire, en utilisant la question 2., que $w_{n+13} = w_{n+1}$.
		\item Interpréter le résultat précédent concernant le positionnement du curseur.
	\end{enumerate}
\item On donne la liste des 15 premières valeurs de $w_n$ :
	
\[5 - 19 - 61 - 187 - 175 - 139 - 31 - 97 - 100 - 109 - 136 - 22 - 70 - 19 - 61.\]
	
On considère l'ensemble $E = \{0,~1,~ 2,~3,~ \ldots,193~, 194\}$ et l'application $f$ de $E$ dans $E$, définie pour tout entier $n$ de l'ensemble $E$ par : $f(n) = w_n$.
	\begin{enumerate}
		\item L'application $f$ est-elle injective ? Justifier la réponse.
		\item L'application $f$ est-elle surjective ? Justifier la réponse.
	\end{enumerate}
\end{enumerate}
\end{document}