wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> Careful Line Construction
(Message started by: Barukh on Dec 16th, 2003, 11:59pm)

Title: Careful Line Construction
Post by Barukh on Dec 16th, 2003, 11:59pm
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: [hide]This is not a joke problem.[/hide]

Title: Re: Careful Line Construction
Post by rmsgrey on Dec 17th, 2003, 4:26am
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.

Title: Re: Careful Line Construction
Post by Barukh on Dec 17th, 2003, 6:06am
rmsgrey: your assumption is perfectly correct. I modified the original post to include the clarification.

Title: Re: Careful Line Construction
Post by Lightboxes on Dec 20th, 2003, 9:40pm
So I guess drawing parallel lines is out of the question?

Title: Re: Careful Line Construction
Post by Barukh on Dec 21st, 2003, 11:46am

on 12/20/03 at 21:40:35, Lightboxes wrote:
So I guess drawing parallel lines is out of the question?

Correct. But you don't need to. Hint: [hide]Use projective geometry[/hide].

Title: Re: Careful Line Construction
Post by Barukh on Dec 27th, 2003, 10:26am
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?

Title: Re: Careful Line Construction
Post by Barukh on Feb 16th, 2004, 1:45am
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:

(AC/AD) / (BC/BD)                             (*)

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?  ;) )


Title: Re: Careful Line Construction
Post by Barukh on Mar 21st, 2004, 1:03am
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 (http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/Careful_Line_Const_H.GIF)):

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.


Title: Re: Careful Line Construction
Post by grimbal on Apr 27th, 2004, 3:27pm
Here is my solution.

http://florian.net/pic/prolongation.gif
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.

Title: Re: Careful Line Construction
Post by Barukh on Apr 28th, 2004, 7:11am
Grimbal, I've found it difficult to follow your construction  :-/

Could you please explain it and also argue about it?

Title: Re: Careful Line Construction
Post by grimbal on Apr 28th, 2004, 1:37pm
It is based on the following construction.

http://florian.net/pic/10lines.gif

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.

Title: Re: Careful Line Construction
Post by Barukh on Apr 29th, 2004, 9:01am
Aha! Now it’s much more clear.


on 04/28/04 at 13:37:47, 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!  :D

Title: Re: Careful Line Construction
Post by carpao on Jun 7th, 2004, 7:54am

on 03/21/04 at 01:03:21, 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)...

Title: Re: Careful Line Construction
Post by carpao on Jun 7th, 2004, 7:56am
[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

Title: Re: Careful Line Construction
Post by Barukh on Jun 7th, 2004, 9:04am

on 06/07/04 at 07:54:54, 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'.

Title: Re: Careful Line Construction
Post by carpao on Jun 7th, 2004, 9:23am

on 06/07/04 at 09:04:50, 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...

Title: Re: Careful Line Construction
Post by Icarus on Jun 7th, 2004, 5:15pm
Join, and you can edit or delete your own posts.

Title: Re: Careful Line Construction
Post by carpao on Jun 8th, 2004, 2:14am

on 06/07/04 at 17:15:49, Icarus wrote:
Join, and you can edit or delete your own posts.

I know... but not the ones already written as guest I suppose...

Title: Re: Careful Line Construction
Post by Barukh on Jun 8th, 2004, 6:08am

on 06/07/04 at 09:23:45, carpao wrote:
ys you are right... I wrote a foolish... (and I cannot delete it ... :-[ )

You don’t need to worry about this, carpao. One of the good things about this forum is that nobody is judged according to mistakes he/she made.

Title: Re: Careful Line Construction
Post by Grimbal on Jun 8th, 2004, 8:28am

on 04/29/04 at 09:01:49, 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.

Title: Re: Careful Line Construction
Post by carpao on Jun 8th, 2004, 9:06am
A friend of mine suggest an alternative approach...

To use the shadow of the straightedge  ;D
what do you think of this solution?

Title: Re: Careful Line Construction
Post by Leonid Broukhis on Jun 8th, 2004, 9:48am

on 06/08/04 at 09:06:07, carpao wrote:
A friend of mine suggest an alternative approach...

To use the shadow of the straightedge  ;D
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.

Title: Re: Careful Line Construction
Post by Grimbal on Jun 8th, 2004, 10:37am
Or you could cut out a piece of your straight edge, so it goes around the black patch.  :)

Title: Re: Careful Line Construction
Post by rmsgrey on Jun 9th, 2004, 3:29am
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.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board