Devoir surveillé : Matrices, systèmes, suites de matrices, graphes et chaînes de Markov

1. a)$AB=\left(\begin{array}{cc}2\times 0+(-1)\times (-1)& 2\times 2+(-1)\times 1\\ 1\times 0+3\times (-1)& 1\times 2+3\times 1\end{array}\right)=\left(\begin{array}{cc}1& 3\\ -3& 5\end{array}\right)$ et $BA=\left(\begin{array}{cc}0\times 2+2\times 1& 0\times (-1)+2\times 3\\ (-1)\times 2+1\times 1& (-1)\times (-1)+1\times 3\end{array}\right)=\left(\begin{array}{cc}2& 6\\ -1& 4\end{array}\right)$. Comme $AB\ne BA$, les matrices $A$ et $B$ ne commutent pas. (1 pt : 0,5 par produit) (1)
2. b)$det(C)=3\times 2-1\times 4=2\ne 0$, donc $C$ est inversible et $C^{-1}={\displaystyle \frac{1}{2}}\left(\begin{array}{cc}2& -1\\ -4& 3\end{array}\right)=\left(\begin{array}{cc}1& -0,5\\ -2& 1,5\end{array}\right)$. Contrôle, ligne 1 de $C$ par colonne 1 de $C^{-1}$ : $3\times 1+1\times (-2)=1$. (1 pt : 0,5 pour le déterminant, 0,5 pour l'inverse) (1)
3. c)D'après le lemme des poignées de main, la somme des degrés vaut le double du nombre $m$ d'arêtes : $1+2+2+3+4=12=2m$, donc le graphe a $m=6$ arêtes. (1 pt) (1)
4. d)Les sommets sont les équipes et chaque match est une arête : deux équipes quelconques sont reliées, le graphe est le graphe complet $K_n$, où $n$ est le nombre d'équipes. Il a ${\displaystyle \frac{n(n-1)}{2}}$ arêtes, donc $n(n-1)=56=8\times 7$. Le produit $n(n-1)$ augmente avec l'entier $n⩾1$ ($7\times 6=42$, $9\times 8=72$) : $n=8$. Il y a $8$ équipes. (1 pt : 0,5 pour la modélisation, 0,5 pour $n$) (1)
5. e)Le coefficient de la ligne $i$ et de la colonne $j$ vaut $1$ quand l'arc $i\to j$ existe : les arcs sont $1\to 2$, $1\to 3$, $2\to 3$ et $3\to 1$ ($4$ arcs, la somme des coefficients). Le degré sortant de $3$ est la somme de la ligne $3$ : $d^{+}(3)=1$ ; son degré entrant est la somme de la colonne $3$ : $d^{-}(3)=2$. (1 pt : 0,5 pour les arcs, 0,5 pour les degrés) (1)

Méthode — Avant un produit, on écrit les formats ; pour l'inverse d'une matrice $2\times 2$, on calcule d'abord le déterminant, puis on contrôle un coefficient du produit $C{C}^{-1}$.

1. a)$det(A)=5\times 4-3\times 7=20-21=-1\ne 0$, donc $A$ est inversible et $A^{-1}={\displaystyle \frac{1}{-1}}\left(\begin{array}{cc}4& -3\\ -7& 5\end{array}\right)=\left(\begin{array}{cc}-4& 3\\ 7& -5\end{array}\right)$. Contrôle : $5\times (-4)+3\times 7=1$. (1 pt : 0,5 pour le déterminant, 0,5 pour l'inverse) (1)
2. b)Le système s'écrit $AX=B$ avec $X=\left(\begin{array}{c}x\\ y\end{array}\right)$ et $B=\left(\begin{array}{c}1\\ 2\end{array}\right)$. Comme $A$ est inversible, $X=A^{-1}B=\left(\begin{array}{c}-4\times 1+3\times 2\\ 7\times 1-5\times 2\end{array}\right)=\left(\begin{array}{c}2\\ -3\end{array}\right)$. Le système admet pour unique solution le couple $(2;-3)$ ; contrôle : $14-12=2$. (1 pt) (1)
3. c)$U_2=A{U}_1$ ; en multipliant à gauche par $A^{-1}$ : $A^{-1}{U}_2=(A^{-1}A)U_1=U_1$. Donc $U_1=\left(\begin{array}{cc}-4& 3\\ 7& -5\end{array}\right)\left(\begin{array}{c}2\\ 3\end{array}\right)=\left(\begin{array}{c}-8+9\\ 14-15\end{array}\right)=\left(\begin{array}{c}1\\ -1\end{array}\right)$. (1 pt) (1)
4. d)De même, $U_0=A^{-1}{U}_1=\left(\begin{array}{c}-4-3\\ 7+5\end{array}\right)=\left(\begin{array}{c}-7\\ 12\end{array}\right)$. Vérification : $A{U}_0=\left(\begin{array}{c}-35+36\\ -49+48\end{array}\right)=\left(\begin{array}{c}1\\ -1\end{array}\right)=U_1$. (1 pt) (1)

