|
|Store|
|
|
|
|
|
|
|
CTK Exchange
KennyJ

guest
|
Jun-17-02, 08:01 PM (EST) |
|
"a rectangle box with segment??"
|
Hey yall.. Can any one figure out this.. You have to draw a line to all the segment without touching it again, or overlap it. Here are the pictures, that some I did and other people did... But this is all wrong.. 



Please help me.. |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
 |
|
 |
|
bluediamond
Member since Apr-9-02
|
Jun-22-02, 10:16 AM (EST) |
 |
4. "RE: a rectangle box with segment??"
In response to message #0
|
Well, it certainly can't be done in a plane. I've seen some tricks to do it involving folding the paper as you draw the line and drawing on the back of the paper. Of course, that's not really helpful mathematically  The proof I was taught involved the T junctions of the figure. Notice that whenever three segments meet in a T intersection, then when you are drawing the figure, one segment must begin or end at that intersection. If you do not start drawing at that point, then when you visit it for the first time, you obviously have to leave that point through a different segment. Thus, you have drawn two of the three segments, and there is only one segment remaining connected to that vertex. Obviously, when you draw that segment, there will be no way to leave that vertex again. For these kinds of problems, it follows that for every intersection of an odd number of segments, you must begin or end drawing a line there. Since the line you are drawing begins and ends somewhere, it can handle only two of the intersections with an odd number of segments. The figure you give has 8 T intersections, so it will take at least four seperate lines to draw. This method can certainly disprove whether you can draw a figure in so many seperate, non-overlapping lines, but I am not sure if it can give the number of lines needed. It gives 4 lines as a floor, but I am not sure if it proves that you can actually draw the figure in 4 lines. It'seems like it'should, so I wonder if any figure can be drawn in so many lines as half the number of intersections with an odd number of segments. Does anyone know any proofs or counterexamples? dave |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
 |
alexb
Charter Member
787 posts |
Jun-22-02, 10:28 AM (EST) |
 |
5. "RE: a rectangle box with segment??"
In response to message #4
|
LAST EDITED ON Jun-22-02 AT 10:29 AM (EST) >Well, it certainly can't be done in a plane. I've seen some >tricks to do it involving folding the paper as you draw the >line and drawing on the back of the paper. Of course, that's >not really helpful mathematically It is in fact, because there's all mathematics one needs to solve that problem. However, the problem itself is a little different from what you discuss. You seem to think that the task is to draw that shape of five rectangles, but it's not. The figure is given. Think of it as a house blueprint with five rooms such that every wall segment has a door. The task is to walk through all the doors, not to draw a blueprint. >The proof I was taught involved the T junctions of the >figure. Notice that whenever three segments meet in a T >intersection, then when you are drawing the figure, one >segment must begin or end at that intersection. If you do >not start drawing at that point, then when you visit it for >the first time, you obviously have to leave that point >through a different segment. Thus, you have drawn two of the >three segments, and there is only one segment remaining >connected to that vertex. Obviously, when you draw that >segment, there will be no way to leave that vertex again. >For these kinds of problems, it follows that for every >intersection of an odd number of segments, you must begin or >end drawing a line there. Since the line you are drawing >begins and ends somewhere, it can handle only two of the >intersections with an odd number of segments. The figure you >give has 8 T intersections, so it will take at least four >seperate lines to draw. > >This method can certainly disprove whether you can draw a >figure in so many seperate, non-overlapping lines, but I am >not sure if it can give the number of lines needed. It gives >4 lines as a floor, but I am not sure if it proves that you >can actually draw the figure in 4 lines. It'seems like it >should, so I wonder if any figure can be drawn in so many >lines as half the number of intersections with an odd number >of segments. Does anyone know any proofs or counterexamples? The problem (regardless of the interpretation) is one of those resolved by Euler's theorem, the theorem that started graph theory. Assume, e.g. as you think, there's a graph with 8 T vertices, other vertices being of even degree, i.e. being incident with an even number of edges. Connect the 8 T (or, in general, odd degree) vertices with 4 new edges making all of them even. Now, Euler's theorem says that, for such a graph, there exists an Euler cycle, a closed path on the graph - a sequence of adjacent edges - that contains all the edges and each only once. Now, remove the 4 add-on edges from the cycle. The cycle is bound to get split into four pieces, since the number of loose ends is 8. |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
|
 |
Michael Klipper

guest
|
Aug-03-02, 05:33 PM (EST) |
|
6. "RE: a rectangle box with segment??"
In response to message #5
|
I heard about this problem, now that Alex mentions it'slightly differently (the original Description of the problem was very confusing, KennyJ). It is called the Euler graph theorem since Euler first solved problems of this type. In memory of this problem, any path on a graph that uses all the edges only once is called an Eulerian tour, I believe. Anyway, this is called the Konnigsberg bridge problem. Supposedly the story goes that there were two coasts and the island of Konnigsberg in between. Or maybe it was two islands... If we call the top coast A, the bottom coast B, and the islands C and D, then there were two bridges from A to C, two bridges from B to C, one bridge from A to D, and one bridge from B to D. People were happy, until the architects built another bridge between C and D, since this disrupted people's walking patterns. So the question is, is it possible to take a path which walks over every bridge exactly once? You can relate this to your rectangle problem by considering each box as an island and the segments as "bridges" separating the islands. |
|
Alert | IP |
Printer-friendly page | Edit |
Reply |
Reply With Quote | Top |
|
|
|

You may be curious to visit the old CTK Exchange archive.
|Front page|
|Contents|
|Store|
Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
|
Advertise
|