Enigme des 3 maisons

[inviteb0201e7c]

bonjour, j'ai regardé un ptit coup et normalement cette énigme n'a pas encore été posée.

on a 6 batiments:
- 3 maisons
- 3 services (eau, électricité, gaz)

le but du jeu est de relier chacune des 3 maisons à chacun des 3 services sachant que:
-les maisons et les services sont sur le même plan
-les tuyaux ne doivent jamais se croiser et ne peuvent pas se chevaucher
-on place les maisons et les services ou on veut sur le plan

Bon voila j'espère ne pas avoir dit des bétises dans l'énoncé.

Bonne chance!
-----

[invite8241b23e]

Salut !

De mémoire, c'est une énigme à la conclusion décevante...

[invite284605b7]

Question: les tuyaux sont ils aussi sur le meme plan? (je suppose que oui)

Un tuyau peut-il aller d'un service a une maison, puis continuer vers une autre maison?

[abracadabra75]

Salut !
De mémoire, c'est une énigme à la conclusion décevante...

Bonjour.
Benjy..... tu dépoétises tout!
Comment veux-tu qu' on cherche si tu flingues un sujet, qui serait neuf?
Et puis, le plaisir est dans la recherche, et la conclusion personnelle...
A+

[A voir en vidéo sur Futura]

[piwi]

Le sujet n'est malheureusement pas neuf
On le retrouve facilement avec l'outil de recherche avancé. homotopie c'etait alors fendu d'une longue démonstration.

Cordialement,
piwi

[invite8241b23e]

Le pauvre...

[invite35452583]

Le pauvre...

Il vous en prie.
Maintenant, montrer rigoureusement que c'est impossible même en restreignant les conduites à être des lignes brisées est déjà un beau défi (il est vrai que l'on n'est pas obligé non plus de montrer le théorème de Jordan en toute généralité, du moins en partie, comme je l'avais fait ).

[inviteb0201e7c]

J'ai réussi à trouver une solution, mais dans un cas vraiment particulier...

En fait ca fait 7 ans que je me pose la question alors j'ai vraiment cherché des trucs tirés par les cheveux.

Bon en tout cas ma réponse colle avec les critères dit sur l'énoncé, j'aimerai juste avoir une définition du mot "plan" pour voir si ca colle... puis je vous dit

[yat]

Bon en tout cas ma réponse colle avec les critères dit sur l'énoncé, j'aimerai juste avoir une définition du mot "plan" pour voir si ca colle... puis je vous dit

Il y a des solutions sur un tore et sur une sphère, mais si c'est ça ta question, non, ce n'est pas ça un plan.

[invité576543]

Il y a des solutions sur un tore et sur une sphère, mais si c'est ça ta question, non, ce n'est pas ça un plan.

Bonjour,

Quel est le max de n d'ailleurs? C'est 2 sur le plan. Mais sur le tore? Sur la sphère? Sur le plan projectif? Sur la bande de Moebius? Sur la bouteille de Klein?

J'arrive à 4 facilement sur le plan projectif, mais je ne vois pas immédiatement de solution à 5.

Cordialement,

[inviteb0201e7c]

Bon effectivement c'était sur une tore (je me voyait deja médaille fields pour ma célèbre théorie des donuts )

en tout cas je suis fière d'avoir trouvé une réponse (même fausse) car ca fait des années que j'en cherchait une, je suis fière de moi!!!

au fait, je suis étonné que tu dise que ca marche sur une sphère, je ne me souvient pas d'avoir réussi avec.

En y réfléchissant ma réponse est pas fausse, après tout j'ai juste a changer l'énoncé... a moi le futuroscar de mathématiques!!!

[invité576543]

Bonjour,

Sauf erreur de ma part on arrive à 4 sur le tore, non?

Cordialement,

[invité576543]

Solution 4-4 sur le tore...

Est-ce que le 5-5 est possible?

Cordialement,

[yat]

au fait, je suis étonné que tu dise que ca marche sur une sphère, je ne me souvient pas d'avoir réussi avec.

Euh... en fait, j'ai fait l'essai sur un tore, et la solution s'est déroulée toute seule, j'ai intuité que c'était aussi facile sur une sphère, mais en faisant quelques essais, je n'y arrive pas de manière évidente. Je maintiens donc pour le plan projectif et le tore, mais pour la sphère je ne sais pas.

[yat]

Solution 4-4 sur le tore...

Est-ce que le 5-5 est possible?

Cordialement,

Je ne vois pas encore la pièce jointe, mais effectivement, sur le tore j'ai une solution à 4. A 5 à mon avis ça va commencer à devenir coton.

