Énigme des trois maisons

Les deux canalisations sont équivalentes.

Le nombre de combinaisons à tester n'est pas fini.

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'énigme[7]. 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 praticable[Note 3].

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 envisageable[8] avant le XIX^e siècle. 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.

Un archipel forme un ensemble non connexe par arc. Il n'est pas possible d'aller à pied sec d'une île à l'autre. Chaque île est une composante connexe par arc.

Le concept clé de la démonstration est la connexité. Une illustration du concept est donné 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.

La courbe de Jordan (en noir) divise le plan en deux régions : un « intérieur » (en bleu) et un « extérieur » (en rose).

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.

Le théorème de Jordan est utilisable pour résoudre l'énigme de l'article.

En termes de connexité et de frontière, les deux composantes connexes par arcs du plan sont analogues à la figure.

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 : M₁, M₂, M₃ désignent les trois maisons, F₁ le fournisseur d'eau, F₂ celui d'électricité et F₃ 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 M₁ à F₁, à laquelle on adjoint celle reliant F₁ à M₂, à laquelle on adjoint celle reliant M₂ à F₂, adjointe à F₂ à M₃, puis M₃ à F₃, puis F₃ à M₁. Elles sont illustrées sur la figure de gauche. On obtient une courbe de Jordan contenant, dans l'ordre, les points M₁, F₁, M₂, F₂, M₃, F₃ puis à nouveau M₁. 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.

Si le résultat ne semble pas choquant pour la composante bleue, il peut paraître plus surprenant pour la rose. La composante rose correspond plus à un continent infiniment vaste percé par une mer intérieure qu'à une île. Comme les deux éléments clés sont la connexité et la frontière, cela n'a guère d'importance. Pour s'en persuader, on peut imaginer cette transformation du plan appelée inversion, qui laisse invariant le cercle, transforme l'intérieur en extérieur et vice-versa. Cette transformation ne traite pas le centre du cercle. Mais, pour l'énigme, ajouter un point isolé ne change rien quant à l'existence ou non d'une solution. Il est aisé de le contourner, par la droite ou la gauche. Une autre manière de voir les choses est d'imaginer résoudre l'énigme sur la sphère et non pas le plan. En plaçant la courbe de Jordan sur l'équateur, la similitude entre les deux îles devient évidente. La figure en bas à droite montre qu'une sphère sans son pôle nord peut être vue, à l'aide d'une projection stéréographique, comme un plan. Les deux énigmes sur un plan ou une sphère sont donc équivalentes.

Après avoir posé la huitième canalisation, le plan est divisé en quatre composantes connexes par arcs.

À partir de maintenant, la pose de toute nouvelle canalisation se traduit par un coup de ciseau qui engendre une nouvelle île. Cette fragmentation de l'espace est à l'origine de l'impossibilité. L'intérêt d'une telle démarche est qu'elle évite toute combinatoire. Comme le montre le paragraphe précédent, prise dans le bon ordre, les six premières poses sont, d'un certain point de vue, forcées. Quelle que soit la manière dont on s'y prend, la pose des six premières canalisations débouche toujours sur la même configuration topologique. À condition de décomposer l'espace en îles telles que le littoral contiennent les nœuds (maisons et fournisseurs), il est possible de se limiter à l'étude d'une unique configuration, pour la suite du raisonnement.

La canalisation fournissant en électricité la première maison est dans l'une des deux composantes connexes par arcs du paragraphe précédent. Notons là A. Cette composante A contient une ligne reliant M₁ à F₂, située à l'intérieur de A composée de points soit tous roses soit tous bleus, mais jamais vert. On obtient une nouvelle courbe de Jordan composée de la ligne M₁F₂, puis des lignes F₂M₃F₃M₁. Finalement, on obtient la ligne M₁F₂M₃F₃M₁. Elle définit une nouvelle composante connexe par arcs, notée A₁. On peut se demander si cette nouvelle île contient les points F₁ et M₂. On sait déjà qu'ils ne sont pas sur la ligne F₂M₃F₃M₁. Ils ne peuvent pas non plus se situer sur la ligne M₁F₂ car cette ligne se situe à l'intérieur de A, c'est-à-dire dans l'île A et non pas sur le littoral, or les points F₁ et M₂ ne sont pas situés sur l'île à proprement parler mais sur la frontière. La même raison indique qu'ils ne peuvent pas non plus se situer à l'intérieur de A₁. On obtient de même une île A₂, dont la frontière est formée des canalisations reliant : M₁F₁M₂F₂M₁. Le théorème de Jordan nous assure encore que ces deux zones sont bien des îles distinctes, c'est-à-dire des composantes connexes par arcs disjointes.