Erreur fréquente — De $AX=B$, on tire $X=A^{-1}B$ en multipliant à gauche par $A^{-1}$ : le produit $B{A}^{-1}$ n'existe même pas, et l'on ne divise jamais par une matrice.

1. a)$𝒢$ a $5$ sommets : il est d'ordre $5$. $d(A)=2$, $d(B)=3$, $d(C)=4$, $d(D)=3$ et $d(E)=2$. La somme des degrés vaut $2+3+4+3+2=14=2\times 7$ : c'est bien le double du nombre d'arêtes. (1 pt) (1)
2. b)Il n'est pas complet : A et D ne sont pas adjacents. Il est connexe : C est adjacent à A, B, D et E, donc deux sommets quelconques sont reliés par une chaîne qui passe par C. (1 pt : 0,5 + 0,5) (1)
3. c)$M=\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 1& 0& 1& 1& 0\\ 1& 1& 0& 1& 1\\ 0& 1& 1& 0& 1\\ 0& 0& 1& 1& 0\end{array}\right)$. Elle est symétrique (graphe non orienté) et de diagonale nulle (pas de boucle). (1 pt) (1)
4. d)C'est la ligne $1$ de $M$ multipliée par la colonne $4$ de $M$ : $0\times 0+1\times 1+1\times 1+0\times 0+0\times 1=2$. D'après le cours, il y a $2$ chaînes de longueur $2$ de A à D : A–B–D et A–C–D (B et C sont les voisins communs de A et de D). (1 pt : 0,5 pour le calcul, 0,5 pour l'interprétation) (1)
5. e)$𝒢$ est connexe et a exactement deux sommets de degré impair, B et D. D'après le théorème d'Euler, il n'a pas de cycle eulérien, mais il admet une chaîne eulérienne d'extrémités B et D, par exemple B–A–C–B–D–C–E–D, qui emprunte une fois chacune des $7$ arêtes : B–A, A–C, C–B, B–D, D–C, C–E, E–D. (1 pt : 0,5 pour la justification, 0,5 pour la chaîne) (1)

Astuce — Pour un seul coefficient de $M^2$, on multiplie la ligne $i$ de $M$ par la colonne $j$ : chaque produit égal à $1$ correspond à un voisin commun de $i$ et de $j$, donc à une chaîne de longueur $2$.

