verma@ucla-cs.UUCP (02/04/86)
In article <1146@ecsvax.UUCP> hal@ecsvax.UUCP writes: > >Here is a diagram consisting of five squares, two on top and three on >bottom. It has been divided into 16 lines, which I have numbered as >shown: > I've added labels to each box. > > _____1____________2____ > | | | > 3| a 4| b 5| > |___6____7__|__8_____9__| > | | | | >10| c 11| d 12| e 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. The answer -- There is no way to do this. Proof - This problem is isomorphic to Euler's bridge broblem. Each box is just an island, and the outside is just one bank (there is only one bank here). Each line is just a bridge, and the 'line' to be drawn is just a Eulerian walk. Now this can be solved by looking at the multi-graph with nodes {a,b,c,d,e,f} (where the letters a-e correspond to boxex, and f is the outside), and the edges corresponding to the lines. That is edge #1 is (a,f), #2 is (b,f), #3 is (a,f), #4 is (a,b), et cetera. Now Euler has this theorem which says that a multi-graph can be traversed, visiting each edge only once iff there are at most two nodes with an odd degree. (The degree of a node is the number of edges incident to it.) The degree of node a is 5, b is 5, c is 4, d is 5, e is 4, f is 9. Clearly there are more then two nodes with odd degree. Thus there is no solution. TS Verma