[invité576543]

Une variante amusante de la solution 4-4 sur le tore, en changeant le pavage! (Il y a un pavage correspondant en parallélogrammes, mais je le vois mieux avec la forme indiquée.)

Cordialement,

[invité576543]

Sur la bande de Möbius, 3-3 est immédiat. 4-4 semble difficile.

Mais je ne vois pas de solution immédiate pour 3-3 sur le cylindre. Dommage, on aurait un début de "pattern"...

Cdlt,

[invite6055d2a6]

De mémoire, c'est une énigme à la conclusion décevante...

Je me souviens avoir passé des heures à faire des essais dans tous les sens lors de mes années collège. La conclusion "standard" est en effet décevante.....
Les solutions un peu exotiques, même si il faut modifier l'énoncé, sont plus stimulantes...

[invité576543]

Je n'arrive pas à trouver de solution 4-4 sur la bouteille de Klein... (Le 3-3 est immédiat, c'est le même que sur Möbius!)

Cordialement,

[invite35452583]

On va éviter d'être rigoureux, les résultats topologiques utilisés ci-après sont intuitivement assez évidents mais très techniques.
Pour la sphère c'est assez facile, on retire un point hors conduites, maisons et compagnies de distributions, on a un plan donc max 2-2.
Pour le tore et les autres, ce n'est pas comme ça qu'on va retourner sur le plan (on complexifie plutot de simplifier). Un peu d'homologie alors ?
Prenons un point d'une surface compacte sans bord.
On considère les composantes connexes de la surface à laquelle on a oté les sommets (maisons, compagnies) et les arêtes (conduites). Celles-ci forment surfaces compactes à bord. Si une d'elles n'est pas homéomorphes à un disque, elle n'est pas simplement connexe, on peut découper un cercle dans la surface et ainsi obtenir une surface plus simple (dans le sens du groupe fondamental) (par exemple : Tore->cylindre, max 3-3 cf ci-après, ou disque, max 2-2).
Si toutes sont des disques on a alors un complexe simplicial homéomorphe à la surface. Et là on utilise :
1) caractéristique d'Euler-Poincaré
2) le bord d'une face a au moins 4 arêtes (maison1-compagnie1-maison1, impossible il n'y a qu'un chemin d'après l'énoncé aussinon on s'y ramène, maison1-compagnie1-maison2-maison1 ça ne va pas non plus.)
Exemple 1 : le tore
5x2=10 sommets
5x5=25 arêtes
caractéristique d'Euler-Poincaré (f-a+s) d'un tore=0 donc 15 faces.
Une arête est arête de deux faces. On a donc 50=25x2 liens arêtes-faces. Mais pour chaque face on a au moins 4 liens arêtes-faces d'où un minimum de 15x4 liens, c'est impossible.
Pour4-4, s=8 a=16 f=8 et chaque face a 4 un bord constitué de 4 arêtes.
Exemple 2 : le cylindre (ce qui finira le tore)
Cette fois on a des composantes connexes qui sont sur un bord qui n'est pas nécessairement constitués d'arêtes formés par des conduites. On les retire ou on constate qu'une amène le cercle bord sur un chemin formé d'arêtes (au moins 4) par déformation continue, ces arêtes n'ont qu'un lien avec les faces limités par des arêtes formées par les conduites. Il en est de même sur l'autre bord. Donc cette fois au plus ax2-4x2 liens arêtes faces. (Une même arête peut donner flanc à deux "non-faces" au total on perd au moins 4x2 liens)
3-3 impossible
s=3x2=6 a=3x3=9 f=3 (caractéristique=0) max liens arêtes-faces 9x2-4x2=10 il en faudrait au moins fx4=12, c'est impossible.
Exemple 3 : la sphère (le retour)
3-3 impossible
caractéristique=2
s=6 a=9 f=5 9x2=18<20=5x4 =>impossible

C'est joli et amusant, non ? je vous laisse trouver des obstructions pour d'autres cas et d'autres surfaces (je crois que ce sont les seules mais je n'en suis pas sûr) On peut évidemment mixer 3-5 possible sur un tore ? (Apriori oui) 4-5, non

[invite35452583]

Exemple 4 : ruban de Moëbius
homotopiquement c'est un cercle caractéristique=0
3-3 s=6 a=9 f=3 bord=1 (contrairement au cylindre)
liens au plus 9x2-4x1=14 besoin en liens pour faces=12
Soit un bord extérieur de 6 arêtes et 4 afces internes avec des bords de 4 arêtes, ou bien bord extérieur de 4 arêtes et 2faces bord à 4 arêtes et une face à bord de 6 arêtes. A priori les deux sont possibles.
3-4 a priori possible s=7 a=12 (max liens=12x4-4x1=20) f=12-7=5 (besoin en liens =5x4=20).

