Terminale maths expertes / Graphes et chaînes de Markov

Ex. 1★★★Lire un graphe avec une boucle — Le graphe $G$ a pour sommets $A$, $B$, $C$, $D$, $E$, $F$ et pour arêtes $A$–$B$, $A$–$C$, $B$–$C$, $B$–$D$, $C$–$E$, $D$–$E$, $E$–$F$ et une boucle en $F$.

1. aDonne l'ordre du graphe $G$.
2. bCombien d'arêtes possède $G$ ?
3. cDonne le degré du sommet $B$.
4. dDonne le degré du sommet $F$.
5. eCalcule la somme des degrés de tous les sommets. Vérifie le lemme des poignées de main.
6. fListe les sommets de degré impair. Combien y en a-t-il ?

Ex. 2★★★Calculs directs avec le lemme — Réponds à chaque question en posant le calcul.

1. aCombien d'arêtes possède le graphe complet $K_6$ ?
2. bDans le graphe complet $K_4$, quel est le degré de chaque sommet ?
3. cUn graphe d'ordre $6$ a tous ses sommets de degré $3$. Combien a-t-il d'arêtes ?
4. dLes degrés des sommets d'un graphe sont $1$, $2$, $2$, $3$ et $4$. Combien a-t-il d'arêtes ?
5. eDans un graphe simple d'ordre $6$, quel est le plus grand degré possible pour un sommet ?
6. fUn graphe complet possède $10$ arêtes. Quel est son ordre ?

Ex. 3★★★Ce graphe existe-t-il ? — Pour chaque liste de degrés, dis si un graphe simple (sans boucle ni arête multiple) ayant exactement ces degrés existe. Justifie. S'il existe, donne une liste de ses arêtes.

1. aOrdre $5$, degrés $3$, $3$, $3$, $2$, $2$.
2. bOrdre $6$, degrés $5$, $3$, $2$, $2$, $1$, $1$.
3. cOrdre $6$, degrés $6$, $3$, $3$, $2$, $1$, $1$.
4. dOrdre $5$, degrés $4$, $4$, $4$, $1$, $1$.

Ex. 4★★★Poignées de main à Rennes — À une réunion d'association à Rennes, $5$ personnes sont présentes. Deux personnes se serrent la main au plus une fois, et personne ne se serre la main à soi-même.

1. aModélise la situation par un graphe : que sont les sommets ? les arêtes ? Explique pourquoi ce graphe est simple.
2. bInès affirme que chaque personne a serré exactement $3$ mains. A-t-elle raison ? Justifie.
3. cEn réalité, une personne a serré $4$ mains et les $4$ autres en ont serré $3$. Combien de poignées de main y a-t-il eu ?
4. dHugo affirme qu'une personne a pu serrer $5$ mains. A-t-il raison ? Justifie.
5. eJustifie que, dans n'importe quelle réunion de ce type, le nombre de personnes ayant serré un nombre impair de mains est pair.

Ex. 5★★★Deux sommets de même degré — Dans tout l'exercice, $G$ est un graphe simple, c'est-à-dire sans boucle ni arête multiple, d'ordre $n \geqslant 2$.

1. aJustifie que, pour tout sommet $s$ de $G$, $0 \leqslant d(s) \leqslant n-1$.
2. bDémontre que $G$ ne peut pas avoir à la fois un sommet de degré $0$ et un sommet de degré $n-1$.
3. cDéduis-en que $G$ possède au moins deux sommets de même degré.
4. dÀ un tournoi de ping-pong à Annecy, $6$ joueurs s'affrontent, au plus une fois par paire. Modélise la situation par un graphe, puis démontre que deux joueurs au moins ont eu le même nombre d'adversaires.
5. eDonne la liste des arêtes d'un graphe simple de sommets $A$, $B$, $C$, $D$ dans lequel exactement deux sommets ont le même degré.

Ex. 6★★★Câbler un centre de données — Dans un centre de données à Lille, on veut relier $7$ serveurs $S_0$, $S_1$, …, $S_6$ par des câbles. Deux serveurs sont reliés par au plus un câble, aucun câble ne relie un serveur à lui-même, et chaque serveur est relié à exactement $k$ autres serveurs ($k \geqslant 1$).

1. aModélise ce réseau par un graphe : que sont les sommets ? les arêtes ? Explique pourquoi ce graphe est simple et pourquoi $k \leqslant 6$.
2. bDémontre que $k$ est nécessairement pair.
3. cPour $k = 4$, calcule le nombre de câbles. Pour $k = 6$, quel graphe obtient-on ? Combien faut-il de câbles ?
4. dPour $k = 4$, Ben propose de relier chaque $S_i$ à $S_{i+1}$, $S_{i+2}$, $S_{i-1}$ et $S_{i-2}$, les indices étant pris modulo $7$ (ainsi $S_{6+2} = S_1$). Justifie que ce réseau convient.
5. eDans le réseau de Ben, Sacha ajoute un câble de test qui relie $S_0$ à lui-même. Il affirme : « $d(S_0)$ vaut $5$, donc la somme des degrés devient impaire. » Corrige-le.

Ex. 7★★★Reconstituer un graphe à partir d'indices — Un graphe simple $G$ a pour sommets $A$, $B$, $C$, $D$, $E$, $F$ et possède $10$ arêtes. On sait que $d(A) = 5$, $d(B) = 4$, $d(E) = 2$, $d(F) = 1$ et $d(C) = d(D)$.

1. aLina affirme que $G$ est d'ordre $10$. A-t-elle raison ? Justifie.
2. bCalcule $d(C)$ à l'aide du lemme des poignées de main.
3. cDémontre que $A$ est adjacent à tous les autres sommets. Déduis-en l'unique voisin de $F$.
4. dDétermine les voisins de $B$. Le graphe $G$ existe-t-il ? Justifie.
5. eOn considère un graphe simple $G'$ de mêmes sommets, avec $9$ arêtes et les mêmes conditions sur les degrés. Calcule $d(C)$, puis donne la liste des arêtes d'un tel graphe.

Ex. 8★★★Rues à sens unique — À Annecy, cinq carrefours $A$, $B$, $C$, $D$, $E$ sont reliés par des rues à sens unique. On les modélise par un graphe orienté d'arcs $A \to B$, $B \to C$, $C \to A$, $C \to D$, $D \to E$, $E \to C$.

1. aDonne le demi-degré sortant et le demi-degré entrant du sommet $C$.
2. bCalcule la somme des demi-degrés sortants de tous les sommets. Compare-la au nombre d'arcs.
3. cDétermine la longueur du plus court chemin de $A$ vers $E$.
4. dDétermine la longueur du plus court chemin de $E$ vers $A$.
5. eLe chemin $C \to D \to E \to C \to A \to B \to C$ est-il un cycle ? Justifie et donne sa longueur.

