Exercice 1 — Le cavalier boiteux

Sujet

Sur un échiquier, le cavalier se déplace de la manière suivante : il bouge de deux cases dans une direction puis d'une case dans une direction perpendiculaire.

Ces déplacements sont indiqués sur le schéma ci-contre.
On dit qu'une case B est accessible à partir d'une case A , si on peut arriver sur la case B après un ou plusieurs déplacements en partant de la case A.

Pour simplifier les notations, un échiquier de largeur \(\ell\) et de longueur \(L\) sera noté \(\ell \times L\).

1. (a) Sur un échiquier de \(3 \times 3\), quelles sont les cases accessibles en partant du coin en bas à gauche? (On pourra faire un dessin)
   Pourquoi la case centrale est-elle inaccessible?
   (b) Justifier que si la taille de l'échiquier est de \(3 \times 4\) ou plus grand (c'est-à-dire de largeur au moins 3 et de longueur au moins 4), alors toutes les cases de l'échiquier sont accessibles à partir du coin en bas à gauche.
   Pourquoi toutes les cases de l'échiquier sont alors accessibles en partant de n'importe quelle case?
   (c) Si on considère un cavalier qui se déplace de 3 cases en avant (au lieu de 2 ) et de 1 case sur le côté, et qui part du coin en bas à gauche, pourquoi y aura-t-il toujours des cases inaccessibles à ce cavalier, quelle que soit la taille de l'échiquier?
2. On considère maintenant le chameau, qui se déplace de 3 cases en avant puis de 2 cases sur le côté, et on va chercher le plus petit échiquier rectangulaire dans lequel toutes les cases lui sont accessibles.
   (a) Déterminer sur un échiquier \(4 \times 7\) toutes les cases accessibles au chameau en partant du coin en bas à gauche.
   (b) Déterminer sur un échiquier \(5 \times 5\) toutes les cases accessibles au chameau en partant du coin en bas à gauche.
   (c) Déterminer sur un échiquier \(5 \times 5\) les cases accessibles au chameau en partant d'une case adjacente (c'est-à-dire avec un côté commun) à celle du coin en bas à gauche.
   (d) En déduire la taille du plus petit (en nombre de cases) échiquier rectangulaire (comportant au moins 2 cases) dans lequel toutes les cases sont accessibles au chameau.
3. On qualifiera de «boiteux» un cavalier ou un chameau qui ne peut tourner qu'à gauche après avoir avancé.
   Expliquer pourquoi il existera toujours des cases inaccessibles à un chameau ou un cavalier boiteux, quelle que soit la taille de l'échiquier.