Caracolades sur échiquiers

Le 6 avril 2015  - Ecrit par  Patrick Popescu-Pampu Voir les commentaires

Un livre récent de Jacques Sesiano analyse l’article d’Euler consacré à la marche d’un cavalier sur un échiquer. En voici un aperçu.

En 1766 parut [1] un article d’Euler au titre propre à aiguiser la curiosité du lecteur :

« Solution d’une question curieuse qui ne paroit soumise à aucune analyse »

De quoi pouvait-il bien s’agir ? On le découvre dès les premières lignes de l’article :

Je me trouvai dans une compagnie, où, à l’occasion du jeu d’échecs 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.

Pourquoi cela paraît n’être « soumis à aucune analyse » ? Car il faut faire plein d’essais avant d’arriver à une solution et que, si on impose de partir d’une autre case, alors il faut tout recommencer dès le début. À ce sujet, Euler commente :

D’ailleurs une telle recherche ne mérite aucune attention, à moins qu’elle ne soit fondée sur quelques principes ; ou qu’on ne la puisse soumettre à quelque espèce d’Analyse, qui en dirige les opérations.

Le but d’Euler est justement de présenter une telle « espèce d’Analyse » : une méthode pour transformer un parcours incomplet qui ne peut pas se prolonger plus, en des parcours de même longueur, dont certains pourront parfois se prolonger. On rajoute alors autant de sauts de cavalier que l’on peut, et si l’on bloque à nouveau avant d’avoir occupé toutes les cases de l’échiquier, alors on cherche une nouvelle transformation, comme précédemment. On espère bien sûr aboutir ainsi à un parcours complet. Et Euler montre par plusieurs exemples comment cette méthode lui permet de recouvrir de plusieurs manières tout l’échiquier.

Comment transformer un parcours en un autre ?

Supposons que l’on ait un parcours qui passe par les cases $c(1), c(2), ..., c(n).$ Euler explique que, si l’on trouve une case $c(k)$ qui est à un saut de cavalier de la case $c(n)$, alors on obtient un nouveau parcours en suivant le premier parcours de $c(1)$ jusqu’à $c(k)$, puis en sautant directement en $c(n)$, et en continuant sur le premier parcours, mais de la fin vers le début, par les cases $c(n-1), c(n-2), ..., c(k+1).$ Ce parcours est différent du premier si $k < n-1.$ Et il peut être allongé si on peut sauter de la case $c(k+1)$ vers une case encore libre de l’échiquier ...

Euler a été tout particulièrement intéressé par les parcours complets qui se referment sur eux-mêmes. En effet, si on a trouvé un tel parcours, on sait alors en trouver un qui part de n’importe quelle case : il suffit de garder le même cheminement, mais en démarrant de cette case-là.


Dans son livre « Euler et le parcours du cavalier » [2], Jacques Sesiano [3] étudia de manière très détaillée cet article d’Euler, ainsi que le manuscrit [4] qui lui a servi de base.

Le lecteur qui désire se faire d’abord sa propre opinion sur le travail d’Euler peut commencer par lire l’article et le manuscrit d’Euler, puisqu’ils sont repris en facsimilé à la fin de l’ouvrage de Sesiano. Voici par exemple une page du manuscrit, qui illustre le fait qu’Euler étudia le même problème sur d’autres formes d’échiquiers :

Euler examina l’influence de la forme de l’échiquier sur l’existence de solutions
au problème. Par exemple, dans l’article il explique pourquoi :

  • il n’est pas possible de passer par toutes les cases sur un échiquier $4 \times 4$ ;
  • il n’est pas possible de trouver un parcours fermé qui passe par toutes les cases sur un échiquier $5 \times 5$.

Mais avant de lire les explications d’Euler dans l’image qui suit, essayez de démontrer cela vous-mêmes, les raisons en sont simples et jolies !

Un problème relié

Pendant que je rédigeais ce billet, et sans que je lui en ai dit quoi que ce soit, un ami m’a parlé du problème élémentaire suivant :

En chaque case d’un carré $5 \times 5$, se trouve une personne. À un signal, chaque personne saute sur l’une des cases adjacentes (il n’y a donc que deux possibilités pour les personnes situées dans les coins, trois pour les autres personnes situées le long des côtés, et quatre pour celles situées à l’intérieur). Montrer que l’on a nécessairement deux personnes ayant sauté sur la même case.

Le fait d’être en train de rédiger ce billet m’avait mis dans un état d’esprit parfait pour ce problème : je vis en quelques secondes que la raison en était exactement la même que celle de l’impossibilité de trouver un parcours fermé et passant pas toutes les cases sur un échiquier $5 \times 5$ ! Voyez-vous pourquoi ?

Le livre de Sesiano contient aussi une étude des prédécesseurs d’Euler [5]. On y apprend par exemple qu’on trouve dans un manuscrit arabe du XII-ème siècle :

[...] quatre poésies, toutes de la même forme (32 paires de vers), [qui] permettent de reconstituer le parcours. En effet, les deux premières lettres de chaque vers indiquent les coordonnées de la case où doit être inscrit le quantième du vers. [6]

Ce travail d’Euler est considéré parfois comme l’un des articles fondateurs de la théorie des graphes et, par conséquent, de la topologie. Peut-être pour cette raison, le livre contient aussi une analyse détaillée d’un autre article d’Euler qui est jugé fondateur de la topologie, celui sur la relation d’Euler entre nombres de sommets, d’arêtes et de faces d’un polyèdre convexe.


Au fait, pourquoi ai-je choisi de parler de « caracolades » dans le titre de ce billet ? C’est parce que je trouvai la citation suivante [7] dans le livre de Sesiano, extraite de l’édition de 1741 des « Récréations mathématiques » d’Ozanam :

On sait que le Cavalier du jeu des Échecs a une marche toute particulière ; il va, pour ainsi dire, en caracolant, et il passe d’une case d’un rang à une case d’un autre rang en sautant par-dessus deux cases, et allant du blanc au noir et du noir au blanc.

Et vous, pensiez-vous que les cavaliers caracolaient pendant les parties d’échecs ?

Notes

[1Dans les Mémoires de l’Académie Royale des Sciences et Belles-Lettres 15 (1759 [1766]), 310-337. Repris dans Opera omnia I/7, 26-56.

[2L’ouvrage est paru en 2015 aux Presses Polytechniques et Universitaires Romandes.

[3Le lecteur pourra découvrir ici un article de cet auteur sur IdM.

[4Il s’agit du sixième des carnets d’Euler conservé aux Archives de la branche pétersbourgeoise de l’Académie des Sciences de Russie, classé actuellement sous la cote « fonds 136, inventaire 1, numéro 134 ».

[5Le lecteur curieux d’apprendre des résultats plus récents pourra lire cela.

[6Cet extrait provient des pages 158-159 du livre.

[7Cette citation est reproduite à la page 168 du livre de Sesiano. J’en modernise l’orthographe.

Partager cet article

Pour citer cet article :

Patrick Popescu-Pampu — «Caracolades sur échiquiers» — Images des Mathématiques, CNRS, 2015

Crédits image :

Image à la une - La photo du logo provient de Wikimedia Commons. Elle représente un fragment de poterie égyptienne datant de la période 1425-1390 AJC.

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

registros

Cet article fait partie du dossier «Recensions» voir le dossier

Suivre IDM