Straight Dope Message Board > Main Is it possible?
 User Name Remember Me? Password
 Register FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
02-08-2001, 01:36 PM
 Syehoc Guest Join Date: Feb 2001
I've been bothered with this puzzle since about 9th grade (I'm now in the army) I've tried off and on to figure it out when I was bored and can't seem to come up with a solution.

The object is to get Water [W] Electricity [E] and Gas [G] to each House [H] by drawing a line from and two each one. That means 9 lines all together, none of which can cross or touch. The setup looks like this:

[H] [H] [H]

[W] [G] [E]

Use your imagination or some paper to spread them out a little.

I personally don't think it can be done, but am interested in other opinions.
__________________
··· -·- ---·· ·-· ··-· ·-·· -·--
#2
02-08-2001, 02:19 PM
 dublos Guest Join Date: Nov 2000
Ummm..

Syehoc

Well, A couple quick attemtps seems to leave me consistently with one line that has to cross something.

Is this a puzzle you are sure has a solution?

(I'm assuming there's no limit to the length or curvature of the lines?)

-Doug
#3
02-08-2001, 06:49 PM
 fenrir Guest Join Date: Jun 2000
I've seen this puzzle before and solved.It involves a bunch of long twisting lines.
#4
02-08-2001, 10:25 PM
 Cabbage Guest Join Date: Sep 1999
It's impossible. You can try searching for Kuratowski's theorem, which basically says:

A graph is planar if and only if it doesn't have a piece like the one you just mentioned (the water-light-gas graph, as it's known, or, alternatively, the complete bipartite graph K[3,3]), and if it doesn't have a piece like a pentagon with a pentagram inside it (the complete graph with 5 vertices, K[5]).

In other words, if you've got a bunch of dots, along with some lines connecting some of the dots, can you draw in all of the connections without crossing over any lines? You can, if and only if it doesn't have a piece like the one you're talking about, and it doesn't have a piece like the pentagon with a pentagram inside it.

Let me know if I'm not making any sense here.
__________________
...ebius sig. This is a moebius sig. This is a mo...
(sig line courtesy of WallyM7)
#5
02-09-2001, 07:12 PM
 Syehoc Guest Join Date: Feb 2001
Thanks

I'm not sure that it does have a solution. According to Cabbage (who's input I appreciate by the way) it's not. To answer Dublos's question, there is no limit to the length and curvature of the lines.
Thanks all...
__________________
··· -·- ---·· ·-· ··-· ·-·· -·--
#6
02-09-2001, 10:05 PM
 TheNerd Guest Join Date: Aug 1999
it's not possible with normal planar geometry. However, when someone posed this puzzle to me, I cut the paper and taped it back together in a mobius strip. The solution on that surface is quite elegant.

|...........|
[H] [H] [H]
|....\.|./...|
[W] [G] [E]
|...........|

It's also possible on a torus.
#7
02-09-2001, 10:09 PM
 TheNerd Guest Join Date: Aug 1999
Doh. I forgot to connect the middle house.

|.....\./....|
[H] [H] [H]
|....\.|./...|
[W] [G] [E]
|.\........./.|
#8
02-10-2001, 08:58 PM
 Syehoc Guest Join Date: Feb 2001
hmmm

I guess you went a little over my head, Nerd. I can't figure out exactly how that is a solution. I realize that the detail of your drawing is limited due to this typing program but I still just don't see it. I will continue to look at it though... Thanks though.
__________________
··· -·- ---·· ·-· ··-· ·-·· -·--
#9
02-10-2001, 09:16 PM
 TheNerd Guest Join Date: Aug 1999
Well, imagine that on the surface of a mobius strip. Above and below where the lines don't seem to connect to anything, they were intended to continue on all the way around the strip.
Because there is a half-twist in a mobius strip, those lines are swapped around the middle when they come around once. For example the line above the leftmost house continues around the strip, becoming the line coming up under the electric company. The others are similar.

When I handed a taped together and scrawled on mobius strip to the girl who posed me this riddle, she thought it was pretty neat. Then again, she's a math major.
#10
02-10-2001, 10:08 PM
 Tripler Charter Member Join Date: May 2000 Location: JSOTF SDMB, OL-SLC Posts: 6,725
Damn engineers. . .

What the problem didn't specify is if the sources and houses could be moved. Well, maybe not the houses, but here's my solution
here

Tripler
Just my \$0.02
#11
02-10-2001, 10:29 PM
 Skwerl Guest Join Date: Jul 2000
Here's a similar problem:
http://www.drmath.com/dr.math/faq/faq.3utilities.html
It goes through and explains everything very well.
#12
02-11-2001, 07:15 AM
 Syehoc Guest Join Date: Feb 2001
That definately works, Trpler. It looks like that is really the only way to solve this thing on a two dimensional level. (change the location of the utilities)

I looked at your page, Skwerl. I wouldn't have imagined that there would so much information on this puzzle somewhere on the internet. Thanks.

Thanks everyone, I feel like I have a more extensive knowlege about it now and will start occupying my guard duty hours with something else..Much appreciated.
__________________
··· -·- ---·· ·-· ··-· ·-·· -·--
#13
02-14-2001, 06:45 PM
 PlanMan Guest Join Date: Dec 2000
Can the utilities go underground? The Gas would loop around one end, say Water, then you would have Gas and Water coming in, parallel, from the west, under the Houses, while Electricity came in from the east, either u/g or above. No utility lines cross another.

Or.... you could beam the Electricity via microwaves to each house, no physical Electric lines. But this is kinda hair-splitting. And if one got in the way of the m/w beam, hare splitting.
__________________
"My mind is going ... I can feel it," HAL9000
#14
02-14-2001, 07:02 PM
 bouv Guest Join Date: Aug 2000
Well, if this were any engineering problem I'd have to solve, just do the following.

Send gas, water, and electricity to one house, send it from that house to the other three.

Yes, I know, it's in a series and if one fails they all do, but in real life the lines can cross so it doesn't really matter.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     Straight Dope Chicago     General Questions     Great Debates     Elections     Cafe Society     The Game Room     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit Side Conversations     The Barn House

All times are GMT -5. The time now is 11:47 AM.

 Contact Us - Straight Dope Homepage - Archive - Top

Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

Send questions for Cecil Adams to: cecil@chicagoreader.com