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

 nums Veteran user I have a life, or I would have more than 366 Posts Posted: Jan 10, 2004 11:26 pm    0 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 26867 Posts Posted: Jan 10, 2004 11:45 pm    0 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 Posted: Jan 11, 2004 02:50 am    0 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 Posted: Jan 11, 2004 05:34 am    0 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. Adventures in ASIC digital design mike paris Regular user 179 Posts Posted: Mar 18, 2004 02:50 pm    0 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 Posted: Mar 19, 2004 06:24 am    0 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 Adventures in ASIC digital design funemagic Loyal user Asheville NC 221 Posts Posted: Mar 19, 2004 09:37 am    0 Make one of the houses solar powered. alekz New user Munich, Germany 86 Posts Posted: Mar 22, 2004 01:09 pm    0 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..) BTW.. another one from Nuernberg here. Small world, isn't it? Jonathan Townsend Eternal Order Ossining, NY 26867 Posts Posted: Mar 22, 2004 01:31 pm    0 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 221 Posts Posted: Mar 22, 2004 01:47 pm    0 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 Posted: Mar 22, 2004 03:13 pm    0 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 Posted: Mar 23, 2004 07:57 am    0 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 Eternal Order Ossining, NY 26867 Posts Posted: Mar 23, 2004 09:16 am    0 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.12 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 <