1. a)Graphe : deux sommets $L$ et $B$ ; arcs $L\to L$ de poids $0,8$, $L\to B$ de poids $0,2$, $B\to L$ de poids $0,3$ et $B\to B$ de poids $0,7$ (les poids issus d'un sommet ont pour somme $1$). Dans l'ordre $(L;B)$ : $P=\left(\begin{array}{cc}0,8& 0,2\\ 0,3& 0,7\end{array}\right)$. (1,5 pt : 0,5 pour le graphe, 1 pour la matrice) (1,5)
2. b)La semaine $0$, Noé emprunte un livre : ${\pi }_0=\left(\begin{array}{cc}1& 0\end{array}\right)$. ${\pi }_1={\pi }_{0}P=\left(\begin{array}{cc}0,8& 0,2\end{array}\right)$ (première ligne de $P$). ${\pi }_2={\pi }_{1}P=\left(\begin{array}{cc}0,8\times 0,8+0,2\times 0,3& 0,8\times 0,2+0,2\times 0,7\end{array}\right)=\left(\begin{array}{cc}0,7& 0,3\end{array}\right)$. La semaine $2$, Noé emprunte un livre avec la probabilité $0,7$ et une bande dessinée avec la probabilité $0,3$. (1,5 pt : 0,5 pour ${\pi }_0$ et ${\pi }_1$, 1 pour ${\pi }_2$) (1,5)
3. c)Le premier coefficient de ${\pi }_{n+1}={\pi }_{n}P$ vaut $x_{n+1}=0,8x_n+0,3y_n$, avec $y_n=1-x_n$ : $x_{n+1}=0,8x_n+0,3-0,3x_n=0,5x_n+0,3$. Une distribution $\left(\begin{array}{cc}x& 1-x\end{array}\right)$ est invariante si et seulement si $x=0,5x+0,3$, soit $0,5x=0,3$ et $x=0,6$. La distribution invariante est $\pi =\left(\begin{array}{cc}0,6& 0,4\end{array}\right)$ ; contrôle : $0,6\times 0,8+0,4\times 0,3=0,48+0,12=0,6$. (1,5 pt : 0,5 pour la relation, 1 pour $\pi$) (1,5)
4. d)On pose $v_n=x_n-0,6$. Alors $v_{n+1}=0,5x_n+0,3-0,6=0,5(x_n-0,6)=0,5v_n$ : la suite $(v_n)$ est géométrique de raison $0,5$ et de premier terme $v_0=1-0,6=0,4$. Donc $v_n=0,4\times 0,5^n$ et $x_n=0,6+0,4\times 0,5^n$ (contrôle : $x_2=0,6+0,1=0,7$). Comme $-1<0,5<1$, $0,5^n$ tend vers $0$, donc $(x_n)$ converge vers $0,6$ : à long terme, la probabilité que Noé emprunte un livre une semaine donnée est proche de $0,6$. (1,5 pt : 1 pour la forme explicite, 0,5 pour la limite) (1,5)

Piège — Ce sont les lignes de $P$ qui ont pour somme $1$ (une ligne = un état de départ). La distribution est une matrice ligne placée à gauche : ${\pi }_{n+1}={\pi }_{n}P$, et non $P{\pi }_n$.

1. a)$A$ est de format $2\times 3$ et $B$ de format $3\times 2$. $(2\times 3)(3\times 2)$ : $AB$ existe et est de format $2\times 2$ ; $(3\times 2)(2\times 3)$ : $BA$ existe et est de format $3\times 3$. $AB=\left(\begin{array}{cc}6-1+0& 3+0+0\\ 2+2+2& 1+0-6\end{array}\right)=\left(\begin{array}{cc}5& 3\\ 6& -5\end{array}\right)$. (1 pt : 0,5 pour les formats, 0,5 pour $AB$) (1)
2. b)Le déterminant de la matrice du système vaut $3\times 4-(-2)\times (-6)=12-12=0$ : le système n'a pas une unique solution. En multipliant la première équation par $-2$ : $-6x+4y=-8$. Si $m=-8$, la seconde équation est équivalente à la première : en posant $y=t$, les solutions sont les couples $\left({\displaystyle \frac{4+2t}{3}};t\right)$, $t\in ℝ$ (une infinité). Si $m\ne -8$, le système imposerait $-8=m$ : il n'a aucune solution. (1 pt : 0,5 pour $m=-8$ et les solutions, 0,5 pour les autres cas) (1)
3. c)La somme des degrés vaut $18=2\times 9$ : le graphe a $9$ arêtes (lemme des poignées de main). Il est connexe et a exactement deux sommets de degré impair, B et E : d'après le théorème d'Euler, il n'admet pas de cycle eulérien, mais il admet une chaîne eulérienne, d'extrémités B et E. (1 pt : 0,5 + 0,5) (1)
4. d)On cherche $\pi =\left(\begin{array}{cc}x& 1-x\end{array}\right)$ telle que $\pi P=\pi$. Le premier coefficient donne $0,6x+0,1(1-x)=x$, soit $0,1=0,5x$, d'où $x=0,2$. Donc $\pi =\left(\begin{array}{cc}0,2& 0,8\end{array}\right)$ ; contrôle sur le second coefficient : $0,2\times 0,4+0,8\times 0,9=0,08+0,72=0,8$. (1 pt) (1)

Piège — Un déterminant nul ne signifie pas « aucune solution » : il exclut seulement la solution unique. On revient alors aux équations pour trancher entre aucune solution et une infinité.