L'espace est maintenant fragmenté en trois îles, dont deux ne contiennent plus que quatre nœuds. Posons maintenant la canalisation qui relie la deuxième maison au gaz. Elle est située dans l'une des trois composantes connexes par arcs. Cette composante connexe par arcs possède une frontière contenant à la fois M₂ et F₃. Ni A₁ ni A₂ ne possède cette propriété. C'est donc la composante connexe par arcs qui n'a pas été découpée par la canalisation reliant M₁ à F₂ qui contient cette canalisation. Une fois encore, avec le point de vue adopté, le coup est forcé. Si l'on note B₁ et B₂ ces deux nouvelles composantes connexes par arcs, elles ont toutes deux comme frontière une courbe de Jordan et leurs frontières passent, pour B₁ par les points M₁F₁M₂F₃M₁ et pour B₂ par M₂F₂M₃F₃M₂.

L'espace est maintenant fragmenté en quatre îles, les fournisseurs et les maisons se trouvent toutes sur le littoral et aucune île n'en contient plus de quatre. De plus, on connaît, pour chaque île la nature exacte des fournisseurs et des maisons présentes sur le littoral. Il s'agit maintenant de relier la troisième maison à l'eau. Un rapide passage en revue des différentes frontières montre qu'aucune d'elles ne contient à la fois la troisième maison M₃ et l'eau F₁.

Cette dernière canalisation parcourt au moins deux composantes connexes par arcs (c'est-à-dire passe d'une île à l'autre sans passer par la mer). Ce résultat est en contradiction avec le théorème de Jordan. Elle termine la démonstration par l'absurde[9].

Sur un ruban de Möbius, une solution existe.

L'impossibilité de résoudre l'énigme est une conséquence du théorème de Jordan. Une géométrie pour laquelle une solution existe doit donc admettre des courbes de Jordan qui ne divisent pas l'espace en deux composantes connexes par arcs. Comme le montre le paragraphe intitulé Topologie géométrique, la recherche d'une solution sur une sphère est vaine, une méthode rapide pour s'en convaincre est de remarquer que le théorème de Jordan est valide sur cette géométrie.

En revanche, le théorème ne s'applique pas si l'espace n'est pas orientable. Dans un espace non orientable, le côté droit de certaines courbes finit par devenir le côté gauche. Autrement dit, le concept de droite et de gauche n'a pas de sens sur un tel espace. Tel est le cas sur un ruban de Möbius[14]. La ligne à égale distance des deux bords possède cette propriété. Placer les trois maisons et les trois fournisseurs sur une telle ligne, à l'image de la figure de gauche, est judicieux[Note 5]. Les six premières canalisations n'ont alors pas coupé la géométrie en deux composantes connexes par arcs.

Pour comprendre ce qu'il advient une fois ces six premières canalisations posées, le plus simple est de construire un ruban de Möbius, de dessiner les différents nœuds et de couper effectivement le ruban. On obtient la figure en haut à droite (on n'a pas représenté la double torsion induite par le découpage dans la mesure où celle-ci ne change pas la résolution de l'énigme). Le ruban devient un unique nouveau ruban, deux fois plus long et deux fois moins large. Une des frontières du ruban contient maintenant deux séries des six nœuds à la suite l'une de l'autre.

Pour une raison de simplicité, il est plus simple de déformer le cylindre obtenu. On resserre la frontière ne contenant pas les nœuds jusqu'à ce que cette frontière soit réduite à un point, on ajoute alors ce point (on a vu précédemment que cela ne change rien à la résolution de l'énigme) pour obtenir un cône. Aplatir ce cône, ce qui ne change encore rien à l'existence ou l'absence de solution, donne la figure en bas à droite[Note 6]. Il devient aisé de trouver comment placer les trois dernières canalisations. La solution en bas à droite est celle qui est illustrée à gauche, une fois réalisées les transformations inverses[15].

Le tore ne vérifie pas le théorème de Jordan. La courbe de Jordan verte ne divise pas le tore en deux composantes connexes par arcs.

