CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Manifesto: what CTK is about |Store| Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot

CTK Exchange

Subject: "a rectangle box with segment??"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #272
Reading Topic #272
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

  Subject     Author     Message Date     ID  
a rectangle box with segment?? KennyJ Jun-17-02 TOP
  RE: a rectangle box with segment?? Omar Jun-17-02 1
     RE: a rectangle box with segment?? KennyJ Jun-21-02 2
         RE: a rectangle box with segment?? alexb Jun-21-02 3
  RE: a rectangle box with segment?? bluediamond Jun-22-02 4
     RE: a rectangle box with segment?? alexb Jun-22-02 5
         RE: a rectangle box with segment?? Michael Klipper Aug-03-02 6

Conferences | Forums | Topics | Previous Topic | Next Topic
Omar
guest
Jun-17-02, 09:24 PM (EST)
 
1. "RE: a rectangle box with segment??"
In response to message #0
 
   Heres are a hint.

1) It can't be done on a computer screen or a chalkboard.


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
KennyJ
guest
Jun-21-02, 01:05 PM (EST)
 
2. "RE: a rectangle box with segment??"
In response to message #1
 
   Can any one figure this our??


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
alexb
Charter Member
787 posts
Jun-21-02, 01:26 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
3. "RE: a rectangle box with segment??"
In response to message #2
 
   Well, it's an old and well known problem. If you search the Web for "+Euler +theorem +graph" you will rpobably run into a solution. But you may also think a little as well.

There are 3 boxes with 5 segments each. For each box, getting into the box and then getting out, or getting out first and then getting in, means crossing two of its segments. If a box has an odd number of segments, then you either have to start or end there. But you have 3 such. Now do the thinking. (The outside should be also looked at as a region whose boundary is composed of the segments - seven segments to be exact. So in fact you have four regions with an odd number of segments.)


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
bluediamond
Member since Apr-9-02
Jun-22-02, 10:16 AM (EST)
Click to EMail bluediamond Click to send private message to bluediamond Click to view user profileClick to add this user to your buddy list Click to send message via ICQ  
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)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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

Conferences | Forums | Topics | Previous Topic | Next Topic

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

New Books
Second editions of J. Conway's classic On Numbers And Games and the inimitable Winning Ways for Your Mathematical Plays