1. a)Faux. Avec $A=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)$ et $B=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ : $A+B=\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right)$ et $(A+B{)}^2=(\begin{array}{cc}1& 1\\ 0& 0\end{array})$. Or $A^2=A$, $AB=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)=B$ et $B^2=O$, donc $A^2+2AB+B^2=\left(\begin{array}{cc}1& 2\\ 0& 0\end{array}\right)$, qui est différente. En fait $(A+B{)}^2=A^2+AB+BA+B^2$, et ici $BA=O\ne AB$. (1 pt) (1)
2. b)Vrai. Supposons $A$ inversible. En multipliant $A^2=A$ à gauche par $A^{-1}$ : $A^{-1}{A}^2=A^{-1}A$, soit $(A^{-1}A)A=I$, donc $A=I$, ce qui contredit l'hypothèse. Donc $A$ n'est pas inversible. (1 pt) (1)
3. c)Faux. Le graphe de sommets A, B, C, D et d'arêtes A–B et C–D a tous ses sommets de degré $1$, mais aucune chaîne ne relie A à C : il n'est pas connexe. (1 pt) (1)
4. d)Vrai. Soient $i$ et $j$ deux sommets distincts. Le coefficient $(i;j)$ de $M^2$ est le nombre de chaînes de longueur $2$ de $i$ à $j$ ; il est non nul, donc au moins une chaîne relie $i$ à $j$. Deux sommets quelconques sont ainsi reliés : le graphe est connexe. (1 pt) (1)

Erreur fréquente — Avec des matrices, $(A+B{)}^2=A^2+AB+BA+B^2$ : on ne regroupe $AB+BA$ en $2AB$ que si $A$ et $B$ commutent.

1. a)$M=\left(\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 1& 0& 0\end{array}\right)$. Les sommes des lignes donnent les degrés sortants : $d^{+}(A)=2$, $d^{+}(B)=1$, $d^{+}(C)=1$, $d^{+}(D)=2$. Les sommes des colonnes donnent les degrés entrants : $d^{-}(A)=1$, $d^{-}(B)=2$, $d^{-}(C)=2$, $d^{-}(D)=1$. La somme de tous les coefficients vaut $6$ : il y a $6$ passages. (1 pt : 0,5 pour $M$, 0,5 pour les degrés) (1)
2. b)$M^2=M\times M=\left(\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 0& 1\\ 1& 1& 0& 0\\ 0& 1& 2& 0\end{array}\right)$, puis $M^3=M^2\times M=\left(\begin{array}{cccc}1& 1& 0& 1\\ 1& 1& 0& 0\\ 0& 1& 2& 0\\ 0& 0& 1& 2\end{array}\right)$. Par exemple, la ligne $4$ de $M^2$ est la somme des lignes $1$ et $2$ de $M$, car les voisins sortants de D sont A et B. (1 pt : 0,5 par matrice) (1)
3. c)La diagonale de $M^3$ est $(1,1,2,2)$, de somme $6$. Le coefficient $(i;i)$ de $M^3$ compte les chemins fermés de longueur $3$ issus de $i$, et chaque circuit de longueur $3$ est compté depuis ses $3$ sommets : il y a $6÷3=2$ circuits, A → C → D → A et B → C → D → B. (1 pt : 0,5 pour le nombre, 0,5 pour les circuits) (1)
4. d)$S=M+M^2+M^3=\left(\begin{array}{cccc}1& 2& 2& 2\\ 1& 1& 1& 1\\ 1& 2& 2& 1\\ 1& 2& 3& 2\end{array}\right)$ (graphe d'ordre $4$, on s'arrête à $M^3$). Tous ses coefficients hors de la diagonale sont non nuls : de toute salle, on peut atteindre toute autre salle, le graphe est fortement connexe. Le coefficient $(2;1)$ vaut $0$ dans $M$ et dans $M^2$, et $1$ dans $M^3$ : $d(B;A)=3$, par le chemin B → C → D → A. (1 pt : 0,5 + 0,5) (1)

Méthode — La diagonale de $M^3$ compte les chemins fermés de longueur $3$ ; chaque circuit de longueur $3$ y est compté une fois depuis chacun de ses trois sommets, d'où la division par $3$.

