É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 : Georges Perec, Je me souviens, (réédition de 1998) Souvenir , Mathématiquement, l'assertion de Georges Perec n'est pas totalement exacte : si les trois énoncés sont élémentaires, et si la résolution de l'énigme des ponts de Königsberg est facile, celle de l'article l'est déjà moins et celle des quatre couleurs ne l'est plus du tout. De plus, sur un tore ou un ruban de Möbius, des surfaces de dimension deux, une solution existe..

Cette énigme est déjà posée par Henry Dudeney en 1917 dans son livre . Il précise qu'. Celle de l'article en est une, qu'il appelle eau, gaz, et électricité. Elle a été popularisée par Martin Gardner, qui la présente dans son Sixième livre de jeux mathématiques (1971) M. Gardner, The Sixth Book of Mathematical Games from Scientific American, University of Chicago Press, 1984 , .

Il existe deux approches pour démontrer l'inexistence d'une solution connectant chacune des trois maisons 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.

Énoncés

Sous la forme d'historiette, l'énigme s'exprime de la manière suivanteOn trouve cette anecdote dans . :

L'historiette possède de nombreuses variantesCette version possède l'avantage d'interdire la solution illustrée droite. C'est une solution où la canalisation alimentant en gaz la maison 2 traverse la maison 3. En mathématique, elle n'est pas acceptable, car aucun lien ne relie le nœud de la maison 2 au nœud du fournisseur gaz. Sous la forme de l'énigme, elle ne l'est généralement pas non plus, même si certains sites populaires comme Trois maisons sur Pedagonet l'acceptent.. On trouve par exemple celle-ci : Cette citation est extraite du site www.mathsaharry.com, énigme par Math au matou..

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. 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é Km, n. Un graphe dans lequel deux liens ne se croisent pas est appelé planaire. La question devient : K3,3 est-il un graphe planaire ?

Topologie géométrique Préambule

Une première démarche, pour élucider l'énigme, consiste à faire des essais. Elle débouche sur un double constat. Rapidement, celui qui cherche à résoudre l'énigme y arrive presque, c'est-à-dire qu'il parvient à poser huit canalisations, mais la dernière résiste. Le deuxième constat est qu'il existe beaucoup de possibilités différentes à tester.

Intuitivement, il semble évident que certaines d'entre elles sont équivalentes. Deux tentatives telles qu'il est possible de déformer continument les canalisations pour passer de la première à la seconde correspondent en fait à la même tentative. Cette équivalence porte un nom en mathématique, elle s'appelle l'homotopie. Il s'avère que cette notion, difficile à formaliser précisément, n'est guère nécessaire pour résoudre l'énigmeLa démonstration usuelle n'en fait pas usage (voir ).. Malgré cette remarque, il reste encore une grande quantité de tentatives possibles. La canalisation reliant la première maison au gaz (en suivant l'ordre proposé dans l'illustration du paragraphe Énoncés) peut passer entre l'eau et l'électricité, mais aussi passer entre la première maison et le fournisseur d'eau, ou encore passer par en dessous et contourner par le bas les deuxième et troisième maisons.

Un rapide examen permet de conclure qu'il existe une infinité de possibilités. La canalisation qui relie la première maison et l'électricité peut commencer par faire n fois le tour des trois maisons puis rejoindre l'électricité. Ces n tours n'offrent aucun espoir de solution, mais, au premier regard, il ne semble pas simple de trouver un bon critère permettant d'éliminer les tentatives inutiles, ce qui rend l'énigme un peu déroutante. Passer en revue une infinité de possibilités n'est guère praticableIl existe deux manières de définir l'homotopie dans le cas de l'article. On peut appliquer le concept aux chemins, deux chemins sont homotopes si l'on peut continument déformer le premier pour le superposer au second. On peut aussi appliquer le concept au graphe, ce qui revient à pouvoir aussi déplacer continument les points du graphe. La convention choisie dans ce paragraphe est de n'appliquer l'homotopie qu'aux chemins. Sinon, il n'existe qu'un nombre fini de graphes homotopes..

Toutes les tentatives de cette nature débouchent au mieux par la pose de huit canalisations, puis il devient impossible d'aller plus loin. Ce point commun peut laisser penser que la bonne démarche consiste à procéder d'un raisonnement différent. Cette bonne démarche se fonde sur un concept et un théorème suffisamment intuitif pour qu'une démonstration ne soit pas jugée envisageableC'est le mathématicien Bernard Bolzano qui se pose le premier la question : J. Sebestik, Logique et mathématique chez Bernard Bolzano, Vrin, 2002 , . avant le . Une réflexion plus approfondie montre qu'il n'en est rien et qu'ils suffisent à bâtir une preuve aisément compréhensible de l'inexistence d'une solution.

Ensemble connexe par arcs

