Solution sought!
Frank A. Scafidi
I am trying to solve a very old challenging puzzle.
You have three houses and three utilities water, gas, and electric:
/\ /\ /\
|H1| |H2| |H3|
|--| |--| |--|
o o o
Gas Water Electric
Now the object is to draw a line from each utility to each house.
Rules:
1.) The puzzle is in two dimentions only.
2.) You cannot connect the houses in series, e.g. run the electric
to one house then from that house to the next house etc, not allowed.
3.) You cannot bury the lines or run them overhead, remember only
two dimentions.
If anyone gets a solution for this puzzle please let me know!!!
Frank A. Scafidi Work: 215-898-6002 Home: 215-492-1062
Email: fsca...@heartland.bradley.edu
Thanks,
Good Luck!!!!
--
s
s
s
s
Thomas Magliery
>I am trying to solve a very old challenging puzzle.
>You have three houses and three utilities water, gas, and electric:
*Sigh*. Every time I see one of these, I work just a little more on
the FAQ. It really is coming soon...
mag
P.S.: No solution. Refer to any graph theory text for a proof that
the complete bipartite graph K3,3 is nonplanar.
--
Tom Magliery ** Dept of CS ** 1304 W Springfield ** Urbana IL 61801 ** USA
Jonathan Haas
}
}I am trying to solve a very old challenging puzzle.
}
}You have three houses and three utilities water, gas, and electric:
}
} |H1| |H2| |H3|
} |--| |--| |--|
}
} o o o
} Gas Water Electric
}
}Now the object is to draw a line from each utility to each house.
}
}Rules:
}
}1.) The puzzle is in two dimentions only.
}
}2.) You cannot connect the houses in series, e.g. run the electric
} to one house then from that house to the next house etc, not allowed.
}
}3.) You cannot bury the lines or run them overhead, remember only
} two dimentions.
Yes, this is a very old puzzle... and an insolvable one. I don't remember
the proof... does anyone else?
--
__/\__ Jonathan S. Haas | Jake liked his women the way he liked
\ / University of Michigan | his kiwi fruit: sweet yet tart, firm-
/_ _\ posi...@eecs.umich.edu | fleshed yet yielding to the touch, and
\/ Finger for PGP 2.2 key | covered with short brown fuzzy hair.
W Darren Prouty
There is absolutely no way to solve the problem except
to break the rules which cannot be broken.
I have tried it hundreds of times, probably more,
over the last few years (on and of, not straight)
and despite the fact that I know it's impossible,
I still think (stupidly) that maybe I'll find an
answer - but I haven't yet.
-W.D.
(funny little quote to come soon...)
Chris Cole
>
>I am trying to solve a very old challenging puzzle.
>
>You have three houses and three utilities water, gas, and electric:
>
> /\ /\ /\
> |H1| |H2| |H3|
> |--| |--| |--|
>
> o o o
> Gas Water Electric
>
>Now the object is to draw a line from each utility to each house.
>
>Rules:
>
>1.) The puzzle is in two dimentions only.
>
>2.) You cannot connect the houses in series, e.g. run the electric
> to one house then from that house to the next house etc, not allowed.
>
>3.) You cannot bury the lines or run them overhead, remember only
> two dimentions.
********
geometry/K3,3.s
********
The problem you describe is to draw a bipartite graph of 3 nodes connected
in all ways to 3 nodes, all embedded in the plane. The graph is called K3,3.
A famous theorem of Kuratowsky says that all graphs can be embedded
in the plane, EXCEPT those containing K3,3 or K5 (the complete graph
on 5 vertices, i.e., the graph with 5 nodes and 10 edges) as a
subgraph. So your problem is a minimal example of a graph that
cannot be embedded in the plane.
The proofs that K5 and K3,3 are non-planar are really quite easy, and only
depend on Euler's Theorem that F-E+V=2 for a planar graph.
For K3,3 V is 6 and E is 9, so F would have to be 5. But each face has at
least 4 edges, so E >= (F*4)/2 = 10, contradiction.
For K5 V is 5 and E is 10, so F = 7. In this case each face has at least 3
edges, so E >= (F*3)/2 = 10.5, contradiction.
The difficult part of Kuratowsky is the proof in the other direction!
A quick, informal proof by contradiction without assuming Euler's Theorem:
Using a map in which the houses are 1, 2, and 3 and the utilities are
A, B, and C, there must be continuous lines that connect the buildings and
divide the area into three sections bounded by the loops A-1-B-2-A,
A-1-B-3-A, and A-2-B-3-A. (One of the areas is the infinite plane *around*
whichever loop is the outer edge of the network.) C must be in one of these
three areas; whichever area it is in, either 1, or 2, or 3, is *not* part of
the loop that rings its area and hence is inaccessible to C.
The usual quibble is to solve the puzzle by running one of the pipes
underneath one of houses on its way to another house; the puzzle's
instructions forbid crossing other *pipes*, but not crossing other *houses*.
******************************
To request a copy of the index to the Archive, send a letter to
archive...@questrel.com
containing the line:
send index
The index will be mailed via return email to the address in your
request's "From:" line. If you are unsure of this address, and cannot
edit this line, then include in your message BEFORE the first "send" line
the line:
return_address <your_return_email_address>
The Archive has been posted to news.answers. News.answers is archived
in the periodic posting archive on rtfm.mit.edu. Postings are located
in the anonymous ftp directory /pub/usenet/news.answers, and are
archived by "Archive-name". Other subdirectories of /pub/usenet
contain periodic postings that may not appear in news.answers.
Other news.answers archives are:
ftp.cs.ruu.nl [131.211.80.17] in the anonymous ftp
directory /pub/NEWS.ANSWERS (also accessible via mail
server requests to mail-...@cs.ruu.nl)
cnam.cnam.fr [192.33.159.6] in the anonymous ftp directory /pub/FAQ
ftp.uu.net [137.39.1.9 or 192.48.96.9] in the anonymous ftp
directory /usenet
ftp.win.tue.nl [131.155.70.100] in the anonymous ftp directory
/pub/usenet/news.answers
grasp1.univ-lyon1.fr [134.214.100.25] in the anonymous ftp
directory /pub/faq (also accessible via mail server
requests to list...@grasp1.univ-lyon1.fr), which is
best used by EASInet sites and sites in France that do
not have better connectivity to cnam.cnam.fr (e.g.
Lyon, Grenoble)
Note that the periodic posting archives on rtfm.mit.edu are also
accessible via Prospero and WAIS (the database name is "usenet" on port
210).