Is it possible?

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.

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

I’ve seen this puzzle before and solved.It involves a bunch of long twisting lines.

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.

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…

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.

Doh. I forgot to connect the middle house.
|…/…|
[H] [H] [H]
|…|./…|
[W] [G] [E]
|…/.|

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.

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.

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

Here’s a similar problem:
http://www.drmath.com/dr.math/faq/faq.3utilities.html
It goes through and explains everything very well.

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.

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.

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.