Ex. 9★★★Sentiers entre refuges — Des sentiers relient six refuges de montagne $F$, $G$, $H$, $I$, $J$, $K$. Les arêtes du graphe sont $F$–$G$, $G$–$H$, $H$–$I$, $I$–$J$, $J$–$F$, $G$–$J$, $I$–$K$.

1. aDonne l'ordre du graphe et le degré de chaque sommet.
2. bDonne la longueur de la chaîne $K$–$I$–$J$–$G$–$F$.
3. cCalcule la distance entre $K$ et $F$.
4. dCalcule la distance entre $H$ et $J$.
5. eThomas affirme : « $F$–$G$–$J$–$F$ et $F$–$G$–$F$ sont deux cycles. » Corrige son affirmation.

Ex. 10★★★Un réseau social en morceaux — Sur un réseau social, on relie deux personnes si elles sont amies. Les sept personnes sont Amel ($A$), Bruno ($B$), Chloé ($C$), Driss ($D$), Eva ($E$), Farid ($F$), Gaspard ($G$). Les arêtes sont $A$–$B$, $A$–$C$, $B$–$C$, $D$–$E$, $E$–$F$, $D$–$F$.

1. aLina affirme : « Le graphe a $7$ sommets et $6$ arêtes, et $6 = 7 - 1$, donc il est connexe. » A-t-elle raison ? Justifie.
2. bOn met deux personnes dans un même groupe si une chaîne les relie. Détermine ces groupes.
3. cVrai ou faux : « Si on ajoute l'arête $C$–$D$, le graphe devient connexe. » Justifie.
4. dDétermine le nombre minimal d'arêtes à ajouter pour rendre le graphe connexe, et propose de telles arêtes.

Ex. 11★★★Le tramway de Brest — À Brest, six stations de tramway sont modélisées par les sommets $G$ (Gare), $H$ (Halles), $M$ (Mairie), $P$ (Port), $S$ (Stade), $U$ (Université). Les arêtes sont $G$–$H$, $H$–$M$, $M$–$P$, $P$–$S$, $H$–$U$, $U$–$S$, $M$–$U$.

1. aDémontre que le graphe est connexe.
2. bZoé trouve la chaîne $G$–$H$–$M$–$P$–$S$ et en déduit que la distance entre $G$ et $S$ vaut $4$. Repère son erreur, puis donne la bonne distance.
3. cDétermine le diamètre du graphe. Justifie.
4. dLa ville crée une liaison directe $G$–$S$. Détermine le nouveau diamètre du graphe. Justifie.

Ex. 12★★★Pistes cyclables à Tours — À Tours, des pistes cyclables relient sept quartiers $A$, $B$, $C$, $D$, $E$, $F$, $G$. Les arêtes du graphe sont $A$–$B$, $A$–$C$, $B$–$C$, $C$–$D$, $D$–$E$, $D$–$F$, $E$–$F$, $F$–$G$.

1. aÉcris une chaîne de longueur $4$, puis une chaîne de longueur $6$, qui relient $A$ à $G$.
2. bDétermine la distance entre $A$ et $G$. Justifie qu'aucune chaîne plus courte ne relie $A$ à $G$.
3. cPour chaque sommet, donne sa plus grande distance aux autres sommets. Déduis-en le diamètre du graphe.
4. dOn ajoute une seule piste. Propose une piste à ajouter pour que le diamètre devienne au plus égal à $3$, et justifie ton choix.

Ex. 13★★★Tapis roulants à l'aéroport de Nantes — À l'aéroport de Nantes, des tapis roulants à sens unique relient six zones $A$, $B$, $C$, $D$, $E$, $F$. Les arcs du graphe orienté sont $A \to B$, $B \to C$, $C \to A$, $C \to D$, $D \to E$, $E \to F$, $F \to D$.

1. aÉcris un chemin de $A$ vers $F$ et donne sa longueur.
2. bNina affirme : « Il existe un chemin de $A$ vers $F$, donc il existe aussi un chemin de $F$ vers $A$. » A-t-elle raison ? Justifie.
3. cDétermine la longueur du plus court chemin de $B$ vers $F$, puis celle du plus court chemin de $E$ vers $D$.
4. dOn ajoute un seul tapis roulant. Propose un arc à ajouter pour que, depuis chaque zone, on puisse atteindre toutes les autres. Justifie.
5. eDans un graphe orienté, un sommet $G$ a un demi-degré entrant égal à $0$. Démontre qu'aucun chemin ne mène d'un autre sommet à $G$.

Ex. 14★★★Les salles d'un musée à Toulouse — Un musée de Toulouse compte sept salles $H$, $J$, $K$, $L$, $N$, $V$, $W$. Voici la liste complète des portes entre salles : $H$–$J$, $H$–$K$, $J$–$K$, $K$–$L$, $K$–$N$, $L$–$N$, $N$–$V$.

1. aDémontre qu'aucun cycle ne passe par l'arête $N$–$V$. Déduis-en la plus grande longueur possible d'un cycle de ce graphe.
2. bDémontre que le graphe n'est pas connexe. Quelles salles sont reliées à $K$ par une chaîne ?
3. cLe musée veut fermer des portes et garder les six salles $H$, $J$, $K$, $L$, $N$, $V$ reliées entre elles. Combien de portes peut-il fermer au maximum ? Justifie.
4. dLa salle $W$ rouvre avec une seule porte. À quelles salles peut-on la relier pour que la plus grande distance entre $W$ et une autre salle soit la plus petite possible ? Donne cette distance.

Ex. 15★★★Les allées d'un jardin à Nantes — À Nantes, un jardin a six kiosques $P$, $Q$, $R$, $S$, $T$, $U$. Ils sont reliés par les allées $P$–$Q$, $P$–$R$, $Q$–$R$, $Q$–$S$, $R$–$S$, $S$–$T$, $T$–$U$ et $U$–$S$. Lina veut emprunter chaque allée une fois et une seule.

1. aDonne l'ordre du graphe et son nombre d'arêtes.
2. bDonne le degré de chaque sommet.
3. cVérifie le lemme des poignées de main.
4. dJustifie que le graphe est connexe.
5. eCombien de sommets sont de degré impair ? Déduis-en si le graphe admet un cycle eulérien, une chaîne eulérienne non fermée ou ni l'un ni l'autre.
6. fLina veut partir du kiosque $S$. Peut-elle réaliser son parcours ? Justifie.
7. gDonne une chaîne eulérienne du graphe.

Ex. 16★★★Cycle, chaîne ou rien ? — Pour chaque graphe, dis s'il admet un cycle eulérien, une chaîne eulérienne non fermée (précise ses extrémités) ou ni l'un ni l'autre. Justifie.