Le ruban de Möbius est un exemple de surface qui ne satisfait pas le théorème de Jordan car il n'est pas orientable. D'autres surfaces sont orientables et ne satisfont néanmoins pas le théorème. C'est le cas du tore. Il existe cette fois, non pas un, mais deux types de courbes de Jordan dont le complémentaire est connexe par arcs. Pour cette raison, il est possible de résoudre l'énigme[16], même avec quatre maisons et quatre fournisseurs. Le fait de considérer une géométrie contenant un trou, comme le tore autorise la représentation de graphe non planaire. Tout graphe se représente sur une surface ayant un nombre de trous, encore appelé genre de la surface[17], suffisamment élevé. Sur une telle surface, et à condition de s'y prendre convenablement, il existe deux courbes de Jordan qui ne créent pas de nouvelles faces, l'équation d'Euler s'écrit alors n - a + f = 0. S'il existe quatre maisons et quatre fournisseurs, le graphe est composée de huit nœuds et seize arêtes, ce qui implique l'existence de huit faces. Le nombre moyen d'arêtes par face est le double du nombre d'arêtes, on trouve donc comme valeur moyenne quatre. Comme c'est aussi le nombre minimal d'arêtes pour une face, la solution ne comporte que des faces à quatre arêtes.

La première courbe de Jordan est illustrée sur la figure en haut à gauche. Comme pour le ruban de Möbius, on obtient un cylindre, illustré à droite. Cette fois-ci, les nœuds ne se trouvent pas tous en haut mais une série est sur la frontière haute et une sur la frontière basse. La technique précédente, pour transformer le cylindre en disque reviendrait à identifier les différents nœuds en un unique point, ce qui n'est pas acceptable. En revanche, il est possible d'établir un lien entre le nœud M₁ situé en bas (avec les notations précédentes M₁ correspond à la première maison. Les maisons sont illustrées en bleu sur les figures) et le nœud F₂ (qui désigne le deuxième fournisseur. Les fournisseurs sont illustrés en rouge sur les figures). Ce lien est illustré en vert sur la figure en haut à droite. On obtient alors une figure comparable à un disque. Ce disque, illustré en bas à droite, comporte dix-huit nœuds. Chaque nœud est représenté deux fois, à l'exception des nœuds M₁ et F₁ qui le sont trois fois. La zone supérieure est représentée en gris clair et celle inférieure en gris foncé. Sous cette forme de disque, trouver la bonne configuration est aisée[17].

On peut se demander si une solution existe pour cinq fournisseurs et cinq maisons. Le même calcul montre que le nombre moyen d'arêtes par face est égal à dix tiers, soit strictement inférieur à quatre. Or quatre est le minimum d'arêtes pour construire une face pour cette énigme. La recherche d'une solution est donc vaine.

Construction de la solution

Un raisonnement simple permet de déterminer la bonne configuration et sans tâtonnement. La première courbe de Jordan fournit huit liens. Le neuvième lien transforme la question en un problème plan. Il reste encore sept liens à placer et l'on sait déjà que chaque face (c'est-à-dire chaque composante connexe par arcs du complémentaire) est bordée par exactement quatre liens.

Sous sa forme de disque, on dispose de dix-huit nœuds, qui sont des répétitions des huit nœuds présents sous la forme du tore. Ils sont répétés deux fois, à l'exception des nœuds M₁ et F₂ qui sont répétés trois fois. Sous la forme du disque, l'ajout d'un lien, pour créer des faces contenant quatre liens, se traduit par la pose d'une canalisation qui saute deux nœuds pour se connecter au suivant. Comme, in fine, ce sont les seuls faces qui existent, il est inutile de rechercher d'autres types de pose de canalisation. Placer un lien rend alors inaccessible, sous la forme du disque, les deux nœuds qu'il enserre.

• Liens dix à douze :

Les nœuds M₁ et F₂ disposent de deux spécificités, non seulement ils sont présents trois fois sous la forme de disque, mais, sous la forme torique, ils disposent déjà de trois liens sur quatre. Il est possible, sans dommage, d'enserrer par au moins deux liens ces deux nœuds. Il en restera toujours une instance pour fournir les liens encore manquants. Il existe sur le disque deux séries de nœuds M₁ et F₂ adjacents. Celle du haut sur la figure représentant le disque avec les dix-huit nœuds conduit à la création d'un lien M₂F₁ inutile car déjà existant. Celle du bas permet de créer le lien manquant M₄F₃, c'est celui-ci qu'il faut choisir pour dixième lien.

