| Property |
Value |
| dbo:abstract
|
- 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 Henry Dudeney en 1917 dans son livre Amusements in mathematics. Il précise qu'« il existe une demi-douzaine d'énigmes vieilles comme le monde, qui réapparaissent perpétuellement ». 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. (fr)
- 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 Henry Dudeney en 1917 dans son livre Amusements in mathematics. Il précise qu'« il existe une demi-douzaine d'énigmes vieilles comme le monde, qui réapparaissent perpétuellement ». 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. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 39942 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:contenu
|
- 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 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 M1 et F2 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 M1 et F2 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 M1 et F2 adjacents. Celle du haut sur la figure représentant le disque avec les dix-huit nœuds conduit à la création d'un lien M2F1 inutile car déjà existant. Celle du bas permet de créer le lien manquant M4F3, c'est celui-ci qu'il faut choisir pour dixième lien.
:Les nœuds M4 et F3 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 M4 et F3 sans dommage. Il est encore possible d'enserrer une instance des nœuds M1 et F2 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
right|200px
: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 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 : F1, M2, F3 et M4. Ce sont donc ces liens qu'il faut enserrer. Il existe deux manières d'enserrer les liens F1 et M2. Les deux débouchent chacune sur une solution acceptable. On choisit de poser la canalisation M1F3 en haut à droite, qui devient à treizième. Il n'existe alors plus qu'une solution pour enserrer les liens F3M4, la quatorzième canalisation relie M3 à F1. Les deux dernières sont évidentes et illustrées sur la figure de droite.
thumb|400px|left|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. (fr)
- 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 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 M1 et F2 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 M1 et F2 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 M1 et F2 adjacents. Celle du haut sur la figure représentant le disque avec les dix-huit nœuds conduit à la création d'un lien M2F1 inutile car déjà existant. Celle du bas permet de créer le lien manquant M4F3, c'est celui-ci qu'il faut choisir pour dixième lien.
:Les nœuds M4 et F3 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 M4 et F3 sans dommage. Il est encore possible d'enserrer une instance des nœuds M1 et F2 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
right|200px
: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 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 : F1, M2, F3 et M4. Ce sont donc ces liens qu'il faut enserrer. Il existe deux manières d'enserrer les liens F1 et M2. Les deux débouchent chacune sur une solution acceptable. On choisit de poser la canalisation M1F3 en haut à droite, qui devient à treizième. Il n'existe alors plus qu'une solution pour enserrer les liens F3M4, la quatorzième canalisation relie M3 à F1. Les deux dernières sont évidentes et illustrées sur la figure de droite.
thumb|400px|left|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. (fr)
|
| prop-fr:formatÉlectronique
| |
| prop-fr:nom
|
- Chomette (fr)
- Chomette (fr)
|
| prop-fr:nomUrl
|
- UtilityGraph (fr)
- UtilityGraph (fr)
|
| prop-fr:prénom
| |
| prop-fr:titre
|
- Construction de la solution (fr)
- Graphes planaires (fr)
- Utility Graph (fr)
- Construction de la solution (fr)
- Graphes planaires (fr)
- Utility Graph (fr)
|
| prop-fr:url
| |
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- cultureMATH (fr)
- cultureMATH (fr)
|
| dct:subject
| |
| rdfs:comment
|
- 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) ». (fr)
- 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) ». (fr)
|
| rdfs:label
|
- Problema das três casas (pt)
- Problema de los tres servicios (es)
- Énigme des trois maisons (fr)
- Вода, газ та електрика (uk)
- Домики и колодцы (ru)
- 三間小屋問題 (zh)
- Problema das três casas (pt)
- Problema de los tres servicios (es)
- Énigme des trois maisons (fr)
- Вода, газ та електрика (uk)
- Домики и колодцы (ru)
- 三間小屋問題 (zh)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is prop-fr:renomméPour
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.svg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.svg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
.jpg){kind=link}