Le concept clé de la démonstration est la connexité. Une illustration du concept est donnée par l'archipel des Canaries dans l'image ci-contre. Une île est connexe par arcs, c'est-à-dire que pour tout couple de points de l'île, il existe un chemin allant d'un point à l'autre sans quitter l'île. En revanche, la réunion de deux îles n'est pas connexe par arcs : il n'existe pas de chemins permettant de se rendre entre deux points sans se mouiller, s'ils sont sur deux îles différentes. Une île est une composante connexe par arcs : c'est un ensemble maximal de points entre lesquels il existe un chemin. Un archipel consiste ainsi en plusieurs composantes connexes par arcs, soit 5 dans l'image ci-contre.

En termes mathématiques, si A est un ensemble muni d'une topologie et si, pour deux points quelconque de A, il existe un chemin dans A qui relie les deux points, A est dit connexe par arcs.

Un second concept est celui de frontière. Sur l'exemple de l'archipel, la frontière correspond au littoral, c'est-à-dire à l'ensemble des points qui touchent en même temps une île et la mer. En termes plus mathématiques, un point est à la frontière d'un ensemble E lorsqu'un disque centré en ce point et de rayon strictement positif, touche à la fois l'ensemble E et son complémentaire.

Théorème de Jordan

Le théorème clé de la démonstration est encore plus déroutant de simplicité apparente. En substance, il indique qu'il n'est pas possible d'aller de la Suisse à la France sans traverser la frontière. Pour l'énoncer en termes plus mathématiques, un peu de vocabulaire n'est pas inutile.

Pour établir la démonstration, il faut introduire la notion de courbe de Jordan, aussi appelée lacet simple. Cette courbe est une ligne continue dans le plan, qui ne se croise pas. Dans la figure de droite, la frontière en noir est un exemple d'une courbe de Jordan. Un cercle est aussi une courbe de Jordan, puisqu'il s'agit toujours d'une ligne continue sans croisement. En revanche, un 8 ne l'est pas puisqu'il y a croisement au centre du 8.

Le théorème de Jordan traite du complémentaire d'une courbe de Jordan S. Le théorème considère la partie du plan qui ne contient pas S. Il indique que ce complémentaire contient deux composantes connexes par arcs, dont la frontière est la courbe S. Sur l'exemple ci-contre, une composante est en bleu tandis que l'autre est en rouge, et la frontière est en noir. Bien que le résultat semble intuitivement évident, sa démonstration ne l'est pas. En effet, il a fallu plus d'un demi-siècle pour l'obtenir. L'élément clé du théorème réside dans la définition de connexité de la section précédente : considérons un point a dans la zone bleue et un point b dans la rouge. Si l'on souhaite se rendre de a à b, il est nécessaire de sortir de la zone bleue, et une frontière est traversée. De même façon, la France peut correspondre à une composante connexe par arcs, la Suisse à une autre, et il n'est pas possible d'aller d'une ville en Suisse à une ville en France sans traverser la frontière. Raisonner en termes de composantes connexes par arcs et de frontière, ou encore d'îles et de littoral permet d'éviter la complexité combinatoire.

Placement des six premières canalisations

Poser une canalisation revient à interdire une zone de l'espace. Si un jeu de canalisation forme une boucle, les idées précédentes sont applicables. On peut, en dessinant la solution sur une feuille de papier, découper les deux zones séparées, bien les éloigner et tenter de résoudre l'énigme sur les différentes îles ainsi obtenues.

Le principe du raisonnement est par l'absurde. On suppose qu'il existe une solution, on montre que cette existence contredit le théorème de Jordan. On en déduit qu'elle ne peut exister car le théorème de Jordan n'est jamais contredit. On utilise les notations suivantes : M1, M2, M3 désignent les trois maisons, F1 le fournisseur d'eau, F2 celui d'électricité et F3 celui de gaz.

Le premier objectif consiste à séparer l'espace en deux composantes connexes par arcs, c'est-à-dire à créer deux îles distinctes. Comme on suppose qu'une solution existe, il est possible de considérer la canalisation reliant M1 à F1, à laquelle on adjoint celle reliant F1 à M2, à laquelle on adjoint celle reliant M2 à F2, adjointe à F2 à M3, puis M3 à F3, puis F3 à M1. Elles sont illustrées sur la figure de gauche. On obtient une courbe de Jordan contenant, dans l'ordre, les points M1, F1, M2, F2, M3, F3 puis à nouveau M1. Si rien ne nous assure que la configuration solution de l'énigme (que l'on suppose exister) est effectivement celle de gauche, nous savons au moins une chose : ces canalisations forment une courbe de Jordan contenant dans l'ordre précédent, les trois maisons et les trois fournisseurs.

Cette courbe divise le plan en deux composantes connexes par arcs, que l'on peut considérer comme deux îles éloignées. Chacune de ces deux composantes connexes par arcs possède une frontière contenant toutes les maisons et tous les fournisseurs. Chacune de ces deux composantes connexes par arcs est analogue à la figure de droite. Analogue signifie ici que les ensembles sont connexes par arcs et de même frontière.