1. a)Le mois suivant, F contient les chats restés en F, ceux venus de G et les nouveaux : $u_{n+1}=0,7u_n+0,2v_n+20$ ; de même $v_{n+1}=0,1u_n+0,6v_n+10$. C'est $U_{n+1}=A{U}_n+B$. Puis $U_1=\left(\begin{array}{c}28+16+20\\ 4+48+10\end{array}\right)=\left(\begin{array}{c}64\\ 62\end{array}\right)$. (1 pt : 0,5 + 0,5) (1)
2. b)$I-A=\left(\begin{array}{cc}0,3& -0,2\\ -0,1& 0,4\end{array}\right)$ a pour déterminant $0,3\times 0,4-(-0,2)\times (-0,1)=0,1\ne 0$ : elle est inversible, et l'équation $(I-A)X=B$ a une unique solution. Or $AC+B=\left(\begin{array}{c}70+10+20\\ 10+30+10\end{array}\right)=\left(\begin{array}{c}100\\ 50\end{array}\right)=C$ : $C$ est l'unique état stable. Enfin $V_{n+1}=A{U}_n+B-(AC+B)=A(U_n-C)=A{V}_n$. (1 pt : 0,5 + 0,5) (1)
3. c)$AP=\left(\begin{array}{cc}0,5& 1,6\\ -0,5& 0,8\end{array}\right)$ et $PD=\left(\begin{array}{cc}0,5& 1,6\\ -0,5& 0,8\end{array}\right)$ : $AP=PD$. $det(P)=1+2=3$, donc $P^{-1}={\displaystyle \frac{1}{3}}\left(\begin{array}{cc}1& -2\\ 1& 1\end{array}\right)$, et $A=PD{P}^{-1}$ (multiplication à droite par $P^{-1}$). Récurrence : $P{D}^0{P}^{-1}=P{P}^{-1}=I=A^0$ ; si $A^n=P{D}^n{P}^{-1}$, alors $A^{n+1}=A^{n}A=P{D}^n(P^{-1}P)D{P}^{-1}=P{D}^{n+1}{P}^{-1}$. (1 pt : 0,5 pour $AP=PD$ et $P^{-1}$, 0,5 pour la récurrence) (1)
4. d)$V_n=A^n{V}_0$ (suite homogène), avec $V_0=U_0-C=\left(\begin{array}{c}-60\\ 30\end{array}\right)$. $P^{-1}{V}_0={\displaystyle \frac{1}{3}}\left(\begin{array}{c}-60-60\\ -60+30\end{array}\right)=\left(\begin{array}{c}-40\\ -10\end{array}\right)$, puis $V_n=P{D}^n\left(\begin{array}{c}-40\\ -10\end{array}\right)=P\left(\begin{array}{c}-40\times 0,5^n\\ -10\times 0,8^n\end{array}\right)=\left(\begin{array}{c}-40\times 0,5^n-20\times 0,8^n\\ 40\times 0,5^n-10\times 0,8^n\end{array}\right)$. Donc $u_n=100-40\times 0,5^n-20\times 0,8^n$ et $v_n=50+40\times 0,5^n-10\times 0,8^n$ (contrôle : $u_1=64$, $v_1=62$). Comme $0,5$ et $0,8$ sont dans $]-1;1[$, $0,5^n$ et $0,8^n$ tendent vers $0$ : $(u_n)$ tend vers $100$ et $(v_n)$ vers $50$. À long terme, F accueille environ $100$ chats et G environ $50$ ; on vérifie que les adoptions, $20\%$ de $150$, soit $30$ par mois, compensent les $30$ arrivées. (1 pt : 0,5 pour $u_n$ et $v_n$, 0,5 pour les limites) (1)

Erreur fréquente — Si $A^n$ tend vers la matrice nulle, c'est l'écart $U_n-C$ qui disparaît : la suite tend vers l'état stable $C$, pas vers la matrice nulle.

1. a)Graphe : sommets C, M, N ; arcs C → C ($0,7$), C → M ($0,3$), M → M ($0,6$), M → N ($0,4$), N → N ($0,6$), N → C ($0,2$) et N → M ($0,2$). $P=\left(\begin{array}{ccc}0,7& 0,3& 0\\ 0& 0,6& 0,4\\ 0,2& 0,2& 0,6\end{array}\right)$ ; chaque ligne a pour somme $1$. (1 pt : 0,5 + 0,5) (1)
2. b)${\pi }_0=\left(\begin{array}{ccc}1& 0& 0\end{array}\right)$, donc ${\pi }_1={\pi }_{0}P=\left(\begin{array}{ccc}0,7& 0,3& 0\end{array}\right)$. ${\pi }_2={\pi }_{1}P=\left(\begin{array}{ccc}0,7\times 0,7& 0,7\times 0,3+0,3\times 0,6& 0,3\times 0,4\end{array}\right)=\left(\begin{array}{ccc}0,49& 0,39& 0,12\end{array}\right)$. Lina nage le jour $2$ avec la probabilité $0,12$. (1 pt : 0,5 + 0,5) (1)
3. c)$P^2=\left(\begin{array}{ccc}0,49& 0,39& 0,12\\ 0,08& 0,44& 0,48\\ 0,26& 0,3& 0,44\end{array}\right)$ (sa première ligne redonne ${\pi }_2$). Tous les coefficients de $P^2$ sont strictement positifs : d'après le résultat rappelé, $({\pi }_n)$ converge vers l'unique distribution invariante de la chaîne, quelle que soit ${\pi }_0$. (1 pt : 0,5 + 0,5) (1)
4. d)$\pi P=\pi$ donne, sur la première colonne, $0,7x+0,2z=x$, soit $z=1,5x$, et sur la troisième, $0,4y+0,6z=z$, soit $y=z$. Avec $x+y+z=1$ : $x+1,5x+1,5x=4x=1$, d'où $x=0,25$ et $y=z=0,375$. Contrôle sur la deuxième colonne : $0,3\times 0,25+0,6\times 0,375+0,2\times 0,375=0,075+0,225+0,075=0,375$. Donc $\pi =\left(\begin{array}{ccc}0,25& 0,375& 0,375\end{array}\right)$ : à long terme, Lina fait du cardio un jour sur quatre environ, et de la musculation ou de la natation avec la probabilité $0,375$ chacune. (1 pt : 0,5 pour le système, 0,5 pour $\pi$ et l'interprétation) (1)

