estate@abnjh.UUCP (D.R.Pierce) (08/08/84)
I found this puzzle in an old issue of Science digest, It's one of my favorites. There are 3 men living in 3 seperate houses within a fenced in courtyard. Following a particulary vicious argument over a gardenhose, they made up their minds never to cross each others paths again. This seemed like a good idea at the time (considering the heated debate over gun control :-) ), however, they all had to go to work at the same time of the morning. They settled on this: Each man was to use the gate directly opposing his house, the man living in house A had to exit through gate A, the man living in house B had to exit through gate B, and the man living in house C had to stumble out through gate C (he didn't take well to mornings). I'm not sure if this diagram will be readable on other terminals, so I'll do my best to describe it as well. This is a square courtyard with house A being in a corner, flush against the fence. His exit is diagonally across from his house (in the far corner). Houses B and C are to the right and left of house A set away from the fence (on either arm of the 90 degree angle formed by house A) and their exits are directly across from them. The object is to draw their paths to their respective exits without their paths crossing. ________________________ | A | | |___| ___ | | d | C | | | |___| | | d | | | | ___ | | | B | d B | |___| | | |________________ ___ A C Where d represents the location of the door. (Visions From The Orcrest Stone) Carl D. PS If it turns out to be too easy, I won't post the answer. On the other hand, if it turns out to be too difficult, I might not post them anyway ! Only kidding ! :-)
graham@convex.UUCP (08/16/84)
#R:abnjh:-78500:convex:50900001:000:731
convex!graham Aug 16 10:14:00 1984
There are 3 men living in 3 seperate houses within a fenced in courtyard.
Following a particulary vicious argument over a gardenhose, they made
up their minds never to cross each others paths again. This seemed
like a good idea at the time (considering the heated debate over gun
control :-) ), however, they all had to go to work at the same time of
the morning. They settled on this: ...
This seems to be the same as the three houses, three tanks (water, gas, oil)
problem: run pipes from all tanks to all houses without crossing pipes.
I believe that planar graph theory can be used to show that it is impossible,
though I can't give the proof.
Marv Graham; Convex Computer Corp. {allegra,ihnp4,uiucdcs,ctvax}!convex!grahameklhad@ihnet.UUCP (K. A. Dahlke) (08/17/84)
The three houses / three utilities problem has been around for a while. The three angry workers going to work is isomorphic, and more interesting. Planar graph theory is sufficient. You are looking for Kerotowski's theorem (name probably badly miss-spelled). It states: a graph can be placed in a plane with no crossings if and only if the graph does not contain a K3,3 or a K5. A K3,3 is the houses/utilities construct. A K5 is five points all interconnected. Another impossible puzzle: five homes have telephones with wires directly connecting each house with the other four houses (no crossings of ccourse). This (a K5) can also never be planar. I find the theorem absolutely amazing. A program could take an arbitrary scrawly graph and tell you if it could be put in a plane, just by checking for K3,3 and K5. I don't know if the program could actually rearrange the graph to make it planar. That would be interesting. Someone in the CAD world has probably solved this problem. -- Karl Dahlke ihnp4!ihnet!eklhad
mwm@ea.UUCP (08/18/84)
#R:abnjh:-78500:ea:10200003:000:1345
ea!mwm Aug 17 16:47:00 1984
/***** ea:net.puzzle / convex!graham / 10:14 am Aug 16, 1984 */
This seems to be the same as the three houses, three tanks (water, gas, oil)
problem: run pipes from all tanks to all houses without crossing pipes.
I believe that planar graph theory can be used to show that it is impossible,
though I can't give the proof.
Marv Graham; Convex Computer Corp. {allegra,ihnp4,uiucdcs,ctvax}!convex!graham
/* ---------- */
You are right, and wrong. The 3 houses/3 tanks problem calls for K\-{3,3}
(see below) which is not planar. The proof is to long to post. Try looking
in Harary's _Graph Theory_, under Kuratowski's theorom (pg 108 in my copy).
The graph for the 3 houses/3 doors problem is 3 * K\-2 (see below), which
*is* planar. The solution to the problem is straight forward after you
realize that.
<mike
K\-{3,3} is the complete bigraph on two pairs of 3 points. The \-{3,3} is a
TeX-like notation for subscripting. To see what K\-{3,3} looks like, draw
two lines of three points, about an inch apart. Now, from each point in the
left set of points draw a line to each point in the right set, for a total
of nine lines. Note that you will not be able to draw all nine lines without
one crossing another, unless you have 3d paper.
3 * K\-2 is the three copies of the complete graph on two points. In other
words, three line segments.mcewan@uiucdcs.UUCP (08/27/84)
#R:abnjh:-78500:uiucdcs:40700013:000:2611 uiucdcs!mcewan Aug 26 22:17:00 1984 > You are right, and wrong. The 3 houses/3 tanks problem calls for K\-{3,3} > (see below) which is not planar. The proof is to long to post. Try looking > in Harary's _Graph Theory_, under Kuratowski's theorom (pg 108 in my copy). > The graph for the 3 houses/3 doors problem is 3 * K\-2 (see below), which > *is* planar. The solution to the problem is straight forward after you > realize that. > > <mike > > K\-{3,3} is the complete bigraph on two pairs of 3 points. The \-{3,3} is a > TeX-like notation for subscripting. To see what K\-{3,3} looks like, draw > two lines of three points, about an inch apart. Now, from each point in the > left set of points draw a line to each point in the right set, for a total > of nine lines. Note that you will not be able to draw all nine lines without > one crossing another, unless you have 3d paper. > > 3 * K\-2 is the three copies of the complete graph on two points. In other > words, three line segments. Almost. This would be correct if A weren't in the corner. The set-up looks like this: ________________________ | A | | |___| ___ | | | C | | | |___| | | | | | | ___ | | | B | b | |___| | | |________________ ___ a c Assuming that the men can't climb over the walls, then you have to consider the lines Ac, ca, ab and bA as part of the graph, plus the added restraint that Aa must fall between the square formed by those lines. There are only 3 possibilities for the line Aa, giving: A ------------------------- b |\ | | \ | | \----------------------- a | | | C | | | | B | | | --------------------------- c A ------------------------- b |\ | | \ C | | \ | | \---------------------- a | | | B | | | --------------------------- c or A ------------------------- b |\ | | \ C | | \ | | \ B | | \ | | \-------------------- a | | | | --------------------------- c None of these has a solution. Scott McEwan pur=ee!uiucdcs!mcewan
mcewan@uiucdcs.UUCP (08/27/84)
#R:abnjh:-78500:uiucdcs:40700014:000:2170 uiucdcs!mcewan Aug 26 22:47:00 1984 > You are right, and wrong. The 3 houses/3 tanks problem calls for K\-{3,3} > (see below) which is not planar. The proof is to long to post. Try looking > in Harary's _Graph Theory_, under Kuratowski's theorom (pg 108 in my copy). > The graph for the 3 houses/3 doors problem is 3 * K\-2 (see below), which > *is* planar. The solution to the problem is straight forward after you > realize that. > > <mike > > K\-{3,3} is the complete bigraph on two pairs of 3 points. The \-{3,3} is a > TeX-like notation for subscripting. To see what K\-{3,3} looks like, draw > two lines of three points, about an inch apart. Now, from each point in the > left set of points draw a line to each point in the right set, for a total > of nine lines. Note that you will not be able to draw all nine lines without > one crossing another, unless you have 3d paper. > > 3 * K\-2 is the three copies of the complete graph on two points. In other > words, three line segments. Almost. This would be correct if A weren't in the corner. The set-up looks like this: A ------------------------- b | | | C | | | | a | | | B | | | --------------------------- c Assuming that the men can't climb over the walls, then you have to consider the lines Ac, ca, ab and bA as part of the graph, plus the added restraint that Aa must fall between the square formed by those lines. The solution looks like: A ------------------------- b |\ / | | \ / | | \---------- / | | | / | | -------C | / | | | | / | | | -------- / | | | | / | | | | B-------/ | | | | | | | |-------------------- a | | | | |---------------------\ | | \ | --------------------------- c Scott McEwan pur=ee!uiucdcs!mcewan