Exercice 28 Marche sur un carré

Le carré et ses quatre arêtes sont en ocre. En violet, un trajet de deux pas mène de $A$ à $C$ en passant par $B$ : il ne revient pas en $A$.

1. $$M=\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}, \qquad M^{2}=\begin{pmatrix} 2 & 0 & 2 & 0 \\ 0 & 2 & 0 & 2 \\ 2 & 0 & 2 & 0 \\ 0 & 2 & 0 & 2 \end{pmatrix}, \qquad M^{3}=\begin{pmatrix} 0 & 4 & 0 & 4 \\ 4 & 0 & 4 & 0 \\ 0 & 4 & 0 & 4 \\ 4 & 0 & 4 & 0 \end{pmatrix}=4M$$

2. On note $\mathcal{P}_{k}$ : « $M^{2k+1}=4^{k}M$ et $M^{2k}=4^{k-1}M^{2}$ ».

Initialisation : Pour $k=1$ : $M^{3}=4M$ (question 1) et $M^{2}=4^{0}M^{2}$.

Hérédité : Si $\mathcal{P}_{k}$ est vraie pour un $k\in\mathbb{N}^{*}$, alors : $$M^{2k+2}=M^{2k+1}M=4^{k}M^{2} \qquad \text{et} \qquad M^{2k+3}=M^{2k+2}M=4^{k}M^{3}=4^{k}\times 4M=4^{k+1}M$$ ce qui est $\mathcal{P}_{k+1}$.

Conclusion : $\mathcal{P}_{k}$ est vraie pour tout $k\in\mathbb{N}^{*}$.

3. D'après la Proposition 2, on cherche le coefficient $(A\,;A)$ de $M^{n}$.

• Si $n=2k+1$ est impair, ce coefficient vaut $4^{k}\times 0=0$ : on ne peut pas revenir en $A$ en un nombre impair de pas.

• Si $n=2k$ est pair, il vaut $4^{k-1}\times 2=2^{2k-2}\times 2=2^{2k-1}=2^{n-1}$.

$$\boxed{\text{nombre de trajets de } n \text{ étapes de } A \text{ à } A=\left\{\begin{array}{ll} 0 & \text{si } n \text{ est impair} \\ 2^{n-1} & \text{si } n \text{ est pair} \end{array}\right.}$$ Contrôle pour $n=2$ : les deux trajets sont $A\to B\to A$ et $A\to D\to A$.

4. À chaque étape, le pion a exactement $2$ choix, donc il y a $2^{n}$ trajets de $n$ étapes partant de $A$. Pour $n$ pair, $2^{n-1}=\frac{2^{n}}{2}$ : la moitié des trajets revient en $A$.

Colorions $A$ et $C$ en blanc, $B$ et $D$ en noir : chaque pas change la couleur. Après un nombre pair de pas, le pion est donc sur un sommet blanc, $A$ ou $C$. Le coefficient $(A\,;C)$ de $M^{2k}$ vaut d'ailleurs aussi $4^{k-1}\times 2=2^{n-1}$ : les trajets se partagent à égalité entre $A$ et $C$.

On retrouve, sous forme de comptage, la marche aléatoire de Bernoulli étudiée dans le poly. Si l'on numérote les sommets $0$, $1$, $2$, $3$ dans l'ordre $A$, $B$, $C$, $D$, la position du pion est la somme des pas $\pm 1$, prise modulo $4$ (chapitre 4).