wu :: forums « wu :: forums - Careful Line Construction » Welcome, Guest. Please Login or Register. Jan 27th, 2022, 2:58pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, Eigenray, william wu, Grimbal, ThudnBlunder, towr, SMQ)    Careful Line Construction « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Careful Line Construction  (Read 3166 times)
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Careful Line Construction   Prolong_the_line.GIF « on: Dec 16th, 2003, 11:59pm » Quote Modify

Given a segment AB in the plane and a region R, as shown in the figure. It is desired to continue the line AB to the right of R. How may this be done with straightedge alone so that the straightedge never crosses R during the construction?

Clarification: The "straightedge" here is a classical Euclidian tool capable of constructing the straight line segment defined by any two arbitrarily chosen points, or extending an existing straight line segment an arbitrary distance in either direction (Thanks rmsgrey for pointing out).

Hint: This is not a joke problem.
 « Last Edit: Dec 17th, 2003, 6:04am by Barukh » IP Logged

rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: Careful Line Construction   « Reply #1 on: Dec 17th, 2003, 4:26am » Quote Modify

To clarify a little: I assume by straightedge you mean a device that constructs the straight line segment defined by any two arbitrarily chosen points, or extends an existing straight line segment an abitrary unknown distance in either direction. In particular, there's no way of constructing specific lengths or angles.
 IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Careful Line Construction   « Reply #2 on: Dec 17th, 2003, 6:06am » Quote Modify

rmsgrey: your assumption is perfectly correct. I modified the original post to include the clarification.
 IP Logged
Lightboxes
Full Member

Gender:
Posts: 203
 Re: Careful Line Construction   « Reply #3 on: Dec 20th, 2003, 9:40pm » Quote Modify

So I guess drawing parallel lines is out of the question?
 IP Logged

A job is not worth doing unless it's worth doing well.
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Careful Line Construction   « Reply #4 on: Dec 21st, 2003, 11:46am » Quote Modify

on Dec 20th, 2003, 9:40pm, Lightboxes wrote:
 So I guess drawing parallel lines is out of the question?

Correct. But you don't need to. Hint: Use projective geometry.
 IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Careful Line Construction   Careful_Line_Const_H.GIF « Reply #5 on: Dec 27th, 2003, 10:26am » Quote Modify

As the progress on this thread is slow (I hope it’s not due to lack of interest  ), here’s another problem from projective geometry which will help to solve the original one.

In projective geometry, a complete quadrangle is defined as a configuration consisting of four arbitrary points (no 3 of which are collinear) and six lines obtained by joining the pairs of points. In the attached figure, the elements of the complete quadrangle are colored in black. Of course, this configuration determines additional points and lines. For instance, let A be the intersection of lines 13 and 24; B – the intersection of lines 14 and 23. They define the (red) line AB, that intersects lines 12 and 34 in points D and C, respectively.

What relation exists between points A, B, C, D?
 « Last Edit: Dec 27th, 2003, 10:27am by Barukh » IP Logged

Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Careful Line Construction   Cross_Ratio_Inv.GIF « Reply #6 on: Feb 16th, 2004, 1:45am » Quote Modify

As no progress was made for almost 2 months, I would like to give the solution to the question asked in my last post. I will begin with a very gentle introduction.

Given four distinct points A, B, C, D on a line, consider the following value:

Note that the distances in the above formula are directed (i.e. AB = -BA). This value – which is a ratio of rations – is called cross-ratio of pairs of points A, B and C, D. We will note it as (AB|CD). Direct inspection of formula (*) reveals the following properties of the cross-ratio:

1.      (AB|CD) = (CD|AB).
2.      (AB|CD) = (BA|CD)-1.

But the all-important property of cross-ratio is that it is not changed under central or parallel projection. What that means, is illustrated on the attached drawing. Take a point O and draw four lines through it. Next, draw another two lines,1 and 2, to form two groups of 4 points with the original lines. Then we have (AB|CD) = (A’B’|C’D’). This fundamental property is easily proved using triangle sine theorem.

Armed with all this, we are ready now to answer the question given in my last post: In the complete quadrangle configuration, the points A, B, C, D satisfy the following relation:  (AB|CD) = -1. Here’s how we prove it (refer to the drawing in my last post; E is the intersection of lines 12 and 34):

(AB|CD) = (12|ED)  (projecting from point 3),
(12|ED) = (BA|CD)  (projecting from point 4),

so – according to property 2 above - (AB|CD)2 = 1. Because point C lies inside segment AB, distances AC and BC have different signs, thus (AB|CD) < 0, and (AB|CD) = -1.

When four points have (AB|CD) = -1, it is said that C and D divide the segment AB internally and externally in the same ratio (harmonically), or that D is a harmonic conjugate of C w.r.t. segment AB.