1. aUn graphe connexe d'ordre $5$ dont les degrés sont $2$, $4$, $2$, $4$, $2$. Donne aussi la longueur du parcours.
2. bUn graphe connexe d'ordre $7$ dont les degrés sont $2$, $3$, $2$, $4$, $2$, $3$, $2$. Donne aussi la longueur du parcours.
3. cLe graphe de sommets $V$, $W$, $X$, $Y$, $Z$ et d'arêtes $V$–$W$, $W$–$X$, $X$–$V$, $X$–$Y$, $Y$–$Z$, $Z$–$X$. Donne un cycle eulérien s'il en existe un.
4. dUn graphe d'ordre $6$ formé de deux triangles, sans aucune arête entre eux.
5. eLe graphe de sommets $A$, $B$, $C$, $D$ et d'arêtes $A$–$B$, $B$–$C$, $C$–$D$, $D$–$B$. Donne une chaîne eulérienne s'il en existe une.
6. fUn graphe connexe dont quatre sommets sont de degré $3$ et tous les autres de degré $2$.

Ex. 17★★★Les pistes cyclables d'Annecy — À Annecy, six carrefours $A$, $B$, $C$, $D$, $E$, $F$ sont reliés par les pistes cyclables $A$–$B$, $A$–$C$, $B$–$C$, $B$–$D$, $C$–$E$, $D$–$E$, $D$–$F$ et $E$–$F$. On veut parcourir chaque piste une fois et une seule.

1. aMalo propose $A$–$B$–$D$–$F$–$E$–$C$–$A$ : « il passe par tous les carrefours, donc c'est un cycle eulérien ». Explique son erreur.
2. bDémontre que le réseau n'admet aucune chaîne eulérienne.
3. cLa mairie crée la piste $B$–$E$. Le nouveau réseau admet-il une chaîne eulérienne ? Si oui, précise ses extrémités. Justifie.
4. dDonne une chaîne eulérienne du nouveau réseau et vérifie qu'elle emprunte toutes les pistes.
5. eAu lieu de $B$–$E$, une seule nouvelle piste peut-elle suffire pour obtenir un cycle eulérien ? Combien de pistes faut-il créer au minimum ? Justifie.

Ex. 18★★★La tournée d'Inès à Colmar — À Colmar, Inès est factrice. Sa tournée relie la poste $L$ et les carrefours $M$, $N$, $O$, $R$, $S$ par les rues $L$–$M$, $L$–$N$, $M$–$N$, $M$–$O$, $M$–$R$, $N$–$O$, $N$–$S$, $O$–$R$ et $O$–$S$.

1. aJustifie que le graphe est connexe et donne le degré de chaque sommet.
2. bInès peut-elle partir de $L$, emprunter chaque rue une fois et une seule, et revenir en $L$ ? Justifie.
3. cDonne un tel parcours et vérifie qu'il emprunte toutes les rues.
4. dDes travaux ferment la rue $M$–$N$. Inès peut-elle encore, en partant de $L$, emprunter une fois et une seule chaque rue ouverte ? Justifie.
5. eDonne un parcours qui emprunte une fois et une seule chaque rue ouverte, et précise d'où Inès doit partir.

Ex. 19★★★Les portes d'un musée à Lyon — À Lyon, un musée a six salles $A$, $B$, $C$, $D$, $E$, $F$. Les portes relient $A$–$B$, $A$–$C$, $A$–$D$, $B$–$C$, $B$–$E$, $C$–$D$, $C$–$F$, $D$–$F$ et $E$–$F$. Une porte se franchit dans les deux sens. Les salles sont les sommets d'un graphe et les portes ses arêtes.

1. aJustifie que le graphe est connexe et donne le degré de chaque sommet. Déduis-en qu'aucun visiteur ne peut franchir chaque porte une fois et une seule.
2. bPour rendre ce parcours possible, le musée perce une seule porte entre deux salles non reliées. Démontre que ces deux salles sont de degré impair, puis donne tous les choix possibles.
3. cLe musée choisit la porte $B$–$D$. Construis un parcours qui franchit chaque porte une fois et une seule ; précise sa salle de départ et sa salle d'arrivée.
4. dZoé affirme : « Avec deux nouvelles portes entre salles non reliées, on pourrait partir de $E$ et y revenir en franchissant chaque porte une fois. » A-t-elle raison ? Justifie et, si oui, donne un tel parcours.

Ex. 20★★★Graphes complets et parité — Pour un entier $n \geqslant 3$, on note $K_n$ le graphe complet d'ordre $n$ : ses sommets sont $1$, $2$, …, $n$ et deux sommets distincts sont toujours adjacents.

1. aDonne le degré de chaque sommet de $K_n$. Déduis-en, grâce au lemme des poignées de main, le nombre d'arêtes de $K_n$.
2. bPour quelles valeurs de $n$ le graphe $K_n$ admet-il un cycle eulérien ? Et une chaîne eulérienne non fermée ? Justifie.
3. cDonne explicitement un cycle eulérien de $K_5$ et vérifie qu'il emprunte chaque arête une fois et une seule.
4. dOn retire des arêtes à $K_6$. Démontre qu'en retirer une seule ne suffit pas pour obtenir une chaîne eulérienne. Donne deux arêtes à retirer qui conviennent et les extrémités de la chaîne.

Ex. 21★★★Le chasse-neige de Briançon — À Briançon, un chasse-neige doit dégager chaque rue une fois et une seule. Les carrefours $D$, $E$, $F$, $G$, $H$, $I$, $J$ sont reliés par les rues $D$–$E$, $D$–$F$, $E$–$F$, $G$–$H$, $G$–$I$, $G$–$J$, $H$–$I$ et $I$–$J$. Les ponts $E$–$G$ et $F$–$H$ sont fermés pour travaux et ne comptent pas.

1. aLucas affirme : « Seuls $G$ et $I$ sont de degré impair, donc le chasse-neige peut tout dégager en allant de $G$ à $I$. » A-t-il raison ? Justifie.
2. bLa mairie ne peut rouvrir qu'un seul pont : $E$–$G$ ou $F$–$H$. Lequel permet au chasse-neige de dégager chaque rue une fois ? Justifie pour chacun des deux.
3. cOn rouvre ce pont. Le dépôt du chasse-neige est en $D$. Peut-il partir du dépôt et dégager chaque rue, pont compris, une fois et une seule ? Justifie.
4. dDonne explicitement un parcours du chasse-neige qui dégage chaque rue, pont compris, une fois et une seule. Précise sa longueur.

Ex. 22★★★Les refuges de Gap — Près de Gap, cinq refuges $A$, $B$, $C$, $D$, $E$ sont reliés par des sentiers. On obtient ainsi un graphe non orienté dont les arêtes sont $A$–$B$, $A$–$C$, $B$–$C$, $B$–$D$, $C$–$D$ et $D$–$E$. On range les sommets dans l'ordre alphabétique.

1. aDonne l'ordre du graphe et son nombre d'arêtes.
2. bÉcris la matrice d'adjacence $M$ du graphe.
3. cExplique pourquoi $M$ est symétrique.
4. dCalcule la somme des coefficients de la ligne de $D$. Que représente ce nombre ?
5. eCalcule $(M^2)_{14}$ (ligne $A$, colonne $D$) en faisant le produit ligne par colonne, puis interprète ce nombre.
6. fCalcule $(M^2)_{11}$ et compare ce nombre au degré de $A$.
7. gOn trouve $(M^2)_{15}=0$. Sami en déduit qu'aucun chemin ne relie $A$ à $E$. A-t-il raison ? Justifie.

Ex. 23★★★Sens uniques à Nantes — Dans un quartier de Nantes, les rues à sens unique entre les places $A$, $B$, $C$, $D$ forment un graphe orienté. Sa matrice d'adjacence, avec les sommets dans l'ordre alphabétique, est $M=\begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix}$.

1. aÉcris la liste de tous les arcs du graphe.
2. bJustifie à l'aide de $M$ que ce graphe ne peut pas être non orienté.
3. cQue signifie le coefficient $m_{44}=1$ ?
4. dDonne le nombre d'arcs qui partent de $C$.
5. eCalcule $M^2$.
6. fLucas affirme : « $M^2=M$, car $0^2=0$ et $1^2=1$. » A-t-il raison ? Justifie.
7. gÉcris tous les chemins de longueur $2$ qui vont de $C$ à $B$.

Ex. 24★★★Un réseau d'amis — Six amis sont reliés sur un réseau social : Anaïs ($A$), Basile ($B$), Chloé ($C$), Dylan ($D$), Emma ($E$) et Farid ($F$). Le graphe non orienté a pour arêtes $A$–$B$, $A$–$C$, $B$–$C$, $C$–$D$, $D$–$E$, $D$–$F$ et $E$–$F$. $M$ est sa matrice d'adjacence, avec les sommets dans l'ordre alphabétique.

1. aSans calculer toute la matrice $M^2$, détermine sa ligne $A$ à l'aide des voisins de $A$.
2. bDéduis-en le nombre de chemins de longueur $3$ de $A$ à $E$, puis écris ce ou ces chemins.
3. cDéduis-en la distance entre $A$ et $E$. Justifie.
4. dEn Python, la liste de listes M3 contient $M^3$. Noé tape print(M3[1][5]) pour afficher le nombre de chemins de longueur $3$ de $A$ à $E$. Corrige son instruction.

Ex. 25★★★Triangles dans un club d'échecs — Dans un club d'échecs de Dijon, quatre joueurs $A$, $B$, $C$, $D$ ont déjà joué l'un contre l'autre selon le graphe non orienté d'arêtes $A$–$B$, $A$–$C$, $A$–$D$, $B$–$C$ et $C$–$D$. $M$ est sa matrice d'adjacence (ordre alphabétique). Pour chaque affirmation, dis si elle est vraie ou fausse et justifie.

1. a« Il y a exactement $2$ chemins de longueur $2$ de $B$ à $D$. »
2. b« Il y a $4$ chemins de longueur $3$ qui partent de $A$ et reviennent en $A$, donc $A$ appartient à $4$ triangles. »
3. c« Le graphe contient exactement deux triangles. »
4. d« Il y a exactement $2$ chemins de longueur au plus $2$ de $A$ à $C$. »

Ex. 26★★★Pistes cyclables de l'île de Ré — Sur l'île de Ré, des pistes cyclables relient cinq villages $A$, $B$, $C$, $D$, $E$. Elles forment le graphe non orienté d'arêtes $C$–$E$, $A$–$D$, $B$–$C$, $A$–$B$, $C$–$D$, $B$–$E$. On note $M$ sa matrice d'adjacence, avec les sommets rangés dans l'ordre alphabétique.

1. aÉcris $M$. Justifie que la somme de tous ses coefficients est le double du nombre de pistes, puis vérifie-le.
2. bCalcule $M^2$. Déduis-en le diamètre du graphe. Justifie.
3. cJustifie que $M^2$ est symétrique, puis que $(M^4)_{AA}$ est la somme des carrés des coefficients de la ligne $A$ de $M^2$. Calcule $(M^4)_{AA}$ et interprète-le.
4. dCalcule les coefficients diagonaux de $M^3$. Justifie que leur somme divisée par $6$ est le nombre de triangles du graphe, puis nomme chaque triangle.

Ex. 27★★★Le visiteur du musée de Lyon — Dans un musée de Lyon, quatre salles $A$, $B$, $C$, $D$ communiquent deux à deux par une porte. Chaque minute, Malik franchit une porte. On note $M$ la matrice d'adjacence du graphe (ordre alphabétique). Pour $n \geqslant 1$, on pose $u_n = (M^n)_{AA}$ et $v_n = (M^n)_{AB}$. On admet que $(M^n)_{AC} = (M^n)_{AD} = v_n$.

1. aÉcris $M$ et calcule $M^2$. Interprète $(M^2)_{AA}$ en citant les parcours concernés.
2. bJustifie qu'il y a $3^n$ chemins de longueur $n$ qui partent de $A$. Déduis-en une relation entre $u_n$ et $v_n$.
3. cEn écrivant $M^{n+1} = M^n \times M$, démontre que $u_{n+1} = 3v_n$. Déduis-en $u_{n+1}$ en fonction de $u_n$ et de $n$.
4. dDémontre par récurrence que, pour tout $n \geqslant 1$, $u_n = \frac{3^n + 3 \times (-1)^n}{4}$.
5. eCalcule $u_6$ et $v_6$. Après $6$ minutes, Malik a-t-il plus de parcours possibles qui finissent en $A$ ou qui finissent en $B$ ? Justifie.

Ex. 28★★★Le jeu de plateau de Lille — À Lille, Ben a créé un jeu de plateau. Un pion se déplace entre quatre cases $A$, $B$, $C$, $D$ en suivant une flèche à chaque coup. La matrice d'adjacence du graphe orienté (ordre alphabétique ; ligne = case de départ) est $M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}$.

1. aExplique pourquoi $M$ n'est pas symétrique. Interprète le coefficient situé ligne $B$, colonne $B$.
2. bHugo affirme : « La colonne $D$ contient deux $1$, donc deux flèches partent de $D$. » Corrige-le, puis donne le nombre total d'arcs du graphe.
3. cCalcule $M^2$, puis $M^3$.
4. dLe programme suivant calcule $M^3$. M = [ [0, 1, 1, 0], [0, 1, 0, 1], [1, 0, 0, 1], [1, 0, 0, 0] ] def produit(X, Y): n = len(X) Z = [ [0] * n for i in range(n)] for i in range(n): for j in range(n): for r in range(n): Z[i][j] = Z[i][j] + X[i][r] * Y[r][j] return Z M2 = produit(M, M) M3 = produit(M2, M) print(M3[0][3]) Quel nombre affiche-t-il ? Interprète-le et écris le ou les chemins correspondants.
5. eÉcris une instruction Python qui affiche le nombre de chemins de longueur $4$ de $A$ à $D$. Donne ce nombre en multipliant une ligne par une colonne.

