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]

 

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 &endash; 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