DEFINITION GEOMETRIQUE DU PROBLEME DES LABYRINTHES

Nous pouvons considérer les carrefours d'un labyrinthe comme des points géométriques; les allées, corridors, rues, galeries, comme des lignes droites ou courbes, planes ou gauches, réunissant ces points deux à deux. Nous dirons que ces points et ces lignes forment un réseau géométrique ou un labyrinthe lorsqu'un point mobile placé sur l'une des lignes du réseau peut passer à un autre point quelconque, sans quitter les lignes du système. Gela posé, nous allons démontrer que ce point mobile peut décrire successivement toutes les lignes du réseau, sans saut brusque, et sans passer plus de deux fois sur chacune d'elles. En d'autres termes, un labyrinthe ti est jamais inextricable.

Vous réaliserez un jeu de la manière suivante : Choisissez arbitrairement sur une feuille de papier blanc un nombre quelconque de points; joignez-les deux à deux et autant de fois que vous voudrez par un nombre quelconque de lignes, droites ou courbes, de telle sorte qu'aucun point du système ne reste isolé des autres; vous avez ainsi un réseau géométrique. Dessinez, par exemple, le réseau des lignes d'omnibus et de tramways d'une grande ville, le réseau des chemins de fer d'un pays, le réseau des fleuves, des rivières et des canaux d'une contrée quelconque, en y ajoutant, à volonté, les côtes et les frontières.

On recouvre le dessin d'une feuille de carton opaque, de manière à ne pas conserver le souvenir du plan du labyrinthe; cette feuille de carton est percée d'un trou que nous appellerons oculaire, et qui permet seulement d'apercevoir une petite fraction du réseau. On déplace le carton ou Vécranj de telle sorte

Le jeu des labyrinthes. 47

que l'oculaire se trouve placé sur un carrefour A. Il s'agit ensuite de faire parcourir deux fois à l'oculaire toutes les lignes du réseau, d'une manière continue, et de revenir ensuite au point de départ A. Pour conserver le souvenir du passage de l'oculaire sur chacun des chemins qu'il parcourt^ on trace sur chaque ligne suivie un petit trait transversal^ à l'entrée et à la sortie des carrefours. Par conséquent, les deux extrémités de chaque chemin devront, après les pérégrinations du voyage, avoir été marquées deux fois^ mais non davantage.

Dans un labyrinthe effectif, ou dans une galerie de mines, le promeneur égaré déposera une marque, un caillou, à l'entrée et à la sortie de chaque carrefour, dans l'allée qu'il vient de quitter et dans celle qu'il vient de prendre.

SOLUTION DE M. TREMAUX.

Parmi les diverses solutions de ce curieux problème de la Géométrie de situation, dont nous venons de donner Ténoncé, nous choisirons, comme la plus simple et la plus élégante, celle qui nous a été gracieusement communiquée par M. Trémaux, ancien élève de l'Ecole Polytechnique, ingénieur des télégraphes; mais nous en avons modifié légèrement la démonstration.

Première règle. — En partant du carrefour initial, on suit une voie quelconque, jusqu'à ce que l'on arrive à une impasse ou à un nouveau carrefour: 1° si le chemin qu'on a suivi aboutit à une impasse, on revient sur ses pas, et Ton peut alors considérer le chemin parcouru comme supprimé, puisqu'il a été traversé deux fois; 2° si le chemin aboutit à un carrefour, on prend

Troisième récréation.

une voie quelconque, au hasard, en ayant soin de marquer d'un trait transversal la voie d'arrivée dans le sens de la flèche /, et la voie de départ dans le sens delà flèche^ (^^.9). Dans cette figure et dans les trois suivantes, nous avons distingué les anciennes marques des nouvelles, en surmontant celles-ci d'une petite croix.

Fig. 9.

Fis. 10.

On continue l'applicationdela première règle, chaque fois que l'on arrive à un carrefour inexploré; au bout d'un certain parcours, on arrivera nécessairement à un carrefour déjcà exploré; mais cette situation peut se présenter de deux manières différentes, selon que le chemin d'arrivée a déjà été suivi une première fois ou ne contient encore aucune trace de passage. Alors on applique