An interesiting consequence follows if we ask what happen when C is the midpoint of AB? (*) shows that in this case AD = BD. This may be only if D is the point at infinity (why?), or putting it differently – lines 12 and AB are parallel. Thus, we have a method of constructing a parallel line by a straightedge alone given a bisected segment. It is clear that the opposite construction is also possible.

I will give the answer to the original problem in my next post - after a while... Anyway, the comments are welcome (that's one of the reasons we are here, isn't it?   )

 « Last Edit: Feb 16th, 2004, 1:48am by Barukh » IP Logged

Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Careful Line Construction   « Reply #7 on: Mar 21st, 2004, 1:03am » Quote Modify

Here’s the solution to the original problem.

As follows from my previous post about cross-ratios and conjugate points, given the segment AB and a point C on it, it is possible to construct the conjugate point D by means of complete quadrangle. D lies on the line AB, and the closer C is to the midpoint of AB, the farther D will be from the endpoints of the segment.

Thus the construction (for the reference, refer to the following drawing):

1.      Take a point C on the segment AB, sufficiently close to the midpoint of AB.
2.      Take a point 3 not on the line AB, and draw lines A3, B3, C3. Take a point 4 on the line C3, and draw lines A4 and B4. Let point 1 be the intersection of lines A3 and B4, and point 2 – the intersection of lines A4 and B3. Draw the lines l1 = 12. This actually constructs the complete quadrangle.
3.      Take another point 3, and repeat the construction of step 2, getting the line l2. Let D be the intesection of lines l1 and l2. We know that D is the conjugate of C w.r.t. segment AB, and therefore lies on the line AB.
4.      Take another point C’ on the segment AB, and repeat steps 2-3. Get the point D’.

DD’ is the desired line.

 « Last Edit: Mar 21st, 2004, 1:04am by Barukh » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7517
 Re: Careful Line Construction   « Reply #8 on: Apr 27th, 2004, 3:27pm » Quote Modify

Here is my solution.

Draw from A to N.  Lowercase letters are lines to be drawn after the corresponding point.  The points or lines are sometimes arbitrary or only partially constrained.  A few lines are horizontal or vertical, they don't need to be.  I did not optimize for accuracy.
 « Last Edit: Apr 27th, 2004, 3:31pm by Grimbal » IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Careful Line Construction   « Reply #9 on: Apr 28th, 2004, 7:11am » Quote Modify

 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7517
 Re: Careful Line Construction   « Reply #10 on: Apr 28th, 2004, 1:37pm » Quote Modify

It is based on the following construction.

A, B and C are guaranteed to be on a straight line.

