L'énigme des 3 maisons...

[CDavid2005]

Salut à tous,

Voici une énigme qui, je pense, doit être assez connue :

Voici 3 maisons et 3 bornes - eau, gaz et électricité. Chacune des trois maisons doit être alimentée sachant que les liaisons ne peuvent se croiser ou passer par une autre maison. Il doit donc y avoir 3 départs à chaque bornes et 3 arrivées à chaque maison. La vue subjective des croisements à éviter se place vue de haut en projection verticale. Ce qui suppose une solution en 2D et non pas en 3D.

Ma question n'est pas de résoudre ce problème mais plutôt de démontrer sa faisabilité ou son impossibilité. Ce qui implique, toutefois, de chercher la solution. Avez-vous une idée ?
-----

[inviteee57e7e1]

Il me semble que c'est impossible;
idée de démo:

On appelle les maisons M1, M2, M3, et les bornes B1, B2, B3.

Il est toujours possible de relier (pas forcément par des droites !) chacune des maisons à B1 et B2.
On le fait.
Cette étape ne restreint pas la généralité de l'étude car elle est nécessaire à la construction finale.

Supposons maintenant que l'aire B1-M1-B2-M3 est plus grande que les aires B1-M1-B2-M2 et B1-M2-B2-M3, où les aires sont celles des surfaces délimitées par les reliements de l'étape précédente.
C'est possible, car une des 3 aires est forcément plus grande (c'est alors la somme des deux autres); les maisons (et les bornes) étant identiques et indifférenciées, ça ne restreint pas la généralité du problème.

On a alors 2 cas possibles:

- B3 se trouve à l'extérieur de B1-M1-B2-M3: alors M2 est isolée;

- B3 se trouve à l'intérieur de B1-M1-B2-M3: alors B3 est isolée;

dans les 2 cas, on a impossibilité de la construction graphique voulue.

J'espère ne pas m'être trompé...


Notons au passage que si on n'est dans aucun des 2 cas, i.e. si B3 est sur une des lignes de raccords B1-M2 ou B2-M2, alors c'est possible; mais j'ai écarté la possibilité de faire passer les raccords sur des points remarquables (autres que leurs extrêmités).

[invite8ef897e4]

Bonjour

J'espère ne pas m'être trompé...

Un raisonnement geometrique direct est possible, utilisant le lemme de Jordan. Une autre possibilite de demonstration simple utilise la caracteristique d'Euler-Poincare des polyedres, appliquee ici au graph plan.

Le probleme est bien connu et beaucoup de demonstrations existent a plusieurs niveaux. Il s'agit du graph biparti complet a 6 sommets, egalement connu sous le sigle , qui n'est pas planaire. N'importe quel graph peut etre rendu planaire, a moins d'avoir comme sous graphe (la clique a 5 sommets) ou .

Je trouve la demonstration geometrique directe avec le lemme de Jordan moins elegante qu'avec la caracteristique d'Euler-Poincare. Ce jugement de valeur parfaitement subjectif, je crois, me viens de ce que le lemme de Jordan necessite plus de developpements que je considere comme formels et/ou calculatoires, alors que l'approche topologique m'est plus intuitive. Je repete, c'est parfaitement subjectif

[CDavid2005]

J'ai fait une petite recherche sur internet sur les graphes planaires et j'ai pu trouver cette documentation au format PDF avec la démonstration du problème....

Je dois dire, il est vrai, que la démonstration à l'aide des graphes planaires est assez élégantes....

[A voir en vidéo sur Futura]

[invite19431173]

CDavid2005 : quelle est la source STP ?

[piwi]

Une longue "étude" (je ne suis pas mathématicien donc le développement m'impressionne. Je mets des guillemets car je ne sais pas juger la rigueur de la chose. Elle me semble sérieuse pourtant) réalisée par homotopie et mmy:
http://forums.futura-sciences.com/sh...hlight=maisons (ca part doucement au début de la discussion mais ensuite ca décolle)

Cordialement,
piwi

[CDavid2005]

Trouvé avec Google..... lien direct vers le PDF. J'ai effectué une recherche sur "Graphes Planaires". Il me semble qu'il s'agit d'une université appelé DMA 'Département de Mathématique et Application"

[invite1defc0d3]

Bonjour je recherche désespérément ou je pourrai envoyer la réponse a la question officiel qui a été posé dans une conférence, si vous connaisser le nom de celui qui la poser ou même juste le nom exacte de cette conférence cela m'aiderait beaucoup pour y envoyer la réponse.

SVP: N'effacer pas mon message comme sur les autres forum en pensant que c'est impossible la question a belle et bien été officiellement posé et j'ai la réponse officiel.