Partie A
Un club sportif organise une course d’orientation. Sept postes de contrôles (appelés balises) sont prévus.
Les sept balises notées B1 ; B2 ; . . . ; B7 sont représentées sur le graphe ci-dessous.
Les arêtes du graphe représentent les chemins possibles entre les balises et sur chaque arête est indiqué le temps de parcours estimé en minutes.
1) a) Le graphe est-il connexe ? Justifier la réponse.
b) Existe-t-il un parcours qui permet de revenir à une balise de départ en passant une et une seule fois par tous les chemins ? Justifier la réponse.
c) Existe-t-il un parcours qui permet de relier deux balises différentes en passant une et une seule fois par tous les chemins ?
2) Les organisateurs décident de situer le départ à la balise B1 et l’arrivée à la balise B7.
Chaque participant doit rallier la balise B7 en un minimum de temps. Ils ne sont pas tenus à emprunter tous les chemins.
Quelle est la durée minimale du parcours possible et quel est ce parcours ? Justifier votre réponse à l’aide d’un algorithme.
Partie B
Depuis l’année 2011, ce club sportif propose à ses licenciés une assurance spécifique. La première année, 80% des licenciés y ont adhéré.
En 2012, 70% des licenciés ayant adhéré en 2011 ont conservé cette assurance et 60% de ceux n’ayant pas adhéré en 2011 ont adhéré en 2012.
En supposant que cette évolution se maintienne, le club sportif souhaite savoir quel pourcentage de licenciés adhèrera à cette assurance à plus long terme.
On note :
$A$ « le licencié est assuré »
$B$ « le licencié n’est pas assuré »
Pour tout entier $n$ non nul, l’état probabiliste du nombre d’assurés l’année $2011+n$ est défini par la matrice ligne :
$P_n \begin{pmatrix} x_n&y_n \end{pmatrix}$ où $x_n$ désigne la probabilité pour un licencié d’être assuré l’année $2011+n$.
1) Représenter cette situation par un graphe probabiliste de sommets $A$ et $B$.
2) Écrire la matrice de transition $M$ de ce graphe en prenant les sommets $A$ et$B$ dans cet ordre.
3) En remarquant que $P_0 = \begin{pmatrix} 0,8&0,2 \end{pmatrix}$, déterminer $P_1$. Interpréter ce résultat.
4) Le club sportif maintiendra son offre d’assurance spécifique si le nombre d’assurés reste supérieur à $55$%.
L’évolution prévue lui permet-elle d’envisager le maintien de son offre à long terme ?
1) a) Deux sommets quelconques de ce graphe sont reliés par une chaîne, donc ce graphe est connexe.
b) Un parcours de graphe est « eulérien » s’il passe une fois et une seule par chaque arête.
Il s’agit d’un cycle eulérien si on part et on revient au même sommet après avoir parcouru toutes les arêtes.
Il existe un cycle eulérien dans un graphe, si et seulement si ce graphe ne contient aucun sommet de degré impair ; or ce graphe contient 6 sommets de degré impair : B2(3), B3 (3), B4 (5), B5 (3), B6 (3) et B7 (3).
Donc il n’existe pas de parcours permettant de revenir à une balise de départ en passant une et une seule fois par tous les chemins.
c) Il existe un chemin eulérien joignant deux sommets différents, c’est-à-dire par courant toutes les arêtes, s’il y a exactement 2 sommets de degré impair.
Comme il y a 6 sommets de degré impair, il n’y a pas de parcours permettant de relier deux balises différentes en passant une et une seule fois par tous les chemins.
On va chercher le plus court chemin allant de B1 à B7 en utilisant l’algorithme de Dijkstra :
Le trajet le plus rapide reliant B1 à B7 est donc :
$B1\xrightarrow[\text{}]{\text{13}}B3\xrightarrow[\text{}]{\text{ 5}}B5\xrightarrow[\text{}]{\text{ 2}}B4\xrightarrow[\text{}]{\text{ 4}}B6\xrightarrow[\text{}]{\text{ 5}}B7$
Il a une durée totale de $13+5+2+4+5 = 29$ minutes.
Partie B
1) Sachant qu’on désigne par A « le licencié est assuré » et par B « le licencié n’est pas assuré», les deux sommets, le graphe probabiliste associé à la situation décrite dans le texte est :
2) D’après le cours, la matrice de transition est $M =\begin{pmatrix} 0,7&0,3 \\ 0,6&0,4 \end{pmatrix}$
3) $P_0= \begin{pmatrix} 0,8&0,2 \end{pmatrix}$
$P_1=P_0 \times M=\begin{pmatrix} 0,8&0,2 \end{pmatrix} \times \begin{pmatrix} 0,7&0,3 \\ 0,6&0,4 \end{pmatrix}$
$P_1 =\begin{pmatrix} 0,68&0,32 \end{pmatrix}$
$P_0$ correspond à l’année 2012, donc $P_1$ correspond à 2013.
En 2013, il y a donc $68$% de licenciés qui ont l’assurance spécifique, et $32$% qui ne l’ont pas.
4) En faisant les calculs à la calculatrice, on peut conjecturer que le pourcentage de licenciés ayant souscrit l’assurance spécifique tend à se rapprocher de $66,67$ % ; on va donc chercher un état stable du graphe probabiliste.
L’état stable est solution du système :
$ \begin{cases} \begin{pmatrix} a&b \end{pmatrix}= \begin{pmatrix} a&b \end{pmatrix} \times M \\ a+b=1 \end{cases}$
On a :
$ \begin{pmatrix} a&b \end{pmatrix}= \begin{pmatrix} a&b \end{pmatrix} \times M \iff \begin{pmatrix} a&b \end{pmatrix} \times \begin{pmatrix} 0,7&0,3 \\ 0,6&0,4 \end{pmatrix}$
$\iff \begin{cases}a =0,7a + 0,6b \\ b=0,3a+0,4b \end{cases}$
$\iff 3a-6b=0 $
Ainsi :
$ \begin{cases} \begin{pmatrix} a&b \end{pmatrix}= \begin{pmatrix} a&b \end{pmatrix} \times M \\ a+b=1 \end{cases} \iff \begin{cases} 3a-6b=0 \\ a+b=1 \end{cases} \iff \begin{cases} a=\dfrac{2}{3} \\ b=\dfrac{1}{3} \end{cases}$
Donc on peut conclure que le pourcentage de licenciés ayant souscrit l’assurance spécifique tend en diminuant vers $\dfrac{2}{3} \approx 66,67\%$;
on peut en déduire que le pourcentage d’assurés reste au dessus de $55$ %.
Le club sportif peut donc maintenir son offre à long terme.