

nums Veteran user I have a life, or I would have more than 366 Posts 
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 Eternal Order Ossining, NY 26976 Posts 
Okay to do this on the surface of a donut instead of a plane?
...to all the coins I've dropped here

Bong780 Regular user Toronto, Canada 172 Posts 
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 Inner circle Munich, Germany 1390 Posts 
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 Regular user 179 Posts 
No you are wrong it is possible,but how do I draw the answer on this page,mike

Nir Dahan Inner circle Munich, Germany 1390 Posts 
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 Loyal user Asheville NC 225 Posts 
Make one of the houses solar powered.

alekz New user Munich, Germany 86 Posts 
Quote:
On 20040319 10:37, funemagic wrote: 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? 
Jonathan Townsend Eternal Order Ossining, NY 26976 Posts 
Anyone got a citation for the proof?
Is it a graph theory thing?
...to all the coins I've dropped here

funemagic Loyal user Asheville NC 225 Posts 
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 New user Munich, Germany 86 Posts 
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 
Mushu Loyal user 253 Posts 
Quote:
On 20040322 14:31, Jonathan Townsend wrote: http://www.cuttheknot.org/do_you_know/3Utilities.shtml 
Jonathan Townsend Eternal Order Ossining, NY 26976 Posts 
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 © 20012019 Steve Brooks. All Rights Reserved. This page was created in 0.2 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 < 