Problème proposé par Michel Lafond

Zig est au centre d’un labyrinthe carré de n x n cases [n entier impair ≥3] dans lequel chaque case contient une flèche indiquant la direction à prendre. À chaque étape, Zig se déplace d’une case dans la direction indiquée par la flèche de la case où il se trouve, sauf s’il se trouve face à un mur auquel cas il reste sur sa case. Il n’y a pas de mur en haut de la case de sortie. A la fin de chaque étape, que Zig ait bougé ou non, la flèche de la case où il se trouvait au début de l’étape tourne de 90° dans le sens horaire*.
Le parcours s’arrête quand Zig sort en haut.

Q1  Au bout de combien d’étapes Zig sortira-t-il du labyrinthe ci-après ?
 








Q2 Démontrer que quelle que soit la taille du labyrinthe, la case de départ, la case de sortie et les directions initiales des flèches, Zig sortira au bout d’un nombre fini d’étapes.

Q3  Pour n égal à 3, 5, 7, 9 et 11, déterminer une direction initiale des flèches rendant maximal le nombre d’étapes nécessaires pour atteindre la sortie [La case départ est au centre, et la sortie en haut au milieu]. * exemple : description de trois étapes dans le labyrinthe de Q₁

 Solution