Barre utilisateur

[ID: 3840] [Date de publication: 14 mars 2024 22:15] [Catégorie(s): Usage de la réduction ] [ Nombre commentaires: 1] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Michel Quercia ]

Solution(s)

Solution(s)

Ulm MP\(^*\) 2001
Par Michel Quercia le 14 mars 2024 22:15

Soit \(d_n(i,j)\) le nombre de chemins de longueur \(n\) allant du sommet \(i\) au sommet \(j\). \(j\) admet trois voisins \(k_{1},k_{2},k_{3}\) et l’on a : \(d_n(i,j) = d_{n-1}(i,k_{1}) + d_{n-1}(i,k_{2}) + d_{n-1}(i,k_{3} )\). On numérote les sommets de \(0\) à \(7\) de sorte que les voisins du sommet \(i\) sont les sommets \(i+1 \bmod 8\), \(i+2 \bmod 8\) et \(i+4 \bmod 8\). Le vecteur \(d_n = (d_n(0,0),\dots,d_n(0,7))\) vérifie la relation de récurrence \(d_n = Ad_{n-1}\) où \(A\) est la matrice suivante (\(.\) désigne \(0\)) : \[A = \begin{pmatrix}. &1 &1 &. &1 &. &. &.\\ 1 &. &. &1 &. &1 &. &.\\ 1 &. &. &1 &. &. &1 &.\\ . &1 &1 &. &. &. &. &1\\ 1 &. &. &. &. &1 &1 &.\\ . &1 &. &. &1 &. &. &1\\ . &. &1 &. &1 &. &. &1\\ . &. &. &1 &. &1 &1 &.\\\end{pmatrix} = \begin{pmatrix}B &I_4\\ I_4&B\end{pmatrix} = P\begin{pmatrix}B+I_4 &0\\ 0&B-I_4\end{pmatrix}P^{-1}\] avec \[B = \begin{pmatrix}. &1 &1 &.\\ 1 &. &. &1\\ 1 &. &. &1\\ . &1 &1 &.\\\end{pmatrix} \text{ et } P = \begin{pmatrix}I_4 &I_4\\ I_4&-I_4\end{pmatrix}.\] De même, \[B\pm I_4 = \begin{pmatrix}C\pm I_{2}&I_{2}\\ I_{2}&C\pm I_{2}\end{pmatrix} = Q\begin{pmatrix}C\pm I_{2}+I_{2} &0\\ 0&C\pm I_{2}-I_{2}\end{pmatrix}Q^{-1}\] et enfin, \[C\pm I_{2}\pm I_{2} = \begin{pmatrix}\pm I_{1}\pm I_{1}&I_{1}\\ I_{1}&\pm I_{1}\pm I_{1}\\\end{pmatrix} = R\begin{pmatrix}\pm I_{1}\pm I_{1}+I_{1} &0\\ 0&\pm I_{1}\pm I_{1}-I_{1}\end{pmatrix}R^{-1}.\] Donc \(A\) est diagonalisable de valeurs propres \(-3,-1,1,3\) et on peut certainement terminer les calculs pour obtenir \(d_n = A^n d_{0}\).