[invité576543]

Très joli et très amusant. Je n'ai pas tout compris (pour le cylindre principalement), mais si j'applique ce que je comprend:

Pour la bouteille de Klein, je fais un trou sur une face, j'obtiens le ruban de Moebius, d'où les mêmes limites exactement.

Est-ce correct?

Et qu'obtient-on en faisant un trou dans le plan projectif?

Cordialement,

[invité576543]

Je ne retrouve ma "solution" 4-4 pour le plan projectif. M'suis gouré...

Dans l'autre sens, la caractéristique semble 1 (le "triangle" a s=3, f=1, a=3, f+s-a=1)

comme on a 2a/f >= 4, on a f+s-a <= s-a/2

Dans le cas 4-4, s=8, a=16, s-a/2 = 0, impossible. Par contre 3-4, s=7, a=12, s-a/2 = 1, ça doit passer...

C'est bien ça?

Cordialement,

[invité576543]

Et qu'obtient-on en faisant un trou dans le plan projectif?

Moebius, d'après le message précédent (mêmes limites!).

Cordialement,

[invite35452583]

Je ne retrouve ma "solution" 4-4 pour le plan projectif. M'suis gouré...

Tu me rassures.

Dans l'autre sens, la caractéristique semble 1 (le "triangle" a s=3, f=1, a=3, f+s-a=1)

Oui, on colle un disque (dimension paire) en faisant deux fois le tour sur un chemin (dimension impaire) dont a collé les deux bouts sur un même point (dim paire). Total paire=2 total impaire=1, différence=1.

comme on a 2a/f >= 4, on a f+s-a <= s-a/2

C'est bien d'avoir une formule plus simple, en effet.

Dans le cas 4-4, s=8, a=16, s-a/2 = 0, impossible. Par contre 3-4, s=7, a=12, s-a/2 = 1, ça doit passer...

C'est bien ça?

Cordialement,

Apparemment tu as tout compris

Quoique

Je n'ai pas tout compris (pour le cylindre principalement)

Quelle partie?

Et qu'obtient-on en faisant un trou dans le plan projectif?
Moebius, d'après le message précédent (mêmes limites!).

Oui, surface à un bord, si on fait un complexe simplicial faire un trou revient à retirer une face donc caractéristique=1-1=0 donc ruban de Moëbius.

Si tu veux diminuer la caractéristique d'Euler-poincaré : les sommes connexes. Tu prends deux tores, tu découpes un disque dans chacun d'eux et tu recolles bord à bord. Caractéristique=-2. (5-5 pas encore s-a/2=10-25/2=-2,5 mais 4-6,3-10,2-x* oui)* OK 2-x pour toute surface
Caractéristique=-4, on refait une somme connexe du précédent avec un autre tore.(5-6 possible)
...

[invité576543]

Pour le cylindre, mon problème est dans la notion de caractéristique. Tu dis à un moment que la caractéristique est 0, ce qui est la même que le tore, et devrait amener à 4-4 possible, ce qui n'est pas le cas

En partant de la sphère, soit les deux trous sont dans la même face, soit dans des faces différentes. J'aurais donc tendance à comprendre que la caractéristique est soit (f+1)+s-a = 2, soit (f+2)+s-a = 2, le premier cas correspondant aux deux trous dans la même face, et le deuxième a des trous dans des faces distinctes. Ca fait comme caractéristique soit 1 soit 0, ce qui rend pas claire l'intérêt de la notion de caractéristique dans le cas du cylindre.

Mais en raisonnant sur les trous comme 1 ou 2 faces, on voit qu'on peut toujours se ramener à la sphère, dont même limite...

Cordialement,

[invite35452583]

En partant de la sphère, soit les deux trous sont dans la même face, soit dans des faces différentes. J'aurais donc tendance à comprendre que la caractéristique est soit (f+1)+s-a = 2, soit (f+2)+s-a = 2, le premier cas correspondant aux deux trous dans la même face, et le deuxième a des trous dans des faces distinctes. Ca fait comme caractéristique soit 1 soit 0, ce qui rend pas claire l'intérêt de la notion de caractéristique dans le cas du cylindre.

