\chapter{Graphes}

\newpage
\pagestyle{main}

\section{Introduction}

\subsection{Approche intuitive}

Hugo doit partir de son domicile pour aller chez Sylvain, Lucie et Aude. Il souhaite schématiser les différents parcours. Pour cela, il peut utiliser le schéma suivant:
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=9,y=1]{L}
\Vertex[x=2,y=-1]{A}
\Edge(D)(S)\Edge(D)(A)\Edge(D)(L)\Edge(A)(S)\Edge(A)(L)
\Edge(L)(S)
\end{tikzpicture}
\end{center}
Ce schéma lui montre tous les chemins qu'il peut emprunter. De plus, s'il connaît les distances entre chacune des maisons, il peut les reporter dessus:
\begin{center}
\begin{tikzpicture}
\SetGraphUnit{7}
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=9,y=1]{L}
\Vertex[x=2,y=-2]{A}
\Edge[label=7,labelstyle={draw=brown,text=brown}](D)(S)
\Edge[label=3,labelstyle={draw=brown,text=brown}](D)(A)
\Edge[label=10,labelstyle={draw=brown,text=brown}](D)(L)
\Edge[label=5,labelstyle={draw=brown,text=brown}](A)(S)
\Edge[label=8,labelstyle={draw=brown,text=brown}](A)(L)
\Edge[label=3,labelstyle={draw=brown,text=brown}](L)(S)
\end{tikzpicture}
\end{center}
Cette représentation est celle de ce que l'on appelle un \textit{graphe}.
 
\subsection{Définitions}

\begin{defin}
Un \textit{graphe} $\mathcal{G}$ est la donnée de deux ensembles: l'un est constitué de points, appelés\linebreak \textit{sommets}, l'autre est constitué de couples de points, appelés \textit{arêtes}.
\end{defin}

\begin{exemple}
Dans l'exemple précédent, $\mathcal{G}=( \mathcal{S}; \mathcal{A} )$ où:
\begin{itemize}
\item $\mathcal{S} = \{D;A;S;L\}$;
\item $\mathcal{A} = \{ \coord{D}{S}, \coord{D}{L}, \coord{D}{A},\coord{A}{S},\coord{A}{L},\coord{S}{L} \}$.
\end{itemize}
\end{exemple}

\begin{rem}
Attention: il ne faut pas confondre \og graphe \fg{} (donnée formelle) et  \og représentation d'un graphe \fg{} (plus visuelle que le graphe lui-même).
\end{rem}

\section{Vocabulaire}

\subsection{Sommets adjacents}

\begin{defin}
Dans un graphe, deux sommets sont dits \textit{adjacents} s'il existe une arête entre eux.
\end{defin}

\begin{exemple}
Dans l'exemple précédent, tous les sommets sont adjacents car il existe une arête entre chacun d'eux.
\end{exemple}

\subsection{Graphe complet}

\begin{defin}
Une graphe est \textit{complet} si tous les sommets sont adjacents deux à deux.
\end{defin}

C'est le cas de notre exemple de départ.

\begin{prop}
Soit $\mathcal{G}$ un graphe complet à $n$ sommets. Alors, le nombre d'arêtes de $\mathcal{G}$ est:
\[
K_n=\dfrac{n(n-1}{2}.
\]
\end{prop}
\begin{demo}
Numérotons les sommets de 1 à $n$.
\begin{itemize}
\item Le sommet 1 est relié aux $n-1$ autres sommets; il y a donc $n-1$ arêtes qui partent de ce sommet.
\item Le sommet 2 est lui aussi relié à $n-1$ sommets, mais nous avons déjà compté l'arête qui le relie au sommet 1; il y a donc (en plus des $n-1$ arêtes précédentes) $n-2$ arêtes issues du sommet 2.
\item etc. jusqu'au commet $n-1$ qui est relié au sommet $n$ par une arête (distinctes des autres).
\end{itemize}
Ainsi,
\[
K_n = (n-1) + (n-2) + \cdots + 1 = \dfrac{(n-1)(n-1+1)}{2}=\dfrac{n(n-1)}{2}.
\]
\end{demo}

\bigskip

$\blacktriangleright$ Voir l'exercice \ref{exercice:\thechapter.1}.

\newpage

\subsection{Ordre d'un graphe}

\begin{defin}
L'ordre d'un graphe est le nombre de sommets de ce graphe.
\end{defin}

\begin{exemple}
L'ordre du graphe de notre exemple est égal à 4.
\end{exemple}

\subsection{Chaîne d'un graphe}

\begin{defin}
Une chaîne d'un graphe est une liste ordonnée de sommets adjacents deux à deux.

Le nombre de sommets de cette liste est appelé la \textit{longueur} de la chaîne.
\end{defin}

\begin{exemple}
Dans l'exemple de départ,
\begin{itemize}
\item D -- S -- A -- L est une chaîne de longueur 4.
\item A -- D -- S est une chaîne de longueur 3.
\end{itemize}
\end{exemple}

\subsection{Graphe connexe}

\begin{defin}
Un graphe est dit \textit{connexe} si deux sommets quelconques de ce graphe peuvent être reliés par au moins une chaîne.
\end{defin}

Il est assez facile de voir si un graphe est connexe ou non: si sa représentation comporte au moins un sommet isolé alors il n'est pas connexe.

\section{Différents types de graphes}

\subsection{Graphes non orientés et orientés}

\begin{defin}
Un graphe $\mathcal{G}=( \mathcal{S}; \mathcal{A} )$  est \textit{non orienté} si les couples de $\mathcal{A}$ peuvent être inversés.
\end{defin}

\enlargethispage*{3cm}

\begin{exemple}
Dans notre exemple précédent, Hugo peut aller de la maison de Sylvain à celle de Lucie, mais aussi de la maison de Lucie à celle de Sylvain: il n'y a pas de sens imposé.

Le graphe représentant la situation est non non orienté.
\end{exemple}

\newpage

\begin{defin}
Un graphe $\mathcal{G}=( \mathcal{S}; \mathcal{A} )$  est \textit{orienté} si les couples de $\mathcal{A}$ ne peuvent pas être inversés.
\end{defin}

\begin{exemple}
Supposons que dans notre exemple de Départ, Hugo ne puisse pas aller de $S$ à $A$ mais uniquement de $A$ à $S$, et qu'il y ait d'autres contraintes du même type. 

Supposons que la représentation de la situation soit alors celle-ci:
\begin{center}
\begin{tikzpicture}
\SetUpEdge[style={->}]
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=9,y=1]{L}
\Vertex[x=2,y=-1]{A}
\Edge(D)(S)\Edge(D)(A)\Edge(L)(D)\Edge(A)(S)\Edge(A)(L)
\Edge(S)(L)\Edge[style={bend right,->}](S)(D)
\end{tikzpicture}
\end{center}
Nous avons alors ici la représentation d'un graphe orienté.
\end{exemple}

\subsection{Graphe pondéré}

\begin{defin}
Un graphe est dit \textit{pondéré} si ses arêtes sont munies de nombres positifs, appelés \textit{étiquettes} ou \textit{pondérations}.
\end{defin}

\begin{exemple}
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=9,y=1]{L}
\Vertex[x=2,y=-2]{A}
\Edge[label=7,labelstyle={draw=brown,text=brown}](D)(S)
\Edge[label=3,labelstyle={draw=brown,text=brown}](D)(A)
\Edge[label=10,labelstyle={draw=brown,text=brown}](D)(L)
\Edge[label=5,labelstyle={draw=brown,text=brown}](A)(S)
\Edge[label=8,labelstyle={draw=brown,text=brown}](A)(L)
\Edge[label=3,labelstyle={draw=brown,text=brown}](L)(S)
\end{tikzpicture}
\end{center}
Ceci est la représentation d'un graphe pondéré. Ici, les pondérations représente la distance (en kilomètre) entre chaque maison représentées par les sommets.
\end{exemple}

\begin{rem}
Les pondérations peuvent représenter n'importe quoi: distances, temps, probabilités,...
\end{rem}

\subsection{Graphe probabiliste}

\begin{defin}
Un graphe probabiliste est un graphe orienté où la somme des pondérations des arêtes issues d'un même sommet est égale à 1.
\end{defin}

\begin{exemple}
Pendant les vacances, Louis est soit dans sa chambre, soit dans la cuisine.
\begin{itemize}
\item S'il est dans sa chambre, la probabilité qu'il y soit encore 10 minutes plus tard est égale à 0,7.
\item S'il est dans la cuisine, la probabilité qu'il y soit encore 10 minutes plus tard est égale à 0,4.
\end{itemize}
Cette situation peut alors correspondre à un graphe dont une représentation est la suivante:
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\tikzset{LabelStyle/.style = {draw=brown,text=brown,fill=white,outer sep=3mm}}
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{Chambre}{Cuisine}%
{{0,3}}{{0,6}}%
{{0,7}}{{0,4}}%
\end{tikzpicture}
\end{center}
\end{exemple}

\section{Graphes et matrices}

\subsection{Matrice d'adjacence d'un graphe}

\begin{defin}
Soit $\mathcal{G}$ un graphe non pondéré, de sommets $S_k$, $1 \leqslant k \leqslant n$. 

La \textit{matrice d'adjacence} de $\mathcal{G}$ est la matrice $(a_{i,j})$, $1\leqslant i\leqslant n$ et $1\leqslant j\leqslant n$ telle que:
\begin{itemize}
\item s'il existe une arête allant de $S_i$ à $S_j$ alors $a_{i,j} = 1$;
\item sinon, $a_{i,j}=0$.
\end{itemize}
\end{defin}

\begin{exemple}
\begin{enumerate}
\item Graphe non orienté:

\medskip

\begin{minipage}{0.5\linewidth}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[L=$S_1$]{D}
\Vertex[x=3,y=2,L=$S_2$]{S}
\Vertex[x=7,y=1,L=$S_4$]{L}
\Vertex[x=1,y=-1,L=$S_3$]{A}
\Edge(D)(S)
\Edge(D)(L)
\Edge(A)(L)
\Edge(L)(S)
\end{tikzpicture}
\end{minipage}
\begin{minipage}{0.5\linewidth}
\[
\begin{pmatrix}
0 & 1 & 0 & 1\\
1 & 0 & 0 & 1\\
0 & 0 & 0 & 1\\
1 & 1 & 1 & 0
\end{pmatrix}
\]
\end{minipage}

\item Graphe orienté:


\begin{minipage}{0.5\linewidth}
\begin{tikzpicture}
\SetUpEdge[style={->}]
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=7,y=1]{L}
\Vertex[x=2,y=-1]{A}
\Edge(D)(S)\Edge(D)(A)\Edge(L)(D)\Edge(A)(S)\Edge(A)(L)
\Edge(S)(L)\Edge[style={bend right,->}](S)(D)
\end{tikzpicture}
\end{minipage}
\begin{minipage}{0.5\linewidth}
En convenant de classer les sommets dans cet ordre:
\begin{center}
D -- S -- A -- L
\end{center}
\[
\begin{pmatrix}
0 & 1 & 1 & 0\\
0 & 0 & 0 & 1\\
0 & 1 & 0 & 1\\
1 & 0 & 0 & 0
\end{pmatrix}
\]
\end{minipage}
\end{enumerate}
\end{exemple}

\begin{prop}
La matrice d'adjacence $(a_{i,j})_{\substack{1\leqslant i\leqslant n\\1\leqslant j\leqslant n}}$ d'un graphe non orienté d'ordre $n$ est symétrique: pour tous $i$ et $j$ compris entre 1 et $n$,
\[
a_{i,j} = a_{j,i}.
\]
\end{prop}

\begin{prop}
Soit $\mathcal{G}$ un graphe non pondéré d'ordre $n$ de matrice d'adjacence $A=(a_{i,j})_{\substack{1\leqslant i\leqslant n\\1\leqslant j\leqslant n}}$.

On note $S_k$ les sommets de $\mathcal{G}$.

\medskip

Le nombre de chaînes de longueur $k$ reliant $S_i$ à $S_j$ est le coefficient $c_{i,j}$ de la matrice $A^k$.
\end{prop}

\begin{exemple}
Reprenons l'exemple du graphe orienté précédent.
\[
A = \begin{pmatrix}
0 & 1 & 1 & 0\\
0 & 0 & 0 & 1\\
0 & 1 & 0 & 1\\
1 & 0 & 0 & 0
\end{pmatrix}
\qquad\text{et}\qquad
A^3 = \begin{pmatrix}
2 & 0 & 0 & 1\\
0 & 1 & 1 & 0\\
1 & \textcolor{red}{1} & 1 & 0\\
0 & 1 & 0 & 2
\end{pmatrix}.
\]
On en déduit alors qu'il existe une chaîne de longueur 3 reliant A à S.
\end{exemple}

$\blacktriangleright$ Voir l'exercice \ref{exercice:\thechapter.2}.

\subsection{Matrice d'un graphe pondéré ou probabiliste}

\begin{defin}
La matrice $(a_{i,j})_{\substack{1\leqslant i\leqslant n\\1\leqslant j\leqslant n}}$ d'un graphe pondéré ou probabiliste est la matrice telle que $a_{i,j}$ correspond à la pondération de l'arête reliant le sommet $i$ au sommet $j$.
\end{defin}

\begin{exemple}[graphe pondéré]
\begin{minipage}{0.66\linewidth}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=9,y=1]{L}
\Vertex[x=2,y=-2]{A}
\Edge[label=7,labelstyle={draw=brown,text=brown}](D)(S)
\Edge[label=3,labelstyle={draw=brown,text=brown}](D)(A)
\Edge[label=10,labelstyle={draw=brown,text=brown}](D)(L)
\Edge[label=5,labelstyle={draw=brown,text=brown}](A)(S)
\Edge[label=8,labelstyle={draw=brown,text=brown}](A)(L)
\Edge[label=3,labelstyle={draw=brown,text=brown}](L)(S)
\end{tikzpicture}
\end{minipage}
\begin{minipage}{0.33\linewidth}
En convenant d'ordonner les sommets de la manière suivante:
\begin{center}
D -- S -- A -- L
\end{center}
la matrice d'adjacence du graphe ci-contre est:
\[
\begin{pmatrix}
0 & 7 & 3 & 10\\
7 & 0 & 5 & 3\\
3 & 5 & 0 & 8\\
10 & 3 & 8 & 0
\end{pmatrix}
\]
\end{minipage}
\end{exemple}

\begin{exemple}[graphe probabiliste]
\begin{minipage}{0.66\linewidth}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\tikzset{LabelStyle/.style = {draw=brown,text=brown,fill=white,outer sep=3mm}}
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{Chambre}{Cuisine}%
{{0,3}}{{0,6}}%
{{0,7}}{{0,4}}%
\end{tikzpicture}
\end{minipage}
\begin{minipage}{0.33\linewidth}
En convenant d'ordonner les sommets du graphe ci-contre comme ceci:
\begin{center}
Chambre -- Cuisine
\end{center}
la matrice du graphe ci-contre est:
\[
\begin{pmatrix}
0,7&  0,3\\
0,6 & 0,4
\end{pmatrix}
\]
\end{minipage}
\end{exemple}

\bigskip

\begin{rem}[chaîne de Markov]
L'exemple \ref{exemple:\thechapter.12} illustre ce que l'on appelle une \textit{chaîne de Markov} à deux états: \og Chambre \fg{} et \og Cuisine \fg.

Dans un cas général, une chaîne de Markov est une suite d'événements $\suite{X}{n}{n\in\N}$ où chaque $X_n$ ne dépend que de $X_{n-1}$, pour $n>0$
\end{rem}

\begin{defin}[état stable]
Soit $\mathcal{G}$ un graphe probabiliste de matrice $M$.

L'\textit{état stable} du graphe est la matrice colonne $P=\begin{pmatrix}
x_1 & x_2 & \vdots & x_n\end{pmatrix}$ telle que $P = PM$, avec $\displaystyle\sum_{k=1}^n x_k=1$.
\end{defin}


\begin{exemple}
Reprenons le graphe de l'exemple \ref{exemple:\thechapter.12}.

L'état stable de ce graphe est la matrice $P=\begin{pmatrix}a & b\end{pmatrix}$ telle que: 
\begin{align*}
P=PM & \iff PI_2=PM\\
& \iff P(M-I_2) = 0\\
& \iff \begin{pmatrix}a & b\end{pmatrix}\begin{pmatrix}0,7-1 & 0,3\\0,6 & 0,4-1\end{pmatrix}=0\qquad,\qquad a+b=1\\
& \iff \begin{cases}
-0,3a +0,6b = 0\\
a+b=1
\end{cases}\\
& \iff \begin{cases}
a = \frac{2}{3}\\
b = \frac{1}{3}
\end{cases}
\end{align*}

L'état stable du graphe est donc $P = \begin{pmatrix}\frac{2}{3} & \frac{1}{3}\end{pmatrix}$.

\medskip

Cela signifie qu'à très termes, la probabilité que Louis soit dans sa chambre est égale à $\dfrac{2}{3}$.
\end{exemple}

\bigskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.3} à \ref{exercice:\thechapter.7}.


















