Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: $Revision: 1.6.2.14 $; site uiucdcs.UUCP
Path: utzoo!watmath!clyde!burl!mgnetp!ihnp4!inuxc!pur-ee!uiucdcs!mcewan
From: mcewan@uiucdcs.UUCP
Newsgroups: net.puzzle
Subject: Re: Don't cross my path ! - (nf)
Message-ID: <40700013@uiucdcs.UUCP>
Date: Sun, 26-Aug-84 23:17:00 EDT
Article-I.D.: uiucdcs.40700013
Posted: Sun Aug 26 23:17:00 1984
Date-Received: Wed, 29-Aug-84 05:32:24 EDT
References: <785@abnjh.UUCP>
Lines: 89
Nf-ID: #R:abnjh:-78500:uiucdcs:40700013:000:2611
Nf-From: uiucdcs!mcewan    Aug 26 22:17:00 1984

#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