The Magic Café
Username:
Password:
[ Lost Password ]
  [ Forgot Username ]
The Magic Cafe Forum Index » » Puzzle me this... » » Three houses three utility companies (0 Likes) Printer Friendly Version

nums
View Profile
Veteran user
I have a life, or I would have more than
366 Posts

Profile of nums
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
Jonathan Townsend
View Profile
Eternal Order
Ossining, NY
26869 Posts

Profile of Jonathan Townsend
Okay to do this on the surface of a donut instead of a plane?
...to all the coins I've dropped here
Bong780
View Profile
Regular user
Toronto, Canada
172 Posts

Profile of Bong780
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.
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
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.
mike paris
View Profile
Regular user
179 Posts

Profile of mike paris
No you are wrong it is possible,but how do I draw the answer on this page,mike
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
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
funemagic
View Profile
Loyal user
Asheville NC
221 Posts

Profile of funemagic
Make one of the houses solar powered.
alekz
View Profile
New user
Munich, Germany
86 Posts

Profile of alekz
Quote:
On 2004-03-19 10:37, funemagic wrote:
Make one of the houses solar powered.


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..) Smile

BTW.. another one from Nuernberg here. Small world, isn't it? Smile
Jonathan Townsend
View Profile
Eternal Order
Ossining, NY
26869 Posts

Profile of Jonathan Townsend
Anyone got a citation for the proof?
Is it a graph theory thing?
...to all the coins I've dropped here
funemagic
View Profile
Loyal user
Asheville NC
221 Posts

Profile of funemagic
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.
alekz
View Profile
New user
Munich, Germany
86 Posts

Profile of alekz
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 Smile

Greets,
Alex
Mushu
View Profile
Loyal user
253 Posts

Profile of Mushu
Quote:
On 2004-03-22 14:31, Jonathan Townsend wrote:
Anyone got a citation for the proof?
Is it a graph theory thing?


http://www.cut-the-knot.org/do_you_know/3Utilities.shtml
Jonathan Townsend
View Profile
Eternal Order
Ossining, NY
26869 Posts

Profile of Jonathan Townsend
The idea to apply Euler's equation for edges and faces and vertices eluded me. Thanks!
...to all the coins I've dropped here
The Magic Cafe Forum Index » » Puzzle me this... » » Three houses three utility companies (0 Likes)
[ Top of Page ]
All content & postings Copyright © 2001-2019 Steve Brooks. All Rights Reserved.
This page was created in 0.13 seconds requiring 5 database queries.
The views and comments expressed on The Magic Café
are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic.
> Privacy Statement <

ROTFL Billions and billions served! ROTFL