LE MEMOIRE D EULER
i*" Outre cette partie delà Géométrie qui s'occupe de la grandeur et de la mesure, et qui a été cultivée dés les temps les plus reculés, avec une grande application^ Leibniz a fait mention, pour la première fois, d'une autre partie encore très inconnue actuellement, qu'il a appelée Geome^r/a situs. D'après lui, cette branche
Deuxième récréation.
de la science s'occupe uniquement de l'ordre et de la situation, indépendamment des rapports de grandeur. Mais quels sont les problèmes qui appartiennent à cette géométrie ; quelles sont les méthodes qu'il faut employer à leur résolution? C'est ce qui n'a pas encore été nettement défini. Récemment j'ai entendu parler d'un problème qui paraît se rapporter à la Géométrie de situation, puisqu'il ne contient^ dans son énoncé, que des considérations d'ordre et non de mesure ; aussi ai-je résolu d'exposer ici, comme un spécimen^ la méthode que j'ai trouvée pour résoudre ce problème.
2° A Kœnigsberg, en Poméranie, il y a une île appelée Kneiphof; le fleuve qui l'entoure se divise en deux bras {fig. i), sur les-
Fig. I.
Les ponts de Kœnigsberg en lySg.
quels sont jetés les sept ponts a, b, c, d, e,/. g. Cela posé, peuton arranger son parcours de telle sorte que l'on passe sur chaque
Le jeu des ponts et des îles. 23
pont, et que l'on ne puisse y passer qu'une seule fois? Cela semble possible, disent les uns; impossible, disent les autres; cependant personne n'a la certitude de son sentiment. Je me suis donc proposé le problème suivant, qui est très général :
Quelle que soit la forme d'un fleuve, sa distribution en bras, par des îles en nombre quelconque, et quelque soit le nombre des ponts jetés sur le fleuve, trouver si V on peut franchir celui-ci en passant imefois, et une seule, sur chacun des ponts.
3° Quant au problème particulier des sept ponts de Kœnigsberg, on pourrait évidemment le résoudre en faisant l'énumération complète de tous les parcours possibles ; on reconnaîtrait ainsi s'il existe ou non un chemin qui réponde à la question. MaiSj par suite du grand nombre de permutations, cette méthode, déjà difficile et laborieuse dans le cas particulier, serait impraticable pour un plus grand nombre de ponts ; d'autre part, parmi ces permutations, beaucoup d'entre elles sont inutiles, de telle sorte qu'après avoir terminé l'opération on aurait rencontré un grand nombre de choses qui ne sont pas en question ; c'est en cela^ sans aucun doute, que réside la cause d'une aussi grande difficulté ('). Donc, en laissant de côté ces considérations, j'ai recherché s'il n'était pas préférable d'imaginer une méthode qui permît de juger, au premier abord, de la possibilité ou de l'impossibilité du problème ; je pensais, en effet, qu'une telle méthode devait être beaucoup plus simple (*).
(^) C'est pour la même raison, très probablement, que ron n'a pas encore trouvé la solution du problème des reines lorsque le nombre de celles-ci dépasse huit; voir à ce sujet notre quatrième récréation sur le problème des huit reines au jeu des échecs. Quant aux permutations qu'il y aurait lieu de considérer ici, ce sont les permutations avec répétition.
(2) Cette remarque d'Euler comporte un très grand caractère de généralité qu'elle ne paraît pas avoir toutd'abord. J'ai observé que, dans un grand nombre
24 Deuxième récréation.
4*^ Or, toute la méthode repose sur une manière convenable de représenter les divers chemins; pour cela, je me sers des lettres majuscules A, B, G, D, ... pour désigner les diverses régions séparées par les bras du fleuve; alors, si l'on passe de la région A dans la région B, soit par le pont a^ soit par le pont b, je désigne ce chemin par AB ; la première lettre indique la région de départ, et la seconde la région d'arrivée. Maintenant^ si le voyageur passe de la région B dans la région D, par le pont f par exemple, je désigne la seconde traversée par BD, et l'ensemble des deux passages successifs par ABD; ainsi, la lettre intermédiaire B désigne en même temps la région d'arrivée après la première traversée, et la région de départ pour la seconde.
5"" Si le voyageur passe ensuite de D en G par le pont g, je désigne l'ensemble des trois passages successifs par les quatre lettres ABDG. Ainsi, la notation ABDG signifie que le voyageur, situé primitivement dans la région A, est parvenu dans la région G, après avoir occupé successivement les régions B et D, mais, puisque ces quatre régions sont séparées les unes des autres par le bras du fleuve, le voyageur a dû franchir trois ponts; de même, tout parcours dans lequel on traverse quatre ponts sera désigné par cinq lettres. En général, si le voyageur traverse n ponts, la notation de son parcours contiendra n -h i lettres. Ainsi,
de problèmes de la Géométrie desituation, ily a souventunedillérence considérable dans la manière de traiter la possibilité et l'impassibilité ; en général, l'impossibilité se manifeste plus facilement que la possibilité, ainsi que l'on pourra s'en convaincre dans les théories du solitaire, du taquin et de quelques autres jeux. Dans le paragraphe suivant, Euler ajoute que toute sa méthode repose sur une notation spéciale ; nous ferons voir encore que dans tous ces problèmes il en est toujours ainsi. On verra, dans notre récréation sur le jeu de baguenaudier, comment la notation si ingénieuse de M. Gros simplifie considérablement la théorie do ce jeu.
Le jeu des ponts et des îles. 25
dans le problème des sept ponts de Kœnigsberg, tout chemin possible doit être de'signé par huit lettres.
6° On observera que, dans cette notation^ il n'est pas tenu compte de la désignation des ponts par lesquels le passage s'effectue; il est évident, en effet, que les ponts qui réunissent les mêmes régions peuvent être, dans chaque parcours, remplacés les uns par les autres. Par conséquent, dans le problème des sept ponts, tout parcours est représenté par huit lettres; mais, de plus, ces huit lettres doivent être disposées de telle sorte que la succession immédiate des lettres A et B^ dans Fordre AB ou BA, se présente deux fois, puisqu'il y a deux ponts qui réunissent les rives des régions A et B; de même, le voisinage des lettres A et C doit aussi apparaître deux fois; pour la même raison^ il est nécessaire que les lettres B et D^ ou G et D soient voisines une seule "•t'ois.
7° Le problème particulier se réduit donc à former avec les quatre lettres A, B, G, D une série de huit lettres, dans laquelle tous ces voisinages apparaissent autant de fois qu'il a été indiqué; mais, avant de chercher à effectuer une telle disposition, il est bon de se demander si celle-ci est réalisable. En effet, si l'on démontrait, et c'est ce qui a lieu ici, qu'un tel assemblage de lettres est impossible, il serait inutile de continuer. Aussi ai-je trouvé une règle qui donne, pour tous les cas, la condition indispensable pour que le problème des ponts et des îles ne soit pas impossible.
8"^ Pour cela, je considère uniquement la région A, dont la rive est réunie à celle des autres régions par un nombre quelconque de ponts a, b, c, d^ e, ... En commençant par le pont a, j'observe que si le voyageur traverse ce pont, ou bien le voya-
20 Deuxième récréation.
geur se trouvait en A avant le passage, ou s'y trouvera après; par conséquent, en franchissant le pont a dans un sens ou dans l'autre, la lettre A paraîtra une seule fois dans la notation. Supposons maintenant que trois ponts a, b, c conduisent dans la région A ; si le voyageur traverse les trois ponts, la lettre A apparaîtra deux fois dans la notation, soit qu'au début le voyageur parte de cette région ou d'une autre quelconque. De même, si cinq ponts conduisent en A, la lettre A sera comprise trois fois dans la notation du passage à travers tous ces ponts. En général, si le nombre des ponts qui aboutissent à la rive de la région A est impair (une telle région sera appelée région impaire]^ la lettre A apparaîtra, dans la notation du passage complet, un nombre de fois égal à la moitié du nombre des ponts augmenté d'une unité. En d'autres termes, si le nombre des ponts est 2n -\- I, le nombre d'apparitions de A sera la moitié de 2^ + 2
ou 72 4- I .
9° Dans le cas du problème de Kœnigsberg,cinq ponts aboutissent à la région A, et trois ponts à chacune des régions B, C, D ; donc, dans la notation du parcours complet, la lettre A doit apparaître trois fois, et chacune des lettres B^ C, D doit être écrite deux fois; par conséquent cette notation devrait renfermer neuf lettres, et non huit, ainsi que nous l'avions trouvé par d'autres considérations. Ainsi le problème de franchir une seule fois tous les ponts de Kœnigsberg n'est pas possible.
10° On appliquera exactement le même raisonnement pour tous les cas dans lesquels le nombre des ponts qui aboutissent aux différentes régions est toujours impair; on pourra déterminer
Le jeu des ponts et des îles.
des cas d'impossibilité du parcours. En effet, s'il arrive que le nombre total des apparitions de toutes les lettres n'égale pas le nombre de tous les ponts augmenté de Tunité, le problème est alors impossible. On observera que la règle donnée pour obtenir le nombre des répétitions de la lettre A par le nombre impair des ponts de la région s'applique toujours, soit que tous les ponts issus de la rive A aboutissent à une seule région B, soit qu'ils aboutissent à un nombre quelconque de régions.
1 1° Mais, lorsque le nombre des ponts issus de A est pair, on doit considérer deux cas, suivant que le voyageur est parti de A ou d'une autre région. En effet, si deux ponts conduisent en A, et si le voyageur est parti de A, alors la lettre A doit être répétée deux fois : une première fois pour le départ par l'un des ponts, et une deuxième fois pour le retour par l'autre pont; mais si le voyageur a commencé ses pérégrinations par une autre région, la lettre A ne se trouvera écrite qu'une seule fois et désignera tout aussi bien, ainsi qu'il est convenu, l'arrivée en A par l'un des ponts et le départ par l'autre.
12° Supposons que quatre ponts conduisent dans la région A, et que le voyageur parte de celle-ci; alors la notation du parcours contiendra trois fois la lettre A s'il passe une fois, et une seule, sur chacun de ces ponts; mais s'il est parti d'une autre région, la lettre A ne sera répétée que deux fois. De même, lorsque six ponts aboutissent à la région A, la notation du parcours renfermera quatre fois ou trois fois la lettre A, suivant que le départ s'est effectué de la région A ou d'une autre. En général, lorsque le nombre des ponts d'une rive est pair {région paire), la notation correspondante renferme la lettre de cette région un nombre de fois égal à la moitié du nombre des ponts, si le départ s'est établi
Deuxième récréation.
d'une autre région, et à ce nombre augmenté de l'unité, si le commencement du voyage a eu lieu dans cette région.
i3° Mais il est évident que, dans le parcours complet, on ne peut partir que d'une seule région; par conséquent je prendrai toujours pour le nombre des répétitions d'une lettre la moitié du nombre des ponts pour une région paire, et la moitié du nombre des ponts augmenté d'une unité, si la région est impaire. Nous aurons alors deux cas à considérer, suivant que le départ s'effectue d'une région impaire ou d'une région paire.
Dans le premier cas, le problème sera impossible si le nombre total des répétitions des lettres ne surpasse pas d'une unité le nombre total des ponts. Dans le cas de départ d'une région paire, le problème sera impossible, si le nombre total des répétitions des lettres n'égale pas le nombre des ponts; car, en commençant par une région paire, on devra augmenter d'une unité pour cette région, et pour celle-là seulement, le nombre des répétitions de la lettre correspondante.
4" Considérons donc une disposition quelconque des ponts et des îles d'un fleuve. Pour savoir si le parcours complet de tous les ponts n'est pas impossible à priori^ on opère de la manière suivante : i° On désigne chacune des régions séparées les unes des autres par les lettres A, B, C, D; 2° on prend le nombre de tous les ponts, et on le place en tête du tableau de calcul que nous allons indiquer; 3° on écrit dans une colonne verticale chacune des lettres A, B, C, D, et dans une seconde colonne, le nombre des ponts qui aboutissent à ces différentes régions; 4° on
Le jeu des ponts et des îles.
marque d'un astérisque les régions paires, c'est-à-dire celles auxquelles aboutissent des ponts en nombre pair; 5° on écrit dans une troisième colonne verticale les moitiés des nombres pairs, et les moitiés dts nombres impairs, augmentés d'une unité, de la colonne précédente; 6° on fait la somme de tous les nombres de cette dernière colonne. Lorsque cette somme est égale au nombre de tous les ponts ou lui est supérieure d'une unité, le passage complet peut être effectué, sinon le problème est impossible. Mais il faut observer que, dans le premier cas, le départ doit commencer par une région paire, marquée d'un astérisque; dans le second cas, le départ doit s'effectuer d'une région non marquée d'astérisque, ou impaire. Ainsi l'on a, pour le le problème de Kœnigsberg :
Nombre des ponts : 7.
TOTAT
Comme le total est plus grand que 8 ou 7 -^ i, le problème est impossible.
iS" Considérons la disposition formée par deux îles A et B, réunies entre elles et aux rives d'un fleuve par quinze ponts, ainsi que l'indique la fig. 2. On demande si l'on peut voyager de manière à passer sur tous les ponts, sans jamais repasser
Deuxième récréation.
sur l'un deux. D'abord, je désigne les six re'gions par les
Fig. 2.
lettres A, B, C, D, E, F; puis je construis le tableau d'après les explications données ci-dessus :
Nombre des ponts : i5.
fi
Total
i6 Dans cet exemple, le problème est possible, pourvu que l'on
Le jeu des ponts et des îles.
parte de la région D, et alors on arrive à la région E, ou inversement; le parcours pourra s'effectuer ainsi :
EaFbBcFdAeFfC^AhCiDkAmEnApBqElD,
ou dans l'ordre inverse; dans cette notation, nous avons intercalé entre les lettres majuscules, qui indiquent les régions, les lettres minuscules qui désignent les quinze ponts.
i6° En dehors de la méthode précédente, pour juger de l'impossibilité, nous indiquerons un moyen plus simple et plus expéditif. Nous observerons d'abord que la somme des nombres de la seconde colonne verticale du tableau est exactement égale au double du nombre des ponts ; cela tient à ce que nous avons compté chaque pont deux fois, puisque par chacune de ses extrémités il aboutit à deux régions distinctes.
17° Il résulte évidemment de cette remarque, que la somme des nombres renfermés dans la seconde colonne verticale est un nombre pair, puisque sa moitié représente le nombre des ponts.
Par conséquent, il n'est pas possible que le nombre des régions impaires soit un, trois, cinq, etc. ; ainsi dans tous les tableaux de calcul, la seconde colonne renferme toujours un nombre pair de nombres impairs; en d'autres termes, le nombre des régions impaires est nécessairement zéro ou un nombre pair. C'est, en particulier, ce que nous avons trouvé pour le problème de Kœnigsberg, et aussi pour le problème du n° i5.
18° Il ressort de ces conF'dérations que le problème n'est pas impossible si toutes les régions sont paires. Alors tous les nombres de la seconde colonne verticale sont pairs, et le total des
32 Deuxième récréation.
nombres de la troisième colonne est égal au nombre des ponts ; et l'on verra que le problème est toujours possible en prenant pourpoint de départ uns région quelconque.
Ainsi, dans l'exemple de Kœnigsberg, on pourrait franchir tous les ponts par deux fois ; par exemple :
ababcdcde ff g g e.
En effet, chaque pont est dédoublé, et toutes les régions deviennent paires (^).
19° Supposons encore qu'il y aitdeux régions impaires, toutes les autres étant paires; dans ce cas, la somme des nombres de la troisième colonne surpasse d'une unité le nombre des ponts; on s'assurera encore que le problème est possible, à la condition de prendre pour point de départ ou d'arrivée Tune ou l'autre des deux régions impaires. On voit encore que si le nombre des régions impaires était de quatre^ six, huit, la somme des nombres de la troisième colonne surpasserait de deux, trois, quatre unités le nombre total des ponts ; par conséquent le problème serait impossible.
20" En résumé, étant donnée une disposition quelconque, il sera facile de savoir s'il est possible de franchir, une seule fois, tous les ponts. Le problème est impossible, lorsqu'il y a plus de deux régions impaires; il est possible : 1° lorsque toutes les régions sont paires, et alors le point de départ peut se faire arbitrairement d'une région quelconque; 2° lorsqu'il n'y a que deux régions impaires, et alors le parcours commence par l'une de celles-ci et finit par l'autre, ou inversement.
(*) Ce raisonnement s'applique évidemment à une distribution quelconque des pontset des îles dans les bras d'un fleuve, à la condition de passer deux fois sur chaque pont.
Le jeu des ponts et des îles. 33
21° Lorsque l'on a conclu à la possibilité du problème, il reste à résoudre la question de savoir comment on doit diriger sa course; à cet effet, je me sers de la règle suivante : a On supprime par la pensée, autant de fois qu'on le peut, les couples de ponts qui conduisent d'une région dans une autre; de cette manière, le nombre des ponts est considérablement diminué; on cherche ensuite la course à effectuer avec le reste des ponts. Cela fait, on rétablit les ponts supprimés, ce qui devient très facile avec un peu d'attention. Aussi je ne crois pas qu'il soit nécessaire d'en dire davantage sur la loi de formation des parcours. »
Ici se termine le Mémoire d'Euler. Cet illustre géomètre n'a traité pour ainsi dire que la question d'impossibilité. On trouvera dans la Note 11^ placée à la fin du volume, la théorie de la possibilité, que l'on doit considérer comme la suite du Mémoire qui précède.
