Le problème du cavalier - Lycée Blaise Pascal (Orsay)

Titre du sujet
Le problème du cavalier
Établissement
Lycée Blaise Pascal (Orsay)
Année
2003-2004
Résumé
Un cavalier se déplace le long dπune bande, divisée en cases numérotées par les entiers naturels, n étant le numéro attribué la nième case en partant de lπorigine. Le cavalier peut se déplacer soit de p cases, soit de q cases (), en avant ou en arrière. On place sur cette demi-droite un mur, auquel correspond le numéro m (), qui empêche le cavalier de passer par une quelconque case dont le numéro est strictement supérieur à celui du mur.

On demande si lπon peut placer le mur de manière à ce que le cavalier, en partant de la case 0, puisse atteindre toutes les cases situées entre la case 0 et la case m (au sens large), et, si cela est possible, quelles valeurs peut on donner à m.