Une énigme à prouver impossible

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

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

Imod

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

Eléa a écrit:Imod : Ah bon ? Et comment tu fais ?

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

Imod

:ptdr:
Mais ca marche pas...

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.

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

ffpower a écrit: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.

Je veux dire:la preuve est simple?

ffpower a écrit: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.

ffpower a écrit::ptdr:
Mais ca marche pas...

Tu veux dire sur la terre ou dans un plan ?

Imod