Challenge V: Sylvester-Gallai Theorem, solved by Mandelbroth

[Theorem.]

Sure, post it!

\textbf{Definition}[\text{set of lines generated by a set of points in the plane}]: \\<br /> \text{ Given any two points on the plane }p_1,p_2\text{, let } L_{p_1 p_2} \text{ denote the line going through the two points.}\\ \text{We will call this the line generated by }p_1 \text{ and }p_2.

\text{If } P \text{ is a finite set of points in the plane, Let } L_P:=\{L_{p_i p_j}: p_i,p_i\in P, i\neq j\}. \\ \text{ We will call this the set of lines generated by P}


Okay, now we can focus a bit on the question!. We want to show that given any finite set of points
P in the \mathbb{R}^2, if not all the points lay on a straight line, then there exists a line going through exactly two of the points. We will do this by contradiction. As I mentioned before, This is basically Kelly's proof (Which Micromass mentioned earlier), I may have seen it on a problem set earlier on, but the idea struck me regardless. Let us begin.

Suppose towards a contradiction there exists a finite set of points
P=\{p_1,p_2,...,p_n\}\subset \mathbb{R}^2 with the property that |L\cap P|\geq 3 for all L\in L_P. That is, every line in L_P intersects at least
3 points of P.

Consider the set D:=\{d(p,L): p\in P, L\in L_P \thinspace and \thinspace p\notin L\}. This set is finite and bounded below by 0, and thus has a minimum a&gt;0. Let p,L be such that d(p,L)=a.

It is intutively helpful after this point to visualize what is going on graphically (on paper).

Connect p to L by forming the line perpendicular to L that goes through p, We can call this line PL, and notice that it must have length a. By the initial assumption, the line L intersects at least 3 points of P, so at least two of these points must lay to one side of the point where L and PL intersect (as Kelly's proof points out- it is of course okay for one of these points to be exactly on the intersection). Denote the point closest to the intersection q_1 and the point furthest q_2. Then L_{q_2 p}\in L_P. Form
The line L_2Q perpendicular to L_{q_2 p} and through q_1. Then it is easy to see that d(q_1,L_{q_2 p})&lt;d(p,L). As Kelly's proof suggests, you can just note that the triangle with hypotenuse q_1q_2 is similar to the triangle with hypotenuse pq_2.

This of course contradicts the fact that d(p,L)=\min{D}, and we are done.

The proof is identical to Kelly's proof except the notation I used is definitely harsher and some small parts are explained differently. Minor differences that helped me work through the problem but at the end of the day can be cleaned up. I originally tried doing it by strong induction and got stuck for awhile but eventually got the right kind of idea! fun problem

 

[verty]

Darn, the idea I had for proving the generalization didn't work, the hurdle was more like an infinite slope. Instead one must use the number of lines; there are too many lines for all of them to have 3 points on. Each new point generates tons of new lines.

Anyway, I'm leaving this.