Ex. 29★★★Lire une matrice de transition 3 × 3 — Chaque minute, une abeille se trouve sur la lavande $L$, sur le trèfle $T$ ou à la ruche $R$. Dans l'ordre $(L\,;T\,;R)$, sa matrice de transition est $P = \begin{pmatrix} 0{,}2 & 0{,}8 & 0 \\ 0{,}35 & 0{,}4 & 0{,}25 \\ 0 & 0 & 1 \end{pmatrix}$.

1. aL'abeille est sur la lavande. Quelle est la probabilité qu'elle soit sur le trèfle la minute suivante ?
2. bQue représente le coefficient $p_{21}$ ? Donne sa valeur.
3. cListe les arcs du graphe probabiliste associé à $P$ avec leurs poids, boucles comprises.
4. dVérifie que la deuxième ligne de $P$ somme à $1$.
5. eUne fois à la ruche, l'abeille peut-elle en repartir ? Justifie à l'aide de $P$.
6. fLa première colonne de $P$ somme à $0{,}55$. Est-ce une anomalie ? Justifie.

Ex. 30★★★Compléter un graphe probabiliste — Chaque jour, Sami va au lycée à vélo ($V$), en bus ($B$) ou à pied ($M$). Le graphe probabiliste a pour arcs $V \to B$ ($0{,}25$), $V \to M$ ($0{,}1$), $B \to V$ ($0{,}45$), $M \to V$ ($0{,}5$), ainsi que $B \to M$ et $M \to B$, de poids inconnus. $B$ a une boucle de poids $0{,}35$, $V$ une boucle de poids inconnu, $M$ aucune boucle.

1. aCalcule le poids de la boucle en $V$, puis celui de l'arc $B \to M$.
2. bCalcule le poids de l'arc $M \to B$.
3. cÉcris la matrice de transition $P$ dans l'ordre $(V\,;B\,;M)$.
4. dDonne $p_{32}$ et interprète-le dans le contexte.
5. eSami affirme : « J'ai autant de chances de passer du vélo au bus que du bus au vélo. » A-t-il raison ? Justifie.

Ex. 31★★★Deux opérateurs : de l'arbre à la matrice — Deux opérateurs, Alto ($A$) et Brio ($B$), se partagent les clients d'une région. Chaque mois, 15 % des abonnés de $A$ passent chez $B$ et 8 % des abonnés de $B$ passent chez $A$ ; les autres restent. Au mois $0$, 60 % des clients sont chez $A$. On note $\pi_n = \begin{pmatrix} a_n & b_n \end{pmatrix}$ la distribution au mois $n$.

1. aConstruis l'arbre pondéré qui va du mois $n$ au mois $n+1$ : premier niveau, $A$ ou $B$ au mois $n$ ; second niveau, $A$ ou $B$ au mois $n+1$.
2. bÉcris la matrice de transition $P$ dans l'ordre $(A\,;B)$. Justifie la place du coefficient $0{,}15$.
3. cCalcule $\pi_1$.
4. dÀ l'aide de l'arbre, exprime $a_{n+1}$ en fonction de $a_n$ seulement.

Ex. 32★★★L'erreur d'Inès : lignes ou colonnes ? — Chaque soir, Malo lit ($L$), fait du sport ($S$) ou joue ($J$). Après $L$ : $S$ avec $0{,}5$, $J$ avec $0{,}2$, sinon $L$. Après $S$ : jamais $S$, $L$ avec $0{,}7$, sinon $J$. Après $J$ : $L$ avec $0{,}6$, jamais $S$, sinon $J$. Dans l'ordre $(L\,;S\,;J)$, Inès propose $M = \begin{pmatrix} 0{,}3 & 0{,}7 & 0{,}6 \\ 0{,}5 & 0 & 0 \\ 0{,}2 & 0{,}3 & 0{,}4 \end{pmatrix}$.

1. aCalcule la somme de chaque ligne et de chaque colonne de $M$. Déduis-en que $M$ n'est pas une matrice de transition.
2. bExplique l'erreur d'Inès, puis écris la bonne matrice de transition $P$ dans l'ordre $(L\,;S\,;J)$.
3. cInès lit dans $M$ : « ligne 1, colonne 2 : $0{,}7$, donc après une soirée lecture, Malo fait du sport avec la probabilité $0{,}7$ ». A-t-elle raison ? Justifie.
4. dVrai ou faux : « Quelle que soit son activité un soir, Malo lit le soir suivant avec une probabilité d'au moins $0{,}3$. » Justifie à l'aide de $P$.

Ex. 33★★★Vélos en libre-service : la matrice du rapport — À Lorient, un vélo en libre-service est rendu à l'une des stations Nord ($N$), Gare ($G$) ou Halles ($H$). On le suit de trajet en trajet. Le rapport de la mairie donne, dans l'ordre $(N\,;G\,;H)$, la matrice $Q = \begin{pmatrix} 0{,}5 & 0{,}2 & 0{,}1 \\ 0{,}3 & 0{,}6 & 0{,}3 \\ 0{,}2 & 0{,}2 & 0{,}6 \end{pmatrix}$. Le coefficient de la ligne $i$ et de la colonne $j$ de $Q$ est la probabilité qu'un vélo pris à la station $j$ soit rendu à la station $i$.

1. aCalcule la somme de chaque ligne de $Q$. Justifie que $Q$ n'est pas la matrice de transition au sens du cours. Écris la matrice de transition $P$ dans l'ordre $(N\,;G\,;H)$.
2. bBen préfère l'ordre $(G\,;N\,;H)$. Écris la matrice de transition $P'$ dans cet ordre.
3. cUn vélo est pris aux Halles. Calcule la probabilité qu'il soit rendu à la Gare au bout de deux trajets. Fais le calcul avec $P$, puis contrôle-le avec $P'$.
4. dKenza lit dans le rapport : « Un vélo pris à la Gare y est rendu avec une probabilité supérieure à $0{,}5$, et $30$ % des vélos pris à la Gare sont rendus aux Halles. » Vrai ou faux ? Justifie.
5. eAu départ, $40$ % des vélos sont à Nord, $40$ % à Gare et $20$ % aux Halles. Calcule $\pi_1 = \pi_0 P$, avec $\pi_0 = \begin{pmatrix} 0{,}4 & 0{,}4 & 0{,}2 \end{pmatrix}$.

