Énigme des trois maisons

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 : . Cette énigme est déjà posée par Henry Dudeney en 1917 dans son livre Amusements in mathematics. Il précise qu'. Celle de l'article en est une, qu'il appelle eau, gaz, et électricité. Elle est popularisée par Martin Gardner, qui la présente dans son Sixième livre de jeux mathématiques. Il existe deux approches pour démontrer l'inexistence d'une solution connectant chacune des trois maison directement aux trois fournisseurs. La première approche montrant l'impossibilité 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, due à Kazimierz Kuratowski. Sous la forme d'historiette, l'énigme s'exprime de la manière suivante : L'historiette possède de nombreuses variantes. On trouve par exemple celle-ci : . Ce problème peut 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 ou sommets, dont certains sont reliés par des liens (également appelés arêtes). Dans le cas de l'énigme, il existe deux ensembles de 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 qu'il existe un lien entre chaque nœud de M et chaque nœud 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.