l'une des deux règles suivantes :

Deuxième règle. - En arrivant à un carrefour déjà exploré, par une voie nouvelle, on doit rétrograder, en marquant par deux traits l'arrivée au carrefour et le départ, ainsi qu'on le voit dans

la^^. 10.

Troisième règle. - Lorsqu'on arrive à un carrefour de)à exploré par une voie antérieurement suivie, on prendra d'abord

Le jeu des labyrinthes.

une voie qui n'aura pas été parcourue, s'il en existe, ou, à son défaut,, une voie qui n'aura été parcourue qu'une seule fois ; ces deux cas sont représentés dans iQsJig. 1 1 et 12.

Fig. II.

Fiff. 12.

DÉMONSTRATION. — En cxécutaut rigoureusement l'application des règles précédentes, on parcourra nécessairement deux fois toutes les lignes du réseau. D'abord on fera les remarques suivantes :

I. Au départ du carrefour A, on y introduit une sjule marque initiale.

II. Le passage à travers un carrefour, par l'emploi de l'une des trois règles, ajoute deux marques aux lignes qui aboutissent à ce carrefour.

III. A un moment quelconque de l'exploration du labyrinthe, avant l'arrivée au carrefour ou après le départ du carrefour, le carrefour initial contient un nombre impair de marques, et tout autre carrefour en contient un nombre pair.

IV. A un moment quelconque de l'exploration, avant ou après le passage au carrefour, le carrefour initial ne peut avoir

E. Lucas. — Récréations mathém. 4

5o Troisième récréation.

qu'un seul chemin, marqué une seule fois; tout autre carrefour exploré ne peut avoir que deux chemins marqués une seule fois.

V. Après l'exploration complète, tous les carrefours doivent être couverts de deux marques sur chaque chemin; c'est la condition imposée par l'énoncé.

Gela posé, il est facile de voir que, lorsque le voyageur arrive dans un carrefour M différent du carrefour initial A, il ne peut être arrêté dans sa course par les difficultés du problème. En effet, on ne peut arriver à ce carrefour M que par une voie nouvelle, ou par une voie déjà parcourue une seule fois. Dans le premier cas, on applique la première ou la deuxième règle; dans le second cas, l'entrée au carrefour produit un nombre impair de marques; il reste donc, d'après la Remarque III, à défaut d'une voie nouvelle, une ligne qui n'a été traversée qu'une seule fois.

Ainsi, il ne peut y avoir d'arrêt qu'en revenant au carrefour initial A. Soit ZA le chemin qui conduit au repos forcé, en venant du carrefour Z; ce chemin est nécessairement un chemin parcouru une première fois, car sans cela on pourrait continuer le voyage. Puisque le chemin ZA a déjà été traversé, il n'existe dans le carrefour Z aucune voie n'ayant point encore été traversée, car sans cela on aurait oublié d'appliquer le premier cas de la troisième règle; d'ailleurs, il y avait en dehors de ZA une voie, et une seule, YZ, parcourue une seule fois, d'après la Remarque IV. Par conséquent, au moment de l'arrêt en A, toutes les routes du carrefour Z ont été traversées deux fois; on démontrera, de même, que toutes les voies du carrefour précédent Y l'ont été deux fois, et ainsi des autres carrefours. C'est ce qu'il fallait démontrer.

Le jeu des labyrinthes. 5 i

Remarque. — On peut remplacer la deuxième règle par la suivante, quand il ne s'agit pas d'un carrefour ferme'. Si l'on arrive. par une voie nouvelle, à un carrefour déjà exploré, on peut prendre une nouvelle voie , à la condition d'affecter les deux marques du passage au carrefour d'indices correspondants a et a' \ alors, si l'on retourne au carrefour par l'une de ces deux voies^ on doit reprendre l'autre. Cela revient, pour ainsi dire, à placer un pont aa' au-dessus du carrefour. Cette règle nous a été indiquée par M. Maurice, ancien élève de TÉcole Polytechnique