Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.2 6/6/85; site csee-vax.unlv.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!pyramid!hplabs!parcvax!unlv!ray
From: ray@unlv.UUCP (Ray Tripamer)
Newsgroups: net.puzzle
Subject: Re: 5 boxes
Message-ID: <89@csee-vax.unlv.UUCP>
Date: Wed, 5-Feb-86 21:40:27 EST
Article-I.D.: csee-vax.89
Posted: Wed Feb  5 21:40:27 1986
Date-Received: Tue, 11-Feb-86 03:18:00 EST
References: <1146@ecsvax.UUCP>
Reply-To: ray@unlv.UUCP (Ray Tripamer)
Distribution: net
Organization: Unversity of Nevada, Las Vegas
Lines: 38

In article <1146@ecsvax.UUCP> hal@ecsvax.UUCP writes:
			.
			.
			.
>
>
>   _____1____________2____
>  |           |           |
> 3|          4|          5|
>  |___6____7__|__8_____9__|
>  |      |         |      |
>10|    11|       12|    13|
>  |______|_________|______|
>     14       15      16
>
>
>The object is to draw a single line that crosses all of the 16 lines
>in the figure once and only once.  The line may start inside or outside
>the figure, and it may not cross itself.  I suppose the best way to 
>post an answer is to indicate whether the solution starts inside or outside
>the figure, and then list the lines as they are crossed as indicated in
>the figure above.
>
>-- 
This problem is similar to the classic Konigsberg Bridge problem
encountered by Euler, the great mathematician.  It can be shown
using graph theory that this problem indeed has NO solution.

My reference is "Introduction to Discrete Structures" by Preparata and Yeh,
Addison-Wesley, 1973, but I'm sure that any decent discrete structure
book will have this problem explained.

Reply to me directly if you desire more info on the proofs in the pudding :-)
If are there enough responses, I'll post them to the net.
--
Ray Tripamer
!seismo!unrvax!unlv!ray
University of Nevada, Las Vegas