26/02/2015

Euler et le parcours du cavalier

8520576-leonhard-euler-1707-1783-on-engraving-from-the-1800s-swiss-mathematician-and-physicist-engraved-by-b.jpgDes deux récréations mathématiques les plus importantes traitées par Euler, l’une remonte à l’époque de son premier séjour à Saint-Pétersbourg (1727-1741), l’autre aux années passées à Berlin, avant son deuxième séjour à Saint-Pétersbourg (1766-1783). La première de ces récréations est le problème des ponts de Königsberg, dans lequel il s’agit de déterminer s’il est possible ou non de passer une fois et une seule par chacun des sept ponts enjambant les deux bras de la rivière Pregel.




Euler déduisit dans sa Solutio problematis de 1736 les conditions de résolution de ce genre de problèmes : un trajet est possible si les régions, îles ou rives, que joignent les ponts sont chacune touchées par un nombre pair de ponts ou bien si deux seulement sont rencontrées par un nombre impair de ponts (qui seront alors nécessairement points de départ et d’arrivée).

Il en découle que le cas particulier de Königsberg est impossible, puisque les quatre régions sont reliées par un nombre impair de ponts : A est jointe par 5 ponts, B par 3, C par 3, D par 3. En revanche, un pont de plus entre D et C, appelons-le h, rendrait la traversée possible, puisqu’il ne resterait plus que deux régions reliées par un nombre impair de ponts. Un trajet serait alors A abc C dB.

L’addition d’un autre pont entre A et B rendrait toutes les régions «paires», c’est-à-dire que chacune aurait un nombre pair d’accès ; ainsi, le circuit deviendrait fermé, en sorte que la traversée pourrait commencer n’importe où, se clore, et se répéter.

La seconde récréation est le problème du parcours du cavalier. Il s’agit de passer une fois et une seule par chacune des cases de l’échiquier en avançant uniquement à l’aide de sauts du cavalier, donc en avançant verticalement de deux cases et horizontalement d’une case, ou, inversement, verticalement d’une case et horizontalement de deux cases. Cet exercice était devenu au XVIIIe siècle un jeu d’habileté utilisé par certains en société, le but étant d’enlever successivement des pions disposés sur un échiquier pour qu’on puisse ainsi vérifier que toutes les cases avaient bien été parcourues. C’est du reste lors d’une soirée mondaine que Euler eut pour la première fois connaissance de ce problème du cavalier, à la résolution duquel il devait laisser son nom attaché. Il narre cette expérience dans les termes suivants au début de son étude imprimée de 1758/59.

978-2-88074-857-9.pngJe me trouvai un jour dans une compagnie où, à l’occasion du jeu d’echecs, quelqu’un proposa cette question : de parcourir avec un cavalier toutes les cases d’un échiquier, sans parvenir jamais deux fois à la même, & en commençant par une case donnée. On mettoit pour cette fin des jettons sur toutes les 64 cases de l’échiquier, à l’exception de celle où le Cavalier devoit commencer sa route ; & de chaque case où le Cavalier passoit conformément à sa marche, on ôtoit le jetton, de sorte qu’il s’agissoit d’enlever de cette façon successivement tous les jettons. Il faloit donc éviter d’un côté que le cavalier ne revint jamais à une case vuide, & d’un autre côté il faloit diriger en sorte (= en telle sorte) sa course qu’il parcourut enfin (= à la fin) toutes les cases.

Ceux qui croyoient cette question assez aisée firent plusieurs essais inutiles sans pouvoir atteindre au but ; après quoi celui qui avoit proposé la question, ayant commencé par une case donnée, a sçu si bien diriger la route qu’il a heureusement (= avec succès) enlevé tous les jettons. Cependant la multitude des cases ne permettoit pas qu’on ait pû imprimer à la mémoire la route qu’il avoit suivie ; & ce n’étoit qu’après plusieurs essais que j’ai enfin rencontré une telle route qui satisfit à la question ; encore ne valoit-elle que pour une certaine case initiale. Je ne me souviens plus si on lui a laissé la liberté de la choisir lui-même ; mais il a très positivement assuré qu’il étoit en état de l’éxécuter, quelle que soit la case où l’on voulut qu’il commençat. 

De fait, ce n’est pas la première description du problème par Euler. Le 26 avril 1757, il envoie de Berlin une lettre à Christian Goldbach, dans laquelle on lit ce qui suit. «Le souvenir d’un problème qui me fut proposé autrefois m’a récemment amené à d’élégantes recherches sur lesquelles l’analyse semblerait n’avoir aucune prise. La question était la suivante. On doit avec un cavalier traverser toutes les cases de l’échiquier en sorte qu’il ne pénètre dans aucune d’entre elles plus d’une fois. A cette fin on occupa toutes les cases avec des marques, qui au contact du cavalier étaient enlevées. Il fut encore ajouté qu’on devait commencer à une case donnée. Cette dernière condition me parut rendre la question particulièrement difficile, car j’avais assez rapidement trouvé quelques trajets, mais dans lesquels le point de départ devait m’être laissé libre. Je remarquai toutefois que, lorsque le trajet revenait en lui-même, donc lorsque le cavalier pouvait sauter de la dernière case à la première, cette difficulté disparaissait aussitôt. Après avoir effectué quelques essais à ce propos, j’ai finalement trouvé une méthode sûre, dépourvue de tâtonnement, permettant de découvrir autant de trajets que l’on désire –mais la quantité de toutes les possibilités n’est pas infinie. Un tel trajet est montré dans la figure annexée : le cavalier y saute en effet selon la suite des nombres. Comme il y a du dernier, 64, au n°1 un saut du cavalier, ce trajet revient en lui-même. En plus, il y a ici la propriété que la différence des nombres dans des cases opposées est de 32 partout.»