I don't know if this construction has a name.  It is marvelously symetric.  Every point and each line has exactly the same role.  There are 10 lines and 10 points.  Each point is at the crossing of 3 lines and each line crosses 3 points.
From a point, there are exactly 3 points not connected to that point.  These points are on a line. (I'll call that line the dual of the point).
Similarily, from a line, there are 3 lines that do not have a point in common with it.  These 3 lines cross in a single point.  (That point is the dual of the line).
And if you name the points A..J, and call a the line dual to A, b the dual of B, etc, you will find that X,Y,Z are aligned iff x,y,z cross at a single point.
 IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Careful Line Construction   « Reply #11 on: Apr 29th, 2004, 9:01am » Quote Modify

Aha! Now it’s much more clear.

on Apr 28th, 2004, 1:37pm, grimbal wrote:
 A, B and C are guaranteed to be on a straight line.   I don't know if this construction has a name.

Yes, it does: this is the famous Desargues’s theorem, which is at least 350 years old. It states: If two triangles are perspective from a point, and if their pairs of corresponding lines meet, then the three pairs of intersection are collinear.

In your drawing, the leftmost point is the center of projection, the six unnamed points are vertices of two triangles, and A, B, C are the points of intersection.

Awesome approach, Gimbal! Bravo!
 IP Logged
carpao
Guest

 Re: Careful Line Construction   « Reply #12 on: Jun 7th, 2004, 7:54am » Quote Modify Remove

on Mar 21st, 2004, 1:03am, Barukh wrote:
 Here’s the solution to the original problem.

I used a nice applet to draw the solution... (I stopped after the construction of the first point at the right of the forbidden area)

In the figure generated by the applet is possible to move points A,B,C, 3, 4, 3', and 4'  and see the corresponding construction that change accordingly...

I leave only this possibility out the applet... but if you prefer I can upload a version where it is possible to see the correct order in the construction... let me know...

Quote:
 4. Take another point C’ on the segment AB, and repeat steps 2-3. Get the point D’.

BTW there is no need to take another point C'... it suffices to take other points 3 and 4...

PS (The applet is about 900KB)...
 IP Logged
carpao
Guest

 Re: Careful Line Construction   « Reply #13 on: Jun 7th, 2004, 7:56am » Quote Modify Remove

[quote author=carpao l
In the figure generated by the applet [/quote]
I forgot to put the address

http://members.xoom.virgilio.it/carpao/segmenti.html
 IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Careful Line Construction   « Reply #14 on: Jun 7th, 2004, 9:04am » Quote Modify

on Jun 7th, 2004, 7:54am, carpao wrote:
 I used a nice applet to draw the solution... (I stopped after the construction of the first point at the right of the forbidden area)

Wow! It's really nice, carpao! Thanks for that visualization.

Quote:
 BTW there is no need to take another point C'... it suffices to take other points 3 and 4...

No, this is not enough. A certain point C on the segment AB uniquely specifies the point D on extension of AB. You may see it by moving points 3' and 4' – the lines still intersect in the same point (by the way, it is a good idea to label that point on the applet). Therefore, to construct another point D' we need another point C'.
 IP Logged
carpao
Guest

 Re: Careful Line Construction   « Reply #15 on: Jun 7th, 2004, 9:23am » Quote Modify Remove

on Jun 7th, 2004, 9:04am, Barukh wrote:
 Wow! It's really nice, carpao! Thanks for that visualization.

thanks...
Quote:
 No, this is not enough. A certain point C on the segment AB uniquely specifies the point D on extension of AB. You may see it by moving points 3' and 4' – the lines still intersect in the same point (by the way, it is a good idea to label that point on the applet). Therefore, to construct another point D' we need another point C'.

yes you are right... I wrote a foolish... (and I cannot delete it ... )

however a very nice riddle thanks...
 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: Careful Line Construction   « Reply #16 on: Jun 7th, 2004, 5:15pm » Quote Modify

Join, and you can edit or delete your own posts.
 IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
carpao
Guest

 Re: Careful Line Construction   « Reply #17 on: Jun 8th, 2004, 2:14am » Quote Modify Remove

on Jun 7th, 2004, 5:15pm, Icarus wrote:
 Join, and you can edit or delete your own posts.

I know... but not the ones already written as guest I suppose...
 IP Logged
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: Careful Line Construction   « Reply #18 on: Jun 8th, 2004, 6:08am » Quote Modify

on Jun 7th, 2004, 9:23am, carpao wrote:
 ys you are right... I wrote a foolish... (and I cannot delete it ... )

 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7517
 Re: Careful Line Construction   « Reply #19 on: Jun 8th, 2004, 8:28am » Quote Modify

on Apr 29th, 2004, 9:01am, Barukh wrote:
 In your drawing, the leftmost point is the center of projection, the six unnamed points are vertices of two triangles, and A, B, C are the points of intersection.

Then you didn't fully understand what I was trying to explain.  Every point has the same role.  So every point can be used as the perspective point (even though sometimes the perspective point is not at the end of a perspective line, but between two points).

PS: oops, on a second thought, you are right.  To get the result that A, B, C are aligned, then the perspective point must be the one you mentionned.
 « Last Edit: Jun 8th, 2004, 9:25am by Grimbal » IP Logged
carpao
Guest

 Re: Careful Line Construction   « Reply #20 on: Jun 8th, 2004, 9:06am » Quote Modify Remove

A friend of mine suggest an alternative approach...

To use the shadow of the straightedge
what do you think of this solution?
 IP Logged
Leo Broukhis
Senior Riddler

Gender:
Posts: 459
 Re: Careful Line Construction   « Reply #21 on: Jun 8th, 2004, 9:48am » Quote Modify

on Jun 8th, 2004, 9:06am, carpao wrote:
 A friend of mine suggest an alternative approach...   To use the shadow of the straightedge   what do you think of this solution?

Who says the light source provides for a shadow? E.g. office lighting or overcast sky does not.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7517
 Re: Careful Line Construction   « Reply #22 on: Jun 8th, 2004, 10:37am » Quote Modify

Or you could cut out a piece of your straight edge, so it goes around the black patch.
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2846
 Re: Careful Line Construction   « Reply #23 on: Jun 9th, 2004, 3:29am » Quote Modify

As mentioned in the problem statement, the straightedge is a mathematical tool whose (only) capabilities are:
L1)Create the straight line segment connecting two known points.
L2)Extend an existing straight line a non-specific distance in either direction.

There is an additional constraint in the problem that the straightedge cannot create a line segment that passes through the region R, meaning that no line can be created directly from two points on opposite sides of R, and any line extended towards R will terminate before reaching R.

For completeness, specific points can only be created/identified by the following processes:
P1)Pick an arbitrary point in a region of the plane bounded by existing lines (and not inside region R).
P2)Pick an arbitrary point on an existing line segment bounded by existing points.
P3)The end-point of a line extended using L2.
P4)The point of intersection of any two lines.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »