\documentclass[a4paper,11pt,french]{article}
\linespread{1}


\newcommand{\ch}{Chapitre 3}
\newcommand{\Ch}{Graphes et Probabilit\'es}	
\newcommand{\Cl}{T$^{\circ}$ ES Sp\'ecialit\'e}	
\newcommand{\Annee}{2010-2011}	
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%		Package
%\usepackage[french,lined,boxed,commentsnumbered]{algorithm2e}

\input macro_final.tex

\geometry{hmargin=2cm,vmargin=2.5cm}

\setcounter{NumLecon}{3}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	Premiere page
\begin{document}
 


\debutExoCha

\Exop[Amérique du Sud Nov 2005 \hfill 5 points]{
\begin{enumerate}
\item \`A l'occasion de la coupe du monde de football 2006 en Allemagne, une agence touristique 
organise des voyages en car \`a travers les diff\'erentes villes où se joueront les matchs d'une 
\'equipe nationale.
Les routes emprunt\'ees par les cars sont repr\'esent\'ees par le graphe ci-dessous. Le long de chaque 
ar\^ete figure la distance en kilom\`etres s\'eparant les villes.\\
Les lettres B, D, F, H, K, M, N et S repr\'esentent les villes Berlin, Dortmnd, Francfort, Hambourg, 
Kaiserslautern, Munich, Nuremberg et Stuttgart.

\bigskip

\begin{center}
\begin{pspicture}(8,6.7)
\psset{arrowsize=2.5pt 3} \psset{arcangle=20}
\cnodeput(0,0){A}{K} \cnodeput(0,2){B}{F} 
\cnodeput(0,4){C}{D} \cnodeput(3,6.7){D}{H}
\cnodeput(8,4){E}{B} \cnodeput(8,2){F}{N}
\cnodeput(5,0){G}{M} \cnodeput(3,1){H}{S}
\ncarc{A}{B} \ncput*{120} \ncarc{B}{D} \ncput*{490} 
\ncarc{D}{H} \ncput*{650} \ncarc{D}{G} \ncput*{780} 
\ncarc{D}{F} \ncput*{600} \ncarc{C}{E} \ncput*{490} 
\ncarc{C}{G} \ncput*{600} \ncarc{E}{H} \ncput*{630} 
\ncarc{E}{G} \ncput*{580} \ncarc{F}{H} \ncput*{210} 
\ncarc{G}{H} \ncput*{230} 
\end{pspicture}
\end{center}

\bigskip
En pr\'ecisant la m\'ethode utilis\'ee, d\'eterminer le plus court chemin possible pour aller de 
Kaiserslautern \`a Berlin en utilisant les cars de cette agence.
\item Pour des raisons de s\'ecurit\'e, les supporters de certaines \'equipes nationales participant \`a 
la coupe du monde de football en 2006 ne peuvent \^etre log\'es dans le m\^eme h\^otel.\\
L'objectif de cette question consiste \`a rechercher une r\'epartition des supporters afin d'utiliser le 
minimum d'h\^otels.\\
On donne ci-dessous le graphe d'incompatibilit\'e entre les supporters de diff\'erentes \'equipes : 
par exemple, un supporter de l'\'equipe A ne peut \^etre log\'e avec un supporter de l'\'equipe B .\\
\emph{Ce m\^eme graphe figure sur la feuille annexe qui peut \^etre rendue avec la copie.}
\begin{center}
\begin{pspicture}(7,4.1)
\psset{arrowsize=2.5pt 3} \psset{arcangle=40}
\cnodeput(0,0){A}{G} \cnodeput(0,3){B}{A} 
\cnodeput(3,4){C}{P} \cnodeput(6,3){D}{C}
\cnodeput(6,1.7){E}{Q} \cnodeput(6,0){F}{E}
\cnodeput(3,0){G}{R} 
\ncline{A}{B}  \ncline{B}{C} \ncline{B}{F} 
\ncline{C}{E} \ncline{C}{F} 
\ncline{C}{E} %\ncline{D}{F}
\ncline{D}{G}  \ncline{D}{B} 
\ncline{E}{B} \ncline{F}{E} 
\ncline{G}{A} 
\end{pspicture}
\end{center}
\bigskip

\begin{enumerate}
\item  D\'eterminer le nombre chromatique de ce graphe en justifiant la valeur trouv\'ee. 
\item  Proposer une r\'epartition des supporters par h\^otel en utilisant un nombre minimum d'h\^otels.
\end{enumerate}
\end{enumerate}
}

\Exop[Asie Juin 2003 \hfill 5 points]{
Dans la ville de GRAPHE, on s'intéresse aux principales rues 
permettant de relier différents lieux ouverts au public, à savoir la mairie 
(M), le centre commercial (C), la bibliothèque (B), la piscine (P) et le lycée (L). 
Chacun de ces lieux est désigné par son initiale. Le tableau ci-dessous  donne les rues existant entre ces lieux.

\begin{center} \begin{tabularx}{0.8\linewidth}{|*{6}{>{\centering \arraybackslash}X|} } \cline{2-6}	
\multicolumn{1}{c|}{}&B 	&C 	&L 	&M 	&P\\ \hline
B 				& 	&X 	& 	&X 	&X\\ \hline
C 				&X 	& 	&X 	&X 	& \\ \hline
L 				& 	&X	& 	& X & \\ \hline
M 				&X 	&X 	&X	& &X \\ \hline
P 				& X 	& 	& 	& X & \\ \hline
\end{tabularx} \end{center}

\begin{enumerate} 
\item Dessiner un graphe représentant cette situation.

\item Montrer qu'il est possible de trouver un trajet empruntant une 
fois et une seule toutes les rues de ce plan. Justifier. Proposer un tel 
trajet.

Est-il possible d'avoir un trajet partant et arrivant du même lieu 
et passant une fois et une seule par toutes les rues ?

\parbox[l]{0,45\textwidth}{\item Dimitri habite dans cette ville ; 
le graphe ci-contre  donne le \textbf{nouveau} plan du quartier avec les sens de
circulation dans les différentes rues et le temps de parcours entre les différents
lieux.} \hfill \parbox[l]{0,5\textwidth}{\begin{pspicture}(6,5)
\psset{arrowsize=2.5pt 3}\cnodeput(0,1.3){A}{P} \cnodeput(1.9,2.9){B}{B}
\cnodeput(1.8,0){C}{M} \cnodeput(3.6,1.5){D}{C}
\cnodeput(4.5,3.8){E}{D} \cnodeput(5.7,0.4){F}{L}
 \ncarc{->}{B}{A} \ncput*{10} \ncarc{<->}{A}{C} \ncput*{4}
\ncarc{<->}{B}{C} \ncput*{5} \ncarc{<->}{D}{C} \ncput*{9}
\ncarc{->}{D}{B}  \ncput*{3}\ncarc{->}{E}{B} \ncput*{9}
\ncarc{->}{E}{D} \ncput*{5} \ncarc{<->}{F}{E} \ncput*{11}
\ncarc{<->}{F}{D} \ncput*{4} \ncarc{->}{F}{C} \ncput*{10}
\end{pspicture}
}

\bigskip

Dimitri désire prendre sa voiture pour se rendre de son domicile noté D jusqu'à la piscine.

Proposer un trajet le plus court possible lui permettant de se rendre de son domicile à la piscine.

La réponse proposée devra être justifiée par un algorithme.

\end{enumerate}
}

\Exop[Métropole Sept 2005 \hfill 5 points]{
Mademoiselle Z travaille dans une soci\'et\'e sp\'ecialis\'ee dans la vente par t\'el\'ephone. 
Chaque jour, elle doit appeler une liste de clients pour leur proposer un produit particulier. 
Apr\`es avoir observ\'e un grand nombre d'appels de Mademoiselle Z, on peut faire l'hypoth\`ese suivante :\\
- si un client contact\'e r\'epond favorablement (situation A), cela donne de l'assurance \`a Mademoiselle Z 
et elle arrive \`a convaincre le client suivant une fois sur deux ;\\
- si le client contact\'e ne r\'epond pas favorablement (situation B), Mademoiselle Z se d\'ecourage et n'arrive 
\`a convaincre le client suivant qu'une fois sur cinq.
\begin{enumerate}
 \item \begin{enumerate}
\item Traduire les donn\'ees de l'\'enonc\'e par un graphe probabiliste de sommets A et B.
\item \'Ecrire la matrice de transition $M$ de ce graphe en respectant l'ordre alphab\'etique des sommets.
\end{enumerate}
\item Ce lundi, Mademoiselle Z est en forme et elle a convaincu le premier client d'acheter le produit propos\'e. La matrice ligne d\'ecrivant l'\'etat initial au premier appel est donc $P_{0} = (1~; ~0)$.
Donner la matrice ligne $P_{1}$ exprimant l'\'etat probabiliste au deuxi\`eme appel.
\item On donne la matrice $M^5 =  \begin{pmatrix}
\nombre{0,28745}&  \nombre{0,71255}\\
\nombre{0,28502}&  \nombre{0,71498}\\
\end{pmatrix}$
\begin{enumerate}\item Calculer le produit $P_{0}M^5$. En d\'eduire la probabilit\'e que Mademoiselle Z convainque son sixi\`eme client ce lundi.
\item Quelle aurait \'et\'e la probabilit\'e que Mademoiselle Z convainque son sixi\`eme client si elle n'avait pas convaincu le premier ?
\end{enumerate}
\item D\'eterminer l'\'etat stable du syst\`eme. Comment peut-on l'interpr\'eter ?
\end{enumerate}
}

\Exop[Amérique du Sud Nov 2004 \hfill 5 points]{ 
Au cours de la première semaine de l'année scolaire, un professeur propose aux élèves de sa classe le choix entre 
deux sorties pédagogiques une sortie A et une sortie B. 

20\,\% des élèves de la classe sont favorables à la sortie A et tous les autres 
élèves sont favorables à la sortie B. 

Les arguments des uns et des autres font évoluer cette répartition en cours 
d'année. 

Ainsi $30\:\%$ des élèves favorables à la sortie A et 20\,\% des élèves 
favorables à la sortie B changent d'avis la semaine suivante. 

On note : 

$a_n$ la probabilité qu'un élève soit favorable à la sortie A la semaine 
$n$ ; 

$b_n$ la probabilité qu'un élève soit favorable à la sortie B la semaine $n$ ; 

$P_n$ la matrice $\left(a_n~ ;~ b_n\right)$ traduisant l'état probabiliste la 
semaine $n$. 

\begin{enumerate}
\item Déterminer l'état initial $P_1$. 
\item Représenter la situation par un graphe probabiliste. 

\item En déduire que $P_{n+1} = P_n \times \text{M}$ o\`u M est la matrice 
$\begin{pmatrix} 
0,7 & 0,3\\0,2 & 0,8\\ 
\end{pmatrix}$ 
\item Déterminer l'état probabiliste $P_3$ et en déduire la probabilité qu'un élève 
soit favorable à la sortie A la troisième semaine. 
\item Déterminer le réel $x$ tel que $(x~; 1-x) \times \text{M} =(x~;~ 1 - 
x)$. 

On admet que la suite $\left(a_n\right)$ est croissante. La sortie A finira-t-elle par être préférée à la sortie B 
? 
\end{enumerate} 
}

\Exop[Polynésie Sept 2006\hfill 5 points]{
Une commune poss\`ede deux clubs de sport que l'on note A et B.\\
 Le club A est install\'e depuis 1990, le club B a ouvert ses portes au cours de l'ann\'ee 2004. Au premier janvier 
2005, on constate que \nombre{1100} personnes sont abonn\'ees au club A et 400 au club B.\\
  Le prix de l'abonnement est moins co\^uteux au club A ; les activit\'es propos\'ees sont plus nombreuses au club 
B. Aussi, chaque ann\'ee, 14\,\% des abonn\'es au club A changent pour le club B et 6\,\% des abonn\'es au club B 
changent pour le club A. On suppose que la population totale des abonn\'es reste constante et qu'une personne ne 
s'abonne jamais aux deux clubs en m\^eme temps.\\
 \noindent On note $a_{n}$ le nombre d'abonn\'es au club A et $b_{n}$ le nombre d'abonn\'es au club B au premier 
janvier de l'ann\'ee $2005+n$.\\
$E_{n}$ d\'esigne la matrice ligne $\left(a_{n} ~~ b_{n}\right)$ ; ainsi $E_{0} = \left(a_{0} ~~ b_{0}\right) =  
(\nombre{1100}~~ 400)$.
\begin{enumerate}
\item  Traduire les donn\'ees par un graphe probabiliste.
\item   \begin{enumerate}
\item  \'Ecrire la matrice de transition $M$ telle que $E_{n+1} = E_{n} \times M.$\\
En d\'eduire $E_{n}$ en fonction de $E_{0}$, $M$ et $n$. On ne demande pas de d\'emontrer le r\'esultat.
\item  Calculer $M^2$ . En d\'eduire le nombre d'abonn\'es aux deux clubs au premier janvier 2007.
\end{enumerate}
\item   \begin{enumerate}
\item  D\'emontrer que, pour tout entier naturel $n$ , on a : $a_{n+1}  = 0,8 \times a_{n} + 90$.
\item Pour $n$ entier naturel, on pose : $u_{n} =  a_{n} - 450$. D\'emontrer que la suite $\left(u_{n}\right)$ est 
g\'eom\'etrique.
\item  En d\'eduire que, pour tout entier naturel $n$, on a : $a_{n+1} =  650 \times  0,8^n + 450$.
\item  D\'eterminer la limite de $a_{n}$ quand $n$ tend vers $+ \infty$. Interpr\'eter ce r\'esultat pour les deux 
clubs sportifs.
\end{enumerate}
\end{enumerate}
}




\end{document}