Astuce — Pour justifier la convergence à trois états, il suffit d'exhiber une puissance de $P$ sans aucun coefficient nul : souvent, $P^2$ convient même quand $P$ contient des zéros.

1. a)$A^2=\left(\begin{array}{cc}4-3& -6+3\\ 2-1& -3+1\end{array}\right)=\left(\begin{array}{cc}1& -3\\ 1& -2\end{array}\right)$ et $A^3=A^2\times A=\left(\begin{array}{cc}2-3& -3+3\\ 2-2& -3+2\end{array}\right)=\left(\begin{array}{cc}-1& 0\\ 0& -1\end{array}\right)=-I$. Donc $A\times (-A^2)=-A^3=I$ : $A$ est inversible et $A^{-1}=-A^2=\left(\begin{array}{cc}-1& 3\\ -1& 2\end{array}\right)$. Comme $50=3\times 16+2$ : $A^{50}=(A^3{)}^{16}\times A^2=(-I{)}^{16}{A}^2=A^2=\left(\begin{array}{cc}1& -3\\ 1& -2\end{array}\right)$, car $(-1{)}^{16}=1$. (1 pt : 0,5 pour l'inverse, 0,5 pour $A^{50}$) (1)
2. b)Notons $k$ le nombre de sommets de degré $4$ ; les $10-k$ autres sont de degré $3$. Le lemme des poignées de main donne $4k+3(10-k)=2\times 17$, soit $30+k=34$ : $k=4$. Le graphe a $4$ sommets de degré $4$ et $6$ de degré $3$. (1 pt) (1)
3. c)Le premier coefficient de $\pi P$ doit valoir ${\displaystyle \frac{1}{3}}$ : ${\displaystyle \frac{1}{3}}(1-a)+{\displaystyle \frac{2}{3}}\times 0,2={\displaystyle \frac{1}{3}}$, soit $1-a+0,4=1$, d'où $a=0,4$. Le second coefficient est alors juste aussi, car les coefficients de $\pi P$ ont pour somme $1$ : ${\displaystyle \frac{1}{3}}\times 0,4+{\displaystyle \frac{2}{3}}\times 0,8={\displaystyle \frac{2}{3}}$. (1 pt) (1)

