Titre 2
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)»1,Note 1.
Titre 3
Cette énigme est déjà posée par Henry 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étuellement2». Celle de l'article en est une, qu'il appelle eau, gaz, et électricité2. Elle est popularisée par Martin Gardner, qui la présente dans son Sixième livre de jeux mathématiques3.
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).
Titre 4
La seconde approche, plus générale, utilise la formule d'Euler pour les graphes planaires.
Titre 5
Elle est une étape dans la démonstration du théorème clé des graphes planaires, dû à Kazimierz Kuratowski.
Titre 6
Sous la forme d'historiette, l'énigme s'exprime de la manière suivante4:
«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 faire5?»
L'historiette possède de nombreuses variantesNote 2; 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 chaquevoiture à 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).
- Item 1
- Item 2
- Item 3
- Item 4
- Item 5
- Item 6
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)»6.