Une énigme à prouver impossible

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Eléa

Voila une énigme que m'a donné mon prof de maths de l'an dernier :

http://nsa01.casimages.com/img/2008...28303212945.jpg

On doit relier chaque maison (M1, M2 et M3) à leur alimentation en eau, gaz et électricité. Seulement aucune liaison ne doit se croiser. (on pense en 2D, en 3D c'est trop facile ^^).

Après avoir cherché toute la journée, le prof nous avait prouvé que cette nigme était impossible à résoudre, mais je ne sais plus comment ^^

Et vous ? Vous savez comment faire ?


Posted by: ffpower

J avais reussi a le "prouver" jadis(manquait p-e un chouia de rigueur).Pour cela je considerais pas les emplacements des differentes ressources comme fixe.c plutot les reliements que je considérer comme fixe.Exemple:une fois qu on a relié le gaz et l electricité a M1 et M2,je considérais que la figure obtenue était un carré(avec gaz et electricité sur 2 sommets opposés,et M1 et M2 sur les 2 autres cotés).Puis je disais que l eau était soit a l interieur soit a l exterieur du carré que je relis a son tour a M1 et M2. Puis je placais M3.Ya alors 3 composantes connexes possible pour placer M3,mais dans les 3 cas,ya une des ressources qui n est pas dans la meme composante connexe.

Bon che pas si j ai reussi a etre clair,et je suis pas sur que ce soit tres rigoureux,mais en tout cas ca avait suffit a l epoque pour me convaincre


Posted by: Imod

Moi je dis que c'est possible en 2D !

Imod

PS : elle n'est pas neuve cette énigme .


Posted by: Eléa

A oui, je crois comprendre ce que tu veux dire ... D'ailleurs je crois que c'est un truc comme ça que mon prof avait fait !

Imod : Ah bon ? Et comment tu fais ?

PS : Je sais qu'elle est pas neuve, mais moi je la connais depuis l'an dernier seulement :P


Posted by: Imod

Citation:
Posté par Eléa
Imod : Ah bon ? Et comment tu fais ?

La terre est ronde et si la dépense ne fait pas peur ....

Imod


Posted by: Eléa

C'est vrai lol ! Mais faut y penser ^^ ! Mais bonne idée !!


Posted by: ffpower


Mais ca marche pas...


Posted by: Patastronch

Sur un tore ca marche.

Pour prouver simplement que c'est impossible avec seulement 2 dimensions, il faut utiliser le théorème de Kuratowski (me demandez pas la preuve de ce théorème, elle doit faire une cinquantaine de pages facile et de toute facon je la connais pas) qui dit en gros qu'un graphe est planaire si il contiens pas de graphe homéomorphe a K3,3 ou K5. Or le graphe demandé par l'énoncé est un K3,3 donc non planaire => problème impossible en 2 dimensions.
On doit pouvoir réussir aussi a prouver que c'est impossible en utilisant le théorème d'Euler sur les graphes, mais autant utiliser Kuratowski qui répond directement a la question.

Par contre le tore crée une dimension fictive par laquelle on peut passer une arrête qui permet de s'en sortir pour résoudre le problème.


Posted by: ffpower

simplement?m a pas l air simple ton theoreme...


Posted by: Patastronch

Citation:
Posté par ffpower
simplement?m a pas l air simple ton theoreme...


Il l'est mais faut savoir ce qu'est un K3,3 et un K5.
Un k5 c est un grpahe complet a 5 sommet.
Un K3,3 c est le graphe demandé par l'ennoncé de ce probleme, c 'est a dire 3 points relié a 3 autres points de maniere complete.
APres homeomorphe ca veut dire "similaire" pour vraiment vulgariser la notion. Donc en gros si t as pas de sous-graphe K3,3 ou de K5 dans ton graphe c'est une condition necessaire et suffisante pour qu'il soit planaire.


Posted by: ffpower

Je veux dire:la preuve est simple?


Posted by: Patastronch

Citation:
Posté par ffpower
Je veux dire:la preuve est simple?

De ce théorème ? Non, j'ai jamais eu le courage de la lire entierement en tous cas, comme je le disais la preuve originale doit faire une cinquantaine de pages facile. Par contre le résultat est assez intuitif quand on a l'habitude de manipuler les graphes.










-