Astuce — Une puissance égale à $\pm I$ fournit à la fois l'inverse et toutes les puissances : on réduit l'exposant grâce à la division euclidienne par $3$.

1. a)Pour $k⩾1$, notons $𝒫(k)$ : « pour tous $i$ et $j$, $(M^k{)}_{ij}$ est le nombre de chemins de longueur $k$ de $i$ à $j$ ». Initialisation : $m_{ij}$ est le nombre d'arcs de $i$ vers $j$, c'est-à-dire de chemins de longueur $1$ : $𝒫(1)$ est vraie. Hérédité : supposons $𝒫(k)$ vraie. Un chemin de longueur $k+1$ de $i$ à $j$ se découpe d'une seule façon en un chemin de longueur $k$ de $i$ à un sommet $r$ (l'avant-dernier), suivi d'un arc de $r$ vers $j$. Pour $r$ fixé, il y en a $(M^k{)}_{ir}\times m_{rj}$, d'après $𝒫(k)$. En sommant sur $r$, on obtient ${\displaystyle {\sum }_{r=1}^n(M^k{)}_{ir}{m}_{rj}}$, qui est le coefficient $(i;j)$ de $M^k\times M=M^{k+1}$ : $𝒫(k+1)$ est vraie. Conclusion : $𝒫(k)$ est vraie pour tout $k⩾1$. (1 pt : 0,5 pour la décomposition d'un chemin, 0,5 pour le lien avec le produit et la rédaction) (1)
2. b)Par l'absurde : supposons que l'arête u–v soit un pont, et notons $𝒢\prime$ le graphe obtenu en la supprimant. Soit $H$ l'ensemble des sommets reliés à u par une chaîne de $𝒢\prime$. Le sommet v n'est pas dans $H$ : sinon, une chaîne de $𝒢\prime$ de u à v remplacerait l'arête u–v dans toute chaîne, et $𝒢\prime$ serait connexe. Aucune arête de $𝒢\prime$ ne relie un sommet de $H$ à un sommet hors de $H$ ; les sommets de $H$ et les arêtes qui les relient forment donc un graphe où chaque sommet garde son degré dans $𝒢\prime$ : u y est de degré $d(u)-1$, impair, et les autres sommets de $H$ (différents de v) gardent leur degré pair. Ce graphe aurait un seul sommet de degré impair, ce qui contredit le lemme des poignées de main (le nombre de sommets de degré impair est pair). Il n'y a donc aucun pont. (1 pt : 0,5 pour le graphe formé par $H$, 0,5 pour la contradiction) (1)
3. c)Le coefficient $i$ de $PE$ est $p_{i1}+p_{i2}+p_{i3}$, la somme de la ligne $i$ de $P$. Donc $PE=E$ équivaut à « chaque ligne a pour somme $1$ » : avec des coefficients positifs ou nuls, c'est la définition d'une matrice de transition. Supposons-le, et montrons par récurrence que $P^{n}E=E$ pour $n⩾1$ : c'est vrai pour $n=1$, et si $P^{n}E=E$, alors $P^{n+1}E=P^n(PE)=P^{n}E=E$. De plus, les coefficients de $P^{n+1}=P^n\times P$ sont des sommes de produits de nombres positifs ou nuls, donc positifs ou nuls (récurrence immédiate). Ainsi $P^n$ est une matrice de transition. (1 pt : 0,5 pour l'équivalence, 0,5 pour la récurrence) (1)
4. d)$(I+N)(I-N)=I-N+N-N^2=I$ : $I+N$ est inversible, d'inverse $I-N$. Récurrence : $(I+N{)}^0=I$ ; si $(I+N{)}^n=I+nN$, alors $(I+N{)}^{n+1}=(I+nN)(I+N)=I+N+nN+n{N}^2=I+(n+1)N$. Application : $N^2=\left(\begin{array}{cc}4-4& -8+8\\ 2-2& -4+4\end{array}\right)=O$, donc $(I+N{)}^{10}=I+10N=(\begin{array}{cc}21& -40\\ 10& -19\end{array})$. (1 pt : 0,5 pour l'inverse et la récurrence, 0,5 pour l'application) (1)

Erreur fréquente — Dans une récurrence sur des puissances de matrices, l'hérédité s'écrit avec $A^{n+1}=A^n\times A$ et l'associativité ; on ne développe « comme avec des réels » qu'après avoir vérifié que les matrices commutent.

