Comptes Rendus MATh.enJEANS, 04-04

Le problème du cavalier

par
Arnaud Dumas, Antony Lee, Gaël Lemoine,
Régis Millet, Nelle Varoqueux, Catherine Wacogne
élèves du lycée Blaise Pascal (Orsay)
(Texte de Antony Lee)

Club Math en Jeans du Lycée Blaise Pascal (Orsay – Essonne). Atelier scientifique année 2003-2004. 
Professeurs : Chantal BASTIN, Nadine DELBARRE, Denis JULIOT, Didier MISSENARD
Chercheurs : Cédric BOUTILLIER, Aurélien GARIVIER (Moniteurs Université Paris Sud, Orsay), Pierre PANSU (Université Paris Sud, Orsay ), Frédéric PAULIN (ENS),

 [Article en cours d'analyse et de vérification : les passages entre crochets sont des éditeurs]

[Sujet initial de Pierre PANSU]
•	Sur la demi-droite des naturels, si l'on se donne deux entiers p et q, peut-on, en partant de l'origine, atteindre tout point du segment [0 ; N] en ne se déplaçant que de p ou q pas dans une direction ou l'autre ?
•	Dans le plan discret, si l'on se donne un carré N *N, peut-on, par des déplacements de cavaliers d'ampleur p et q, atteindre tout point du carré ?
•	Dans l'espace discret, si l'on se donne un cube N *N *N, peut-on, par des déplacements de cavaliers d'ampleur p, q, r atteindre tout point du cube ?

I.	Le problème

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.

II.	Condition nécessaire pour l’existence de m.

On exclut le cas où , où on a trivialement 
Il est évident que toutes les cases pouvant être atteintes par le cavalier ont un numéro qui peut s’écrire sous la forme (Z), donc divisible par . On doit donc avoir, si l’on veut atteindre toutes les cases, .
On supposera donc que  et que  dans la suite de l’exposé.

III.	Existence de m sous la condition précédente.

Montrons que  convient.

On va commencer par montrer que pour tout , il existe  tels que .
En effet, d’après le théorème de Bézout, il existe Z tels que , soit, pour tout Z, .
Or, pour que  et , il faut et suffit que . Or, il existe toujours un entier dans l’intervalle , puisqu’il est d’amplitude .
CQFD.

Pour tout , il existe donc  tels que , et la case x peut donc être atteinte par le cavalier qui, en faisant  pas de p cases en avant et  pas de q cases en avant, arrive sur la case souhaitée en passant par des cases de numéros croissants, et donc ne dépasse pas le mur, dont le numéro est supérieur ou égal à celui de la case que l’on souhaite atteindre.
D’autre part, soit ,  le quotient et  le reste de la division euclidienne de  par . On a , d’où. On a , donc  est atteignable. On peut donc atteindre la case x en se rendant d’abord sur la case , puis en reculant de  fois de , et ce quelque soit . Comme on peut aussi atteindre les cases de E,  convient donc (puisque ). m existe donc.   CQFD.

IV.	Ensemble des valeurs pouvant être prises par m.

Soit m1 une valeur possible de m. Montrons que tout m'> m1 est également une valeur possible de m.

En effet, on a clairement  (puisque pour atteindre toutes les cases de , il faut faire au moins un déplacement).
Soit  et r le reste de la division euclidienne de n par . , donc la case r est atteignable sans dépasser le mur placé en m’. Pour atteindre la case n sans dépasser ce même mur, il suffit d’aller en r, puis d’avancer du bon nombre de fois de  cases.   CQFD.

Ainsi, pour déterminer l’ensemble des valeurs pouvant être prises par m, il suffit de déterminer le plus petit élément de cet ensemble. L’ensemble recherché sera alors composé de tous les entiers supérieurs ou égaux à ce plus petit élément.

V.	Plus petite valeur pouvant être prise par m.

On va montrer que cette plus petite valeur est .

a.	
Montrons que toutes les cases peuvent être atteintes avec un mur placé à .
Pour cela, commençons par remarquer que si l’on peut atteindre toutes les cases de  en partant de la case 0, on peut aussi le faire en partant de n’importe quelle case de . En effet, il suffit pour cela de se rendre de la case de départ à la case 0 (en suivant le chemin inverse de celui que le cavalier suit pour aller de la case 0 à la case de départ), à partir de laquelle il est possible de se rendre sur n’importe quelle case de  (par hypothèse).
Le mur étant placé en , demandons au cavalier, initialement placé sur la case , de réaliser le parcours suivant : s’il peut reculer de q cases ou avancer de p cases, il le fait (les deux ne sont pas possibles simultanément, puisque la longueur de segment qu’il peut parcourir est de  cases), sinon il s’arrête.
En notant xn le numéro de la case où se trouve le cavalier après le nième déplacement (x0 étant par convention la case de départ du cavalier), on a donc :

Si , le cavalier s’arrête.
Nous allons montrer qu’en suivant un tel parcours, le cavalier passe nécessairement une unique fois par toutes les cases de , et seulement celles-ci.

Il est clair que par construction, la suite  est à valeurs dans , et que pour tout n pour lequel  est défini, il existe  tels que  et , le cavalier ne faisant que des déplacements de p cases en avant et des déplacements de q cases en arrière.
Montrons, par l’absurde, que cette suite ne boucle pas. Supposons que la suite boucle, c’est à dire qu’elle est périodique à partir d’un certain rang. Dans ce cas, il existe  () distincts tels que  et que  soit minimum. Alors la suite prend des valeurs deux à deux distinctes pour des indices compris (au sens large) entre i et , par hypothèse de minimalité sur . Comme la suite est à valeurs dans , on a donc  ( est l’ensemble des valeurs que peut prendre la suite, au nombre de m ; or, entre xi et , la suite prend par hypothèse des valeurs deux à deux distinctes, au nombre de ).
Il existe donc  tels que  et , ainsi que  et , soit , d’où  et . On a aussi   et , puisque . p et q étant supposés premiers entre eux, d’après le théorème de Gauss, on a  et . D’autre part, si , alors l’égalité  entraîne clairement , soit , ce qui est exclu par hypothèse. Donc , et, de même, . On a donc  et , d’où , ce qui est absurde.

Ainsi, pour tout  () pour lesquels la suite est définie, . Or, la suite ne peut prendre que  valeurs distinctes, ce qui signifie que la suite ne sera jamais définie pour des indices supérieurs ou égaux à m. Puisque si ,  est défini, on en déduit qu’il existe k tel que . Il existe donc  tels que  et , d’où , soit , d’où, p et q étant premiers entre eux,  et , d’où  et , et .  étant par hypothèse défini, on en déduit  (puisque ).
Donc ce parcours va faire passer le cavalier par les cases , c’est à dire par  cases deux à deux distinctes. Comme l’on demande au cavalier de passer par les  cases , on en déduit que le cavalier va effectivement passer par toutes les cases souhaitées.   CQFD.

b.	
Montrons qu’un mur placé à  ne permet pas au cavalier de passer par toutes les cases. Supposons, par symétrie des rôles, que . On commence par exclure le cas où . Dans ce cas, si , on aurait , c’est à dire que le cavalier n’aurait pu faire que des déplacements de  cases, puisque tout déplacement de p cases le ferait dépasser les limites. Le cavalier ne pourrait donc pas atteindre les cases de numéro impair, ce qui conclut la démonstration.

Nous allons introduire la notion de classe de congruence modulo q. La classe de congruence de a modulo q est l’ensemble des entiers congrus à a modulo q, c’est à dire s’écrivant sous la forme  (). Dans ce qui suit, on sous-entendra le « de congruence modulo q ».
Montrons qu’il existe exactement q classes : celle de 0 (l’ensemble des multiples de p), celle de 1,…, celle de  et celle de . D’après la définition, la différence de deux entiers d’une même classe est divisible par q, puisqu’on a , que divise q. Comme la différence de deux entiers distincts de  appartient clairement à , elle ne peut être divisible par q, et les classes de 0, 1,..,  sont donc distinctes. En revanche, tout entier n’appartenant pas à  appartient clairement à la classe du reste de sa division euclidienne par q.
Il s’ensuit que les q classes que sont celle de 0, celle de 1,…, celle de  sont deux à deux distinctes, et que ce sont les seules. Il existe donc q classes.
D’autre part, les classes de 0, p,…,  sont deux à deux distinctes, car si kp et  étaient dans la même classe (avec  et ), alors , d’où, p et q étant premiers entre eux, d’après le théorème de Gauss, . Comme la différence de deux entiers distincts de  appartient clairement à , elle ne peut être divisible par q, kp et  sont dans des classes distinctes.
L’ensemble des q classes que sont celle de 0, celle de p,…, celle de  est donc égal à l’ensemble de toutes les classes.

La démonstration suivante repose sur le dénombrement des classes que le cavalier peut atteindre. Nous allons montrer que le cavalier ne peut pas atteindre plus de  classes, ce qui sera suffisant pour conclure la démonstration, puisqu’il existe clairement des éléments de chacune les classes dans , puisque p est supposé supérieur à 1, c’est à dire que . Remarquons tout de suite que la classe sur laquelle se trouve le cavalier après un certain nombre de coups ne dépend que du nombre de déplacement de p cases qu’il aura fait et de leur sens, puisque la classe ne change pas lorsque le cavalier se déplace de q cases.

Pour pouvoir avancer de p cases, il faut se trouver dans une case de , pour pouvoir reculer de p cases, il faut se trouver dans une case de . Comme chaque classe est représentée au plus une fois dans  et une fois dans , et que tout changement de classe nécessite un déplacement de p cases, il apparaît que si un cavalier se trouve dans la classe de a, un quelconque déplacement (de p ou de q cases) va soit le laisser dans cette même classe, soit l’amener dans la classe de , soit l’amener dans la classe de .
Ainsi, le cavalier en partant de la classe de 0, pourra atteindre les classes de la forme p, 2p,…, kp, où la classe de kp est une classe qui n’est pas représentée dans G (il en existe nécessairement une, puisque seules  classes y sont présentes – on a donc , ce qui assure que les classes sont deux à deux distinctes), si bien qu’elle n’est pas liée à la classe de  (on ne peut pas avancer de p cases en partant d’une case de G). On pourra de même reculer, et ce pour atteindre les classes de la forme , ,…, . Mais comme pour tout , les classes de ip et de  sont liées, cela signifie que pour tout , la classe de ip est représentée dans G, ce qui implique que le nombre de classes que le cavalier peut atteindre est égal au nombre de cases dans G plus une (la classe de kp), et donc que le cavalier ne peut atteindre que  classes, ce qui achève la démonstration.   CQFD.

Ainsi, pour , le cavalier peut ne atteindre peut pas atteindre les q classes, c’est à dire qu’il ne peut pas passer par toutes les cases.
La plus petite valeur possible pour m est donc , ce qui correspond à une bande de  cases.

VI.	Le cas bidimensionnel

On peut également se poser la question suivante (qui va expliquer le titre de l’exposé…) : on se donne un « cavalier » qui se déplace sur un échiquier  selon des pas de p cases dans un sens, suivies de pas de q cases dans une direction perpendiculaire. Dans le cas du cavalier du jeu d’échecs, on a ainsi  et . On demande quelle est la plus petite valeur de m telle que le cavalier, en partant d’un case quelconque du l’échiquier, puisse atteindre toutes les cases de celui-ci.

Nous n’avons pas entièrement résolu ce problème. Toutefois, nous avons dégagé quelques minorations intéressantes. On supposera ici aussi, par symétrie, que . En revanche, on n’aura pas nécessairement .

Tout d’abord, on peut remarquer que l’abscisse du cavalier varie à chaque mouvement ou de p, ou de q. Si le cavalier passe par toutes les cases, alors son abscisse prendra aussi toutes les valeurs de , ce qui nous ramène au problème précédent, à une unité près (puisque lors du problème initial, la bande de déplacement étant numérotée à partir de 0, et ici, à partir de 1). On a donc nécessairement , et .
D’autre part, lorsque le cavalier se trouve sur la case  (où […] désigne la partie entière), il doit pouvoir faire au moins un déplacement. Si l’on ne tient pas compte des problèmes de borne, les 8 cases atteignables par le cavalier sont celles de coordonnées  et . Au moins l’une d’entre elles appartient à , d’où  ou .
On a donc nécessairement , ce qui est plus fort que la minoration précédente, mais ne nous aurait pas fourni la condition .
***

MOTS CLEFS  SAUTS DE CAVALIER PGCD VECTEURS ENTIERS COMBINAISON LINÉAIRE FROBENIUS 

Comptes Rendus MATh.enJEANS, 04-04	 ©MATH.enJEANS, 2005