Topic: Three houses three utility companies
 Message: Posted by: nums (Jan 10, 2004 11:26PM)
My nephew says it is possible, I say not. After years of trying your thoughts or access to solution...the object is to connect each house to each utility without crossing a line, you can go around but do not cross any lines:

HHHH HHHH HHHH
HHHH HHHH HHHH
HHHH HHHH HHHH

GGGG EEEE CCCC
GGGG EEEE CCCC
GGGG EEEE CCCC

Thanks Jeff
 Message: Posted by: Jonathan Townsend (Jan 10, 2004 11:45PM)
Okay to do this on the surface of a donut instead of a plane?
 Message: Posted by: Bong780 (Jan 11, 2004 02:50AM)
I don't think it's possible, also this question bugged me for years. Some people said it's possible but they can't give a solution to it.
 Message: Posted by: Nir Dahan (Jan 11, 2004 05:34AM)
It is actually quite easy to prove it is NOT possible—unless you allow the houses to have some physical size (i.e. not point size). Then one of the lines can go under one of the houses.

N.
 Message: Posted by: mike paris (Mar 18, 2004 02:50PM)
 Message: Posted by: Nir Dahan (Mar 19, 2004 06:24AM)
Given only point size houses and point size utilities. it is NOT possible (it is called a 3,3 graph), given that we assume it is done on a flat page and each line leaves each utility to connect to a house DIRECTLY.
if you need a proof of impossibility I'll either draw it or refer you to an internet link.
if you assume that the houses have some "width" you can experiment a bit and see that there is a solution when one of the lines go under a house.

N
 Message: Posted by: funemagic (Mar 19, 2004 09:37AM)
Make one of the houses solar powered.
 Message: Posted by: alekz (Mar 22, 2004 01:09PM)
[quote]
On 2004-03-19 10:37, funemagic wrote:
Make one of the houses solar powered.
[/quote]

LOL!
Hey, a friend of mine gave me exactly that riddle a week ago at school. You can't imagine how fast history lessons can pass by..
However, I was getting crazy about this, because after about 2 minutes I told him it's impossible, and I KNEW it. (Now I know I don't know..) :)

BTW.. another one from Nuernberg here. Small world, isn't it? :)
 Message: Posted by: Jonathan Townsend (Mar 22, 2004 01:31PM)
Anyone got a citation for the proof?
Is it a graph theory thing?
 Message: Posted by: funemagic (Mar 22, 2004 01:47PM)
It's not possible on a flat sheet of paper in a 2D drawing. It can be done with one sheet of paper but you need to fold a square piece of paper into a cube making a 3D plane to work on. On three sides draw the houses and the remaining 3 sides the utility companies. Now each house can receive 3 utility lines without crossing. A website I found gave a proof why it is not possible on a 2D plane then stated you would either a. draw a line through one of the houses (the directions do not say you can't cross through a house, just can't cross lines) or b. work it out on a 3D plane, thus the paper cube.
 Message: Posted by: alekz (Mar 22, 2004 03:13PM)
I found that one on a german board:

Falls Dich ein (sehr schoener) Beweis dafuer, dass man den Graph nicht zeichnen kann, interessiert, kannst Du ihn z.B. in Aigner/Ziegler: Proofs from the Book, Springer Verlag 2001 I'm Kapitel 10 nachschlagen.

Now for the translation:
If you are interested in a very nice proof, why you can't draw the graph, you may look at Aigner/Ziegler: Proofs from the Book, 2001 in chapter 10.

AFAIK my library doesn't carry english books.. If one of you is interested in this, he can look for that book :)

Greets,
Alex
 Message: Posted by: Mushu (Mar 23, 2004 07:57AM)
[quote]
On 2004-03-22 14:31, Jonathan Townsend wrote:
Anyone got a citation for the proof?
Is it a graph theory thing?
[/quote]

http://www.cut-the-knot.org/do_you_know/3Utilities.shtml
 Message: Posted by: Jonathan Townsend (Mar 23, 2004 09:16AM)
The idea to apply Euler's equation for edges and faces and vertices eluded me. Thanks!