1. a)$M=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)$ et $M^2=\left(\begin{array}{ccc}2& 1& 1\\ 1& 2& 1\\ 1& 1& 2\end{array}\right)$. $(M^2{)}_{11}=2$ : deux chemins fermés de longueur $2$ issus de A, A–B–A et A–C–A (autant que le degré de A). $(M^2{)}_{12}=1$ : un seul chemin de longueur $2$ de A à B, A–C–B. (1 pt : 0,5 pour $M^2$, 0,5 pour l'interprétation) (1)
2. b)La ligne $1$ de $M^n$ est $\left(\begin{array}{ccc}{x}_n& y_n& z_n\end{array}\right)$ (théorème des chemins, et $M^0=I$). La ligne $1$ de $M^{n+1}=M^n\times M$ est cette ligne multipliée par $M$ : $\left(\begin{array}{ccc}{y}_n+z_n& x_n+z_n& x_n+y_n\end{array}\right)$, d'où les trois relations. Récurrence : $z_0=y_0=0$, et si $z_n=y_n$, alors $z_{n+1}=x_n+y_n=x_n+z_n=y_{n+1}$. Donc $x_{n+1}=2y_n$ et $y_{n+1}=x_n+y_n$, soit $U_{n+1}=T{U}_n$ avec $T=\left(\begin{array}{cc}0& 2\\ 1& 1\end{array}\right)$. (1 pt : 0,5 pour les relations, 0,5 pour $z_n=y_n$ et $A$) (1)
3. c)$TP=\left(\begin{array}{cc}0-2& 0+2\\ 2-1& 1+1\end{array}\right)=\left(\begin{array}{cc}-2& 2\\ 1& 2\end{array}\right)$ et $PD=\left(\begin{array}{cc}-2& 2\\ 1& 2\end{array}\right)$ : $TP=PD$. $det(P)=2\times 1-1\times (-1)=3\ne 0$, donc $P^{-1}={\displaystyle \frac{1}{3}}\left(\begin{array}{cc}1& -1\\ 1& 2\end{array}\right)$. (1 pt : 0,5 + 0,5) (1)
4. d)La suite est homogène : $U_n=T^n{U}_0=P{D}^n{P}^{-1}{U}_0$, avec $U_0=\left(\begin{array}{c}1\\ 0\end{array}\right)$. $P^{-1}{U}_0={\displaystyle \frac{1}{3}}\left(\begin{array}{c}1\\ 1\end{array}\right)$, $D^n{P}^{-1}{U}_0={\displaystyle \frac{1}{3}}\left(\begin{array}{c}(-1{)}^n\\ 2^n\end{array}\right)$, puis $U_n={\displaystyle \frac{1}{3}}\left(\begin{array}{c}2(-1{)}^n+2^n\\ -(-1{)}^n+2^n\end{array}\right)$ : ce sont les formules annoncées (contrôle : $x_2=2$ et $y_2=1$, comme au a)). Pour $n=10$ : $x_{10}={\displaystyle \frac{1024+2}{3}}=342$ chemins fermés. (1 pt : 0,5 pour les formules, 0,5 pour $x_{10}$) (1)
5. e)$x_n+2y_n={\displaystyle \frac{2^n+2(-1{)}^n+2\times 2^n-2(-1{)}^n}{3}}=2^n$ : c'est le nombre total de chemins de longueur $n$ issus de A ($x_n+y_n+z_n$), et chaque pas offre $2$ choix. $x_n-y_n={\displaystyle \frac{2(-1{)}^n+(-1{)}^n}{3}}=(-1{)}^n$ : selon la parité de $n$, il y a un chemin de plus ou de moins vers A que vers B. Enfin ${\displaystyle \frac{x_n}{2^n}}={\displaystyle \frac{1}{3}}+{\displaystyle \frac{2}{3}}{(-{\displaystyle \frac{1}{2}})}^n$ tend vers ${\displaystyle \frac{1}{3}}$, car $-1<-{\displaystyle \frac{1}{2}}<1$ : pour $n$ grand, environ un tiers des chemins de longueur $n$ issus de A y reviennent. (1 pt : 0,5 pour les deux égalités, 0,5 pour la limite) (1)