Euler introduit, lors de ses constructions, diverses sortes de contraintes supplémentaires. Nous allons définir ci-après les différents types de parcours, et noter –si tant est qu’on les y rencontre– leurs dénominations.

  • On appelle «trajet» ou «parcours» la traversée, par un mouvement continu du cavalier, d’une suite de cases de l’échiquier.
  • Une case pouvant être jointe à une autre par un saut du cavalier communique à, ou avec, elle, ou est communiquante avec elle.
  • Un trajet sera « partiel » ou « complet » selon qu’il recouvrira une partie ou l’ensemble des cases de l’échiquier. La première figure montre un trajet partiel ; la dernière case ne permet pas la poursuite du trajet. Cette tentative infructueuse d’Euler n’a toutefois pas été inutile : elle servira à la construction d’un autre trajet sur la même page. La seconde est un autre exemple de trajet partiel, cette fois arrêté volontairement par Euler bien qu’il eût pu continuer le trajet. Là aussi, il a repris partiellement cette tentative ultérieurement, mais en choisissant l’autre possibilité de sortie pour 25.

  • Un trajet complet sera «ouvert» si sa première case et sa dernière ne peuvent être jointes par un saut du cavalier (c’est une route de la premiere espece). Il sera «fermé» dans le cas contraire (route de la seconde espece, ou rentrante, ou rentrante en elle-même, trajet perfectus). Les deux prochaines figures sont des exemples de l’un et de l’autre. Le parcours de la lettre à Goldbach remplissait lui aussi la condition d’être fermé.

Lorsqu’on a un trajet ouvert, il n’existe, comme le remarque Euler, que deux possibilités de trajet, la seconde consistant à parcourir le même chemin en sens inverse, partant donc de la case de 64. Le choix d’une autre case de départ demandera donc une autre recherche de trajet. Il en va tout autrement dans un trajet fermé, puisqu’on peut placer le point de départ dans n’importe quelle case et effectuer un parcours complet grâce à la jonction entre les cases de 1 et 64. La renumérotation d’un trajet existant fermé à partir d’une autre case initiale est appelée par Euler «autre succession», alius ordo. En fait, la succession des cases reste la même puisqu’une même case succède à une même case, et que ce ne sont que les nombres qui sont décalés. Quant aux modifications d’un trajet donné pour en déduire des trajets réellement différents, ce sont des variationes, des variations, ou, pour le carré entier, des permutationes.

Etablissement d'un trajet complet

Extension d'un trajet partiel

Considérons le carré vide de la figure suivante. On voit que certaines cases présentent plus de possibilités de sortie que d’autres. Ainsi, une case du carré intérieur offre huit possibilités de sortie ; une case de son enceinte six, mais seulement quatre pour celle de l’angle ; une case de la bordure extérieure quatre, trois si elle jouxte la case angulaire et deux pour la case angulaire elle-même, qui ne présente donc qu’une entrée et une sortie.

Supposons que nous voulions établir un trajet sur l’échiquier. A cet effet, nous effectuerons des sauts du cavalier à notre gré, mais en gardant à l’œil les cases présentant un petit nombre de sorties pour éviter de s’y laisser enfermer ou qu’elles ne deviennent inaccessibles ultérieurement. Sans trop de peine, nous parviendrons à établir un trajet partiel couvrant entre 50 et 60 cases, après quoi notre tentative prendra fin, car il restera des cases libres, soit isolées soit pouvant être jointes entre elles, mais inaccessibles depuis les deux extrémités du trajet existant. C’est ici que l’idée que suggéra, semble-t-il, Louis Bertrand trouva son application : prendre comme nouvelle extrémité du trajet une case interne qui permette de rallier une des cases isolées. En effet, si le trajet partiel couvrant m cases est

1,2, ..., m -1, m

et qu’une case intérieure x, différente de m − 1, soit à un saut du cavalier de m, alors

1,2, ..., xm, m-1, ..., x+1

sera un trajet couvrant les mêmes cases que précédemment, mais qui pourra être accru si x+1 permet de passer à une case auparavant hors d’atteinte. Ce mode d’opérer pourra alors être répété au trajet étendu si un blocage se présente à nouveau.

Tel est donc le seul moyen dont se servira Euler dans son manuscrit, qui le mènera aux résultats et déductions énoncés dans son article. C’est la raison pour laquelle il écrit dans ce dernier qu’il va expliquer une méthode certaine, qui nous conduira infailliblement au but proposé, & par le moyen de laquelle on sera en état de découvrir autant de routes satisfaisantes qu’on voudra.

La méthode d’opérer d’Euler sera donc uniformément la même :

  • Considérer l’une des deux cases terminales sans issue du trajet partiel existant.
  • Dresser la liste des cases du trajet existant qui sont reliées à cette case terminale par un saut du cavalier (ce seraient nos x).
  • Placer en dessous (pour nous, ce sera en indice) leurs successeurs (ce seraient nos x+1), qui représenteront l’ensemble des nouvelles cases terminales possibles du trajet transformé.
  • Dresser ensuite la liste des cases devant être jointes.
  • Dresser enfin la liste des cases communiquant avec ces cases.
  • Examiner alors si l’une des cases de cette dernière liste coïncide avec l’une des cases indiquées en indice. Si oui, on pourra étendre le trajet, car une case devant être jointe sera à un saut du cavalier d’une des nouvelles cases terminales. Si non, on appliquera à nouveau le même procédé à l’une ou l’autre des nouvelles extrémités.

Extrait du titre Euler et le parcours du cavalier 
De Jacques Sesiano 
Publié aux Presses polytechniques et universitaires romandes

Les commentaires sont fermés.