CHAPITRE V

Ce chapitre est consacré à quelques questions dépendant de la théorie des réseaux géométriques. Nous commencerons par le Problème et les Théorèmes d'Euler d'où nous déduirons, comme conséquence, la théorie des Labyrinthes et celle des Tracés géométriques que nous présenterons d'ailleurs d'une façon succincte. Les problèmes réciproques du jeu d'Hamilton et de la marche du cavalier sur Véchiquier seront traités dans la dernière partie de ce chapitre qui sera terminé par un aperçu sur le jeu de dominos.

Problème d'Euler. — Ce problème a son origine dans un mémoire (^) présenté par Euler en 1786 à l'Académie de Saint-Pétersbourg et dans lequel il donnait la solution d'une question en discussion à cette époque. Il s'agissait d'établir s'il était possible ou non de se promener dans la ville de Kœnigsberg de façon à traverser tous les ponts de cette ville mais en ne passant qu'une fois sur chacun d'eux.

La ville est construite à l'embouchure de la Pregel, rivière qui prend à cet endroit la forme indiquée ci- dessous en entourant l'île de Kneiphof, En 1759, il y avait sept ponts (qui existent encore

(*) (( Solutio problematis ad geometrlam situs pertinentis », Commentarii Academiœ Scientiarum Petropolitanse pour 1786, Saint-Pétersbourg, 1741» vol. VIII, pp. 128-140. Le mémoire a été traduit en français, par M. Gh, Henry; voir Lucas, vol. J, partie II, pp. 21-33.

suivant Baedeker) jetés sur la rivière et occupant les positions indiquées sur notre figure ; il est facile de voir qu'avec une telle disposition le problème n'est pas possible. Euler cependant ne s'est pas

limité au cas de Kœnigsberg et il a examiné le problème général d'un certain nombre d'îles reliées d'une façon quelconque par des ponts. La solution étant évidemment indépendante de la surface des îles et de la largeur des ponts, s'applique au cas où cbaque île se réduit h un point, et chaque pont à une ligne plus ou moins étendue. Nous obtenons ainsi à la limite une figure géométrique à laquelle on donne le nom de réseau.

Dans le problème de Kœnigsberg, la figure a la forme indiquée ci-dessus, les surfaces sont représentées par les points A, B, C, D et les ponts par les lignes l,m n,p,q,r,s.

Le problème d'Euler revient donc à vérifier si une figure géométrique donnée peut ôtre décrite par un point se déplaçant de façon à parcourir toutes les lignes de la figure en en passant qu'une fois sur chacune d'elles.

Une question plus générale consiste à déterminer le nombre de traits nécessaire pour tracer une telle figure en s'imposant comme condition de ne pas passer deux fois sur la même ligne. La figure

Fîff. 8G

qui peut être à deux ou à trois dimensions est représentée par des lignes (droites, courbes ou sinueuses) joignant un nombre détermine de points, ou par un modèle construit avec des petites baguettes, ou encore au moyen de petites cordes munies à chaque extrémité d'une agrafe permettant de réunir en un point un certain nombre d'entre elles.

La théorie de ces figures est comprise, comme cas particulier, dans les propositions démontrées par Listing dans sa Topologle (^). Toutefois nous nous en tiendrons à la méthode exposée par Euler, mais pour nous permettre de présenter le raisonnement d'une façon plus concise, nous allons donner quelques définitions préliminaires.

Un nœud (ou une île) est le point de départ ou d'arrivée d'une ligne ou de plus de deux lignes. Une branche (un pont ou passage) est une ligne reliant deux nœuds consécutifs : un nœud ne peut donc se trouver au milieu d'une branche. Une extrémité (ou agrafe) est l'origine ou la fin d'une branche.

Vordre d'un nœud est le nombre de branches qui aboutissent à ce nœud. Un nœud d'où part ou aboutit une seule branche est un nœud ou une extrémité libre. Un nœud est d'ordre pair lorsqu'il est le point d'arrivée ou de départ d'un nombre pair de branches ; d'après ce qui a été dit plus haut, il n'existe pas de nœud du second ordre : un pareil nœud est dit imaginaire.

Un nœud est d'ordre impair lorsqu'il est le point d'arrivée ou de départ d'un nombre impair de branches. Une ligure est fermée lorsqu'elle ne présente aucune extrémité libre : une pareille figure est souvent appelée un réseau fermé.

Une route est constituée par un certain nombre de branches parcourues consécutivement de telle sorte qu'aucune d'elles ne soit suivie deux fois. Une route fermée se termine au point de départ.

(') Die Stiidien, Gôttingen, 18/17, Partie X. Voir également Prof. Tait, un article sur la Topologie de Listing, dans le Philosophiccd Magazine, Londres, janvier i884, série V. Vol. XVII, pp. 3o-46.

Une figure est tracée d'un irait continu lorsqu'elle peut être assimilée à une route.

Voici maintenant les conclusions formulées par Euler :

1° Dans un réseau fermé, le nombre des nœuds impairs est toujours pair.

2° Toute figure n'ayant pas de nœuds impairs peut être tracée d'un trait continu (en une route rentrante) par un point partant d'une position quelconque sur le réseau.

3° Une figure qui a deux nœuds impairs, mais deux seulement, peut être décrite d'une façon continue par un point partant de l'un des nœuds impairs pour aboutir à l'autre.

4° Une figure qui a plus de deux nœuds impairs ne peut être décrite complètement en une seule route ; Listing complète cette proposition par ce corollaire : une figure ayant 2n nœuds impairs (et pas plus) peut être décrite complètement par n routes distinctes.

Passons à la démonstration de ces diverses propositions.

1° Le nombre des nœuds impairs dans un réseau fermé est pair.

Soit b le nombre des branches, le nombre des agrafes sera 26.

Représentons par /f„ le nombre des nœuds du /i'"" ordre (c'est-àdire des nœuds où aboutissent n branches). Puisque la figure est fermée, n ne peut être moindre que 2. Le nombre des agrafes à un nœud du n'"*' ordre est n, donc :

par suite,

et

2/^2 + 3/^3 H- 4 /f^ -H ... -\- nkn -f- ... =r 26;

3/i-3 -+- bk.. -+■ est pair,

^3 + ^3 + ®st également pair.

2" Une figure qui ne présente pas de nœuds impairs peut être décrite d'un trait continu en une route rentrante.

Puisque la route doit être rentrante, le point de départ est indifférent. Supposons que l'on parte d'un nœud A. Chaque fois que nous arrivons à un nœ^ud nous prenons une agrafe en entrant et nous laissons une agrafe en l'abandonnant. Il n'y a pas de nœuds impairs

et, par conséquent, le nombre des agrafes à chaque nœud est pair ; dès lors, si nous touchons à un nœud quelconque autre que A, nous trouvons toujours une agrafe qui nous donne accès sur une branche non encore parcourue. Par suite, la route nous conduit finalement au nœud A d'où on est parti.

Si nous avons plus de deux agrafes en A, nous pouvons continuer la route par l'une des branches issues de A, non encore parcourues, mais comme plus haut nous revenons finalement au point de départ A.

Il reste maintenant à montrer que la route peut être arrangée de façon à comprendre toutes les branches. Or, considérons chaque branche du réseau comme représentée par une ficelle munie d'une agrafe à chaque extrémité et supposons qu'à chaque nœud toutes les agrafes soient réunies. Le nombre de ces agrafes à chaque nœud étant pair, si on les sépare, il est possible de les accoupler de nouveau par groupe de deux (cet arrangement par paires étant imaginaire). Le réseau dans son ensemble forme alors une ou plusieurs courbes fermécs, puisque maintenant chaque nœud consiste simplement en deux extrémités agrafées ensemble.

Si cet accouplement fait au hasard nous donne une seule courbe, la proposition est démontrée ; ear en partant d'un point quelconque on peut suivre chaque branche et revenir au point de départ. Mais si cet accouplement fournit en un point quelconque une boucle isolée, L, alors au nœud P par exemple, où elle touche une autre boucle, M, détachons les quatre agrafes qui s'y rencontrent (par exemple, deux de la boucle L et deux de la boucle M) et accouplons-les de nouveau dans un autre ordre, nous amenons ainsi la boucle L à former une partie de la boucle M.

En modifiant de cette manière les accouplements des agrafes, on peut transformer successivement chaque boucle séparée et la faire figurer comme partie d'une seule boucle.

" Considérons, par exemple, le cas de trois îles A,B,C, reliées chacune avec les deux autres par deux ponts. La manière la plus défavorable d'accoupler de nouveau les extrémités en A, B, G se-

PROBLÈMES DES TRACÉS CONTINUS 2o3

rait de transformer ABA, AGA et BGB en boucles séparées. Les boucles séparées ABA et AGA se touchant en A, nous pouvons accoupler les agrafes en A de façon à réunir ABA et AGA en une seule boucle ABAGA. De môme en reliant d'une autre façon, et par deux, les quatre agrafes en B. nous pouvons former une seule boucle avec BGB et ABAGA.

De la façon dont Euler s'exprime, il semblerait résulter pour nous qu'il a cherché à formuler une règle pratique permettant de tracer d'une façon continue, sans en connaître la forme, les figures qui nous occupent, mais qu'il a échoué dans ses tentatives.

Il a cependant avancé qu'une figure géométrique quelconque peut être tracée complètement en une seule route, à la condition que chacune de ses parties soit parcourue deux fois, mais

deux fois seulement, car clia- '°' '^

que branche étant ainsi doublée, aucun des nœuds n'est impair et la figure peut par suite se tracer d'un trait continu. Dans ce cas, une figure quelconque peut être décrite complètement d'un mouvement continu sans en connaître la forme ; nous donnons plus loin, page 207 des règles à cet effet.

3° Toute figure ayant deux nœuds impairs, et seulement deux, peut être décrite d'un mouvement continu par un point qui partirait d'un des nœuds ponr aboutir à Vautre.

Gette proposition se ramène immédiatement à la précédente. Soient A et Z les deux nœuds impairs.

Supposons tout d'abord que Z ne soit pas une extrémité libre. Nous pouvons évidemment suivre une route allant de A à Z ; si nous imaginons les branches de cette route éliminées, nous enlevons une agrafe en A qui devient un nœud pair, deux agrafes à tous les nœuds intermédiaires entre A et Z qui restent par suite pairs et enfin une agrafe en Z qui devient nœud pair. Tous les

nœuds du rcscau ainsi forme sont dès lors pairs ; ce réseau peut donc, d'après 2°, être tracé d'un trait continu et si la route commence en Z, elle se terminera également en Z. Par suite, si ces deux roules sont faites successivement, la première figure sera décrite d'un mouvement continu en commençant en A pour finir eu Z.

Supposons, en second lieu, que Z soit une extrémité libre, alors nous devons faire route de Z à un nœud Y où se rencontrent plus de deux branches. La route de A à Y comprenant toute la figure à l'exclusion du chemin de Y à Z sera effectuée comme plus haut et on complète le tracé en allant de Y à Z,

4*^ Une figure n ayant seulement que 2n nœuds impairs peut être décrite complètement en n routes distinctes.

Considérons une route dont l'origine est un nœud impair et suivons-la jusqu'à ce qu'on arrive à un nœud où nous ne trouvons aucun chemin nouveau, il est évident que ce dernier nœud est impair ; car, chaque fois que nous rencontrons un nœud pair sur la route, il se présente un chemin pour en sortir ; et, chaque fois que nous arrivons à un nœud impair, nous comptons une agrafe en entrant et une agrafe en sortant, mais si ce nœud se présente à la fin de la route, nous ne comptons qu'une agrafe. Supprimons cette route par la pensée, il reste une figure avec 2n — 2 nœuds. Par suite, n routes semblables, nous donneront un ou plusieurs réseaux avec des nœuds pairs seulement. Mais chacun d'eux a un nœud commun avec l'une des routes déjà prise et peut dès lors être décrit en le considérant comme une partie de cette route. Par conséquent, le tracé complet exige n et seulement n routes distinctes.

Il s'ensuit, ainsi d'ailleurs que l'a remarqué Euler, que si le réseau comporte plus de deux nœuds impairs, il ne peut être tracé complètement en une seule route.

Le problème des ponts de Kœnigsberg nous conduit à un réseau contenant quatre nœuds impairs ; par suite, d'après 4°. ce réseau ne peut être parcouru d'un mouvement continu en un seul voyage, mais il peut être parcouru complètement en deux routes distinctes.

Les figures 88 et 89, ci-après, ne contenant que des nœuds pairs, peuvent être tracées d'un trait continu. La première de ces figures, un pentagone étoile ou à angles rentrants, était une des figures symboliques des Pythagoriciens ; la seconde représente, dit-on, le sceau ou la signature de Mahomet ; suivant la légende, il l'aurait

Fig. 88 Fig. 89 Fig. 90

tracée pour la première fois sur le sable avec la pointe de son cimeterre sans la faire quitter le sol ou repasser sur des parties déjà dessinées de la figure; le fait est possible, puisqu'elle ne contient que des nœuds pairs.

La figure 90 est empruntée à un article du professeur Tait : elle ne contient que deux nœuds impairs, et, par suite, peut être décrite d'un trait continu en partant de l'un de ces nœuds pour aboutir à l'autre.

Citons, comme nouvel exemple, la figure formée en traçant les diagonales d'un polygone convexe de (2/1 -+- i) côtés, un pareil réseau de lignes peut être tracé d'un mouvement continu.

Un échiquier divisé, suivant l'usage, en 6/| cases, contient 28 nœuds impairs et 53 nœuds pairs, le dessin de la figure exige quatorze traits continus pour tracer toutes les limites sans passer plus d'une fois sur chaque ligne. Enfin, la figure de la page 123 compte 20 nœuds impairs et, par conséquent, exige dix traits continus pour son tracé.

C'est un théorème bien connu que toute courbe dont le nombre de nœuds égale le degré peut être tracée d'un mouvement continu.

Labyrinthes. — Tout le monde a lu la légende du labyrinthe

de Minos en Crcfc, On trouve encore çà et là quelques labyrinthes (nous citerons notamment celui de Hampton Court qui est un spécimen assez médiocre de ce genre de construction), et probablement plusieurs de nos lecteurs ont cherché à reconnaître leur route dans certains d'entre eux ou, tout au moins, sur leurs dessins.

Notre but ici est d'étudier la manière de parcourir en tous sens ces sorles de constructions, même lorsqu'on n'en connaît pas le plan.

La théorie des labyrinthes est une conséquence de l'étude que nous venons de faire des théorèmes d'Euler sur les courbes à tracé continu. Les chemins dans un labyrinthe constituent ce que nous avons appelé des branches et les carrefours où deux ou plusieurs chemins se rencontrent sont des nœuds. L'entrée du labyrinthe, l'extrémité d'une impasse et le centre du labyrinthe sont des extrémités libres et, par suite, des nœuds d'ordre impair.

Si un labyrinthe ne présente comme nœuds impairs que l'entrée et le centre — ce qui implique l'absence d'impasses — il peut être parcouru d'un mouvement continu. C'est une conséquence de la proposition 3° de la page 201. Egalement, quel que soit le nombre des nœuds impairs dans un labyrinthe, on peut toujours suivre une route conduisant de l'entrée au centre sans revenir sur ses pas, mais cette route ne fait parcourir qu'une partie du labyrinthe. Dans les deux cas que nous venons de mentionner, la route à suivre ne peut être déterminée qu'avec un plan.

Un plan n'est pas nécessaire cependant si nous faisons la même supposition qu'Euler, c'est-à-dire si nous supposons que chaque chemin dans le labyrinthe est doublé. Dans ce cas, nous pouvons donner des règles précises permettant le parcours complet d'un labyrinthe quelconque, même si son plan n'est pas connu. Il est bien évident que décrire deux fois le même chemin dans un labyrinthe n'est pas la manière la plus prompte d'arriver au centre, mais en s'orientant convenablement, le labyrinthe tout entier est parcouru, on est certain de trouver le centre sur sa route à un moment donné, et il est impossible de perdre son chemin.

On voit immédiatement que le tracé complet d'un labyrinthe

PROBLEMES DES TRACES COîiTINUS 2O7

ainsi doublé est toujours possible, puisque chaque nœud est rendu pair, et, d'après la proposition 2° d'Euler, en partant de l'entrée on peut parcourir le labyrinthe dans son entier développement ; à un moment donné, on arrive au centre et finalement on revient au point de départ. Cette méthode nous met dans l'obligation de passer deux fois par chaque chemin, et il va de soi que les deux passages sont opposés en direction.

Lorsque le labyrinthe est représenté par un dessin, la route à suivre est généralement facile à déterminer, mais le problème n'est pas toujours aussi aisé quand il s'agit d'une construction, à moins d'en posséder le plan exact. Pour parcourir d'une façon certaine et sans erreur possible, un labyrinthe dont on ne connaît pas le plan, il est nécessaire d'adopter des signes conventionnels pour marquer les chemins suivis et la direction du parcours, par exemple en traçant une flèche à l'entrée et à l'extrémité de chaque chemin, ou encore mieux, peut-être, en marquant le mur sur le côté droit, de sorte qu'on ne s'engagera pas dans un chemin dont les deux côtés seront marqués.

En opérant de la sorte si, lorsqu'on arrive à un nœud, on prend, lorsque la chose est possible, un chemin non encore suivi, ou si, aucun autre chemin ne pouvant être utilisé, on s'engage dans un chemin déjà parcouru une fois seulement, on peut traverser complètement tout labyrinthe à deux dimensions (^).

Bien entendu, un même sentier ne doit pas être suivi deux fois dans la même direction, un chemin déjà traversé deux fois (une fois dans chaque direction) doit être laissé de côté, et à l'extrémité d'une impasse il est nécessaire de revenir sur ses pas en suivant le chemin par où on y a été amené.

Pour beaucoup de personnes, un labyrinthe consiste en une suite de chemins entrelacés au milieu desquels on peut suivre une certaine route aboutissant, au centre, à un espace libre ou h une

(*) Voir Le problème des labyrinthes, par G. Tarry, Nouvelles annales de mathématiques, mai 1896, série III, vol. XIV.

construction quelconque. 11 existe probablement bien peu, si même il en existe, de labyrinthes de cette sorte datant des temps classiques ou du Moyen Age.

Les anciens donnaient le nom de dédale ou de labyrinthe à toute construction un peu compliquée, souterraine ou non, et comprenant des chambres et des couloirs tellement enchevêtrés que le visiteur s'y perdait et ne pouvait en retrouver l'issue (*). Une telle construction peut, à la rigueur, être considérée comme un labyrinthe, mais ce n'est pas ce qu'on entend généralement par ce mot. D'ailleurs, les règles précédentes permettent à quiconque veut s'en donner la peine de parcourir en tous sens un monument de ce genre.

Un autre genre de labyrinthes antiques consistait en une route sinueuse couvrant un espace relativement faible et conduisant à une place vide ou à un temple situé au centre (-). C'est là un exemple de labyrinthe dans lequel il est possible de s'aventurer sans craindre de perdre son chemin ; mais, comme la surface entière peut être occupée par les sinuosités de la route, la distance à parcourir pour aller de l'entrée au centre peut être considérable quand bien même la surface couverte par le labyrinthe serait très petite.

Comme spécimen du genre, nous citerons le labyrinthe légendaire construit pour le Minotaure. Il était figuré sur le revers des

(*) Voir par exemple les descriptions du labyrinthe du lac Mœris, données par Hérodote, livre II, c. cxlviii. — Strabon : livre XVII, c. i, art. 87. — DiODORE : livre I, ce. lxi, lxvi, et Pline : Hist. nat., livre XXXVI, c. xiii, art. 84-89. Pour d'autres références, voir A. Wiedemann, Herodots Zweiles Buch, Leipzig, 1890, p. 622 et suivantes. Voir aussi Virgile : Enéide, livre V, v. 588. — Ovide : Met., livre VIII, c. v, clix. — Str.vbon : livre VIII. c. vi.

(') Sur les labyrinthes anciens et sur ceux du Moyen- Age — particulièrement sur ces derniers — voir un article par M. E. Trollope, dans le Archaeological Journal, i858, vol. XV, pp. 2x6-235; nous lui empruntons la plupart de nos renseignements historiques.

médailles ou monnaies de la ville de Gnosse (qui ne sont pas excessivement rares) et l'une de ses formes est représentée par la figure 91 ci-après. En réalité, le dessin est le même que celui de la figure 92 comme on peut facilement s'en assurer en donnant la forme d'un cercle à cette figure rectangulaire.

M. Inwards a émis l'opinion (^) que ce dessin sur les monnaies de Gnosse était peut-être une réminiscence de celui qui figurait sur un jeton donné par les prêtres de l'antiquité pour guider le profane et lui permettre de reconnaître sa route dans le labyrinthe.

En considérant la figure 91, il suppose chaque mur circulaire

remplacé par deux murs équidistants laissant entre eux un passage libre et il obtient ainsi un labyrinthe pour lequel le dessin original servira de clef ou de guide. La route ainsi indiquée s'obtient immédiatement en notant que lorsqu'on arrive à un nœud (c'est-à-dire à un point où il y a un chemin à choisir), le chemin à prendre est celui qui est le plus voisin, à un près, de celui par lequel on est arrivé au nœud. Ce labyrinthe peut aussi se parcourir en s'imposant comme simple règle de suivre toujours le mur à sa droite ou toujours le mur à sa gauche. On peut modifier et compléter cjuelque peu le tracé du labyrinthe en introduisant des obstacles imprévus, sans toutefois rendre impossible l'application des règles précédentes, mais il n'est guère possible d'augmenter les difficultés. On obtiendrait certainement ainsi un joli jeu, mais bien que l'idée sur laquelle il est basée soit très ingénieuse, elle doit être regardée, pen-

f) Knowledge, Londres, octobre 189' Récrcatiotis mathématiques, H.

2IO RÉCllÉATIONS MATHÉMATIQUES

sons-nous, comme très invraisemblable. Une autre supposition émise est que la ligne courbe qui figure sur le revers des médailles indique la forme de la corde tenue par un certain nombre de personnes prenant part à une danse rythmique.

Du temps des Grecs et des Romains, l'usage était de faire graver sur certains joyaux des reproductions du labyrinthe de Gnosse et on trouve des dessins semblables mais plus compliqués dans un grand nombre de mosaïques romaines (*). La copie du labyrinthe Cretois était brodée sur plusieurs des manteaux d'apparat des derniers empereurs et c'est probablement pourquoi on la trouve reproduite sur les murs et sur le sol de certaines églises (2). En Italie et en France, a une époque reculée, ce genre de décorations murales et de pavage prit une grande extension sous forme de rubans présentant des entrelacements fort complexes, mais consistant toujours (autant qu'il nous en souvienne) en une simple ligne. 11 était d'usage, au Moyen Age, de disposer au milieu de la nef de certaines grandes églises, des pavages de pierres blanches et noires ou de carreaux de couleur formant, par leurs combinaisons, des méandres compliqués auxquels on donnait le nom de labyrinthe, de chemin de Jérusalem ou de La Lieue. Nous ne saurions dire quelle fut l'origine de ces sortes de pavages. Louis Paris, dans son Mémoire du mobilier de Noire-Dame de Reims, prétend que ces pavages étaient une réminiscence de quelque tradition païenne : c'est possible, cependant, il n'en est fait mention ni dans Guillaume Durand, ni dans les auteurs qui lui sont antérieurs et ayant écrit sur les choses touchant aux églises.

Les plus anciens labyrinthes que nous connaissions ne sont pas antérieurs à la fin du xii® siècle, et le Seigneur de Caumont, dans son Voyaïge d'ouliremer en Jhérusalem (en i4i8 — publié par le marquis de la Grange — Paris, A. Aubry, i858), en parlant du labyrinthe de Crête (p. 4 1), ne dit rien qui puisse faire croire à une

(1) Voir l'ouvrage de Breton : Pompeia, p. 3o3.

(') OzANAM. — Graphia aurese urhis Romœ, pp. 92, 178.

tradition de cette nature, c'est-à-dire qu'il n'établit aucun point de comparaison entre le labyrinthe du Minotaure et ceux qu'il avait évidemment vus tracés sur le pavé des églises de son pays.

Le labyrinthe de la Cathédrale de Reims s'appelait Dédale, méandre, Lieue ou Chemin de Jérusalem, Quelques archéologues ont voulu voir, dans ces pavés à combinaisons de lignes concentriques, un jeu des maîtres des œuvres, en se fondant sur ce fait, que trois de ces labyrinthes, ceux de Chartres, de Reims et d'Amiens, représentent dans certains compartiments, les figures des architectes qui avaient élevé ces cathédrales. Nous n'avons pas à trancher la question.

On trouve les traces de la plupart de ces labyrinthes dans l'ouvrage de Amé intitulé : Carrelages émaillés du Moyen Age et de la Renaissance.

Vallet, dans sa description de la crypte de Saint-Bertin de Saint- Omer, établit que les fidèles devaient suivre à genoux les nombreux lacets tracés par les lignes de ces méandres, en mémoire du trajet que fit Jésus de Jérusalem au Calvaire.

La petite basilique de Reparatus à Orléans- Ville (Algérie) montre, sur son pavé, une mosaïque que l'on peut prendre pour un de ces labyrinthes, c'est-à-dire un méandre compliqué. Or, cette basilique date de 828, ainsi que le croit F. Prévost.

Cet usage est-il venu d'Orient après les premières croisades ? ou est-il une tradition locale ? nous inclinerions à penser que la représentation des maîtres de l'œuvre sur ces pavages les rattacherait à quelque symbole maçonnique adopté par l'école des maîtres laïques, d'autant que nous ne voyons apparaître ces labyrinthes sur les pavages des églises qu'au moment où les constructions religieuses tombent dans les mains de cette école puissante. Si ces- méandres avaient été tracés pour représenter le trajet du Sauveur de la porte de Jérusalem au Calvaire, il est à croire qu^un signe religieux aurait rappelé les stations, ou du moins la dernière ; on ne remarque rien de semblable sur aucun des labyrinthes encore existants ou sur ceux dont le dessin nous est resté.

De plus, nous trouvons des carrelages émaillés qui représentent des combinaisons de lignes ou méandres dans des dimensious si petites, qu'on ne pouvait, à coup sûr, suivre ces chemins compliqués, ni à pied ni à genoux, puisque quelques-uns de ces labyrinthes, comme celui de l'église abbatiale de Toussaints (Marne), n'ont pas plus de 25 centimètres de côté. A vrai dire, ces derniers méandres datent du xiv" siècle et peuvent passer pour une copie d'œuvresplus grandes ; mais encore une fois, les petits et les grands ne renferment aucun signe religieux (^).

Quoi qu'il en soit, nous citerons parmi les plus beaux spécimens qui existent encore : les décorations murales des Cathédrales de Lucques, d'Aix en Provence et de Poitiers, et les dallages des églises de Sainte-Marie du ïranstévère à Rome, de San Vitale à Ra venue, de Notre-Dame à Saint Omer et de la cathédrale de Chartres. Ces derniers dessins étaient probablement faits dans le but de symboliser le passage à travers la vie considérée comme un pèlerinage.

En Angleterre, ces labyrinthes étaient le plus souvent (nous pourrions, peut-être, dire toujours) tracés sur une étendue de terrain gazonné confinant certaine maison religieuse ou de refuge et quelques raisons nous portent à supposer qu'on s'en imposait le parcours comme exercice religieux en récitant un pater ou un ave à chaque tournant. Après la Renaissance, ces labyrinthes étaient fréquemment appelés Troie-villes ou Retraites de Julien. Parmi les plus beaux spécimens du genre qui existent encore (autant que nous avons pu le vérifier ), nous citerons ceux de RocklifP Marslies dans le Cumberland ; d'Asenby, dans le Yorkshire, d'Alkborough dans le Lincolnshire, de Wing dans le Rutlandshire ; de Boughton-Green dans le Northamptonshire ; de Comberton dans le Cambridgeshire, de Saffron Walden dans le canton d'Essex ; et de Chilcombe près de Winchester.

Les labyrinthes plus modernes semblent avoir été introduits —

(*) VioLLET-LE-DuG. — Dictiomiaire raisonné de V architecture française, tome VI, pp. 1 52-153.

probablement de l'Italie — durant la Renaissance, et plusieurs des palais ou des grands châteaux construits en Angleterre sous les rognes des Tudor et des Stuart avaient comme annexes des labyrinthes. Ceux qui formaient dépendances des palais royaux de Southwark, Greenwich et Ilampton Court étaient particulièrement connus à cause de leur proximité de la Capitale. Ce dernier a été dessiné en 1690 par London et Wise pour Guillaume III qui en faisait son séjour de prédilection ; les divers guides de Londres et de ses environs en contiennent un plan. Pour la majorité des visiteurs qui s'y rendent dans un but de promenade, il est suffisamment compliqué, mais c'est en réalité une construction assez terne qui peut être parcourue complètement en suivant toujours le même côté (soit de droite, soit de gauche) et ne présentant aucun nœud d'un ordre supérieur à 3.

A moins qu'en un certain point la roule pour aller au centre bifurque en deux branches qui se réunissent ensuite en formant une boucle dans laquelle se trouve situé le centre du labyrinthe, la partie centrale peut

toujours être atteinte ^'S 93 - Le labyrinthe d'Hampton Court.

en suivant l.a règle que nous venons de donner, c'est-à-dire en longeant le mur, soit du 'côté droit, soit du côté gauche. Il n'est guère possible de considérer comme un jeu de patience un labyrinthe pouvant être parcouru d'une façon aussi simple. En supposant l'existence d'une bifurcation, le labyrinthe sera d'autant moins facile à parcourir qu'il présentera plus de nœuds et que leur ordre sera plus élevé ; la difficulté peut môme être considérablement augmentée en introduisant des ponts et des tunnels de façon à avoir un labyrinthe à trois dimensions.

2l4 RÉCRÉATIONS MATHÉMATIQUES

Les arbres géométriques. -~- Euler n'a fait porter ses recherches que sur les réseaux fermés et dans le problème du labyrinthe on admet l'existence d'un nombre quelconque d'impasses dont les extrémités forment ce que nous avons appelé des nœuds libres. La question peut maintenant se généraliser en supposant que chaque partie de la figure constituant un réseau fermé diminue jusqu'à se réduire h. un point. L'arrangementobtenu alors est connu sous le nom d*arbre géométrique. Le nombre des tracés continus, nécessaires pour décrire d'une façon complète un arbre géométrique^ est appelé la base de la ramification.

Nous pouvons donner un exemple d'une forme possible de ces arbres au moyen de tringles portant une agrafe ou un crochet à chaque extrémité. Prenant une de ces tiges, nous attachons à chaque extrémité une ou plusieurs tiges semblables, puis à chaque extrémité libre nous fixons de nouveau une ou plusieurs tiges, et ainsi de suite. Chaque extrémité libre et chaque point où se rencontrent deux ou plus de deux tringles constituent ce que nous avons déjà appelé des nœuds. Les tringles elles-mêmes sont les branches ou les chemins.

La théorie des arbres géométriques qui joue déjà un rôle assez important dans certaines branches de l'analyse moderne et qui, peut-être, contient le germe de plusieurs théories chimiques ou biologiques, fut mise à jour dans un mémoire de Cayley (') écrit en

(*) Philosophicnl Magazine, mars 1857, série IV, vol. XIII, pp. 172-176; ou Collected Works, Cambridge, 1890, vol. III, n° 2o3, pp. 242-246. — Voir aussi une note sur les partitions doubles, Philosophical Magazine, novembre 1860, série IV, vol. XX, pp. 337-34i- Sur le nombre des arbres avec un nombre donné de nœuds, voir le Quarlerly Journal of Mathematics, Londres, 1889, vol. XXIIL pp. 376-378. Son affinité avec la chimie a été signalée pour la première fois par le Prof. Cayley dans un article sur les corps isomères paru dans le Philosophical Magazine de juin 1874, série IV, vol. XLVII, pp. 444-447; 1* question a été traitée d'une façon plus complète dans son mémoire sur la théorie des arbres à l'Association britannique, en 1876, Repporls, pp. 257-3o5.

i856. La discussion de cette théorie a été présentée plutôt analytiquement que géométriquement. Nous nous contenterons de mentionner les résultats suivants.

Le nombre des arbres ayant n nœuds donnés est /i"~^. Si on représente par A„ le nombre des arbres ayant n branches et par B„ le nombre des arbres avec n branches libres formant les dernières bifurcations, on a :

(i:c)-i(i x=»)~^i(i — a;3)~^2... = n-Aja:4-A2a?2-^A3x3 + ...; (t a;2)-i(i:c2)-B2(i a^3)

Au moyen de ces formules nous pouvons déterminer successivement les valeurs de A^, Ag... et B^, B2...

Ces valeurs pour n = 2, 3,/i, 5, 6, et7 sont données dans le tableau suivant :

An

ii5

Bn

Nous allons maintenant traiter quelques questions dans lesquelles on se propose de déterminer une route passant une fois, mais seulement une fois, partons les nœuds d'une figure géométrique donnée. Ces questions peuvent être regardées comme les inverses de celles du chapitre précédent et leur solution présente de plus grandes difficultés. La théorie générale des problèmes de cette nature n'a peutêtre pas été traitée complètement par les mathématiciens, bien que deux cas spéciaux consistant dans \g jeu d'Ilamilton (ou Icosien) et dans la marche du cavalier aux échecs aient été examinés avec quelques détails. Ce sont ces deux jeux qui vont nous occuper.

Le jeu d'Hamilton. — Ce jeu consiste à déterminer la route à suivre le long des arêtes d'un dodécaèdre régulier pour passer par

RÉCRÉAT101\S MATHÉMATIQUES

tous les sommets une fois seulement, Sir William Hamilton (*) à qui on doit ce jeu — si toutefois le mot jeu est le terme à employer dans la circonstance — représentait les trente sommels du solide par des lettres qui désignaient des villes, et les vingt arêtes constituaient les seules routes possibles. On comprend sans peine l'inconvénient de se servir d'un solide et le dodécaèdre peut être remplacé avantageusement par sa représentation sur une surface plane ainsi que le montre la figure 9^. La figure 96 et la figure 96 remplissent également notre but et elles sont plus faciles à tracer. Le premier problème est « Le voyage autour du monde ». II

Fig. 96

s'agit, en partant d'une ville quelconque, de passer par toutes les autres villes, une seule fois, et de revenir au point de départ; on se donne l'ordre des n villes devant être visitées tout d'abord, n ne surpassant pas 5.

Hamilton a fait connaître la règle pour effectuer un tel voyage à Dublin, en 1857, au congrès de l'Association Britannique. A chaque sommet, trois arêtes seulement aboutissent et si nous arrivons à un sommet quelconque par l'une de ces trois arêtes, nous nous trouvons en présence de deux routes à prendre, l'une à droite, que nous représenterons par d, et l'autre, à gauche, que nous désignerons par g. On s'assure facilement sur la figure que la suite des opérations in-

(*) Voir Quarlerly Journal of Malhematics, Londres, 1862, vol. V, p. 3o5; ou Philosophical Magazine, janvier, i884, série V, vol. XVII, p. 4^; voir aussi Lucas, Recréations, vol. II, part. VII,

PROBLEMES DES TllVCES GOxNTlNUS 217

diquées dans chacun des membres des égalilés suivantes nous conduit au même point et que, par suite, les résultats sont équivalents,

gd'g = dgd, dg'-d ^ gd.g, gd'g = d\ dgH = gK

Les opérations g^ et d-' nous ramonent au point de départ, ce que nous représenterons par les égalités

Pour résoudre le problème avec une figure ayant trente sommets, la difficulté consiste à établir une relation embrassant trente opérations successives et dont l'effet final serait représenté par l'unité. Or, en nous reportant à la relation g^ = d. g^. d nous voyons que :

î =g' = ^2 ^3 ^ (dg^d)g' = (dg^ = \d{dghl)g\^ = = \dYdg\^ = \d\dgH)gdg\^ ^ \dYdgdg\\ ainsi

(1) \d>g\dg)Y=i, et semblablement

(2) \gH\gdff = i.

Par suite. Tune ou l'autre des suites de mouvements

(i) dddgggdgdgdddgggdgdg,

(2) gggdddgdgdgggdddgdgd,

indique sur un dodécaèdre la route prise par le voyageur pour passer dans chaque ville. L'arrangement est cyclique et la route peut commencer en un point quelconque de la série des déplacements en transportant d'une extrémité à l'autre le nombre nécessaire de lettres. Le point d'où l'on part est déterminé par l'ordre de certaines villes qui est donné à l'avance.

Ainsi supposons qu'on nous dise de partir de F, d'aller successivement en B, A, U et ï, puis de revenir en F après avoir passé par toutes les autres villes. Si, par la pensée, nous nous considérons

2l8 RÉCRÉATIONS MATHÉMATIQUES

comme étant arrivé en F en venant de G, le chemin FB sera représenté par la lettre g, mais si nous nous figurons être venu de E en F, le chemin FB sera représenté par la lettre d. Le chemin de B à A sera représenté par g, et ainsi de suite. Ainsi la route débute soit par ggqd, soit par dggd. Ce dernier départ ne figurant ni dans la suite (i), ni dans la suite (2), n'entre pas dans nos solutions. Le premier début peut être regardé comme les i^\ 2*^, 3^ et 4® chemins de (2), ou comme les 4^. 5', 6^ et 7^ chemins de (i). Chacun de ces arrangements nous conduit à une route satisfaisant à la question.

Ces routes sont :

FBAUTPONCDEJKLMQRSHGF, et

FBAUTSRKLMQPOINCDEJHGF.

Une bonne précaution à prendre pour éviter de passer une seconde fois sur la même ville consiste à faire une marque ou à placer un jeton sur chaque angle aussitôt qu'on y arrive. Un jeu semblable peut se faire avec tout autre corps solide ne comptant que trois arêtes à chaque sommet. De tous ces solides, le cube et le tétraèdre sont les plus simples, mais le lecteur peut construire luimême un nombre quelconque de figures planes représentant d'autres solides que ceux de la page 2t6. Hamilton en a donné plusieurs exemples. Dans tous les cas on doit déduire de formules analogues à celles établies page 217, des relations cycliques telles que (i) et (2) données plus haut. On suit alors pour la solution la marche déjà indiquée. Celte méthode peut aussi être employée pour trouver une règle permettant de décrire un labyrinthe quelconque dans lequel aucun nœud n'est d'un ordre supérieur à trois.

Pour ce qui est des solides ayant des sommets où aboutissent plus de trois arêtes, tels que l'octaèdre où quatre arêtes se rencontrent à chaque sommet, et l'icosaèdre qui compte cinq arêtes à chaque sommet, en arrivant à chacun des sommets nous nous trouvons en présence de plus de deux chemins à suivre. Par suite (à

moins de supprimer un certain nombre d'arêtes), il est nécessaire de modifier et de donner de l'extension à la notation symbolique mentionnée plus haut avant de l'appliquer aux solides de cette nature et aux figures planes qu'on peut en déduire. Nous abandonnons cette étude à ceux de nos lecteurs désireux d'imaginer un nouveau jeu.

M. Hermary a donné une autre solution fort élégante du problème d'Hamilton. Elle consiste à développer sur un plan les douze pentagones réguliers formant les faces du dodécaèdre de façon que chacun d'eux ait avec le précédent un côté commun, mais la solution est géométrique et ne s'applique pas directement à des solides plus compliqués.

Hamilton a imaginé un autre jeu dans lequel partant d'une ville quelconque on se rend dans un certain nombre d'autres villes désignées, dans un ordre spécifié à l'avance, puis on passe une fois et une seule fois par toutes les villes restantes, enfin le voyage se termine à une ville connue. Il a également proposé d'étudier comment on devait bloquer un certain nombre de villes (qui, par suite, ne pouvaient être traversées) afin d'obtenir un effet déterminé et variable suivant les cas. Si nos recherches sont complètes, ces problèmes n'ont pas encore été soumis à l'analyse mathématique.

Marche du cavalier sur l'échiquier. — Un autre problème géométrique dont l'étude a donné lieu à des recherches vraiment curieuses comme ingéniosité et qui présente quelque analogie avec celui d'Hamilton, consiste à déplacer sur un échiquier un cavalier de façon à lui faire occuper successivement les 64 cases sans passer deux fois sur la même.

La littérature sur ce sujet est si étendue (^) qu'il serait préten-

(') Pour la bibliographie du sujet, voir Deu Linde, Gcschichte und Literatar des Schachspiels, Berlin, 187/1, vol. II, pp. loi-iii. Sur le problème lui-même voir un mémoire de P. Volpicelli dans Atti délia Rcale Accademia dei Lincei, Rome, 1879, vol. XXV, pp. Sy-iGp^; également Applications de

lieux de notre part de chercher à présenter l'historique complet des diverses solutions de ce problème, nous nous contenterons de réunir quelques notes, prises un peu au hasard, sur certaines solutions et en particulier sur celles dues à De Moivre, Euler, Vandermonde, WarnsdorfT et Roget.

Sur un échiquier contenant un nombre pair de cases, la route à suivre peut être rentrante ou non, mais si le nombre des cases est impair, la route ne peut être rentrante. Car si le cavalier part d'une case blanche, son premier mouvement l'amène sur une case noire, le suivant sur une case blanche, et ainsi de suite. Par conséquent, après son passage sur toutes les cases d'un échiquier d'un nombre impair de cases, le dernier mouvement doit le laisser sur une case de la même couleur que celle d'où il est parti, et dès lors aucun mouvement né pourra réunir ces deux cases.

Les solutions les plus anciennes dont nous ayons connaissance sont celles données à la fin du xvii^ siècle par De Montmort et De Moivre Q). Elles s'appliquent à l'échiquier ordinaire de 64 cases et reposent sur la division mentale de l'échiquier en un carré central intérieur de seize cases entouré par une enceiute de deux rangées. Si, à l'origine, le cavalier est placé sur une case de la bande extérieure, il se déplace le long de cette bande et toujours dans le même sens, de façon à toucher chaque case ; il ne pénètre dans le carré central que dans le cas de nécessité absolue. Quand les cases de l'enceinte ont toutes été occupées successivement, l'ordre des mouvements à faire prendre au cavalier pour le faire passer sur les cases restantes se détermine sans grande difficulté. L'opération est con-

V analyse mathématique au jeu des Ecliecs, par C.-F. de Jaenisch, 3 vol., Saint-Pétersbourg, t862-63; et des articles du général PARMErsiiEu, dans les comptes rendus de ['Association française pour l'avancement des Sciences, 1891, 1893, 1894.

(*) Nous ne savons dans quel ouvrage elles furent publiées pour la première fois. Elles sont mentionnées par Ozanam et Motucla; voir Ozaxam, édition de i8o3, vol.l, p. 178; édition de i84o, p. 80.

dulte en sens contraire lorsqu'à l'origine le cavalier est placé sur une case du carré central.

Cette méthode est applicable à des carrés et à des rectangles de toutes dimensions, elle est rendue suffisamment compréhensible par la solution de De Moivre donnée dans la figure ci-après. Les nombres inscrits dans les diverses cases sur cette figure représentent

:'>2 ly

Fig- 97 Solution de De Moivre

Fig. 98 Solution d'Euler pour le carre de 36 cases.

l'ordre dans lequel ces cases doivent être successivement occupées. Nous avons placé à côté une solution par route rentrante, due à Euler et s'appliquant à un échiquier de 36 cases. Il est avantageux, pour se guider sur l'échiquier, de placer un jeton sur chaque case au moment où le cavalier l'abandonne.

Gomme étude sérieuse de la question faite ensuite nous mentionnerons l'essai tenté par Eulcr en 1769 (0, à l'instigation de Bertrand, de Genève, qui, un peu plus tard, (en 1778) en fit l'exposition Gette méthode est applicable à des tableaux de toutes formes et de toutes dimensions, mais d'une façon générale, les solutions qu'elle

Cj Mémoires de Berlin pour 1769, Berlin, 1766, pp. 3 10-337; ou Commentationes Arithmeticœ Collectœ , Saint-Pétersbourg, 1849, vol. I, pp. 337-355.

donne ne sont pas symétriques et on en saisit péniblement les liaisons mutuelles.

Euler commence par faire mouvoir au hasard le cavalier sur l'échiquier, jusqu'à ce qu'il ne puisse plus se déplacer ; avec un peu d'attention, la manœuvre peut être dirigée de façon qu'il ne reste plus que quelques cases à occuper : représentons-les par a, b, c,..., La méthode consiste alors à déterminer certaines règles permettant d'intercaler les cases vacantes dans difTérentes parties du circuit et aussi de rendre le circuit rentrant.

L'exemple suivant cité par Legendre comme étant un des cas les plus difficiles, est une application de la méthode. Supposons que le cavalier ait suivi la route i, 2, 3,.,..., 60 représentée par la figure 99 ci-dessous et qu'il ne reste plus que quatre cases a, 6, c, rf à occuper.

On commence par rendre rentrante la route de i à 60. La case i commande une case p, p étant Sa, 62 ou 2 ; la case 60 commande une case <j, q étant 29, 69 ou 5i. Alors, si deux de ces valeurs de p eÀ q diffèrent d'une unité, la route peut être rendue rentrante. C'est le cas ici pourp = 52 et g =5i. Ainsi, les cases i,2,3,...5i ; 60, 59,..., 62 forment une route rentrante de soixante mouvements. Par suite, en remplaçant les nombres 60, 59...., 52 par 52, 53,..., 60, les sauts seront numérotés consécutivement. Nous conseillons au lecteur, qui désire suivre avec facilité les détails que nous allons donner, de construire, avant d'aller plus loin, le carré d'Euler avec ses divisions.

Il s'agit maintenant d'introduire les cases a, 6, d, dans la route. Dans le nouveau diagramme de soixante cases formé comme nous l'avons expliqué, la case a commande les cases numérotées 5i, 53, 4i, 25, 7, 5 et 3. Le choix de l'une de ces cases est indifférent, supposons que l'on prenne 5i. Alors 5i doit être placé au dernier rang de la route sur les soixante cases, de sorte que nous pourrons la continuer par les mouvements a, b, d,. Par conséquent, si l'on ajoute 9, c'est-à-dire 6o-5i, à chaque nombre du diagramme construit, en remplaçant 61, 62, 63,..., 69 par i, 2, 3,..., 9, nous ob-

tenons une route partant de la case occupée primitivement par 60, le soixantième mouvement se fait sur la case occupée à l'origine par 5i et les soixante et unième, soixante-deuxième, soixante-troisième mouvements nous conduisent respectivement aux cases a, b, d.

Il reste encore à introduire la case c. Or, puisque c commande la case portant actuellement le n'' j5 et que 63 commande la case numérotée 24, on peut opérer comme nous l'avons déjà fait en premier lieu pour obtenir une route rentrante. En fait, les cases nu-

Jf9

fiO

Fig. 99 ^ Fig. loo

Exemple de la méthode d'Euler.

mérotées i, 2, 3,..., 24 ; 62, 63 26, c constituent une marche

du cavalier; nous remplaçons 63, 62,..., 25, par les nombres 26, 26,..., 63 et alors le n" 64 tombe sur la case c. En opérant ainsi, on obtient une route couvrant sans lacune l'échiquier.

Enfin, cette route doit être rendue rentrante. Tout d'abord, les cases I et 64 doivent être situées dans le voisinage l'une de l'autre et ceci peut s'effectuer comme il suit : Prenons une des cases commandées par I, 28 par exemple, 28 à son tour commande i et 27. Par suite, les cases 64, 63,..., 28; 1, 2, 3,..., 27 forment une route, et nous représenterons cette disposition sur le diagramme en remplaçant les n"' i, 2,..., 27 par 27, 26,..., i.

Maintenant, la case occupée par i commande les cases 26, 38, 54, 12, 2, i4, 16 et 28 ; et la case 64 commande les cases i3, 43, 63, 55. Les cases i3 et i4 étant consécutives, il en résulte que les cases

6/î, G3,..., i/i ; I, 2, 3,..., i3 forment une roule. Dos lors, en Tcmplaçant les nombres i, 2, 3,.... i3 par i3, 12,..., i, on obtient une route rentrante couvrant l'échiquier et représentée par la seconde figure de la page 2 23.

Euler a montré comment il était possible de déduire d'une route rentrante quelconque sept autres routes rentrantes.

11 n'est pas difficile non plus d'appliquer la méthode de façon à obtenir une route commençant à une case donnée et finissant à une autre case également donnée.

Euler s'est occupé ensuite des modifications a faire snlir à sa méthode pour en permettre l'application à certains cas mniprenant des conditions restrictives.

Un exemple intéressant est celui dans lequel les trente-deux premiers mouvements doivent s'effectuer sans sortir de la moitié de l'échiquier; la figure ci-aprcs représente une des solutions de ce