Ex. 34★★★Streaming : retrouver un taux de résiliation — Une plateforme de musique compte des abonnés Premium ($P$), Standard ($S$) et résiliés ($R$). Chaque mois, $10$ % des Premium passent en Standard et $5$ % résilient. $20$ % des Standard passent en Premium et une proportion $x$ d'entre eux résilie. Un résilié ne se réabonne jamais. Les autres abonnés gardent leur formule. $X_n$ est l'état d'un abonné au mois $n$.

1. aÉcris, en fonction de $x$, la matrice de transition $T$ dans l'ordre $(P\,;S\,;R)$. Donne les valeurs possibles de $x$.
2. bUn abonné est Standard au mois $0$. Construis l'arbre pondéré des mois $1$ et $2$. Déduis-en $p(X_2 = P)$ en fonction de $x$.
3. cUne étude montre que cette probabilité vaut $0{,}3$. Détermine $x$, puis écris $T$.
4. dAvec cette valeur de $x$, un abonné est Premium au mois $0$. Calcule la probabilité qu'il ait résilié au mois $2$.

Ex. 35★★★Un pion sur trois cases : deux réglages possibles — Dans un jeu de plateau, un pion occupe l'une des trois cases Rouge ($R$), Vert ($V$) ou Jaune ($J$). À chaque tour, il reste sur sa case avec la probabilité $a$. Il va sur chacune des deux autres cases avec la même probabilité $b$. Les réels $a$ et $b$ sont dans $[0\,;1]$.

1. aÉcris la matrice de transition $P$ dans l'ordre $(R\,;V\,;J)$. Justifie que $a = 1 - 2b$ et que $0 \leq b \leq \frac{1}{2}$.
2. bLe pion part de $R$. Exprime en fonction de $b$ seul la probabilité qu'il soit sur $R$ après deux tours.
3. cDétermine toutes les valeurs de $b$ pour lesquelles cette probabilité vaut $\frac{1}{2}$. Écris $P$ dans chaque cas.
4. dOn prend la valeur de $b$ pour laquelle $a \neq 0$. Le pion part de $R$. Calcule la probabilité qu'il soit sur $V$ après deux tours.
5. eNoé affirme : « Pour ce jeu, lire $P$ par lignes ou par colonnes donne le même graphe probabiliste. » A-t-il raison ? Justifie.

Ex. 36★★★Romans ou BD — Chaque samedi, Lina emprunte à la médiathèque de Rennes un roman ($R$) ou une BD ($B$). Le premier samedi correspond à $n = 0$ : ce jour-là, elle emprunte un roman. On note $\pi_n = \begin{pmatrix} r_n & b_n \end{pmatrix}$ la distribution au samedi $n$. La matrice de transition, dans l'ordre $R$, $B$, est $P = \begin{pmatrix} 0{,}6 & 0{,}4 \\ 0{,}3 & 0{,}7 \end{pmatrix}$.

1. aÉcris la distribution initiale $\pi_0$.
2. bCalcule $\pi_1 = \pi_0 P$.
3. cCalcule $\pi_2$.
4. dVérifie que la somme des coefficients de $\pi_2$ vaut $1$.
5. eQuelle valeur de $n$ correspond au 4e samedi ? Calcule la probabilité que Lina emprunte un roman ce samedi-là.
6. fTom propose de calculer $P\pi_1$. Explique pourquoi ce produit n'a pas de sens.

Ex. 37★★★Le robot aspirateur d'Inès — À Lille, toutes les dix minutes, le robot aspirateur d'Inès change de pièce ou reste dans la même : salon $S$, cuisine $C$ ou entrée $E$. Dans l'ordre $S$, $C$, $E$ : $P = \begin{pmatrix} 0{,}5 & 0{,}3 & 0{,}2 \\ 0{,}4 & 0{,}4 & 0{,}2 \\ 0{,}1 & 0{,}3 & 0{,}6 \end{pmatrix}$ et la calculatrice donne $P^2 = \begin{pmatrix} 0{,}39 & 0{,}33 & 0{,}28 \\ 0{,}38 & x & 0{,}28 \\ 0{,}23 & 0{,}33 & y \end{pmatrix}$.

1. aLe robot est dans la cuisine. Lis la probabilité qu'il soit dans l'entrée dix minutes plus tard.
2. bLe robot est dans le salon. Lis la probabilité qu'il soit dans l'entrée vingt minutes plus tard.
3. cDétermine $x$ sans faire de produit de matrices.
4. dCalcule $y$ par un produit ligne × colonne.
5. eLéo affirme : « parti de l'entrée, le robot y est encore 20 minutes plus tard avec une probabilité de $0{,}6^2$ ». A-t-il raison ? Justifie.
6. fLe robot part du salon ou de la cuisine avec la même probabilité : $\pi_0 = \begin{pmatrix} 0{,}5 & 0{,}5 & 0 \end{pmatrix}$. Calcule $\pi_2$.

Ex. 38★★★La météo de Brest : corrige Sacha — À Brest, chaque jour est sec ($S$) ou humide ($H$). Un jour sec est suivi d'un jour sec avec une probabilité de $0{,}8$. Un jour humide est suivi d'un jour sec avec une probabilité de $0{,}45$. Lundi est sec et correspond à $n = 0$. On note $\pi_n = \begin{pmatrix} s_n & h_n \end{pmatrix}$. Voici les réponses de Sacha, à corriger.

1. aSacha écrit $\pi_1 = P\pi_0$ et trouve la colonne $\begin{pmatrix} 0{,}8 \\ 0{,}45 \end{pmatrix}$. Écris $P$ (ordre $S$, $H$), donne deux raisons qui montrent que ce calcul est faux, puis donne $\pi_1$.
2. bCalcule $\pi_2$.
3. cSacha affirme : « s'il fait humide lundi, il fait sec mercredi avec une probabilité de $0{,}45^2$ ». A-t-il raison ? Justifie et donne la bonne valeur.
4. dPour connaître le temps de jeudi, Sacha calcule $\pi_4$. Corrige l'indice, puis donne la probabilité que jeudi soit sec, arrondie au centième.

Ex. 39★★★Deux fournisseurs d'accès à Toulouse — À Toulouse, chaque année, $10\,\%$ des abonnés de Volt ($V$) passent chez Ondi ($O$) et $25\,\%$ des abonnés d'Ondi passent chez Volt ; les autres restent chez le même fournisseur. En 2026, $40\,\%$ des abonnés sont chez Volt. On note $\pi_n = \begin{pmatrix} a_n & b_n \end{pmatrix}$ la distribution en l'année $2026 + n$.

