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

version pdf de l'article [2,7 Mo]


 

[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 . 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