This is a solution to the geometry puzzle about lines posted earlier.
A brief description of the problem:
Given a set $S$ of finite number lines in the 2D plane, no two parallel, and not all concurrent, show that there is a point through which only two lines of $S$ pass (hence the title).
Solution
Since no two lines are parallel, and not all are concurrent, there is at least one triple of lines which forms a non-degenerate triangle.
Of all such triplets, consider the lines which form a triangle of the least area. The claim is that one of the vertices of this triangle satisfies the requirement!
[Sorry, no figures yet, so it might help to draw it out]
Suppose not, then if the triangle was $\triangle ABC$, then there are lines passing through $A,B,C$ such that they form a bigger triangle, $\triangle DEF$, with each of $A,B,C$ lying on different sides of $\triangle DEF$ and $\triangle ABC$, say $A$ is on side $DE$ (between $D$ and $E$), B is on side $DF$ (between $D$ and $F$) and $C$ is on side $EF$ (between $E$ and $F$).
We consider two cases:
1) $A$ is closer to $D$ than $E$ (possibly equidistant from both points). $B$ is closer to $D$ than $F$. Then we must have that the area of $\triangle ABC$ lies between areas of $\triangle ABE$ and $\triangle ABF$, say area of $\triangle ABE$ is smaller. This we can see, by drawing lines parallel to $AB$ through $E$ and through $F$, and considering the altitude lengths.
Since $A$ is closer to $D$ than $E$, we must have that area of $\triangle DAB \lt$ area of $\triangle ABE$, and thus contradicting the fact that $\triangle ABC$ has the least area.
2) $A$ is closer to $D$ than $E$ (possibly equidistant) and $B$ is closer to $F$ than $D$, and $C$ is closer to $E$ than $F$.
In this case, we can move $C$ to the midpoint of $EF$ and $B$ to the midpoint of $DF$ and decrease the area of $\triangle ABC$. This we can see by drawing lines parallel to $AB$ through $C$ and the midpoint $M$ of $EF$, and lines parallel to $MA$ through $B$ and $M'$, the midpoint of $DF$ (and considering the altitude lengths).
The resulting area is exactly one-fourth the area of $\triangle{DEF}$, and hence area of $\triangle ABC$ is more than the average of the sum of triangles $ABC, DAB, EBC, FAB$ and thus there must be a triangle of lesser area.
The above two cases cover all the possibilities, so we are done.
Futher reading
The classic problem I was referring to is the Sylvester-Gallai problem, which is the dual of this problem, by considering the polar/pole version.
A different proof of the claim that $\triangle ABC$ is not the least can also be found here (Theorem 3.1.2 on pages 20-22).
More information about the Sylvester-Gallai theorem, including some nice history can be found here and here.
A brief description of the problem:
Given a set $S$ of finite number lines in the 2D plane, no two parallel, and not all concurrent, show that there is a point through which only two lines of $S$ pass (hence the title).
Solution
Since no two lines are parallel, and not all are concurrent, there is at least one triple of lines which forms a non-degenerate triangle.
Of all such triplets, consider the lines which form a triangle of the least area. The claim is that one of the vertices of this triangle satisfies the requirement!
[Sorry, no figures yet, so it might help to draw it out]
Suppose not, then if the triangle was $\triangle ABC$, then there are lines passing through $A,B,C$ such that they form a bigger triangle, $\triangle DEF$, with each of $A,B,C$ lying on different sides of $\triangle DEF$ and $\triangle ABC$, say $A$ is on side $DE$ (between $D$ and $E$), B is on side $DF$ (between $D$ and $F$) and $C$ is on side $EF$ (between $E$ and $F$).
We consider two cases:
1) $A$ is closer to $D$ than $E$ (possibly equidistant from both points). $B$ is closer to $D$ than $F$. Then we must have that the area of $\triangle ABC$ lies between areas of $\triangle ABE$ and $\triangle ABF$, say area of $\triangle ABE$ is smaller. This we can see, by drawing lines parallel to $AB$ through $E$ and through $F$, and considering the altitude lengths.
Since $A$ is closer to $D$ than $E$, we must have that area of $\triangle DAB \lt$ area of $\triangle ABE$, and thus contradicting the fact that $\triangle ABC$ has the least area.
2) $A$ is closer to $D$ than $E$ (possibly equidistant) and $B$ is closer to $F$ than $D$, and $C$ is closer to $E$ than $F$.
In this case, we can move $C$ to the midpoint of $EF$ and $B$ to the midpoint of $DF$ and decrease the area of $\triangle ABC$. This we can see by drawing lines parallel to $AB$ through $C$ and the midpoint $M$ of $EF$, and lines parallel to $MA$ through $B$ and $M'$, the midpoint of $DF$ (and considering the altitude lengths).
The resulting area is exactly one-fourth the area of $\triangle{DEF}$, and hence area of $\triangle ABC$ is more than the average of the sum of triangles $ABC, DAB, EBC, FAB$ and thus there must be a triangle of lesser area.
The above two cases cover all the possibilities, so we are done.
Futher reading
The classic problem I was referring to is the Sylvester-Gallai problem, which is the dual of this problem, by considering the polar/pole version.
A different proof of the claim that $\triangle ABC$ is not the least can also be found here (Theorem 3.1.2 on pages 20-22).
More information about the Sylvester-Gallai theorem, including some nice history can be found here and here.
No comments:
Post a Comment