Le défi d’Euler

En 1736, le mathématicien Suisse Leonhard Euler voyage à Königsberg (Kaliningrad aujourd’hui). La ville s’organise alors en 4 parties qui s’étendent de part et d’autre de la rivière Pregolia et sur l’île Kneiphof. Sept ponts relient les différentes parties de la ville entres elles. On met au défi Euler de trouver un circuit permettant d’emprunter 1 fois chaque pont et de revenir au point de départ.

Transposons ce défi à la géographie parisienne. Les îles de la Cité et Saint-Louis sont reliées au continent (les rives droite et gauche de la Seine) par 14 ponts auxquels s’ajoutent un 15ème pont entre les 2 îles. Arriverez-vous à créer ce même circuit qui passe par les 15 ponts et revient au point de départ ?

Pour résoudre plus facilement ce défi, il peut être utile de faire abstraction de la géographie et de créer un schéma de 4 points (les rives droite et gauche et les 2 îles) et relier ces points par des traits représentants les ponts.

Trouver une solution à ce défi revient alors à réussir à dessiner ce schéma sans lever son crayon. Ne vous acharnez pas trop longtemps, il n’existe pas de solutions ni pour Paris, ni pour Königsberg.

En terme mathématique, on appelle graphe le schéma créé précédemment, et le graphe est dit Eulerien si il existe un circuit fermé permettant de passer par tous les tronçons. Il a été démontré que pour qu’un graphe soit Eulerien, il faut que chaque sommet du graphe soit connecté à un nombre pair d’arêtes. Dans notre cas, il aurait fallu que des 4 parties de la ville partent un nombre pair de pont. Ce qui n’est pas le cas.

1 pont entre l’île de la Cité et l’île Saint-Louis

2 ponts entre l'île Saint-Louis et la rive gauche

3 ponts entre l’île Saint-Louis et la rive droite

4 ponts entre l’île de la Cité et la rive droite

5 ponts entre l’île de la Cité et la rive gauche