1. aÉcris la matrice de transition $P$ (ordre $V$, $O$). En utilisant $\pi_{n+1} = \pi_n P$ et $b_n = 1 - a_n$, démontre que $a_{n+1} = 0{,}65a_n + 0{,}25$.
2. bDétermine le réel $\ell$ tel que $\ell = 0{,}65\ell + 0{,}25$, puis démontre que la suite $u_n = a_n - \ell$ est géométrique.
3. cDéduis-en l'expression de $a_n$ en fonction de $n$.
4. dQuelle valeur de $n$ correspond à l'année 2030 ? Donne la part des abonnés de Volt cette année-là, arrondie au millième.

Ex. 40★★★Vélo ou tram à Grenoble — À Grenoble, chaque jour, Maëlle va au lycée à vélo ($V$) ou en tram ($T$). Si elle prend le vélo un jour, elle le reprend le lendemain avec une probabilité de $0{,}7$. Si elle prend le tram, elle prend le vélo le lendemain avec une probabilité de $0{,}2$. Le jour de la rentrée, noté $n = 0$, elle prend le vélo. On note $\pi_n = \begin{pmatrix} a_n & b_n \end{pmatrix}$ la distribution du jour $n$ (ordre $V$, $T$).

1. aÉcris la matrice de transition $P$ et la distribution initiale $\pi_0$.
2. bDémontre que, pour tout $n \in \mathbb{N}$, $a_{n+1} = 0{,}5a_n + 0{,}2$.
3. cOn pose $u_n = a_n - 0{,}4$. Démontre que $(u_n)$ est géométrique, puis exprime $a_n$ en fonction de $n$.
4. dExprime $b_n$ en fonction de $n$. Déduis-en la probabilité que Maëlle prenne le tram le 4e jour.
5. eDétermine à partir de quel jour la probabilité que Maëlle prenne le vélo devient inférieure à $0{,}41$.

Ex. 41★★★Le food truck de Yanis à Bordeaux — Pendant un festival à Bordeaux, le food truck de Yanis s'installe chaque jour sur le quai ($Q$), au marché ($M$) ou à l'université ($U$). Le premier jour correspond à $n = 0$ : ce jour-là, Yanis tire au sort son emplacement entre le quai et l'université, de façon équiprobable. Dans l'ordre $Q$, $M$, $U$, la matrice de transition est $P = \begin{pmatrix} 0{,}5 & 0{,}3 & 0{,}2 \\ 0{,}2 & 0{,}6 & 0{,}2 \\ 0{,}4 & 0{,}1 & 0{,}5 \end{pmatrix}$. On note $\pi_n$ la distribution du jour $n$.

1. aÉcris $\pi_0$, puis calcule $\pi_1$ et contrôle la somme de ses coefficients.
2. bCalcule $P^2$. Vérifie que chaque ligne de $P^2$ a une somme égale à $1$.
3. cUn jour, le truck est à l'université. Pour la probabilité qu'il soit au marché deux jours plus tard, Noé lit $0{,}26$ dans la colonne $U$ de $P^2$. Corrige-le.
4. dCalcule $\pi_2$ à l'aide de $P^2$, puis contrôle ton résultat avec $\pi_1$.
5. eCalcule la probabilité que le truck soit à l'université le 4e jour du festival. Arrondis au centième.

Ex. 42★★★Vélos en libre-service à Lyon — À Lyon, un vélo en libre-service est rendu chaque soir à la station Bellecour ($B$) ou à la station Part-Dieu ($D$). Le premier soir correspond à $n = 0$. Dans l'ordre $B$, $D$, la matrice de transition est $P = \begin{pmatrix} 0{,}6 & 0{,}4 \\ 0{,}1 & 0{,}9 \end{pmatrix}$. On pose $J = \begin{pmatrix} 0{,}2 & 0{,}8 \\ 0{,}2 & 0{,}8 \end{pmatrix}$ et $K = \begin{pmatrix} 0{,}8 & -0{,}8 \\ -0{,}2 & 0{,}2 \end{pmatrix}$.

1. aCalcule $JP$ et $KP$, puis exprime chacun de ces produits à l'aide de $J$ ou de $K$.
2. bDémontre par récurrence que, pour tout $n \in \mathbb{N}$, $P^n = J + 0{,}5^n K$.
3. cLe premier soir, le vélo est rendu à Part-Dieu. Donne la probabilité qu'il soit rendu à Bellecour le 6e soir, arrondie au millième.
4. dOn suppose maintenant $\pi_0 = \begin{pmatrix} 0{,}3 & 0{,}7 \end{pmatrix}$. Exprime $\pi_n$ en fonction de $n$, puis contrôle la somme de ses coefficients.
5. eLou affirme : « Quelle que soit la distribution $\pi_0$, $\pi_n$ tend vers la même distribution. » A-t-elle raison ? Justifie.

Ex. 43★★★Distributions invariantes à deux états — Chaque matrice $P$ est la matrice de transition d'une chaîne de Markov à deux états $A$ et $B$, dans cet ordre.

1. a$P = \begin{pmatrix} 0{,}6 & 0{,}4 \\ 0{,}1 & 0{,}9 \end{pmatrix}$. Calcule $\begin{pmatrix} 0{,}2 & 0{,}8 \end{pmatrix} P$. Cette distribution est-elle invariante ? Justifie.
2. b$P = \begin{pmatrix} 0{,}7 & 0{,}3 \\ 0{,}5 & 0{,}5 \end{pmatrix}$. La distribution $\begin{pmatrix} 0{,}5 & 0{,}5 \end{pmatrix}$ est-elle invariante ? Justifie.
3. c$P = \begin{pmatrix} 0{,}75 & 0{,}25 \\ 0{,}2 & 0{,}8 \end{pmatrix}$. Pose $\pi = \begin{pmatrix} x & 1-x \end{pmatrix}$ et détermine la distribution invariante.
4. dLa chaîne passe de $A$ à $B$ avec la probabilité $0{,}35$ et de $B$ à $A$ avec la probabilité $0{,}45$. Détermine son état stable.
5. e$P = \begin{pmatrix} 1 & 0 \\ 0{,}25 & 0{,}75 \end{pmatrix}$. Détermine la distribution invariante, puis interprète-la.
6. f$P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}6 & 0{,}4 \end{pmatrix}$. Malo vérifie que $\begin{pmatrix} 3 & 1 \end{pmatrix} P = \begin{pmatrix} 3 & 1 \end{pmatrix}$ et conclut que c'est l'état stable. A-t-il raison ? Corrige si besoin.

Ex. 44★★★Le chat entre trois pièces — Chaque heure, un chat change de pièce (ou reste) entre la cuisine $C$, le salon $S$ et la chambre $H$. La matrice de transition, dans l'ordre $C$, $S$, $H$, est $P = \begin{pmatrix} 0{,}7 & 0{,}3 & 0 \\ 0{,}2 & 0{,}6 & 0{,}2 \\ 0 & 0{,}4 & 0{,}6 \end{pmatrix}$. On cherche $\pi = \begin{pmatrix} x & y & z \end{pmatrix}$ telle que $\pi P = \pi$.