Attention et reprenons le trouage de surface.
On fait un trou dans une face qui a un bord formé d'arêtes, ensuite soit en déplaçant proprement ces arêtes on le déplace sur le nouveau bord créé par le trou, soit on écrase la face sur les arêtes (c'est désormais possible grace au trou). on a alors dans les deux cas un squelette (c'est le vrai nom) avec f'=f-1.
Si on troue deux fois la même face on ne peut faire ctte opération qu'une fois.

[invite35452583]

Attention et reprenons le trouage de surface.
On fait un trou dans une face qui a un bord formé d'arêtes, ensuite soit en déplaçant proprement ces arêtes on le déplace sur le nouveau bord créé par le trou, soit on écrase la face sur les arêtes (c'est désormais possible grace au trou). on a alors dans les deux cas un squelette (c'est le vrai nom) avec f'=f-1.
Si on troue deux fois la même face on ne peut faire ctte opération qu'une fois.

Poursuivons, ainsi quand tu fais deux trous dans la même face de la sphère et que tu reprends le suelette tu obtiens encore une fois le disque de caract=1. Pour obtenir un cylindre à partir de la sphère et récupérer un squelette pour ce premier il faut faire 2 trous dans des faces distinctes et caract=0.
Cette caract peut être retrouvé avec 2 triangles formant les bords du cylindre puis on raccorde ces deux triangles avec 3 arêtes et 3 quadrilatères pleins. s=6 a=9 f=3 f-a+s=0.

Maintenant, on peut préférer pour le cylindre de reboucher (attention il faut le prolonger un peu avant car des conduites ou sommets peuvent être sur le bord lui-même, c'est pour cela que j'ai préféré éviter).
C'est l'opération inverse du "trouage" caract augmente de 1. cylindre (carac=0)-on colle un bord->disque (carac=1)-on colle l'autre bord->sphère (carac=2)

Mon argument quand on garde les bords avec le cylindre (on retire 4 liens arêtes-faces revient à recoller un disque donc à augmenter d'une face qui nécessite 4 "liens" mais on ne retire plus 4 liens aux arêtes ce qui revient au même).

En espérant avoir un peu éclairci ce point. (Sinon prends la méthode de recoller, elle convient très bien )

[invite35452583]

Je me souviens avoir passé des heures à faire des essais dans tous les sens lors de mes années collège. La conclusion "standard" est en effet décevante.....
Les solutions un peu exotiques, même si il faut modifier l'énoncé, sont plus stimulantes...

J'espère que c'est désormais moins décevant.

[invité576543]

attention il faut le prolonger un peu avant car des conduites ou sommets peuvent être sur le bord lui-même, c'est pour cela que j'ai préféré éviter

Juste pour virer ce point, prenons le cylindre ouvert, ne contenant pas ses bords. Pour le problème posé ça ne peut que simplifier.

Cette caract peut être retrouvé avec 2 triangles formant les bords du cylindre puis on raccorde ces deux triangles avec 3 arêtes et 3 quadrilatères pleins. s=6 a=9 f=3 f-a+s=0.

Bien d'accord. Même si on refuse les sommets sur le bord, on peut compter comme cela, cela est équivalent à ne compter qu'une face pour un triangle dans le plan. Mais si je prend un bête triangle sur le cylindre, la même "règle" amène à f=1, donc caractéristique 1, non? C'est la notion de face sur les surfaces avec bord qui n'est pas claire pour moi. (Elle n'est pas clair pour moi non plus pour le plan projectif: je vois bien que la caractéristique est 1 en partant d'un octaèdre sur la sphère et en assimilant les éléments opposés, on a alors un "triangle" à quatre faces, chacune à trois arêtes, que je vois bien, s=3, f=4, a=6, soit une caractéristique de 1; mais cela donne une seule face pour le triangle "simple", et là je patine... mais ça doit être parce que je prend le problème de travers!)

Et ça ne répond pas, désolé d'être obtus, à la question de pourquoi, si la caractéritique est 0 pour cylindre, il n'y a pas de solution 4-4 comme il en existe pour le tore, de même caractéristique 0. En d'autres termes, si la caractéristique du cylindre est 0, alors la relation s-a/2 >= c ne s'applique qu'aux surfaces sans bord, et il faut une autre formule pour les surface avec bord, genre s-a/2 >= c+b

Tu aurais une définition claire d'une face d'un graphe sur une surface quelconque? (Sommet et arête ça va à peu près, avec un bémol pour arête, e.g., nécessité d'orienter l'arête dans le plan projectif pour distinguer le triangle à trois arêtes et une face (AB, BC, CA) du triangle à six arêtes et quatre faces (AB, BA, BC, CB, AC, CA)...)

Cordialement,