Les nœuds M₄ et F₃ sont maintenant présents deux fois sur le disque et disposent de trois liens sur quatre dans le tore. On peut donc enserrer une instance de chacun de ces deux nœuds M₄ et F₃ sans dommage. Il est encore possible d'enserrer une instance des nœuds M₁ et F₂ car il reste deux instances disponibles alors qu'un unique lien est manquant pour chacun de ces deux nœuds. On en déduit les deux autres liens, illustrés sur le disque à dix-huit nœuds, en vert. Ce sont les liens onze et douze.

• Quatre derniers liens

Pour y voir plus clair, le plus simple est de dessiner ce qu'il reste de la plus grande composante connexe par arcs après la pose des douze premières canalisations, illustrée sur la figure de droite. Chaque nœud (vu du point de vue du tore) dispose maintenant de trois liens et il ne manque plus qu'un lien par nœud, or quatre nœuds sont encore représentés deux fois : F₁, M₂, F₃ et M₄. Ce sont donc ces liens qu'il faut enserrer. Il existe deux manières d'enserrer les liens F₁ et M₂. Les deux débouchent chacune sur une solution acceptable. On choisit de poser la canalisation M₁F₃ en haut à droite, qui devient à treizième. Il n'existe alors plus qu'une solution pour enserrer les liens F₃M₄, la quatorzième canalisation relie M₃ à F₁. Les deux dernières sont évidentes et illustrées sur la figure de droite.

Pour obtenir le tore à partir des figures, il suffit de coller l'arête inférieure du rectangle sur son arête supérieure, puis de coller l'arête de droite, qui est devenue un cercle sur celle de gauche. Les côtés supérieurs et inférieurs du deuxième tore correspondent au cercle de plus petit diamètre du tore.

Il reste encore à remonter la solution sur le tore. La convention choisie consiste à représenter un côté de la première courbe de Jordan en gris foncé et l'autre en gris clair. Les canalisations qui restent proches de la première courbe de Jordan restent sur la même couleur, les autres sont celles qui font le tour du tore, à l'image de la neuvième canalisation. On obtient la première figure de gauche.

Cette solution n'est encore guère satisfaisante pour comprendre véritablement comment s'organisent les canalisations sur le tore. La représentation géométrique est plus simple en positionnant les nœuds de manière plus géométrique. Posons le tore à plat sur un plan horizontal. Sur le cercle de plus haute altitude, plaçons 4 nœuds sur deux diagonales orthogonales, de manière qu'une diagonale supporte deux maisons et l'autre deux fournisseurs. Le cercle correspond aux quatre premières canalisations. Sur le cercle de plus basse altitude, on agit de même, puis on pivote les quatre nouveaux nœuds d'un quart de tour, le cercle de basse altitude correspond à quatre canalisations supplémentaires. En reliant par l'intérieur un nœud au nœud situé exactement au-dessous, on obtient encore quatre canalisations. Pour les quatre dernières, imaginons que les canalisations soient élastiques, on relie, à l'aide de quatre canalisations les quatre nœuds supérieurs aux quatre nœuds inférieurs en passant par l'extérieur, puis une rotation d'un demi-tour est appliquée aux extrémités inférieures des quatre derniers nœuds. Cette configuration est représentée sur la figure la plus basse. Les huit faces, seize arêtes et huit nœuds sont plus aisément visibles. Les huit liens sombres correspondent à la première courbe de Jordan.

• T. Chomette, Graphes planaires, cultureMATH (lire en ligne [PDF])
• (en) J. L. Gross et T. W. Tucker, Topological Graph Theory, Courier Dover Publications, 2001 (ISBN 978-048641741-7).
• J.-C. Novelli, Quand les chemins ne se croisent pas, Les Graphes, de la théorie des jeux à l'intelligence artificielle (Bases pour terminale ES. Approfondissements), numéro hors série du journal Tangente, 2002 (ISBN 978-290973785-0).

• Théorème de Kuratowski (caractérisant les graphes planaires)
• Théorème de Robertson-Seymour (une vaste généralisation du théorème précédent)

• (en) Eric W. Weisstein, « Utility Graph », sur MathWorld