1. aÉcris les trois équations qui traduisent $\pi P = \pi$.
2. bAdditionne-les membre à membre. Qu'obtiens-tu ? Explique pourquoi on doit ajouter la condition $x + y + z = 1$.
3. cÀ l'aide de la première et de la troisième équation, exprime $x$ et $z$ en fonction de $y$.
4. dDéduis-en la distribution invariante $\pi$, en fractions.
5. eVérifie ton résultat avec la deuxième équation.

Ex. 45★★★Météo à Brest : l'erreur d'Inès — À Brest, on modélise le temps qu'il fait jour après jour par trois états : soleil $S$, nuages $N$, pluie $L$.

1. aÉcris la matrice de transition $P$ (ordre $S$, $N$, $L$). Calcule la probabilité qu'il pleuve dans deux jours s'il fait soleil aujourd'hui.
2. bExplique pourquoi Inès obtient $0 = 0$, et ce qu'elle a oublié.
3. cDétermine l'état stable $\pi$, en fractions.
4. dOn admet que la distribution du temps converge vers $\pi$. Combien de jours de pluie environ peut-on prévoir sur une année de $365$ jours ?

Ex. 46★★★Deux opérateurs : Volta et Nexo — Volta et Nexo se partagent les abonnés d'une ville. Chaque mois, $10\,\%$ des abonnés de Volta passent chez Nexo et $20\,\%$ de ceux de Nexo passent chez Volta. Au départ, Volta a $40\,\%$ des abonnés. On note $a_n$ la part de Volta au bout de $n$ mois, et $\pi_n = \begin{pmatrix} a_n & 1-a_n \end{pmatrix}$.

1. aÉcris la matrice de transition $P$ (ordre Volta, Nexo), puis exprime $a_{n+1}$ en fonction de $a_n$ à l'aide de $\pi_{n+1} = \pi_n P$.
2. bDétermine l'état stable $\pi = \begin{pmatrix} x & 1-x \end{pmatrix}$ de la chaîne.
3. cOn pose $u_n = a_n - x$, avec le $x$ trouvé à la question précédente. Démontre que $(u_n)$ est géométrique, puis exprime $a_n$ en fonction de $n$.
4. dDéduis-en la limite de $(a_n)$ et interprète-la. Cette limite dépend-elle de la part de départ $a_0$ ? Justifie.

Ex. 47★★★Une trottinette entre deux stations lyonnaises — À Lyon, une trottinette en libre-service est garée chaque soir à la station Bellecour $B$ ou à la station Part-Dieu $D$. Si elle est à $B$ un soir, elle y est encore le lendemain soir avec la probabilité $0{,}8$. Si elle est à $D$, elle est à $B$ le lendemain soir avec la probabilité $0{,}3$. Le soir $0$, elle est à $D$. On note $b_n$ la probabilité qu'elle soit à $B$ le soir $n$.

1. aÉcris la matrice de transition $P$ (ordre $B$, $D$), puis démontre que $b_{n+1} = 0{,}5\,b_n + 0{,}3$ pour tout entier $n$.
2. bDétermine le réel $\ell$ tel que la suite $(b_n - \ell)$ soit géométrique. Exprime $b_n$ en fonction de $n$, déduis-en sa limite et interprète-la.
3. cDétermine par le calcul, à l'aide d'une inéquation et de la fonction $\ln$, le plus petit entier $n$ tel que $b_n > 0{,}55$.
4. dLucas affirme : « La chaîne a une distribution invariante, donc à partir d'un certain soir, $b_n$ sera exactement égal à sa limite. » Vrai ou faux ? Justifie.

Ex. 48★★★Les abeilles d'un jardin d'Angers — Dans un jardin d'Angers, $3\,400$ abeilles butinent trois massifs : lavande $L$, rosiers $R$, tournesols $T$. Toutes les dix minutes, chaque abeille change de massif ou reste, indépendamment des autres, selon la matrice de transition (ordre $L$, $R$, $T$) $P = \begin{pmatrix} 0{,}5 & 0{,}25 & 0{,}25 \\ 0{,}2 & 0{,}6 & 0{,}2 \\ 0{,}1 & 0{,}3 & 0{,}6 \end{pmatrix}$. On cherche une distribution $\pi = \begin{pmatrix} x & y & z \end{pmatrix}$ telle que $\pi P = \pi$.

1. aÉcris les trois équations de $\pi P = \pi$ sous la forme $\ldots = 0$. Démontre que l'une d'elles est une conséquence des deux autres.
2. bDémontre que si $\pi$ vérifie $\pi P = \pi$, alors $k\pi$ la vérifie aussi pour tout réel $k$. Qu'en déduis-tu si l'on oublie la condition $x + y + z = 1$ ?
3. cDétermine la distribution invariante $\pi$, en fractions. Vérifie-la avec l'équation que tu n'as pas utilisée.
4. dOn admet que $\pi_n$ converge vers $\pi$ quel que soit $\pi_0$. Combien d'abeilles butinent en moyenne chaque massif à long terme ?
5. eÀ 14 h, Romane, l'apicultrice, observe exactement la répartition trouvée à la question précédente. Combien d'abeilles attend-elle en moyenne sur chaque massif à 14 h 10, puis à 15 h ? Justifie.

Ex. 49★★★Les soirées de Yanis — Chaque soir, Yanis, à Toulouse, fait du sport $S$, lit $L$ ou joue aux jeux vidéo $J$. La matrice de transition, dans l'ordre $S$, $L$, $J$, est $P = \begin{pmatrix} 0{,}85 & 0{,}15 & 0 \\ 0{,}25 & 0{,}5 & 0{,}25 \\ 0{,}25 & 0{,}25 & 0{,}5 \end{pmatrix}$. Le soir $0$, il lit. On note $\pi_n = \begin{pmatrix} s_n & l_n & j_n \end{pmatrix}$ la distribution du soir $n$.

1. aDémontre que $s_{n+1} = 0{,}6\,s_n + 0{,}25$ pour tout entier $n$.
2. bQuelle valeur ce programme affiche-t-il ? Justifie avec les valeurs successives de s, puis interprète le résultat. s = 0 n = 0 while s <= 0.55: s = 0.6 * s + 0.25 n = n + 1 print(n)
3. cDétermine la distribution invariante $\pi = \begin{pmatrix} x & y & z \end{pmatrix}$. On admet que $\pi_n$ converge vers $\pi$ : quelle part de ses soirées Yanis consacre-t-il aux jeux vidéo à long terme ?
4. dBen affirme : « Si Yanis avait fait du sport le soir $0$, $s_n$ se stabiliserait autour d'une autre valeur. » Vrai ou faux ? Démontre-le pour tout $s_0$ de $[0\,;1]$.