Énigme des trois maisons - Définition

Introduction

Résoudre l'énigme consiste à relier chacune des trois maisons du bas à chaque usine du haut par un chemin. Cette illustration est l'œuvre de Henry Dudeney qui présente cette énigme en 1917 dans son livre Amusements in mathematics.

L'énigme des trois maisons, aussi appelée l'énigme de l'eau, du gaz et de l'électricité, est un jeu mathématique dont l'analyse utilise un théorème de topologie ou de théorie des graphes. Ce problème n'a pas de solution. Georges Perec le cite en 1978 dans son livre Je me souviens : « Je me souviens des heures que j'ai passées, en classe de troisième, je crois, à essayer d'alimenter en eau, gaz et électricité, trois maisons, sans que les tuyaux se croisent (il n'y a pas de solution tant que l'on reste dans un espace à deux dimensions ; c'est l'un des exemples élémentaires de la topologie, comme les ponts de Königsberg, ou le coloriage des cartes) ».

Cette énigme est déjà posée par H. E. Dudeney en 1917 dans son livre Amusements in mathematics. Il précise qu'« il existe une demi-douzaine d'énigmes aussi vieilles que les collines, qui réapparaissent perpétuellement ». Celle de l'article en est une, qu'il appelle eau, gaz, et électricité. Elle est popularisée par M. Gardner, qui la présente dans ses Six livres de jeux mathématiques.

Il existe deux approches pour démontrer l'inexistence d'une solution. La première utilise le théorème de Jordan, indiquant que si l'on dessine une boucle dans un plan, le complémentaire de la boucle, c'est-à-dire la partie non dessinée du plan, se compose de deux connexes par arcs, l'un borné (l'intérieur de la boucle) et l'autre non (l'extérieur de la boucle). La seconde approche, plus générale, utilise la formule d'Euler pour les graphes planaires. Elle est une étape dans la démonstration du théorème clé des graphes planaires, dit de Kuratowski.

Énoncés

Cette solution n'est pas acceptable la canalisation orange en croise une autre.

Sous la forme d'historiette, l'énigme s'exprime de la manière suivante :

« Un lotissement de trois maisons doit être équipé d'eau, de gaz et d'électricité. La règlementation interdit de croiser les canalisations pour des raisons de sécurité. Comment faut-il faire ? »

L'historiette possède de nombreuses variantes ; on trouve par exemple celle-ci : « Il possède… 3 voitures, lesquelles doivent pouvoir se garer indifféremment sur les places de parking 1, 2 ou 3… Il voudrait tracer des routes reliant chaque voiture à chacun des emplacements (soit un total de 9 routes distinctes) afin que chaque véhicule puisse se rendre sur n'importe laquelle de ces places, mais, afin d'éviter les collisions, ces chemins ne doivent en aucun cas se couper, ni être confondus (même partiellement). Ces chemins peuvent passer derrière les parkings et les autos, et avoir n'importe quelle forme, mais ne doivent pas traverser les emplacements (ni bien sûr les autres véhicules) ».

Ce problème peut-être aussi être vu de façon abstraite comme un graphe, ce qui permet de l'étudier mathématiquement. Un graphe est composé d'un ensemble de points, appelés nœuds, dont certains sont reliés par des liens. Dans le cas de l'énigme, il existe deux ensembles nœuds : l'ensemble M ayant trois nœuds pour les trois maisons (en bleu dans la figure ci-contre), et l'ensemble F ayant trois nœuds pour l'arrivée de gaz, d'eau et d'électricité (en rouge dans la figure ci-contre). L'énigme demande à ce qu'il existe un lien entre chaque nœud de M et de F, de façon telle que deux liens ne se croisent pas : une façon possible de disposer ces liens est montrée dans la figure ci-contre avec les liens en vert. Un graphe dans lequel tous les nœuds d'un ensemble de m éléments doivent être reliés à ceux d'un ensemble de n élément est appelé graphe biparti complet, noté K_m,n. Un graphe dans lequel deux liens ne se croisent pas est appelé planaire. La question devient : K_3,3 est-il un graphe planaire ?