PDA

View Full Version : Is it possible?

Syehoc
02-08-2001, 01:36 PM
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.

dublos
02-08-2001, 02:19 PM
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

fenrir
02-08-2001, 06:49 PM
I've seen this puzzle before and solved.It involves a bunch of long twisting lines.

Cabbage
02-08-2001, 10:25 PM
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.

Syehoc
02-09-2001, 07:12 PM
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...

TheNerd
02-09-2001, 10:05 PM
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.

TheNerd
02-09-2001, 10:09 PM
Doh. I forgot to connect the middle house.

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

Syehoc
02-10-2001, 08:58 PM
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.

TheNerd
02-10-2001, 09:16 PM
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.

Tripler
02-10-2001, 10:08 PM
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

Tripler
Just my \$0.02

Skwerl
02-10-2001, 10:29 PM
Here's a similar problem:
http://www.drmath.com/dr.math/faq/faq.3utilities.html
It goes through and explains everything very well.

Syehoc
02-11-2001, 07:15 AM
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.

PlanMan
02-14-2001, 06:45 PM
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.

bouv
02-14-2001, 07:02 PM
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.