hal@ecsvax.UUCP (02/02/86)
Here's an old one that I have yet to figure out myself. It may not be possible, but if you know the solution, let's see it. 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: _____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. -- "You see, Elvis can't read contracts. All Elvis knows is, no Ferrari, no more rides with the top down." --Sonny Crockett
ark@alice.UucP (Andrew Koenig) (02/02/86)
> _____1____________2____ > | | | > 3| 4| 5| > |___6____7__|__8_____9__| > | | | | > 10| 11| 12| 13| > |______|_________|______| > 14 15 16 The problem as shown has no solution. Consider: if all these cells are to be traversed by a single line, then except for the ends of the line, the line must leave every cell it enters. Thus no more than two cells may have an odd number of entrances, and if exactly two do then the line must begin in one and end in the other. In this diagram, FOUR cells have an odd number of entrances: 1 3 4 6 7 2 4 5 8 9 7 8 12 15 11 1 2 5 13 16 15 14 10 3 (in other words, the outside) Hence, no legitimate solutions.
ewa@sdcc3.UUCP (Eric Anderson) (02/03/86)
In article <1146@ecsvax.UUCP> hal@ecsvax.UUCP writes: >Here's an old one that I have yet to figure out myself. It may not be >possible, but if you know the solution, let's see it. > > _____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. It is impossible to draw such a line. Consider: 1. For each box, the line must 'enter' as many times as it 'leaves', otherwise the line must start/end in that box. 2. It is only possible for a line to enter and leave the same number of times if the box has an even number of 'sides' (numbered lines). 3. Three boxes have five 'sides' each. 4. The line has only two ends. Therefore, it is impossible to draw such a line since one of the large boxes will have a 'side' not crossed by a line. Eric Anderson, UC San Diego {elsewhere}!ihnp4!ucbvax!sdcsvax!sdcc3!ewa Home: (619)453-7315 Work: (619)586-1201 White House: (202)456-1414
bulko@ut-sally.UUCP (Bill Bulko) (02/03/86)
[The postman hits! --More--]
[You have new mail. ]
I remember seeing this puzzle many times. There *is* a solution if you
bend the rules slightly. If you believe that a line passing through the
endpoint of a line segment does NOT cross the segment, then there are
many solutions.
_______________________________________________________________________________
"In the knowledge lies the power." -- Edward A. Feigenbaum
"Knowledge is good." -- Emil Faber
Bill Bulko Department of Computer Sciences
The University of Texas {ihnp4,harvard,gatech,ctvax,seismo}!sally!bulko
_______________________________________________________________________________ins_akaa@jhunix.UUCP (Ken Arromdee) (02/03/86)
It's too easy to prove the problem impossible. There are three boxes with five sides. For a box with five sides, one end of the line must be inside, because otherwise every time your line goes in it also goes out, which can only cross an even number of edges. There are 3 five-sided boxes, requiring 3 ends of the line--obviously im- possible. (Unless you cheat by drawing a line through a corner, or putting the whole figure on a torus). -- "We are going to give a little something, a few little years more, to socialism, because socialism is defunct. It dies all by iself. The bad thing is that socialism, being a victim of its... Did I say socialism?" -Fidel Castro Kenneth Arromdee BITNET: G46I4701 at JHUVM and INS_AKAA at JHUVMS CSNET: ins_akaa@jhunix.CSNET ARPA: ins_akaa%jhunix@hopkins.ARPA UUCP: ...allegra!hopkins!jhunix!ins_akaa
tim@ism780c.UUCP (Tim Smith) (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: > > > _____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. Note that the two top squares each have five lines that must be crossed, as does the bottom middle square. Note also that the when you enter and leave a square, you cross two lines. Thus the only way to cross all the lines on a square with an odd number of lines is to have one of the ends be in that square. Now we have three squares with an odd number, but we only have two endpoints, thus it can't be done. -- Tim Smith sdcrdcf!ism780c!tim || ima!ism780!tim || ihnp4!cithep!tim
ansok@spp3.UUCP (Gary Ansok) (02/04/86)
> _____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. It's impossible. It's related to the famous 'Seven Bridges' problem (you should be able to look this up in most puzzle books). Consider that if we have a region with N boundary lines, and N is odd, then we must either begin or end, but not both, inside that region. If N is even, then we must both begin and end, or neither, inside that region. From this it can be shown that if there are no regions with an odd number of boundary lines, then the problem is solvable with a closed loop. If there are exactly two regions with an odd number of boundary lines, then the problem is solvable with an open curve which must begin and end in those two regions. If there are more than two regions with an odd number of boundary lines, then the problem is not solvable with one curve. In the given problem, we have four regions with an odd number of sides: top left, top right, bottom center (5 each) and the outside (7) -- which must count as a region. Therefore, there is no single curve which will cross all boundary lines.
gwyn@brl-tgr.UUCP (02/04/86)
Since there are three boxes whose sides consist of an odd number of numbered segments, and since a continuous curve has only two ends, the task is impossible. (Of course, if you bend the rules enough, you can cheat.)
bhuber@sjuvax.UUCP (B. Huber) (02/04/86)
In article <1146@ecsvax.UUCP> hal@ecsvax.UUCP writes: > >Here's an old one that I have yet to figure out myself. It may not be >possible, but if you know the solution, let's see it. > >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: > > > _____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. Each time your single line enters a 'room' (or the exterior), it crosses a line. Thus it has either to begin or end in any room whose boundary consists of an odd number of lines. It's easy to find three such 'odd' rooms; the nonsquare ones all have exactly five lines bounding them (the exterior cons- titutes a fourth, actually, having nine lines). Since a continuous curve can have at most two ends, the problem has no solution. Euler solved this one about two hundred years ago. Bill Huber
ray@unlv.UUCP (Ray Tripamer) (02/06/86)
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
mmar@sphinx.UChicago.UUCP (Mitchell Marks) (02/06/86)
--
-- Mitch Marks @ UChicago
...ihnp4!gargoyle!sphinx!mmar