Exercice 58

1. Soit $\sigma$ la configuration avant le coup, et $k$ le jeton déplacé. Le jeton $k$ prend la place de la case vide, et la case vide celle du jeton $k$ ; les autres jetons ne bougent pas. La nouvelle configuration $\sigma'$ vérifie donc $\sigma'(k) = \sigma(9)$, $\sigma'(9) = \sigma(k)$, et $\sigma'(\ell) = \sigma(\ell)$ pour les autres $\ell$. Soit $\tau = \big(\sigma(k)\ \ \sigma(9)\big)$ la transposition qui échange les numéros des deux cases concernées. Alors $\tau\sigma(k) = \sigma(9)$, $\tau\sigma(9) = \sigma(k)$, et $\tau\sigma(\ell) = \sigma(\ell)$ pour $\ell \notin \{k, 9\}$, puisque $\sigma(\ell)$ n'est alors aucune des deux cases échangées. $$\boxed{\sigma' = \tau\sigma, \qquad \tau = \big(\sigma(k)\ \ \sigma(9)\big)}$$

2. La case $9$ étant blanche, les cases blanches sont $1$, $3$, $5$, $7$, $9$, et les noires $2$, $4$, $6$, $8$. Deux cases voisines horizontalement ou verticalement sont de couleurs différentes : à chaque coup, la case vide change de couleur. Partant de la case $9$, blanche, la case vide est blanche après $m$ coups si et seulement si elle a changé de couleur un nombre pair de fois. $$\boxed{\text{après } m \text{ coups, la case vide est blanche} \iff m \text{ est pair}}$$

3. Par la question 1, après $m$ coups, $\sigma = \tau_{m}\cdots\tau_{1}$, produit de $m$ transpositions, donc $\varepsilon(\sigma) = (-1)^{m}$ par la proposition 5 (i). La question 2 relie la parité de $m$ à la couleur de la case vide, qui ne dépend que de la configuration et non du chemin suivi pour l'atteindre. $$\boxed{\varepsilon(\sigma) = \begin{cases} 1 & \text{si la case vide est blanche} \\ -1 & \text{si elle est noire} \end{cases}}$$ Si la case vide est revenue en case $9$, alors $\sigma(9) = 9$, et $\sigma$ est une permutation des huit jetons, de signature $1$ : elle est paire.

4. On lit sur la figure la case occupée par chaque jeton : $\sigma(1) = 2$, $\sigma(2) = 1$, $\sigma(3) = 5$, $\sigma(4) = 8$, $\sigma(5) = 9$, $\sigma(6) = 7$, $\sigma(7) = 6$, $\sigma(8) = 4$, et la case vide $\sigma(9) = 3$. La décomposition en cycles à supports disjoints (théorème 1) est $$\sigma = (1\ 2)(3\ 5\ 9)(4\ 8)(6\ 7), \qquad \varepsilon(\sigma) = (-1)^{1 + 2 + 1 + 1} = -1.$$ Or la case vide de $\mathcal{C}$ est la case $3$, qui est blanche : par la question 3, une configuration accessible devrait avoir pour signature $1$. $$\boxed{\text{la configuration } \mathcal{C} \text{ n'est pas accessible}}$$ Un parcours exhaustif par ordinateur confirme que les configurations accessibles sont au nombre de $181\,440 = \frac{9!}{2}$, et que $\mathcal{C}$ n'en fait pas partie.

À retenir. La signature est un invariant : une quantité que chaque coup modifie de façon prévisible. Elle prouve une impossibilité sans explorer les coups possibles. Le célèbre défi de Sam Loyd, qui demandait d'échanger les jetons $14$ et $15$ du taquin $4 \times 4$, est impossible pour la même raison.