%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercices
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Applications du cours}

\begin{exocor}{}
Soit $\mathcal{G}$ un graphe complet avec $n$ sommets. Dans chacun des cas suivants, donner le nombre d'arêtes.
\begin{enumerate}
\begin{multicols}{4}
\item $n=10$
\item $n=5$
\item $n=300$
\item $n=75$
\end{multicols}
\end{enumerate} 

\tcblower

On va ici appliquer la formule de la propriété \ref{prop:\thechapter.1}: $K_n=\dfrac{n(n-1)}{2}$, où $K_n$ est le nombre d'arêtes du graphe complet à $n$ sommets.
\begin{enumerate}
\item $n=10$ donc $K_{10}=\dfrac{10\times9}{2}=45$.

\medskip

\item $n=5$ donc $K_{5}=\dfrac{5\times4}{2}=10$.

\medskip

\item $n=300$ donc $K_{100}=\dfrac{100\times99}{2}=\numprint{4950}$.

\medskip

\item $n=75$ donc $K_{75}=\dfrac{75\times74}{2}=\numprint{2775}$.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{matrice d'adjacence}
Pour chacun des graphes suivants, donner la matrice d'adjacence correspondant à l'ordre indiqué des sommets, puis déterminer le nombre de chaînes de longueur $p$ demandé.
\begin{enumerate}
\item Ordre des sommets pour la matrice d'adjacence: A, B, C, D, E. Combien y a-t-il de chaînes de longueur 3 qui vont de $A$ à $E$?
\begin{center}
\begin{tikzpicture}[scale=0.75]
\SetUpEdge[style={->}]
\GraphInit[vstyle=Shade]
\Vertex{A}
\Vertex[x=3,y=2]{B}
\Vertex[x=7,y=1]{C}
\Vertex[x=2,y=-1]{D}
\Vertex[x=4,y=-2]{E}
\Loop[dir=WE](A)
\Edge(A)(B)
\Edge[style={bend right,->}](A)(E)
\Edge(A)(C)
\Edge(B)(D)
\Edge(B)(E)
\Edge(D)(E)
\Edge(E)(C)
\Edge(C)(D)
\Edge[style={bend right=10,->}](B)(C)
\Edge[style={bend right=10,->}](C)(B)
\end{tikzpicture}
\end{center}

\item Ordre des sommets pour la matrice d'adjacence: A, B, C, D, E. Combien y a-t-il de chaînes de longueur 3 qui vont de $C$ à $C$?
\begin{center}
\begin{tikzpicture}[scale=0.75]
\GraphInit[vstyle=Shade]
\Vertex{A}
\Vertex[x=3,y=2]{B}
\Vertex[x=7,y=1]{C}
\Vertex[x=2,y=-1]{D}
\Vertex[x=4,y=-2]{E}
\Loop[dir=WE](A)
\Edge(A)(B)
\Edge[style={bend right,->}](A)(E)
\Edge(A)(C)
\Edge(B)(D)
\Edge(B)(E)
\Edge(D)(E)
\Edge(E)(C)
\Edge(C)(D)
\Edge(B)(C)
\end{tikzpicture}
\end{center}
\end{enumerate}

\tcblower

\begin{enumerate}
\item La matrice d'adjacence est:
\[
M = \begin{pmatrix}
1 & 1 & 1 & 0 & 1\\
0 & 0 & 1 & 1 & 1\\
0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 0 & 0
\end{pmatrix}.
\]
On a alors :
\[
M^3 = \begin{pmatrix}
1 & 4 & 5 & 5 & \textcolor{red}{5}\\
0 & 1 & 2 & 2 & 2\\
0 & 1 & 2 & 1 & 1\\
0 & 1 & 0 & 1 & 0\\
0 & 0 & 1 & 1 & 2
\end{pmatrix}.
\]
Il y a donc 5 chaînes de longueur 3 qui vont de $A$ à $E$.

\bigskip

\item La matrice d'adjacence est:
\[
M = \begin{pmatrix}
1 & 1 & 1 & 0 & 1\\
1 & 0 & 1 & 1 & 1\\
1 & 1 & 0 & 1 & 1\\
0 & 1 & 1 & 0 & 1\\
1 & 1 & 1 & 1 & 0
\end{pmatrix}\text{ donc }
M^3 = \begin{pmatrix}
13 & 13 & 13 & 9 & 13\\
13 & 11 & 12 & 10 & 12\\
13 & 12 & \textcolor{red}{11} & 10 & 12\\
9 & 10 & 10 & 6& 10\\
13 & 12 & 12& 10 & 11
\end{pmatrix}
\]

\medskip

Il y a donc 11 chaînes de longueur 3 qui vont de $C$ à $C$.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{graphe probabiliste \& état stable}
Le jeu \og SimultTown Pro \fg{} permet à un joueur de gérer deux villes, désignées par la suite par les lettres A et B. Il peut, entre autre, gérer les flux migratoires des villes A et B.

Un joueur décide que chaque année :
\begin{itemize}
\item \pourcent{30} des habitants de la ville A déménagent pour aller dans la ville B;
\item \pourcent{10} des habitants de la ville B déménagent pour aller dans la ville A;
\item les autres habitants restent dans leur ville.
\end{itemize}

\begin{enumerate}
\item Compléter le graphe probabiliste suivant représentant la situation :

\vspace*{-1cm}
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\tikzset{LabelStyle/.style = {draw=brown,text=brown,fill=white,outer sep=3mm}}
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{A}{B}%
{{...}}{{...}}%
{{...}}{{...}}%
\end{tikzpicture}
\end{center}

\item \'Ecrire la matrice de transition M de ce graphe.

\item On suppose qu'il y a \numprint{150000} habitants dans la ville A et \numprint{350000} dans la ville B en début de partie.

À l'aide de votre calculatrice, déterminer le nombre d'habitants des villes A et B après 5 ans.

\item Déterminer l'état stable de ce graphe et interpréter ce résultat.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le graphe probabiliste représentant la situation est le suivant :
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\tikzset{LabelStyle/.style = {draw=brown,text=brown,fill=white,outer sep=3mm}}
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{A}{B}%
{{0,3}}{{0,1}}%
{{0,7}}{{0,9}}%
\end{tikzpicture}
\end{center}

\item La matrice de transition est : $M=\begin{pmatrix}0,7 & 0,3\\0,1 & 0,9\end{pmatrix}$.

\item On calcule : $\begin{pmatrix}
\numprint{150000} & \numprint{350000}
\end{pmatrix}M^5=\begin{pmatrix}
\numprint{126944} & \numprint{373056}
\end{pmatrix}$.

\medskip


\underline{Il y aura donc \numprint{126944} habitants dans la ville A et \numprint{373056} dans la ville B.}

\item L'état stable $P$ du graphe est tel que $P=PM$, soit $PI=PM$ (où $I$ est la matrice identité).

Alors, $PI-PM=0$ et donc $P(I-M)=0$.

\[
I-M=\begin{pmatrix}
1&0\\0&1
\end{pmatrix}-\begin{pmatrix}
0,7&0,3\\0,1&0,9
\end{pmatrix}=\begin{pmatrix}
0,3 & -0,3\\
-0,1 & 0,1
\end{pmatrix}
\]
Ainsi, en posant $P=\begin{pmatrix}
a & b
\end{pmatrix}$ avec $a+b=1$ :
\[
P(I-M)=0 \iff \begin{pmatrix}
a & b
\end{pmatrix}\begin{pmatrix}
0,3 & -0,3\\
-0,1 & 0,1
\end{pmatrix}=\begin{pmatrix}
0 & 0
\end{pmatrix}\qquad,\qquad a+b=1
\]
soit :
\begin{align*}
\begin{cases}
0,3a-0,1b=0\\
a+b=1
\end{cases} & \iff 
\begin{cases}
0,3a=0,1b\\
a+b=1
\end{cases}\\
& \iff
\begin{cases}
a=\dfrac{0,1b}{0,3}\\
a+b=1
\end{cases}\\
& \iff
\begin{cases}
a=\dfrac{1b}{3}\\
\dfrac{b}{3}+b=1
\end{cases}\\
& \iff
\begin{cases}
a=\dfrac{1b}{3}\\[10pt]
\dfrac{b}{3}+\dfrac{3b}{3}=\dfrac{3}{3}
\end{cases}
\end{align*}

\begin{align*}
\begin{cases}
0,3a-0,1b=0\\
a+b=1
\end{cases} & \iff
\begin{cases}
a=\dfrac{1b}{3}\\[10pt]
4b=3
\end{cases}\\
& \iff
\begin{cases}
a=\dfrac{1}{3}b\\[10pt]
b=\dfrac{3}{4}
\end{cases}\\
& \iff
\begin{cases}
a=\dfrac{1}{3}\times\dfrac{3}{4}=\dfrac{1}{4}\\[10pt]
b=\dfrac{3}{4}
\end{cases}
\end{align*}

L'état stable du graphe est donc $\begin{pmatrix}
0,25 & 0,75
\end{pmatrix}$, ce qui signifie qu'à longs termes, un quart de la population totale des deux villes se trouvera dans la ville A et les autres dans la villes B.

La population totale des deux villes est $\numprint{150000}+\numprint{350000}=\numprint{500000}$ habitants et\linebreak
 $\numprint{500000}\div4=\numprint{125000}$.

\medskip

\underline{Donc \numprint{125000} habitants seront dans la ville A et \numprint{375000} seront dans la ville B.}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{graphe probabiliste}
Deux opérateurs Alpha et Bravo se partagent le marché de la téléphonie mobile dans un pays.

En 2015, l'opérateur Alpha possède 30\,\% du marché de téléphonie mobile. Le reste appartient à l'opérateur Bravo.

On étudie l'évolution dans le temps du choix des abonnés de 2015 pour l'un ou l'autre des opérateurs. Chaque abonné conserve un abonnement téléphonique, soit chez l'opérateur Alpha soit chez l'opérateur Bravo.

On estime que, chaque année :

\begin{itemize}
\item  12\,\% des abonnés de l'opérateur Alpha le quittent et souscrivent un abonnement chez l'opérateur Bravo.
\item  86\,\% des abonnés de l'opérateur Bravo lui restent fidèles, les autres le quittent pour l'opérateur Alpha.
\end{itemize}

\smallskip

On modélise cette situation par un graphe probabiliste à deux sommets Alpha et Bravo :

\begin{itemize}
\item  $A$ est l'événement: \og l'abonné est chez l'opérateur Alpha \fg{} ;
\item $B$ est l'événement: \og l'abonné est chez l'opérateur Bravo \fg.
\end{itemize}

\medskip

\begin{enumerate}
\item Dessiner ce graphe probabiliste.
\end{enumerate}


On admet que la matrice de transition de ce graphe probabiliste, en considérant les sommets dans l'ordre alphabétique, est : $M = \begin{pmatrix}0,88&0,12\\0,14 &0,86\end{pmatrix}$.

On note pour tout entier naturel $n$ :

\begin{itemize}
\item  $a_n$ la probabilité qu'un abonné soit chez l'opérateur Alpha l'année $2015 + n$ ;
\item  $b_n$ la probabilité qu'un abonné soit chez l'opérateur Bravo l'année $2015 + n$.
\end{itemize}

On note $P_n = \begin{pmatrix}a_n& b_n\end{pmatrix}$ la matrice ligne de l'état probabiliste pour l'année $2015 + n$.

\begin{enumerate}[resume]
\item Donner $a_0$ et $b_0$.

\item Montrer qu'en 2018, il y aura environ 44,2\,\% des abonnés chez l'opérateur Alpha.


\item Les deux opérateurs voudraient connaître la répartition de l'ensemble des abonnés sur le long terme. On note $P = \begin{pmatrix}x &y\end{pmatrix}$ l'état stable de la répartition des abonnés.
	\begin{enumerate}
		\item Montrer que les nombres $x$ et $y$ sont solutions du système $\begin{cases}
0,12x - 0,14y = 0\\
		x + y = 1.
		\end{cases}$
		
		
		\item Résoudre le système précédent dans l'ensemble des réels.
		
		\item Déterminer la répartition des abonnés entre les deux opérateurs au bout d'un grand nombre d'années. Arrondir les pourcentages à 0,1\,\%.
		
	\end{enumerate}
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le graphe représentant la situation est le suivant:
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\tikzset{LabelStyle/.style = {draw=brown,text=brown,fill=white,outer sep=3mm}}
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{A}{B}%
{{0,12}}{{0,14}}%
{{0,88}}{{0,86}}%
\end{tikzpicture}
\end{center}

\item D'après l'énoncé, $a_0=\begin{pmatrix}0,3 & 0,7\end{pmatrix}$.

Alors,
\[
\begin{pmatrix}a_1 & b_1\end{pmatrix}=\begin{pmatrix}0,3 & 0,7
\end{pmatrix}\begin{pmatrix}0,88&0,12\\0,14 &0,86\end{pmatrix}=\begin{pmatrix}0,362 & 0,638\end{pmatrix}.
\]


\item On a :
\[
P_3=P_0\times M^3=\begin{pmatrix}0,4418 & 0,5582\end{pmatrix}
\]
Ainsi, en $2015+3=2018$, il y aura bien \pourcent{44,2} d'abonnés chez l'opérateur Alpha.


\item 
\begin{enumerate}
\item $x$ et $y$ sont deux probabilités dont la somme doit être égale à 1 car nous ne considérons pas d'autres opérateurs ; donc $\boxed{x+y=1}$.
		De plus, l'état stable est défini par l'égalité :
		\[
		P=PM\qquad\text{donc}\qquad\begin{pmatrix}
		x & y		\end{pmatrix}=\begin{pmatrix}
	x & y		\end{pmatrix}\begin{pmatrix}
	0,88 & 0,12\\0,14 & 0,86
	\end{pmatrix}
	\]
	soit :
	\[
	\begin{pmatrix}
	x & y
	\end{pmatrix}=\begin{pmatrix}
	0,88x+0,14y & 0,12x+0,86y
	\end{pmatrix}\qquad\text{et donc}\qquad\begin{cases}
	x=0,88x+0,14y\\
	y=0,12x+0,86y
	\end{cases}
	\]
	En mettant $x$ et $y$ à droite des signes \og $=$ \fg, on obtient :
	\[
	\begin{cases}
	0=(0,88-1)x+0,14y\\
	0=0,12x+(0,86-1)y
	\end{cases}
	\]
	La deuxième équation donne : $\boxed{0,12x-0,14y=0}$.
	
	Les deux équations encadrées donnent bien le système demandé.
	
\item Le système s'écrit de façon matricielle ainsi :
		\[
		AX=B\qquad,\qquad A=\begin{pmatrix}0,12 & -0,14\\1 & 1		\end{pmatrix}\quad,\quad X=\dbinom{x}{y}\quad,\quad B=\dbinom{0}{1}
		\]
		donc :
		\[
		X=A^{-1}B\approx\dbinom{0,538}{0,462}
		\]

\item De la question précédente, on déduit qu'à longs termes, \pourcent{53,8} des abonnés seront chez Alpha, et \pourcent{46,2} seront chez Bravo.
\end{enumerate}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{graphe probabiliste}
Les sites internet A, B, C ont des liens entre eux. Un internaute connecté sur un de ces trois sites peut, à toutes les minutes, soit y rester soit utiliser un lien vers un des deux autres sites.

\begin{itemize}
\item Pour un internaute connecté sur le site A, la probabilité d'utiliser le lien vers B est de 0,2 et celle d'utiliser le lien vers C est de 0,2.
\item Pour un internaute connecté sur le site B, la probabilité d'utiliser le lien vers A est de 0,1 et celle d'utiliser le lien vers C est de 0,4.
\item Pour un internaute connecté sur le site C, la probabilité d'utiliser le lien vers A est de 0,2 mais il n'y a pas de lien direct avec B.
\end{itemize}

L'unité de temps est la minute, et à un instant $t = 0$, le nombre de visiteurs est, respectivement sur les sites A, B et C : 100, 0 et 0.

On représente la distribution des internautes sur les trois sites après $t$ minutes par une matrice $N_t$; ainsi, $N_0 = \begin{pmatrix}100 & 0 & 0 \end{pmatrix}$.

On suppose qu'il n'y a ni déconnexion pendant l'heure (de $t = 0$ à $t = 60$) ni nouveaux internautes visiteurs.

\begin{enumerate}
\item Représenter le graphe probabiliste de sommets A, B et C correspondant à la situation décrite.
\item Écrire la matrice $M$ de transition associée à ce graphe (dans l'ordre A, B, C).
\item On donne:
\[
M^2 = \begin{pmatrix}
0,42 & 0,22 & 0,36\\
0,19 & 0,27 & 0,54\\
0,28 & 0,04 & 0,68
\end{pmatrix}
\qquad\text{et}\qquad
M^{20} \approx \begin{pmatrix}
0,3125& 0,125& 0,5625\\
0,3125 &0,125& 0,5625\\
0,3125& 0,125& 0,5625
\end{pmatrix}.
\]
Calculer $N_2$. Interpréter le résultat obtenu.
\item Calculer $N_0 \times M^{20}$. Conjecturer la valeur de l'état stable et interpréter la réponse.
\item Un des internautes transmet un virus à tout site qu'il visitera.

Il se connecte initialement sur le site C et commence sa navigation.

À l'instant $t = 0$, le site C est donc infecté.
\begin{enumerate}
\item Quelle est la probabilité qu'à l'instant $t = 1$ le site A soit infecté ?
\item Quelle est la probabilité qu'à l'instant $t = 2$ les trois sites soient infectés ?
\end{enumerate}
\end{enumerate}

\tcblower

\begin{enumerate}
\item On a le graphe suivant :
\begin{center}
\tikzset{%
	fleche/.style args={#1}{%
		postaction = decorate,%
		decoration={%
			name=markings,
    		mark=at position #1 with {\arrow[scale=2]{>}}
    	}
	}
}
\begin{tikzpicture}
\coordinate (A) at (0,0);
\coordinate (B) at (4,0);
\coordinate (C) at (60:4);
% A -> C
\draw[fleche=0.5] (A) to[bend left=30] (C);
\node[above left] at ($0.5*(A)+0.5*(C)+(-.5,.5)$) {0,2};
% A -> B
\draw[fleche=0.5] (A) to[bend right=30] (B);
\node[below] at ($0.5*(A)+0.5*(B)+(0,-1)$) {0,2};
% B -> C
\draw[fleche=0.5] (B) to[bend right=30] (C);
\node[above right] at ($0.5*(B)+0.5*(C)+(.5,.5)$) {0,4};
% C -> A
\draw[fleche=0.5] (C) to[bend left=30] (A);
\node[right] at ($0.5*(A)+0.5*(C)+(0.6,0)$) {0,2};
% B -> A
\draw[fleche=0.5] (B) to[bend right=30] (A);
\draw[fleche=0.5,yscale=15,xscale=3] (A.west) to[loop left] (A.west);
\node[above] at ($0.5*(B)+0.5*(A)+(0,0.5)$) {0,1};
\node at ($(A.west)+(-1.6,0)$) {0,6};
\node[circle,draw,fill=white] at (A) {A};
\node[circle,draw,fill=white] at (B) {B};
\node[circle,draw,fill=white] at (C) {C};
\end{tikzpicture}
\end{center}

\item La matrice $M$ de transition est alors :
\[
M=\begin{pmatrix}
0,6 & 0,2 & 0,2\\
0,1 & 0,5 & 0,4\\
0,2 & 0   & 0,8
\end{pmatrix}
\]

\item $N_2=N_0M^2=\begin{pmatrix}100 & 0 & 0\end{pmatrix}\begin{pmatrix}
0,42 & 0,22 & 0,36\\
0,19 & 0,27 & 0,54\\
0,28 & 0,04 & 0,68
\end{pmatrix}=\begin{pmatrix}42 & 22 & 36\end{pmatrix}$.

Cela signifie qu'après 2 minutes, il y a 42 internautes sur le site A, 22 sur le site B et 36 sur le site C.

\item $N_0\times M^{20}\approx\begin{pmatrix}31,25 & 12,5 & 56,25\end{pmatrix}=N_{20}$.

\og 20 \fg{}  est assez grand pour que l'on puisse assimiler $N_{20}$ à l'état stable.

Cela signifie alors qu'à long terme, il y aura \pourcent{31,25} des internautes sur le site A, \pourcent{12,5} sur le site B et \pourcent{56,25} sur le site C (quel que soit le nombre d'internautes au départ).

\item
\begin{enumerate}
\item D'après le graphe, la probabilité de passer de C à A  en 1 minute est égale à 0,2.

Ainsi, la probabilité pour qu'à l'instant $t=1$ le site A soit infecté est égale à 0,2.

\item Pour que les trois sites soient infectés, il faut que l'internaute utilise le chemin $C \rightarrow B\rightarrow A$ (ce qui est impossible car il ne peut pas passer de C à B) ou le chemin $C \rightarrow A \rightarrow B$, avec une probabilité de $0,2\times0,2=0,04$.

\medskip

La probabilité pour que les 3 sites soient infectés à l'instant $t=2$ est égale à 0,04.
\end{enumerate}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Alice participe à une compétition de tir à l'arc ; elle effectue plusieurs lancers de flèches. Lorsqu'elle atteint la cible à un lancer, la probabilité qu'elle atteigne la cible au lancer suivant est égale à 0,9.

Lorsqu'elle a manqué la cible à un lancer, Alice se déconcentre et la probabilité qu'elle atteigne la cible au lancer suivant est égale à 0,4. 

On suppose qu'au premier lancer, elle a autant de chances d'atteindre la cible que de la manquer. Pour tout nombre entier naturel $n$ strictement positif, on note :  

\begin{itemize}
\item $a_n$ la probabilité qu'Alice atteigne la cible au $n$-ième lancer ; 
\item $b_n$ la probabilité qu'Alice manque la cible au $n$-ième lancer ;
\item $P_n=\begin{pmatrix}a_n & b_n\end{pmatrix}$ la matrice ligne traduisant l'état probabiliste au $n$-ième lancer.
\end{itemize}

\begin{enumerate}
\item
\begin{enumerate}
\item Représenter la situation par un graphe probabiliste de sommets A et B (A représentant l'état « Alice atteint la cible » et B l'état « Alice manque sa cible »). 
\item Indiquer la matrice de transition M associée à ce graphe. On prendra les sommets A  et B dans l'ordre (A, B).
\item Justifier que $P_1=\begin{pmatrix}0,5&0,5\end{pmatrix}$ et $P_2=\begin{pmatrix}0,65& 0,35\end{pmatrix}$.
\end{enumerate}

\item
\begin{enumerate}
\item  Montrer que, pour tout nombre entier $n$ strictement positif, $a_{n+1}=0,9a_n+0,4b_n$. 
\item En déduire que, pour tout nombre entier $n$ strictement positif, $a_{n+1}=0,5a_n+0,4$.
\end{enumerate}

\item
\begin{enumerate}
\item Compléter le programme fourni en annexe (page suivante) de façon à ce qu'il affiche l'état probabiliste  au $n$-ième lancer.

\item Déterminer l'affichage de cet algorithme pour $n=5$.
\end{enumerate}

\item 
\begin{enumerate}
\item On considère la suite \suite{u}{n}{} définie pour tout nombre entier naturel $n$ strictement positif  par : $u_n=a_n-0,8$.

Montrer que la suite \suite{u}{n}{} est une suite géométrique dont on précisera la raison et le  premier terme. 

\item Donner l'expression de $u_n$ en fonction de $n$, puis en déduire que pour tout nombre entier naturel $n$ strictement positif, $a_n=0,8-0,3\times0,5^{n-1}$.
\item À long terme, que peut-on penser de la probabilité qu'Alice atteigne la cible ?
\item Par quelle autre méthode aurait-on pu trouver le résultat précédent ?
\end{enumerate}
\end{enumerate}

\textbf{Programme à compléter:}

\medskip

\begin{python}
def stable(n):
    a = 0.5
    b = 0.5
    for i in range(2,n+1):
        a = ...
        b = ...
        
    return a,b
\end{python}

\tcblower

\begin{enumerate}
\item 
\begin{enumerate}
\item Le graphe probabiliste est le suivant :

\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\tikzset{LabelStyle/.style = {draw=brown,text=brown,fill=white,outer sep=3mm}}
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{A}{B}%
{{0,1}}{{0,4}}%
{{0,9}}{{0,6}}%
\end{tikzpicture}
\end{center}

\item La matrice de transition M associé au graphe est :
\[
\text{M}=\begin{pmatrix}0,9 & 0,1\\0,4 & 0,6\end{pmatrix}
\]

\item Au premier lancer,Alice a autant de chances d'atteindre sa cible que de la manquer ; ainsi, $a_1=b_1=0,5$ donc $P_1=\begin{pmatrix}0,5 & 0,5\end{pmatrix}$.

\begin{align*}
P_2 & =P_1M\\
& =\begin{pmatrix}0,5 & 0,5\end{pmatrix}\begin{pmatrix}0,9 & 0,1\\0,4 & 0,6\end{pmatrix}\\
& =\begin{pmatrix}
0,5\times0,9+0,5\times0,4 & 
0,5\times0,1+0,5\times0,6
\end{pmatrix}\\
P_2 & = \begin{pmatrix}0,65 & 0,35\end{pmatrix}
\end{align*}
\end{enumerate}

\item
\begin{enumerate}
\item Pour tout entier naturel $n$, on a :
\[ P_{n+1}=P_nM\]
d'où :
\[ P_{n+1}=\begin{pmatrix}a_n & b_n\end{pmatrix}\begin{pmatrix}0,9 & 0,1\\0,4 & 0,6\end{pmatrix}\]
Ainsi,
\[
P_{n+1}=\begin{pmatrix}
0,9a_n+0,4b_n & 0,1a_n+0,6b_n
\end{pmatrix}
\]
Le premier coefficient de $P_{n+1}$ étant $a_{n+1}$, on a bien :
\[ a_{n+1}=0,9a_n+0,4b_n.\]

\item On sait que $a_n+b_n=1$, donc $b_n=1-a_n$. Ainsi, la relation trouvée précédemment donne :
\begin{align*}
a_{n+1} & = 0,9a_n+0,4b_n\\
& = 0,9a_n+0,4(1-a_n)\\
& = 0,9a_n+0,4-0,4a_n\\
\Aboxed{a_{n+1}& = 0,5a_n+0,4}
\end{align*} 
\end{enumerate}

\item
\begin{enumerate}
\item On a l'algorithme complété suivant :

\begin{python}
def stable(n):
    a = 0.5
    b = 0.5
    for i in range(2,n+1):
        a = 0.5 * a + 0.4
        b = 1 - a
        
    return a,b
\end{python}

\item Pour $n=5$, l'algorithme affiche $a=\numprint{0,78125}$ et $b=\numprint{0,21875}$.
\end{enumerate}

\item
\begin{enumerate}
\item $\begin{aligned}[t]
u_{n+1} & = a_{n+1}-0,8\\
& = 0,5a_n+0,4-0,8\\
& = 0,5a_n-0,4\\
& = 0,5(a_n-0,8)\\
& = 0,5u_n
\end{aligned}$

Cette dernière relation de récurrence montre que \suite{u}{n}{} est géométrique de raison $q=0,5$.

Son premier terme est $u_1=a_1-0,8=0,5-0,8=-0,3$.

\item D'après le cours, $u_n=u_1\times q^{n-1}$, donc $u_1=-0,3\times0,5^{n-1}$.

$u_n=a_n-0,8$ donc $a_n=u_n+0,8$, c'est-à-dire \underline{$a_n=0,8-1,3\times0,5^{n-1}$}.

\item $\limite{n}{+\infty}{0,5^{n-1}}=0$ car $0<0,5<1$. Ainsi, $\limite{n}{+\infty}{a_n}=0,8$.

\`A long terme, on peut donc penser qu'il y a 8 chances sur 10 pour qu'Alice atteigne la cible.\label{rep}

\item On aurait pu chercher l'état stable $P_\infty=\begin{pmatrix}a & b\end{pmatrix}$ tel que :
\[ P_\infty = P_\infty M.\]
\[ \begin{pmatrix}a & b \end{pmatrix}=\begin{pmatrix}
a & b\end{pmatrix}\begin{pmatrix}0,9 & 0,1\\0,4 & 0,6
\end{pmatrix}
\]
On arrive alors au système :
\[
\begin{cases}
a & = 0,9a+0,4b\\
b & = 0,1a+0,6b
\end{cases}
\]

Le deux équations sont équivalentes en théorie ; on doit donc remplacer l'une d'elles (par exemple la deuxième) par l'équation : $b = 1-a$, ce qui donne :

\[
\begin{cases}
0,1a & =0,4(1-a)\\
b & = 1-a
\end{cases}
\qquad\text{soit:}\qquad
\begin{cases}
0,5a & = 0,4\\
b & = 1-a
\end{cases}
\]

La première équation donne alors $a=0,8$, ce qui correspond au résultat trouvé à la question \ref{rep}.
\end{enumerate}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Une région se divise en deux zones :

\medskip

\begin{itemize}
\item[$\bullet$] une zone A à proximité d'une grande agglomération
\item[$\bullet$] une zone B à proximité de la mer
\end{itemize}

\medskip

Chaque année, 20\% des habitants de la zone A partent habiter dans la zone B pour avoir un meilleur cadre de vie, et 5\% des habitants de la zone B partent habiter dans la zone A pour se rapprocher de leur lieu de travail.

\medskip

On sait de plus qu'en 2010, 40\% de la population habitait dans la zone A.\\
On suppose que le nombre total d'habitants de la région reste constant au cours du temps.

\medskip

Pour tout entier naturel $n$, l'état probabiliste correspondant à l'année $2010+n$ est défini par la matrice ligne $P_n=\begin{pmatrix}a_n & b_n\end{pmatrix}$, où $a_n$ et $b_n$ désignent respectivement les proportions d'habitants des zones A et B.

\medskip

\begin{enumerate}
\item Déterminer la matrice ligne $P_0$ de l'état initial.
\item Représenter la situation par un graphe probabiliste de sommets A et B.
\item
\begin{enumerate}
\item \'Ecrire la matrice de transition $M$ de ce graphe en respectant l'ordre alphabétique des sommets.
\item Donner la répartition de la population en 2012.
\end{enumerate}

\item Dans la question suivante, on considère la matrice ligne $P=\begin{pmatrix}a & b\end{pmatrix}$ où $a$ et $b$ sont deux nombres réels tels que $a+b=1$.
\begin{enumerate}
\item Déterminer $a$ et $b$ pour que $P=PM$.
\item Les infrastructures de la zone B permettent d'accueillir au maximum 75\% de la population. Lors d'un conseil municipal, le maire affirme qu'il va falloir prévoir de nouvelles infrastructures. A-t-il raison ?
\end{enumerate}
\end{enumerate}

\tcblower

\begin{enumerate}
\item D'après l'énoncé, $P_0=\begin{pmatrix}0,4 & 0,6\end{pmatrix}$.\\
En effet, en 2010, 40\% de la population était dans la zone A, ce qui correspond à une proportion de 0,4.

\item Le graphe est le suivant :

\vspace*{-1cm}
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\tikzset{LabelStyle/.style = {draw=brown,text=brown,fill=white,outer sep=3mm}}
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{A}{B}%
{{0,2}}{{0,05}}%
{{0,8}}{{0,95}}%
\end{tikzpicture}
\end{center}

\item 
\begin{enumerate}
\item La matrice de transition est : $M=\begin{pmatrix}0,8 & 0,2\\0,05 & 0,95\end{pmatrix}$.
\item La répartition de la population en 2012 est donnée par $P_2$.
\[ P_1 = P_0M = \begin{pmatrix}0,4 & 0,6\end{pmatrix}\begin{pmatrix}0,8 & 0,2\\0,05 & 0,95\end{pmatrix} = \begin{pmatrix}0,35 & 0,65\end{pmatrix}
\]
\[ P_2 = P_1M = \begin{pmatrix}0,35 & 0,65\end{pmatrix}\begin{pmatrix}0,8 & 0,2\\0,05 & 0,95\end{pmatrix} = \begin{pmatrix}0,3125 & 0,6875\end{pmatrix}
\]
\underline{Ainsi, 31,25\% de la population habitera en zone A et 68,75\% en zone B.}
\end{enumerate}
\item 
\begin{enumerate}
\item 
On a :
\begin{align*}
P=PM & \iff \begin{pmatrix}a & b\end{pmatrix}=\begin{pmatrix}a & b\end{pmatrix}\begin{pmatrix}0,8 & 0,2\\0,05 & 0,95\end{pmatrix}\\
& \iff \begin{pmatrix}a & b\end{pmatrix}=\begin{pmatrix}0,8a+0,05b & 0,2a+0,95b\end{pmatrix}
\end{align*}
Ainsi: 
\[ 
\left\lbrace
\begin{array}{l}
0,8a+0,05b = a\\
0,2a+0,95b=b
\end{array}
\right.
\]
Soit : $ 0,05b=0,2a$. Donc : $b=4a \qquad (1)$.\\

De plus, \[ a+b=1 \iff a=1-b. \]

Ainsi : \[ (1) \iff b=4(1-b)\;, \]
d'où : \[
b=4-4b.\]
On a alors :
\[ b = \frac{4}{5} \qquad \text{et donc} \qquad a = \frac{1}{5}.\]
Finalement, on a : \[\boxed{P = \begin{pmatrix}0,2 & 0,8\end{pmatrix}}\]

\item Le maire a en effet raison de prévoir de nouvelles infrastructures car la proportion d'habitants dans la zone B se rapprochera des 80\%.
\end{enumerate}
\end{enumerate}

\vspace*{5cm}~
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Exercices divers}

\begin{exocor}{}
Voici le plan de deux maisons:

\medskip

\begin{minipage}{.5\textwidth}
\begin{center}
\begin{tikzpicture}
\draw (0,0) rectangle +(6,4);
\draw (0,2) -- (6,2);
\draw (2,0) -- (2,2);
\draw (4,0) -- (4,2);
\draw (3,2) -- (3,4);
\fill[pageenonce!30] (1.9,.75) rectangle+(.2,.5);
\fill[pageenonce!30] (3.9,.75) rectangle+(.2,.5);
\fill[pageenonce!30] (2.9,2.75) rectangle+(.2,.5);
\fill[pageenonce!30] (.75,1.9) rectangle+(.5,.2);
\fill[pageenonce!30] (4.75,1.9) rectangle+(.5,.2);
\fill[pageenonce!30] (2.25,1.9) rectangle+(.5,.2);
\fill[pageenonce!30] (3.25,1.9) rectangle+(.5,.2);
\node[gray] at (1,1) {\Large A};
\node[gray] at (3,1) {\Large B};
\node[gray] at (5,1) {\Large C};
\node[gray] at (1.5,3) {\Large E};
\node[gray] at (4.5,3) {\Large D};
\end{tikzpicture}

Maison 1
\end{center}
\end{minipage}
\begin{minipage}{.5\textwidth}
\begin{center}
\begin{tikzpicture}
\draw (0,0) rectangle +(6,4);
\draw (0,2) -- (6,2);
\draw (2,0) -- (2,2);
\draw (4,0) -- (4,2);
\draw (3,2) -- (3,4);
\fill[pageenonce!30] (1.9,.75) rectangle+(.2,.5);
\fill[pageenonce!30] (3.9,.75) rectangle+(.2,.5);
\fill[pageenonce!30] (2.9,2.75) rectangle+(.2,.5);
\fill[pageenonce!30] (.75,1.9) rectangle+(.5,.2);
\fill[pageenonce!30] (4.75,1.9) rectangle+(.5,.2);
\fill[pageenonce!30] (2.25,1.9) rectangle+(.5,.2);
\fill[pageenonce!30] (3.25,1.9) rectangle+(.5,.2);
\fill[pageenonce!30] (1.25,3.9) rectangle+(.5,.2);
\fill[pageenonce!30] (4.25,3.9) rectangle+(.5,.2);
\fill[pageenonce!30] (.75,-.1) rectangle+(.5,.2);
\fill[pageenonce!30] (2.75,-.1) rectangle+(.5,.2);
\fill[pageenonce!30] (4.75,-.1) rectangle+(.5,.2);
\fill[pageenonce!30] (-.1,.75) rectangle+(.2,.5);
\fill[pageenonce!30] (-.1,2.75) rectangle+(.2,.5);
\fill[pageenonce!30] (5.9,.75) rectangle+(.2,.5);
\fill[pageenonce!30] (5.9,2.75) rectangle+(.2,.5);
\node[gray] at (1,1) {\Large A};
\node[gray] at (3,1) {\Large B};
\node[gray] at (5,1) {\Large C};
\node[gray] at (1.5,3) {\Large E};
\node[gray] at (4.5,3) {\Large D};
\end{tikzpicture}

Maison 2
\end{center}
\end{minipage}

\bigskip

Donner un graphe représentant ces deux maisons, où les arêtes représentent un passage d'une pièce à l'autre.

\tcblower

\begin{minipage}[t][][t]{.48\textwidth}
\textbf{Maison 1.} Le graphe est le suivant :

\begin{center}
\begin{tikzpicture}[every node/.style={draw,circle,inner sep=3pt}]
\node (A) at (0,0) {A};
\node (B) at (2,0) {B};
\node (C) at (4,0) {C};
\node (D) at (3,2) {D};
\node (E) at (1,2) {E};
\draw (A) -- (B) -- (C) -- (D) -- (E) -- (A);
\draw (B) -- (E);
\draw (B) -- (D);
\end{tikzpicture}
\end{center}
\end{minipage}
\hfill
\begin{minipage}[t][][t]{.48\textwidth}
\textbf{Maison 2.} Le graphe est le suivant :

\begin{center}
\begin{tikzpicture}[every node/.style={draw,circle,inner sep=3pt}]
\node (A) at (0,0) {A};
\node (B) at (2,0) {B};
\node (C) at (4,0) {C};
\node (D) at (3,2) {D};
\node (E) at (1,2) {E};
\draw (A) -- (B) -- (C) -- (D) -- (E) -- (A);
\draw (B) -- (E) -- (C);
\draw (B) -- (D);
\draw (A) -- (D);
\draw (A.south) to[bend right=60] (C.south);
\draw[yscale=10,xscale=2] (A.west) to[loop left] (A.west);
\draw[yscale=2,xscale=5] (B.south) to[loop below] (B.south);
\draw[yscale=10,xscale=2] (C.east) to[loop right] (C.east);
\draw[yscale=2,xscale=5] (D.north) to[loop above] (D.north);
\draw[yscale=2,xscale=5] (E.north) to[loop above] (E.north);
\end{tikzpicture}
\end{center}
\end{minipage}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{les ponts de Königsberg}
La ville de K\"onigsberg (aujourd'hui Kaliningrad) est construite autour de deux \^iles situ\'ees sur le Pregel et reli\'ees entre elles par un pont. Six autres ponts relient les rives de la rivi\`ere \`a l'une ou l'autre des deux \^iles, comme repr\'esent\'es sur le dessin ci-dessuus. 

Représenter par un graphe la situation, où les arêtes représentent le passage d'une berge à l'autre.

\begin{center}
\includegraphics[scale=0.25]{img/graphes-pont_konigsberg.png}
\end{center}

\tcblower

Repr\'esentons cette situation \`a l'aide d'un graphe o\`u les parties de terre seront repr\'esent\'ees par des sommets et o\`u les ponts seront repr\'esent\'es par des ar\^etes :
\begin{center}
\begin{tikzpicture}[scale=2]
\GraphInit[vstyle=Shade]
\tikzset{VertexStyle/.style = {draw,
shape = circle,
shading = ball,
ball color = brown,
minimum size = 24pt,
color = white}}
\tikzset{EdgeStyle/.style = {thick,double = brown,double distance = 1pt}}
\Vertex{A}
\SOWE(A){B}
\SOEA(A){C}
\SOWE(C){D}
\Edge(B)(C)
\Edge(C)(A)
\Edge(D)(C)
\tikzset{EdgeStyle/.append style = {bend left}}
\Edge(A)(B)
\Edge(B)(D)
\tikzset{EdgeStyle/.append style = {bend right}}
\Edge(A)(B)
\Edge(B)(D)
\end{tikzpicture}
\end{center}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Un parc est composé de 7 attractions principales A, B, C, D, E, F et G. 

Le graphe ci-dessous représente les liaisons entre elles :
\begin{center}
\begin{tikzpicture}[scale=2]
\GraphInit[vstyle=Shade]
\tikzset{VertexStyle/.style = {draw,
shape = circle,
shading = ball,
ball color = brown,
minimum size = 24pt,
color = white}}
\tikzset{EdgeStyle/.style = {thick,double = brown,double distance = 1pt}}
\Vertex{A}
\Vertex[x=-1,y=1]{C}
\Vertex[x=-2,y=-1]{B}
\Vertex[x=2,y=-0.5]{D}
\Vertex[x=3,y=0]{G}
\Vertex[x=4,y=-1]{F}
\Vertex[x=2.5,y=-1.5]{E}
\Edges(A,C,B,A,D,B,E,D,C,G,E,F,G)
\Edge(D)(G)
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item Ce graphe est-il complet ?
\item Quel est l'ordre de ce graphe ?
\item \'Ecrire la matrice d'adjacence de ce graphe (en ordonnant les sommets dans l'ordre alphabétique).
\item \`A l'aide de votre calculatrice, trouver le nombre de chemins de longueur 3 reliant E \`a C.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Un graphe est \textit{complet} s'il est simple (sans double liaison entre deux même sommets) et si tous les sommets peuvent être reliés deux à deux.

Ce n'est pas le cas ici car B n'est pas relié à G par exemple.

\medskip

\uline{Ce graphe n'est donc pas complet.}

\item L'ordre d'un graphe est le nombre de sommets du graphe. 

Donc ici, \uline{l'ordre du graphe est égal à 7}.

\item La matrice d'adjacence du graphe est la suivante :
\[
M=\begin{pmatrix}
0 & 1 & 1 & 1 & 0 & 0 & 0\\
1 & 0 & 1 & 1 & 1 & 0 & 0\\
1 & 1 & 0 & 1 & 0 & 0 & 1\\
1 & 1 & 1 & 0 & 1 & 0 & 1\\
0 & 1 & 0 & 1 & 0 & 1 & 1\\
0 & 0 & 0 & 0 & 1 & 0 & 1\\
0 & 0 & 1 & 1 & 1 & 1 & 0
\end{pmatrix}
\]

\item La calculatrice nous donne :
\[
M^3=\begin{pmatrix}
6 & 9 & 9 & 11 & 6 & 4 & 6\\
9 & 8 & 12 & 12 & 11 & 4 & 7\\
9 & 12 & 8 & 12 & \color{violet} 7 & 4 & 11\\
11 & 12 & 12 & 12 & 12 & 4 & 12\\
6 & 11 &\color{violet} 7 & 12 & 6 & 6 & 10\\
4 & 4 & 4 & 4 & 6 & 2 & 6\\
6 & 7 & 11 & 12 & 10 & 6 & 6
\end{pmatrix}
\]
Ainsi, il y a 7 chemins de longueur 3 reliant E \`a C.

\paragraph*{Rappel.} Le coefficient de $M^n$ situ\'e \`a la $i$-\`eme ligne et $j$-\`eme colonne (ou \`a la $j$-\`eme ligne et $i$-\`eme colonne) est le nombre de chemins de longueur $n$ reliant les sommets ayant pour position $i$ et $j$ dans la matrice d'adjacence.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Voici la carte de l'Union Europ\'eenne (U.E.) en 2017 :
\begin{center}
\includegraphics[scale=.8]{img/graphes-carteUE.png}
\end{center}
On d\'esire construire un graphe o\`u les sommets sont les pays suivants : France, Portugal, Espagne, Belgique, Luxembourg, Italie, Allemagne, Tch\`equie,  et o\`u les ar\^etes repr\'esentent l'existence d'une fronti\`ere entre deux pays.
\begin{enumerate}
\item Repr\'esenter ce graphe. Chaque sommet aura pour lettre l'initiale du pays repr\'esent\'e.
\item Quelle est sa matrice d'adjacence ?
\item Combien de voyages (passant au maximum deux fois par le m\^eme pays) o\`u il faut traverser 4 fronti\`eres existent-ils entre l'Espagne et l'Allemagne ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le graphe est le suivant :
\begin{center}
\begin{tikzpicture}[scale=2]
\GraphInit[vstyle=Shade]
\tikzset{VertexStyle/.style = {draw,
shape = circle,
shading = ball,
ball color = brown,
minimum size = 24pt,
color = white}}
\tikzset{EdgeStyle/.style = {thick,double = brown,double distance = 1pt}}
\Vertex{A}
\Vertex[x=1,y=1]{B}
\Vertex[x=1,y=-1]{E}
\Vertex[x=1.5,y=0.5]{F}
\Vertex[x=2,y=-0.5]{I}
\Vertex[x=2.5,y=1.5]{L}
\Vertex[x=3,y=-1]{P}
\Vertex[x=-1,y=-1]{T}
\Edge(F)(E)
\Edge(F)(L)
\Edge(F)(I)
\Edge(F)(B)
\Edge(F)(A)
\Edge(P)(E)
\Edge(B)(A)
\Edge(B)(L)
\Edge(A)(T)
\end{tikzpicture}
\end{center}

\item La matrice d'adjacence de ce graphe est (en mettant les sommets dans l'ordre alphab\'etique : 
\begin{center}
A, B, E, F, I, L, P et T.
\end{center}
\[
M=
\begin{pmatrix}
0 & 1 & 0 & 1 & 0 & 0 & 0 & 1\\ % A
1 & 0 & 0 & 1 & 0 & 1 & 0 & 0\\ % B
0 & 0 & 0 & 1 & 0 & 0 & 1 & 0\\ % E
1 & 1 & 1 & 0 & 1 & 1 & 0 & 0\\ % F
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ % I
0 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ % L
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ % P
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}
\]

\newpage

\item En calculant $M^4$, on voit que le coefficient \`a la 3\ieme{} ligne et 1\iere{} colonne est 9, donc il y a 9 voyages comportant 4 travers\'ees de fronti\`eres entre l'Espagne et l'Allemagne :

\begin{multicols}{3}
E-P-E-F-A

E-F-I-F-A

E-F-B-F-A

E-F-L-F-A

E-F-L-B-A

E-F-A-T-A

E-F-A-B-A

E-F-A-F-A

E-F-E-F-A
\end{multicols}

Parmi ces voyages, tous comportent au maximum deux pays identiques.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Une site internet est compos\'ee de 5 pages, not\'ees A, B, C, D et E.
\begin{itemize}
\item Sur la page A, sont mis des liens vers les pages B et C;
\item Sur la page B, sont mis des liens vers les pages A, C et E;
\item Sur la page C, sont mis des liens vers les pages A et D;
\item Sur la page D, sont mis des liens vers les pages A, B, C et E;
\item Sur la page E, est mis un lien vers la page A.
\end{itemize}

\begin{enumerate}
\item Construire le graphe correspondant \`a ce site, o\`u les sommets d\'esignent les pages, et les ar\^etes d\'esignent les liens.
\item \'Ecrire la matrice d'adjacence de ce graphe.
\item Le webmaster se trouve sur la page A. Combien de chemins de longueur 4 existent pour revenir sur cette page ?
\item Proposer un chemin pour tester tous les liens de ce site en partant de la page A.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le graphe est le suivant :
\begin{center}
\begin{tikzpicture}[scale=2]
\GraphInit[vstyle=Shade]
\tikzset{VertexStyle/.style = {draw,
shape = circle,
shading = ball,
ball color = brown,
minimum size = 24pt,
color = white}}
\tikzset{EdgeStyle/.style = {thick,double = brown,double distance = 1pt, post, bend left}}
\Vertex{A}
\Vertex[x=1,y=1]{B}
\Vertex[x=3,y=0.5]{C}
\Vertex[x=2,y=-0.5]{D}
\Vertex[x=2,y=-1.5]{E}
\Edge(A)(C)
\Edge(C)(A)
\Edge(C)(D)
\Edge(A)(B)
\Edge(B)(A)
\Edge(D)(A)
\Edge(D)(B)
\Edge(D)(C)
\Edge(D)(E)
\Edge[style={bend left=50}](E)(A)
\end{tikzpicture}
\end{center}

\item En convenant de respecter l'ordre alphab\'etique, la matrice d'adjacence de ce graphe est :
\[
M = \begin{pmatrix}
0 & 1 & 1 & 0 & 0\\
1 & 0 & 0 &0&0\\
1 & 0 & 0 & \raisebox{1.5mm}{\tikz[remember picture,overlay] \node[violet,outer sep=-1mm] (n) {1};} & 0\\
1 & 1 & 1 & 0 & 1\\
1 & 0 & 0 & 0 & 0
\end{pmatrix}\qquad\qquad \tikz[remember picture,overlay] \draw[violet,thick,->,>=stealth'] (n.south east) to[bend right=10] ($(n.south east)+(2,-0.4)$) node[right] {1 lien de C vers D};
\]

\item Apr\`es avoir calcul\'e $M^4$, on voit que le coefficient de la 1\iere{} ligne et 1\iere{} colonne est 7.

Il y a donc 7 chemins possibles pour passer de la page A \`a la page A en 4 clics.

\item Le chemin :
\[
\rm A \to B \to A \to C \to D \to E \to A \to C \to A \to C \to D \to B \to A \to C \to D \to C \to D \to A 
\] 
convient, m\^eme s'il passe plusieurs fois par les m\^emes sommets et s'il emprunte plusieurs fois les m\^emes ar\^etes.
\end{enumerate}

\vspace*{3cm}~
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{le jeu du Fan Tan}
Deux joueurs disposent de 2 ou plusieurs tas d'allumettes. \`A tour de r\^ole, chaque joueur peut enlever un certain nombre d'allumettes de l'un des tas (selon la r\`egle choisie). Le joueur qui retire la derni\`ere allumette perd la partie.

\begin{enumerate}
\item Mod\'eliser ce jeu \`a l'aide d'un graphe $\mathcal{G}$ dans le cas o\`u l'on dispose au d\'epart de deux tas contenant chacun trois allumettes et o\`u un joueur peut enlever une ou deux allumettes \`a chaque fois.
\item Soit $c$ une cha\^ine allant du premier sommet au dernier. 

\`A quelle condition sur la longueur de $c$ le premier joueur gagne-t-il la partie ?
\item \'Ecrire la matrice d'adjacence $\mathcal{A}$ de $\mathcal{G}$.
\item \`A l'aide de votre calculatrice, calculer les puissances successives de $\mathcal{A}$ jusqu'\`a prouver qu'il existe bien un \og premier coup gagnant \fg.
\item En observant ce dernier r\'esultat, pouvez-vous dire quel premier coup le joueur doit faire pour \^etre assur\'e de gagner ?
\end{enumerate}

\tcblower


\begin{enumerate}
\item Si chaque sommet est un couple \coord{i}{j} o\`u $i$ d\'esigne le nombre d'allumettes du premier tas et $j$ celui du second tas, alors le graphe est le suivant :

\begin{center}
\begin{tikzpicture}[xscale=3,yscale=3,>=stealth']
\node (A) at (0,0) {\coord{3}{3}}; \node[red] at (A.south) {A};
\node (B) at (0.5,0.5) {\coord{2}{3}};\node[red] at (B.north) {B};
\node (C) at (.75,-0.5) {\coord{1}{3}};\node[red] at (C.south) {C};
\node (D) at (1,0) {\coord{2}{2}};\node[red] at (D.south) {D};
\node (E) at (2.5,1) {\coord{0}{3}};\node[red] at (E.north) {E};
\node (F) at (2.5,0) {\coord{1}{2}};\node[red] at (F.south) {F};
\node (G) at (3.25,.75) {\coord{0}{2}};\node[red] at (G.north) {G};
\node (H) at (3.25,-1) {\coord{1}{1}};\node[red] at (H.south) {H};
\node (I) at (3.5,0) {\coord{0}{1}};\node[red] at (I.east) {I};
\node (J) at (4,0.5) {\coord{0}{0}};\node[red] at (J.south) {J};
\draw[->] (A) -- (B);
\draw[->] (A) -- (C);
\draw[->] (B) -- (E);
\draw[->] (B) -- (C);
\draw[->] (B) -- (D);
\draw[->] (B) -- (F);
\draw[->] (C) -- (E);
\draw[->] (C) -- (F);
\draw[->] (C) -- (H);
\draw[->] (D) -- (G);
\draw[->] (D) -- (F);
\draw[->] (E) -- (G);
\draw[->] (E) -- (I);
\draw[->] (F) -- (G);
\draw[->] (F) -- (H);
\draw[->] (F) -- (I);
\draw[->] (G) -- (I);
\draw[->] (G) -- (J);
\draw[->] (H) -- (I);
\draw[->] (I) -- (J);
\end{tikzpicture}
\end{center}

\item Pour que le premier joueur gagne, il faut que l'autre joueur jour en dernier, ce qui n\'ecessite un nombre pair de coups. \uline{Il faut donc que la longueur de $c$ soit paire.}

\item La matrice d'adjacence du graphe est la suivante, en convenant de classer les sommets par ordre alphabétique: 
\[ 
\mathcal{A}=
\begin{pmatrix}
0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}
\]

\item \`A l'aide du logiciel Xcas, on cherche la plus petite puissance paire de $\mathcal{A}$ telle que $a_{1,10}\neq 0$. Pour $\mathcal{A}^2$, $a_{1,10}=0$ mais pour $\mathcal{A}^4$, on a $a_{1,10}=10$.

On peut donc dire qu'il y a 10 cha\^ines de longueur 4 qui m\`enent du premier sommet au dernier. Par exemple : $(3;3)\to(1;3)\to(0;3)\to(0;2)\to(0,0)$.
\item Sur le graphe $\mathcal{G}$, on peut observer que si le joueur retire deux allumettes, alors il est assur\'e de gagner.

En effet, la cha\^ine $\coord{3}{3}\to\coord{2}{3}\to\coord{2}{2}\to\coord{1}{2}\to\coord{0}{1}\to\coord{0}{0}$ \`a une longueur impaire, donc ne convient pas. Par contre, toutes les cha\^ines commen\c{c}ant par \linebreak $\coord{3}{3}\to\coord{1}{3}$ ont une longueur paire.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{entreprises de couches culotte}
Deux entreprises A et B se disputent le march\'e innovateur des couches culotte en papier recycl\'e.

Les \'etudes de march\'e ont montr\'ees que d'une ann\'ee \`a l'autre :
\begin{itemize}
\item l'entreprise A perd \pourcent{13} de ses clients au profit de l'entreprise B;
\item l'entreprise B perd \pourcent{15} de ses clients au profit de l'entreprise A.
\end{itemize}
Les autres clients restent fid\`eles \`a leur marque.

\medskip

L'ann\'ee de lancement de ces produits, les deux entreprises avaient chacune d'elles \pourcent{50} du march\'e.

On d\'esigne par $P_n=\begin{pmatrix}a_n & b_n
\end{pmatrix}$ la matrice ligne repr\'esentant la r\'epartition du march\'e sur ces deux entreprises. Ainsi, $P_0=\begin{pmatrix}0,5 & 0,5\end{pmatrix}$.

\begin{enumerate}
\item Construire le graphe probabiliste de cette situation.
\item Donner la matrice de transition de ce graphe.
\item Quelle sera la r\'epartition du march\'e 1 ann\'ee apr\`es le lancement du produit ? Apr\`es 5 ann\'ees ?
\item D\'eterminer l'\'etat stable de ce march\'e, puis interpr\'eter ce r\'esultat.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le graphe correspondant \`a cette situation est le suivant :
\begin{center}
\begin{tikzpicture}[scale=0.8]
\clip (-4,-2) rectangle (8,2.1);
\tikzstyle{VertexStyle}=
[shape = circle,
shading = ball,
ball color = brown,
minimum size = 20pt,
draw,color=white]
\tikzstyle{LabelStyle}=[draw=brown,color=brown,fill=white,outer sep=1mm]
\tikzstyle{EdgeStyle}=[->, thick,%
double = brown,%
double distance = 1pt]
\tikzstyle{LoopStyle}=[->, thick,%
 double = brown,%
double distance = 1pt]
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{A}{B}%
{$0,13$}%
 {$0,15$}%
 {$0,87$}% 
 {$0,85$}%
\end{tikzpicture}
\end{center}

\item La matrice de transition est :
\[
M = \begin{pmatrix}
0,87 & 0,13\\
0,15 & 0,85
\end{pmatrix}
\]

\item 
\begin{itemize}
\item On souhaite calculer $P_1$ :
\[
P_1=P_0\times M=\begin{pmatrix}0,5 & 0,5\end{pmatrix}\begin{pmatrix}
0,87 & 0,13\\
0,15 & 0,85
\end{pmatrix}=\boxed{\begin{pmatrix}
0,51 & 0,49
\end{pmatrix}=P_1}
\]
\uline{Ainsi, apr\`es 1 ann\'ee, l'entreprise A d\'etiendra \pourcent{51} du march\'e.}

\item On souhaite calculer $P_5$ :
\[
P_5=P_0\times M^5=\boxed{\begin{pmatrix}
0,5288 & 0,4712
\end{pmatrix}=P_5}
\]
\uline{Ainsi, apr\`es 5 ann\'ees, l'entreprise A d\'etiendra \pourcent{52,88} du march\'e.}
\end{itemize}

\item Notons $P=\begin{pmatrix}a & b\end{pmatrix}$ l'\'etat stable du graphe. Alors, par d\'efinition:
\[
P=PM \qquad \text{soit}\qquad \begin{pmatrix}
a & b\end{pmatrix}=\begin{pmatrix}
a & b\end{pmatrix}\begin{pmatrix}
0,87 & 0,13\\
0,15 & 0,85
\end{pmatrix}.
\]
On arrive ainsi au syst\`eme suivant :
\[
\systeme[][:]{0,87a+0,15b=a:0,13a+0,85b=b}
\]
ou encore, en faisant tout passer \`a gauche :
\[
\systeme[][:]{-0,13a+0,15b=0:0,13a-0,15b=0}
\]
On obtient ainsi deux \'equations \'equivalentes (car la 1\iere{} est l'oppos\'ee de la 2\up{nde}).

De plus, $a+b=1$ car $a$ et $b$ sont les deux seules  probabilit\'es de notre situation.

On a finalement le syst\`eme suivant :
\[
\systeme[][:]{a+b=1:0,13a-0,15b=0}
\]
que l'on peut aussi \'ecrire de fa\c{c}on matricielle :
\[
AX=B\qquad,\qquad A=\begin{pmatrix}
1&1\\0,13&-0,15\end{pmatrix}\quad,\quad X=\dbinom{a}{b}\quad,\quad B=\dbinom{1}{0}.
\]
Ainsi, 
\[
X=A^{-1}B=\boxed{\dbinom{0,5357}{0,4643}}
\]
ce qui signifie qu'\uline{\`a longs termes, l'entreprise A poss\`edera \pourcent{53,57} du march\'e.}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{Lucas le glandeur}
Quand Lucas est en vacances, s'il n'est pas sur son lit en train d'\'ecouter de la musique, il peut \^etre devant un jeu vid\'eo ou en train de manger.

D'une heure \`a l'autre,
\begin{itemize}
\item la probabilit\'e qu'il passe de son lit \`a la cuisine est \'egale \`a 0,2 ;
\item la probabilit\'e qu'il passe de son lit au jeu vid\'eo est \'egale \`a 0,5 ;
\item la probabilit\'e qu'il passe de son jeu vid\'eo \`a la cuisine est \'egale \`a 0,6 ;
\item la probabilit\'e qu'il passe de son jeu vid\'eo \`a son lit est \'egale \`a 0,3 ;
\item la probabilit\'e qu'il passe de la cuisine \`a son lit est \'egale \`a 0,7 ;
\item la probabilit\'e qu'il passe de la cuisine au jeu vid\'eo est \'egale \`a 0,2.
\end{itemize}

\begin{enumerate}
\item Construire le graphe de cette situation.
\item Donner la matrice de transition de ce graphe, puis \'eterminer son \'etat stable. Interpr\'eter.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le graphe est le suivant :
\begin{center}
\begin{tikzpicture}[scale=4]
\GraphInit[vstyle=Shade]
\tikzset{VertexStyle/.style = {draw,
shape = circle,
shading = ball,
ball color = brown,
minimum size = 24pt,
color = white}}
\tikzset{EdgeStyle/.style = {thick,double = brown,double distance = 1pt, post, bend left=15}}
\tikzset{LabelStyle/.style = {draw=brown,text=brown,fill=white,outer sep=3mm}}
\Vertex{L}
\Vertex[x=2,y=0]{J}
\Vertex[x=1,y=1]{C}
\Edge[label={0,2}](L)(C)
\Edge[label={0,5}](L)(J)
\Edge[label={0,6}](J)(C)
\Edge[label={0,3}](J)(L)
\Edge[label={0,7}](C)(L)
\Edge[label={0,2}](C)(J)
\draw[->,thick,double = brown,double distance = 1pt] (J) to [out=45,in=-45,looseness=5] (J) node[right,outer sep=12mm,draw=brown,text=brown,fill=white] {0,1};
\draw[->,thick,double = brown,double distance = 1pt] (L) to [out=150,in=210,looseness=5] (L) node[left,outer sep=12mm,draw=brown,text=brown,fill=white] {0,3};
\draw[->,thick,double = brown,double distance = 1pt] (C) to [out=60,in=120,looseness=7] (C) node[above,outer sep=12mm,draw=brown,text=brown,fill=white] {0,1};
\end{tikzpicture}
\end{center}

\item La matrice de transition de ce graphe est :
\[
M = \begin{pmatrix}
0,1 & 0,2 & 0,7\\
0,6 & 0,1 & 0,3\\
0,2 & 0,5 & 0,3
\end{pmatrix}
\]
en convenant de mettre les sommet dans l'ordre alphab\'etique : C, J, L.

\medskip

Notons $P=\begin{pmatrix}a & b & c\end{pmatrix}$ l'\'etat stable du graphe. Alors, par d\'efinition, 
\[
P = P \times M\qquad\text{soit}\qquad \begin{pmatrix}a & b & c\end{pmatrix} = \begin{pmatrix}a & b & c\end{pmatrix}\begin{pmatrix}
0,1 & 0,2 & 0,7\\
0,6 & 0,1 & 0,3\\
0,2 & 0,5 & 0,3
\end{pmatrix}
\]
d'o\`u le syst\`eme suivant :
\[
\systeme[][:]{0,1a+0,6b+0,2c=a:0,2a+0,1b+0,5c=b:0,7a+0,3b+0,3c=c}
\]
En mettant tout \`a gauche, on obtient :
\[
\systeme[][:]{-0,9a+0,6b+0,2c=0:0,2a-0,9b+0,5c=0:0,7a+0,3b-0,7c=0}
\]
En ajoutant les deux derni\`eres \'equations, on obtient :
\[
0,9a-0,6b-0,2c=0
\]
c'est-\`a-dire la 1\iere{} \'equation. On peut donc supprimer cette derni\`ere et ajouter au syst\`eme l'\'equation : $a+b+c=1$ (somme des probabilit\'es).


On obtient alors le syst\`eme :
\[
\systeme[][:]{a+b+c=1:0,2a-0,9b+0,5c=0:0,7a+0,3b-0,7c=0}
\]
On peut multiplier par 10 les deux derni\`eres \'equations (pour enlever les virgules) :
\[
\systeme[][:]{a+b+c=1:2a-9b+5c=0:7a+3b-7c=0}
\]
et \'ecrire de fa\c{c}on matricielle ce dernier syst\`eme :
\[
AX=B\qquad,\qquad A=\begin{pmatrix}
1&1&1\\2&-9&5\\7&3&-7\end{pmatrix}\quad,\quad X=\begin{pmatrix}a\\b\\c\end{pmatrix}\quad,\quad B=\begin{pmatrix}1\\0\\0\end{pmatrix}.
\]
Ainsi, 
\[
X=A^{-1}B=\begin{pmatrix}\frac{24}{83} \\[8pt] \frac{49}{166} \\[8pt] \frac{69}{166}\end{pmatrix}
\]
L'\'etat stable du graphe est donc :
\[
P=\begin{pmatrix}
\dfrac{24}{83} & \dfrac{49}{166} & \dfrac{69}{166}
\end{pmatrix}
\]
ce qui signifie qu'\`a longs termes,
\begin{itemize}
\item la probabilit\'e que Lucas soit dans la cuisine en train de manger est \'egale \`a \linebreak $\dfrac{24}{83}\approx0,289$, 
\item la probabilit\'e que Lucas soit en train de jouer au jeu vid\'eo est \'egale \`a $\dfrac{49}{166}\approx0,295$, 
\item la probabilit\'e que Lucas soit sur son lit est \'egale \`a $\dfrac{69}{166}\approx0,416$.
\end{itemize}
Quel glandeur ce Lucas!
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{exocor}{notoriété de Squeezie}
Dans cet exercice, on s'int\'eresse \`a la notori\'et\'e de Squeezie, le youtuber.

Cette ann\'ee, en France, sur l'ensemble des personnes interrog\'ees connaissant le personnage, \pourcent{78} affirmaient qu'ils l'aimaient bien.

Les statistiques montrent que d'une ann\'ee sur l'autre :
\begin{itemize}
\item \pourcent{7} des personnes qui l'aimaient bien ne l'aiment plus ;
\item \pourcent{30} de celles qui ne l'aimaient pas l'aiment bien.
\end{itemize}

Pour tout entier naturel $n$, on note :
\begin{itemize}
\item $a_n$ la probabilit\'e qu'une personne aime bien Squeezie dans $n$ ann\'ees ;

\item $P_n=\begin{pmatrix}
a_n & 1-a_n
\end{pmatrix}$ la matrice traduisant l'\'etat probabiliste dans $n$ ann\'ees.
\end{itemize} 

\begin{enumerate}
\item Trouver $P_0$, l'\'etat probabiliste initial.

\item D\'eterminer le graphe probabiliste traduisant la notori\'et\'e de notre ami Squeezie aupr\`es de la population fran\c{c}aise, puis en donner la matrice de transition.

\item Quelle est la probabilit\'e qu'une personne choisie au hasard en France aime Squeezie dans 4 ans ?

\item 
\begin{enumerate}
\item On note $P=\begin{pmatrix}a & 1-a\end{pmatrix}$ l'\'etat stable du graphe.

Montrer que $a = 0,63a+0,3$.

\item \`A longs termes, selon ce mod\`ele math\'ematique, montrer que plus de \pourcent{80} des fran\c{c}ais  aimeront le youtuber.
\end{enumerate}
\end{enumerate}

\tcblower

\begin{enumerate}
\item D'apr\`es l'\'enonc\'e, $\boxed{P_0=\begin{pmatrix}0,78 & 0,22\end{pmatrix}}$.

\item Le graphe est le suivant, o\`u A est l'\'ev\'enement : \og Le jeune aime Squeezie \fg{} :

\begin{center}
\begin{tikzpicture}[baseline]
\clip (-4,-2) rectangle (8,2.1);
\tikzstyle{VertexStyle}=
[shape = circle,
shading = ball,
ball color = brown,
minimum size = 20pt,
draw,color=white]
\tikzstyle{LabelStyle}=[color=brown,fill=white,outer sep=1mm,draw=brown]
\tikzstyle{EdgeStyle}=[->, thick,%
double = brown,%
double distance = 1pt]
\tikzstyle{LoopStyle}=[->, thick,%
 double = brown,%
double distance = 1pt]
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{A}{\evcont{A}}%
{$0,07$}%
 {$0,3$}%
 {$0,93$}% 
 {$0,7$}%
\end{tikzpicture}
\end{center}

La matrice de transition est alors  :
\[
\boxed{M=\begin{pmatrix}
0,93 & 0,07\\
0,30 & 0,70
\end{pmatrix}}
\]


\item $P_4=P_0 \times M^4=\begin{pmatrix}
0,80 & 0,20
\end{pmatrix}$.

\uline{Ainsi, dans 4 ans, \pourcent{80} des personnes aimeront Squeezie.}

\item 
\begin{enumerate}
\item Par d\'efinition, $P = P\times M$ donc :
\[
\begin{pmatrix}a & 1-a\end{pmatrix}=\begin{pmatrix}a & 1-a\end{pmatrix}\begin{pmatrix}
0,93 & 0,07\\
0,3 & 0,7
\end{pmatrix}=\begin{pmatrix}
0,93a+0,3(1-a) & 0,07a+0,7(1-a).
\end{pmatrix}
\]
En ne regardant que la premi\`ere composante des deux matrices de part et d'autre du signe \og $=$ \fg, on a :
\begin{align*}
a =0,93a+0,3(1-a) & \iff a=0,93a+0,3-0,3a\\
& \iff \boxed{a = 0,63a+0,3}
\end{align*}

\item De la question pr\'ec\'edente, on d\'eduit que :
\[ 
0,37a=0,3
\]
et donc que :
\[
a=\dfrac{0,3}{0,37}\approx0,8108.
\]
\uline{Ainsi, \`a longs termes, il y aura \`a peu pr\`es \pourcent{81} des fran\c{c}ais aimeront Squeezie selon ce mod\`ele math\'ematique.}
\end{enumerate}
\end{enumerate}

\vspace*{4cm}~
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{fumeurs et non fumeurs}
On a divis\'e une population en deux cat\'egories : \og fumeurs \fg{} et \og non-fumeurs \fg.

Une \'etude statistique a permis de constater que, d'une g\'en\'eration \`a l'autre,
\begin{itemize}
\item \pourcent{60} des descendants de fumeurs sont des fumeurs,
\item \pourcent{10} des descendants de non-fumeurs sont des fumeurs.
\end{itemize}
On suppose que le taux de f\'econdit\'e des fumeurs est le m\^eme que celui des non-fumeurs.

On d\'esigne par :
\begin{itemize}
\item $f_n$ le pourcentage de fumeurs \`a la g\'en\'eration de rang $n$,
\item $g_n = 1 - f_n$ le pourcentage de non-fumeurs \`a la g\'en\'eration de rang $n$, o\`u $n$ est un entier naturel.
\end{itemize}
On consid\`ere qu'\`a la g\'en\'eration 0, il y a autant de fumeurs que de non-fumeurs.

On a donc $f_0 = g_0 = 0,5$.

\begin{enumerate}
\item Traduire les donn\'ees de l'\'enonc\'e par un graphe probabiliste.
\item Justifier l'\'egalit\'e matricielle :
\[
\begin{pmatrix}
f_{n+1} & g_{n+1}
\end{pmatrix}=\begin{pmatrix}
f_n & g_n
\end{pmatrix}\times A,\quad\text{ o\`u $A$ d\'esigne la matrice : }\begin{pmatrix}
0,6 & 0,4\\0,1 & 0,9
\end{pmatrix}.
\]

\item D\'eterminer le pourcentage de fumeurs \`a la g\'en\'eration de rang 2.
\item D\'eterminer l'\'etat probabiliste stable et l'interpr\'eter.
\item Montrer que pour tout entier naturel $n$, $f_{n+1} = 0,5f_n + 0,1$.
\item On pose, pour tout entier naturel $n$, $u_n = f_n - 0,2$.
\begin{enumerate}
\item Montrer que la suite \suite{u}{n}{} est une suite g\'eom\'etrique dont on pr\'ecisera le premier terme et la raison.
\item Donner l'expression de $u_n$ en fonction de $n$.
\item En d\'eduire que, pour tout entier naturel $n$, $f_n = 0,3 \times 0,5^n + 0,2$.
\item D\'eterminer la limite de la suite \suite{f}{n}{} lorsque $n$ tend vers $+\infty$ et l'interpr\'eter.
\end{enumerate}
\end{enumerate}

\tcblower

\begin{enumerate}
\item Le graphe probabiliste est le suivant, o\`u F repr\'esente l'\'etat \og fumeur \fg{} et $\evcont{F}$ l'\'etat \og non-fumeur \fg{}   :
\begin{center}
\begin{tikzpicture}
\clip (-4,-2) rectangle (8,2.1);
\tikzstyle{VertexStyle}=
[shape = circle,
shading = ball,
ball color = brown,
minimum size = 20pt,
draw,color=white]
\tikzstyle{LabelStyle}=[color=brown,fill=white,outer sep=1mm,draw=brown]
\tikzstyle{EdgeStyle}=[->, thick,%
double = brown,%
double distance = 1pt]
\tikzstyle{LoopStyle}=[->, thick,%
 double = brown,%
double distance = 1pt]
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{F}{\evcont{F}}%
{$0,4$}%
 {$0,1$}%
 {$0,6$}% 
 {$0,9$}%
\end{tikzpicture}
\end{center}

\item La matrice de transition de ce graphe est : $A=\begin{pmatrix}0,6 & 0,4\\0,1 & 0,9\end{pmatrix}$, et par d\'efinition, si on note\linebreak $P_n=\begin{pmatrix}f_n & g_n\end{pmatrix}$, alors $P_{n+1}=P_n \times A$.

\item On cherche $f_2$, donc $P_2$.
\[
P_2=P_0 \times A^2=\begin{pmatrix}
0,275 & 0,725
\end{pmatrix}.
\]
\uline{Ainsi, \`a la g\'en\'eration de rang 2, il y a \pourcent{27,5} de fumeurs.}

\item Notons $P=\begin{pmatrix}f & g\end{pmatrix}$ l'\'etat stable du graphe. Alors, par d\'efinition, $P=P\times A$ :
\[
\begin{pmatrix}f & g\end{pmatrix} = \begin{pmatrix}f & g\end{pmatrix}\begin{pmatrix}0,6 & 0,4\\0,1 & 0,9\end{pmatrix}=\begin{pmatrix}0,6f+0,1g & 0,4f+0,9g\end{pmatrix}
\]
Ainsi,
\[
\systeme[][:]{0,6f+0,1g=f:0,4f+0,9g=g}\qquad\text{soit}\qquad\systeme[][:]{-0,4f+0,1g=0:0,4f-0,1g=0}
\]
Ces deux \'equations sont \'equivalentes car l'une est l'oppos\'ee de l'autre, donc on peut n'en prendre qu'une des deux.

De plus, $g=1-f$, ce qui donne :
\begin{align*}
0,4f-0,1g=0 &\iff 0,4f-0,1(1-f)=0\\
& \iff 0,4f-0,1+0,1f=0\\
& \iff 0,5f=0,1\\
& \iff f = \dfrac{0,1}{0,5}\\
& \iff f = 0,2.
\end{align*}

L'\'etat stable est donc $\boxed{P=\begin{pmatrix}
0,2 & 0,8\end{pmatrix}}$, ce qui signifie qu'\uline{\`a longs termes, il y aura \pourcent{20} de fumeurs et donc \pourcent{80} de non-fumeurs.}

\item De la question 2, on d\'eduit :
\begin{align*}
\begin{pmatrix}
f_{n+1} & g_{n+1}
\end{pmatrix}=\begin{pmatrix}
f_n & g_n\end{pmatrix}\begin{pmatrix}
0,6&0,4\\0,1&0,9\end{pmatrix} & \Longrightarrow
 f_{n+1}=0,6f_n+0,1g_n\\
 & \iff f_{n+1}=0,6f_n+0,1(1-f_n)\\
 & \iff f_{n+1}=0,6f_n+0,1-0,1f_n\\
 & \iff \boxed{f_{n+1}=0,5f_n+0,1}
\end{align*}
\item
\begin{enumerate}
\item $\begin{aligned}[t]
u_{n+1} & = f_{n+1}-0,2\\
& = 0,5f_n+0,1-0,2\\
& = 0,5f_n-0,1\\
& = 0,5\left(f_n-\dfrac{0,1}{0,5}\right)\\
& = 0,5(f_n-0,2)\\
& = 0,5u_n.
\end{aligned}$

Ainsi, \suite{u}{n}{} est une suite g\'eom\'etrique de raison $q=0,5$. Son premier terme est alors :
\[
u_0=f_0-0,2=0,5-0,2=0,3.
\]
\item D'apr\`es le cours, $u_n=u_0\times q^n$, donc $\boxed{u_n=0,3 \times 0,5^n}$.
\item On sait que $u_n=f_n-0,2$, donc $f_n=u_n+0,2$, c'est-\`a-dire :
\[
f_n=0,3 \times 0,5^n + 0,2
\]
\item $0<0,5<1$ donc d'apr\`es le cours, $\limite{n}{+\infty}{0,5^n}=0$. Alors, $\limite{n}{+\infty}{\big(0,3\times0,5^n\big)}=0$ et donc $\boxed{\limite{n}{+\infty}{f_n}=0,2}$.

On peut interpr\'eter ce dernier r\'esultat en disant qu'\`a longs termes, il y aura \pourcent{20} de fumeurs, ce qui n'est pas une surprise dans la mesure o\`u on l'avait d\'ej\`a trouv\'e \`a la question 4.
\end{enumerate}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{modèle d'Ehrenfest}
On considère un espace clos composé de deux parties $R_1$, initialement remplie de $k$ particules que l'on suppose numérotées de 1 à $k$, et $R_2$, initialement vide, ces deux parties étant séparées par une membrane poreuse.

À chaque étape (par exemple chaque seconde), un nombre $x$ compris entre 1 et $k$ est choisi au hasard et la particule $x$ traverse la membrane pour aller de l'autre côté. Ainsi, à l'étape 1, si on choisi le nombre $p$, la boule portant le numéro $p$ passera de $R_1$ à $R_2$.

\medskip

\textbf{État initial:}

\begin{center}
\def\hauteur{5}
\def\largeur{4}
\pgfmathdeclarerandomlist{MyRandomColors}{%
{red}%
{red!25}%
{magenta}%
{magenta!25}%
{olive}%
{olive!25}%
{brown}%
{brown!10}%
{violet}%
{violet!25}%
{gray}%
{purple}%
{orange}%
{orange!25}%
{cyan}%
{green}%    
}
\begin{tikzpicture}[x=1cm, y=1cm]
% source : http://www.texample.net/tikz/examples/membrane-ions/
\foreach \i in {0,1,...,10}{
\foreach \j in {0,1,...,12}{
\pgfmathrandomitem{\RandomColor}{MyRandomColors}
\pgfmathrandominteger{\x}{1}{100}
\ifnum  \x<30
\draw (\i/2.9+0.2,\j/3+0.2)  node[color=\RandomColor] {$\bullet$};
\fi
}
}
\draw  [line width=2pt] (0,\hauteur) -- (0,0) -- (2*\largeur,0) -- (2*\largeur,\hauteur) -- cycle;
\draw  [dotted] (\largeur,0) -- (\largeur,\hauteur);
\node at (0.5*\largeur,-0.5) {$R_1$};
\node at (1.5*\largeur,-0.5) {$R_2$};
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item \textbf{Simulation informatique}.

\begin{enumerate}
\item Expliquer en quoi le programme page suivante permet de simuler l'expérience.

\item Effectuer plusieurs simulations avec des valeurs de $k$ supérieures à 100 et des valeurs de $n$ supérieures à \numprint{1000}.

Que peut-on conjecturer quant à l'état des parties $R_1$ et $R_2$?
\end{enumerate}

\begin{python}
from random import choice

def Ehrenfest(k,n):
    # k : nombre de particules
    # n : nombre d'étapes
    R1 = [ i for i in range(1,k+1) ]
    R2 = []
    for i in range(n):
        j = choice( range(1,k+1) )
        if j in R1:
            R1.remove( j )
            R2.append( j )
        else:
            R2.remove( j )
            R1.append( j )
            
    return len(R1),len(R2)
\end{python}

\item \textbf{Étude mathématique pour $\pmb{k=2}$.}

\medskip

On considère ici que $k=2$ par soucis de simplification. On note $E_{i,j}$ l'état : \og il y a $i$ particules dans $R_1$ et $j$ particules dans $R_2$ \fg.
\begin{enumerate}
\item Compléter le graphe suivant, qui représente la situation:
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[Math]{E_{2,0}}
\Vertex[Math,x=3,y=0]{E_{1,1}}
\Vertex[Math,x=6,y=0]{E_{0,2}}
\Edge[label=...,labelstyle={draw=brown,text=brown},style={bend right,->}](E_{2,0})(E_{1,1})
\Edge[label=...,labelstyle={draw=brown,text=brown},style={bend right,->}](E_{1,1})(E_{0,2})
\Edge[label=...,labelstyle={draw=brown,text=brown},style={bend right,->}](E_{0,2})(E_{1,1})
\Edge[label=...,labelstyle={draw=brown,text=brown},style={bend right,->}](E_{1,1})(E_{2,0})
\end{tikzpicture}
\end{center}

\item On pose:
\begin{itemize}
\item $a_n$ la probabilité d'être dans l'état $E_{2,0}$ à l'étape $n$;
\item $b_n$ la probabilité d'être dans l'état $E_{1,1}$ à l'étape $n$;
\item $c_n$ la probabilité d'être dans l'état $E_{0,2}$ à l'étape $n$.
\end{itemize}
On note alors $U_n = \begin{pmatrix}a_n\\b_n\\c_n\end{pmatrix}$.

\medskip

Spécifier la valeur de $U_0$ et donner la matrice $M$ du graphe (que l'on appelle \textit{matrice de transition}) de sorte que $U_{n+1}=MU_n$.

\item Montrer que pour tout entier naturel $k\geqslant1$, $U_{2k}=U_2$ et $U_{2k+1}=U_1$.
\end{enumerate}

\item \textbf{Étude mathématique pour $\pmb{k=4}$.}

\medskip

On considère ici que qu'il y a initialement 4 particules dans la partie de gauche. On note cette fois-ci $R_k$ l'événement: \og Il y a $k$ particules dans la partie de gauche. \fg. 

On note ensuite $X_n$ la variable aléatoire donnant le nombre de particules dans la partie de gauche après $n$ étapes.

On note: $U_n = \begin{pmatrix}
\probavar{X_n}{0} & \probavar{X_n}{1} & \probavar{X_n}{2} & \probavar{X_n}{3} & \probavar{X_n}{4}\end{pmatrix}$.

\begin{enumerate}
\item Que vaut $U_0$ ?
\item Représenter la situation par un graphe probabiliste à 5 sommets correspondant aux 5 états possibles.

Donner alors la matrice de transition $M$ de ce graphe probabiliste.
\end{enumerate}

On admet que pour tout entier naturel $n$, $U_n=U_0M^n$.

On admet aussi que, pour tout entier naturel $p\geqslant1$:
\[
U_{2p}=\begin{pmatrix}\frac{1}{8}-\frac{1}{2^{2p+1}} & 0 & \frac{3}{4} & 0 & \frac{1}{8}+\frac{1}{2^{2p+1}}\end{pmatrix}
\]
et 
\[
U_{2p+1}=\begin{pmatrix}0 & \frac{1}{2}-\frac{1}{2^{2p+1}} & 0 & \frac{1}{2}+\frac{1}{2^{2p+1}} & 0\end{pmatrix}.
\]
\textit{(On pourrait le démontrer par récurrence)}
\begin{enumerate}[resume]
\item Calculer l'espérance mathématique de $X_n$ suivant la parité de $n$.

Déterminer alors sa limite quand $n$ tend vers $+\infty$ et conclure.
\end{enumerate}
\end{enumerate}

\tcblower

\begin{enumerate}
\item
\begin{enumerate}
\item Dans ce programme, \texttt{R1} est une liste initialement composée des nombres 1, 2, ..., $n$. Elle représente ainsi la partie de gauche de l'espace séparé en deux, les $n$ nombres distincts représentant les $n$ particules. \texttt{R2} est une liste vide représentant ainsi la partie de droite, qui est initialement vide.

\medskip

On entre ensuite dans une boucle dans laquelle on exécute $n$ fois la même chose: on choisit un nombre aléatoire \texttt{j} entre 1 et $n$; si la particule $j$ est dans $R_1$, on la transfert dans $R_2$ en l'ajoutant dans la liste \texttt{R2} et en la supprimant de la liste \texttt{R1}.

\medskip

Une fois hors de la boucle, la fonction retourne la longueur des deux lites, soit le nombre de particules dans chacune des parties.

\item Effectuons plusieurs simulations:
\begin{console}
>>> Ehrenfest(200,2000)
(100,100)
>>> Ehrenfest(900,2000)
(424, 476)
>>> Ehrenfest(900,5000)
(460, 440)
\end{console}
On peut alors conjecturer qu'à longs termes (après un très grand nombre d'étapes), les particules se répartissent de façon équitable.
\end{enumerate}

\item \textbf{Étude mathématique pour $\pmb{k=2}$.}
\begin{enumerate}
\item Le graphe complété est le suivant:
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[Math]{E_{2,0}}
\Vertex[Math,x=3,y=0]{E_{1,1}}
\Vertex[Math,x=6,y=0]{E_{0,2}}
\Edge[label=1,labelstyle={draw=brown,text=brown},style={bend right,->}](E_{2,0})(E_{1,1})
\Edge[label={0,5},labelstyle={draw=brown,text=brown},style={bend right,->}](E_{1,1})(E_{0,2})
\Edge[label=1,labelstyle={draw=brown,text=brown},style={bend right,->}](E_{0,2})(E_{1,1})
\Edge[label={0,5},labelstyle={draw=brown,text=brown},style={bend right,->}](E_{1,1})(E_{2,0})
\end{tikzpicture}
\end{center}
En effet, le passage de $E_{2,0}$ à $E_{1,1}$ est inéluctable, d'où une probabilité de passage de l'état  $E_{2,0}$ à $E_{1,1}$ égale à 1.

De même pour le passage de  $E_{0,2}$ à $E_{1,1}$.

Quant aux probabilités de passage de $E_{1,1}$ à l'un des états $E_{0,2}$ ou  $E_{2,0}$, elles sont identiques, donc égales à 0,5.

\item $U_0=\begin{pmatrix}1\\0\\0\end{pmatrix}$ et $M=\begin{pmatrix}
0 & 0,5 & 0\\1 & 0 & 1\\0 & 0,5 & 0\end{pmatrix}$.

\item Montrons par récurrence ces égalités.
\begin{itemize}
\item \textbf{Initialisation.} 
\begin{itemize}
\item $U_1=\begin{pmatrix}
0 & 0,5 & 0\\1 & 0 & 1\\0 & 0,5 & 0\end{pmatrix}\begin{pmatrix}1\\0\\0\end{pmatrix}=\begin{pmatrix}0\\1\\0\end{pmatrix}$.
\item $U_2=\begin{pmatrix}
0 & 0,5 & 0\\1 & 0 & 1\\0 & 0,5 & 0\end{pmatrix}\begin{pmatrix}0\\1\\0\end{pmatrix}=\begin{pmatrix}0,5\\0\\0,5\end{pmatrix}$.
\item $U_3=\begin{pmatrix}
0 & 0,5 & 0\\1 & 0 & 1\\0 & 0,5 & 0\end{pmatrix}\begin{pmatrix}0,5\\0\\0,5\end{pmatrix}=\begin{pmatrix}0\\1\\0\end{pmatrix}=U_1$.
\item $U_4=\begin{pmatrix}
0 & 0,5 & 0\\1 & 0 & 1\\0 & 0,5 & 0\end{pmatrix}\begin{pmatrix}0\\1\\0\end{pmatrix}=\begin{pmatrix}0,5\\0\\0,5\end{pmatrix}=U_2$.
\end{itemize}

\item \textbf{Hérédité.} Supposons que pour un entier $p$ fixé, $U_{2p}=U_2$ et $U_{2p+1}=U_1$.
\begin{itemize}
\item $U_{2p+2}=MU_{2p+1}=MU_1=U_2$ et donc $U_{2(p+1)} = U_2$;
\item $U_{2p+3}=MU_{2p+2}=MU_2=U_3=U_1$ et donc $U_{2(p+1)+1}=U_1$.
\end{itemize}
L'hérédité est alors vérifiée.
\end{itemize}
Ainsi, les égalités sont vraies pour tout entier $k\geqslant1$.
\end{enumerate}

\item \textbf{Étude mathématique pour $\pmb{k=4}$.}
\begin{enumerate}
\item $U_0 = \begin{pmatrix}0 & 0&  0 & 0 & 1\end{pmatrix}$.

En effet, initialement, il y a 4 particules dans la partie de gauche donc \mbox{$\probavar{X_0}{4}=1$.}

\item Le graphe complété est le suivant:
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[Math]{R_0}
\Vertex[Math,x=3,y=0]{R_1}
\Vertex[Math,x=6,y=0]{R_2}
\Vertex[Math,x=9,y=0]{R_3}
\Vertex[Math,x=12,y=0]{R_4}
\Edge[label=1,labelstyle={draw=brown,text=brown},style={bend right,->}](R_0)(R_1)
\Edge[label={0,75},labelstyle={draw=brown,text=brown},style={bend right,->}](R_1)(R_2)
\Edge[label={0,5},labelstyle={draw=brown,text=brown},style={bend right,->}](R_2)(R_3)
\Edge[label={0,25},labelstyle={draw=brown,text=brown},style={bend right,->}](R_3)(R_4)
\Edge[label={1},labelstyle={draw=brown,text=brown},style={bend right,->}](R_4)(R_3)
\Edge[label={0,75},labelstyle={draw=brown,text=brown},style={bend right,->}](R_3)(R_2)
\Edge[label={0,5},labelstyle={draw=brown,text=brown},style={bend right,->}](R_2)(R_1)
\Edge[label={0,25},labelstyle={draw=brown,text=brown},style={bend right,->}](R_1)(R_0)
\end{tikzpicture}
\end{center}

La matrice de transition du graphe est donc:
\[
M = \begin{pmatrix}
0 & 1 & 0 & 0 & 0\\
0,25 & 0 & 0,75 & 0 & 0\\
0 & 0,5 & 0 & 0,5 & 0\\
0 & 0 & 0,75 & 0 & 0,25\\
0 & 0 & 0 & 1 & 0
\end{pmatrix}.
\]

\item Calculons l'espérance mathématique de $X_n$:
\begin{itemize}
\item si $n=2p$: $E(X_{2p}) = \frac{3}{4}\times2 + \left( \frac{1}{8} -\frac{1}{2^{2p+1}}\right)\times 4 = 2 + \frac{1}{2^{2p-1}}$;
\item si $n=2p+1$: $E(X_{2p+1}) = 1\times\left(\frac{1}{2}-\frac{1}{2^{2p+1}} \right) + 3\times\left( \frac{1}{2}+\frac{1}{2^{2p+1}}\right)=2-\frac{2}{2^{2p}}$.
\end{itemize}
On constate alors que l'espérance tend vers 2 lorsque $n$ tend vers l'infini, ce qui signifie qu'à longs termes, il ne restera que deux particules dans la partie de gauche.
\end{enumerate}
\end{enumerate}
\end{exocor}


\corriges
